Java实现单链表与循环链表

链表的引入

数组和链表的对比

• 数组：

  访问数组时，其实是利用指针，即内存地址，直接访问对应内存地址中的数值，所以访问速度非常快。查找复杂度：O(1)

  添加元素时，需要移动大量元素，在内存中空出一个元素的空间，然后将要增加的元素放在其中。删除一个元素，同样需要移动大量元素去填掉被移动的元素。添加/删除元素的时间复杂度： O(n)

• 链表：

  链表与数组相反，链表中的元素在内存中不是顺序存储的，而是通过存在元素中的指针联系到一起。第一个元素指向第二个，以此类推直到最后一个元素。所以查找链表中某一个元素就要从第一个元素开始找，一直到找到需要的元素。 查找复杂度：O(n)

  但是增加和删除一个元素对于链表数据结构就非常简单了，只要修改相应位置前后元素中的指针就可以了。复杂度：O(1)

  添加node：

  node.next = pre.next;
  pre.next = node;

  删除node：

  pre.next = node.next;

单链表

​ 单向链表是一种线性表，实际上是由节点（Node）组成的，一个链表拥有不定数量的节点。head为头节点，他不存放任何的数据，只是充当一个指向链表中真正存放数据的第一个节点的作用，而每个节点中都有一个next引用，指向下一个节点，就这样一节一节往下面记录，直到最后一个节点，其中的next指向null。

代码实现（已定义Node head）

• 其他功能

  /**
      * 获取链表长度
      * @Author: Wang Rui
      * @Date: 2020/10/29
      */
  int length;
  public int getLength(){
      length = 0;
      if(head == null)
          return 0;
      Node temp = head;
      while (temp != null){
          length++;
          temp = temp.next;
      }
      return length;
  }
  /**
       *获取指定位置的节点
       * @Author: Wang Rui
       * @Date: 2020/10/29
       */
      public Node getNode(int index){
          if(index < 0 && index >= getLength()){
              return null;
          }
          Node temp = head;//从头遍历找
          for(int i = 0; i < getLength(); i++, temp = temp.next){
              if(i == index){
                  return temp;
              }
          }
          return null;
      }
  /**
       *判断链表是否为空
       * @Author: Wang Rui
       * @Date: 2020/10/29
       */
      public boolean isEmpty(){
          if(head == null)
              return true;
          else
              return false;
      }
  /**
       *打印链表
       * @Author: Wang Rui
       * @Date: 2020/10/29
       */
      public void printLink(){
          Node temp = head;
          while (temp != null){
              System.out.print(temp.val + " ");
              temp = temp.next;
          }
      }

• 创建节点

  public class Node {
      public int val;
      public Node next;
  
      public Node() {
      }
  
      public Node(int val) {
          this.val = val;
      }
  }

• 增加节点

  public void addNode(Node node){
      if(isEmpty()){
          head = node;
      }
      Node temp = head;
      while (temp.next != null){
          temp = temp.next;
      }
      temp.next = node;
      node.next = null;
      int l = getLength();
      l++;
  }

• 插入节点

  /**
   *在指定位置插入节点
   * @Author: Wang Rui
   * @Date: 2020/10/29
   */
  public void insert(int index,Node node){
      if (index < 0 && index >= getLength()) {
          return;
      }
      if(index == 0){
          Node temp = head;
          head = node;
          node.next = temp;
      }
      //1 2 3 4 ,length=4
      if(index > 0 && index < length - 1){
          Node pre = getNode(index - 1);
          node.next = pre.next;
          pre.next = node;
      }
  }

• 删除节点

  /**
   *删除指定位置的节点
   * @Author: Wang Rui
   * @Date: 2020/10/29
   */
  public Node delete(int index) {
      if (index < 0 && index >= getLength()) {
          return null;
      }
      //删除头节点
      if (index == 0) {
          head = head.next;
          length--;
          return head;
      }
      //删除尾节点
      if(index == getLength() - 1){
          Node newEndNode = getNode(getLength() - 2);
          newEndNode.next = getNode(index).next;
          length--;
          return head;
      }
      //删除指定位置
      if(index != 0 && index != getLength() - 1){
          getNode(index - 1).next = getNode(index + 1);
          length--;
          return head;
      }
      return null;
  }

