[数据结构与算法]单链表是什么和单链表的基本操作

什么是单链表

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

Java内部也有自己的链表–LinkedList，感兴趣的可以去看一下,我们今天是自己来创建一个单链表然后来进行简单的基本操作
首先我们来定义一个类然后在建立他的一个内部类来作为我们的链表实现类

class Linked
    {
        private Object value;//链表的值
        private Linked next;//链表的下一个
        private Linked upper;//链表的上一个

        public Linked getUpper() {
            return upper;
        }

        public void setUpper(Linked upper) {
            this.upper = upper;
        }

        public Linked() {
        }


        public Object getValue() {
            return value;
        }

        public void setValue(Object value) {
            this.value = value;
        }

        public Linked(Object value) {
            this.value = value;
        }

        public Linked getNext() {
            return next;
        }

        public void setNext(Linked next) {
            this.next = next;
        }

        @Override
        public String toString() {
            return "[Value:"+value+"]";
        }
    }

这样我们的一个链表的设计就算完成了

之所以定义内部类而不是自己定义一个类是因为我们可以把类来作为一个存放方法和全局变量的这么一个地方

public class Linkedlist
{
    public static Linked linked;//链表
    public static int index;//索引

    public Linked getLinked() {
        return linked;
    }

    public void setLinked(Linked linked) {
        Linkedlist.linked = linked;
    }
    public Linkedlist() {
    }

    public Linkedlist(Linked linked) {
        Linkedlist.linked = linked;
    }



    class Linked
    {
        private Object value;
        private Linked next;
        private Linked upper;

        public Linked getUpper() {
            return upper;
        }

        public void setUpper(Linked upper) {
            this.upper = upper;
        }

        public Linked() {
        }


        public Object getValue() {
            return value;
        }

        public void setValue(Object value) {
            this.value = value;
        }

        public Linked(Object value) {
            this.value = value;
        }

        public Linked getNext() {
            return next;
        }

        public void setNext(Linked next) {
            this.next = next;
        }

        @Override
        public String toString() {
            return "[Value:"+value+"]";
        }
    }
 }

然后我们在进行添加和输出在进行链表的一个基本操作

package com0811;

public class Linkedlist
{
    public static Linked linked;
    public static int index;

    public Linked getLinked() {
        return linked;
    }

    public void setLinked(Linked linked) {
        Linkedlist.linked = linked;
    }
    public Linkedlist() {
    }

    public Linkedlist(Linked linked) {
        Linkedlist.linked = linked;
    }



    class Linked
    {
        private Object value;
        private Linked next;
        private Linked upper;

        public Linked getUpper() {
            return upper;
        }

        public void setUpper(Linked upper) {
            this.upper = upper;
        }

        public Linked() {
        }


        public Object getValue() {
            return value;
        }

        public void setValue(Object value) {
            this.value = value;
        }

        public Linked(Object value) {
            this.value = value;
        }

        public Linked getNext() {
            return next;
        }

        public void setNext(Linked next) {
            this.next = next;
        }

        @Override
        public String toString() {
            return "[Value:"+value+"]";
        }
    }

   /*
    添加链表
    * @author Liu
    * @Date 2021-08-13 00:10
    * @param v
    * @return void
    */
    public void add(Object v)
    {
        Linked newLinked = new Linked(v);//要添加的新链表
        Linked linked = Linkedlist.linked;//获取当前链表
        if (linked==null)//如果当前链表为空
        {
            Linkedlist.linked =newLinked;//那么就把新添加的链表变成表头
            return;
        }

        adddnext(linked,newLinked);//如果不是那么就添加到链表的下一个
        addupper(linked.next,linked);//然后在把他的上一个也给添加了
    }

    /*
    添加上一个
    * @author Liu
    * @Date 2021-08-13 00:10
    * @param v
    * @return void
    */
    private void addupper(Linked next,Linked linked)
    {
        if (next.upper==null)
        {
            next.upper=linked;
        }else
        {
            addupper(next.next,next);
        }
    }

     /*
    添加下一个
    * @author Liu
    * @Date 2021-08-13 00:10
    * @param v
    * @return void
    */
    private void adddnext(Linked linked, Linked newList)
    {
        if (linked.next==null)//如果等于空那么就添加
        {
            linked.next=newList;

        }else
        {
            adddnext(linked.next,newList);//如果不等于空那么就把当前节点的下一个变成当前节点 进行递归
        }
    }

    @Test
    /*
    遍历子节点
     * @author Liu
     * @Date 2021-08-13 00:12
     * @param linked
     * @return void
     */
    public void gettoString(Linked linked)
    {

        if (linked!=null)
        {
            System.out.println(linked+"->");
            gettoString(linked.next);
            index++;
            if (linked.next==null&&linked.upper!=null)
            {
                getupper(linked);
            }
        }
    }