循环链表

单链表的尾结点指向 NULL，而循环链表的尾结点指向头结点，构成环状。

代码实现：

• 其他功能:

  /**
       * 获取指定位置的节点
       * @Author: Wang Rui
       * @Date: 2020/10/26
       */
      public Node getNodeByIndex(int index){
          if(index < 0 || index > length){
              return null;
          }
          //从头节点开始遍历链表查找
          Node curr = head;
          for (int i = 0; i<length; i++,curr = curr.next)
              if (i == index)
                  return curr;
          return null;
      }
      /**
       * 获取指定位置元素的值
       * @Author: Wang Rui
       * @Date: 2020/10/26
       */
      public int getVal(int index){
          if(index < 0 && index >= length)
              throw new RuntimeException("没有找到此元素！");
          return getNodeByIndex(index).val;
      }
   /**
       * 打印链表全部节点
       * @Author: Wang Rui
       * @Date: 2020/10/26
       */
       public void show(){
           if(length > 0){
               Node temp = head;
               for(int i = 0; i < length - 1; i++){
                   System.out.print(temp.val+"->");
                   temp = temp.next;
               }
               System.out.println(getVal(length - 1));
               System.out.println("length = "+length);
           }
       }

• 添加节点

  /**
       * 尾部添加元素
       * @Author: Wang Rui
       * @Date: 2020/10/26
       */
      public Node add(Node node){
          if(length == 0){
              head = node;
              head.next = head;
          }
          else{
              Node temp = head;
              //head后还有节点，继续向后
              while(temp.next != head){
                  temp = temp.next;
              }
              //找到目前最后一个元素，它指向head。在它后面插入node
              temp.next = node;
              node.next = head;
          }
          length++;
          return node;
      }
  /**
       * 指定位置添加元素
       * @Author: Wang Rui
       * @Date: 2020/10/26
       */
      public Node insert(int index, Node newNode){
          if(index < 0 && index >= length){
              return null;
          }
          //index = 0,将newNode设为头节点
          if(index == 0){
              newNode.next = head;
              head = newNode;
          }
          else{
              //将newNode插入到链表中，先获取前一个和后一个节点
              Node pre = getNodeByIndex(index - 1);
              newNode.next = pre.next;
              pre.next = newNode;
  
          }
          length++;
          return newNode;
      }

• 删除节点

  /**
       * 删除头节点
       * @Author: Wang Rui
       * @Date: 2020/10/26
       */
      public Node deleteHead(){
          //链表中只有一个元素
          if(length == 1){
              head = null;
          }
          if(length > 1){
              head = head.next;
              getNodeByIndex(length - 1).next = head;
              length--;
          }
          return head.next;
      }
      /**
       * 删除尾节点
       * @Author: Wang Rui
       * @Date: 2020/10/26
       */
      public Node deleteTail(){
          //链表中只有一个元素
          if(length == 1){
              head = null;
          }
          if(length > 1){
              getNodeByIndex(length - 2).next = head;
              length--;
          }
          return head;
      }
      /**
       * 删除指定位置节点
       * @Author: Wang Rui
       * @Date: 2020/10/26
       */
      public Node deleteIndex(int index){
          if(index < 0 && index >= length){
              throw new RuntimeException("没有找到该删除元素！");
          }
          if(index != 0 && index != length -1){
              getNodeByIndex(index - 1).next = getNodeByIndex(index + 1);
              length--;
          }
          return head;
      }

summary: 原理大概都懂，代码实现上有些细节要注意。讨论头节点是否为null；给定某个位置index，讨论index是否在合理范围内。