    @Test
    /*
    让链表变成自旋
     * @author Liu
     * @Date 2021-08-13 00:12
     * @param linked
     * @return void
     */
    public void addspin(Linked linked)
    {

        if (linked!=null)
        {
            addspin(linked.next);
            if (linked.next==null)
            {
                linked.next=Linkedlist.linked;
            }
        }
    }

    @Test
    /*
    遍历父节点
     * @author Liu
     * @Date 2021-08-13 00:13
     * @param upper
     * @return void
     */
    //遍历左
    private void getupper(Linked upper)
    {
        if (upper!=null)
        {
            System.out.println("<--"+upper);
            getupper(upper.upper);
        }
    }

    @Test
    /*
    利用快慢指针查看中间节点
     * @author Liu
     * @Date 2021-08-13 00:15
     * @param linked
     * @return com0811.Linkedlist.Linked
     */
    public Linked zjwz(Linked linked)
    {
        Linked linked1 = linked.next.next;//快指针
       return zjwz1(linked1,linked.next);
    }
    private Linked zjwz1(Linked linked1, Linked linked2)
    {
        if (linked1!=null&&linked1.next!=null)//如果快指针到了最后一个那么就代表慢指针到了中间位置
        {
          linked2 =  zjwz1(linked1.next.next,linked2.next);
        }

            return linked2;//返回慢指针
    }

    @Test
    /*
    利用快慢指针
    判断是否为自旋链表
     * @author Liu
     * @Date 2021-08-13 00:15
     * @param linked
     * @param linked1
     * @return java.lang.Boolean
     */
    public Boolean spin(Linked linked,Linked linked1)
    {
        Boolean blew = false;
        if (linked==linked1&&linked.next!=null)
        {
         
          return true;
        }else
        {
            blew =  spin(linked.next.next,linked1.next);//这里一定要记得
        }
        return blew;
    }









    @Test
    /*
    指定位置添加
     * @author Liu
     * @Date 2021-08-13 00:16
     * @param idx
     * @param v
     * @return void
     */
    public void addzhidingwz(int idx,Object v)
    {


         if (idx == 0)
         { 
          Linked linked1 = new Linked();
          linked1.value= linked.value;
          linked1.next= linked.next;
          linked.value=v;
          linked.next=linked1;
         }else 
         {
            Linked newList = new Linked(v);
            adddigui1(idx,newList,linked);
            index=0;
         }
    }
    private void adddigui1(int idx, Linked newList,Linked linked)
    {

        ++index;
        if (idx==index)
        {
            Linked zuo = linked.upper;//原来的上一个
            zuo.next=newList;//原来的上一个的下一个指向新插入的
            newList.upper=zuo;//新插入的上一个指向原来的上一个
            newList.next = linked;//新添加的下一个指向原来的
            linked.upper = newList;//原来的上一个指向新添加的
        }else
        {
            if (linked.next!=null)
            {
                adddigui1(idx,newList,linked.next);
            }else
            {
                linked.next=newList;
                newList.upper = linked;
            }
        }

    }


  @Test
  /*
   删除节点
   * @author Liu
   * @Date 2021-08-13 00:16
   * @param idx
   * @param linked
   * @return void
   */
  public void sc(int idx ,Linked linked)
    {
        index=0;
        shanchu(idx,linked.next);
    }
    private void shanchu(int idx,Linked linked)
    {

        ++index;
        if (idx==index)
        {
            Linked zuo = linked.upper;//原来的上一个
            zuo.next=linked.next;//原来的上一个的下一个指向新插入的
            linked.next.upper=zuo;
        }else
        {
            if (linked.next!=null)
            {
                shanchu(idx,linked.next);
            }
        }

    }

    @Test
    /*
     反转链表，就地旋转
     * @author Liu
     * @Date 2021-08-13 00:18
     * @param linked
     * @return com0811.Linkedlist.Linked
     */
   
    public Linked getxzhuan(Linked linked)
    {
        Linked linked1 = new Linked();
        linked1.next=Linkedlist.linked;
        Linked pre = new Linked();
        pre = linked1.next;
        Linked con = new Linked();
        con = pre.next;
        return getxzhuan1(con,linked1,pre);
    }


    

    private Linked getxzhuan1(Linked com,Linked linked1,Linked pre)
    {
        if (com!=null)
        {
            pre.next = com.next;
            com.next = linked1.next;
            linked1.next = com;
             getxzhuan1(pre.next,linked1,pre);
        }
        return linked1;
    }


}