写在前面

在日常开发中，一般在对于List的场景，基本上都是通过ArrayList去封装数据的，而对于链表LinkedList相对来说用的比较少。对我而言，好像ArrayList熟练度高一些，所以基本上也很少用LinkedList，也就是在面试的时候去背过八股文。

02.线性表之链表LinkedList - 图1

链表：数据分散的存储在物理空间中，通过一根线保存着它们之间的逻辑关系，这种存储结构称为链式存储结构，简称链表。

链表的前驱和后继

数据结构中，一组数据中的每个个体被称为“数据元素”（简称“元素”）。
另外，对于具有“一对一”逻辑关系的数据，我们一直在用“某一元素的左侧（前边）或右侧（后边）”这样不专业的词，其实线性表中有更准确的术语：

  • 某一元素的左侧相邻元素称为“直接前驱”，位于此元素左侧的所有元素都统称为“前驱元素”；
  • 某一元素的右侧相邻元素称为“直接后继”，位于此元素右侧的所有元素都统称为“后继元素”；
    02.线性表之链表LinkedList - 图2

单链表

概念：单链表，用于存储逻辑关系为 “一对一” 的数据。与顺序表不同，链表不限制数据的物理存储状态，换句话说，使用链表存储的数据元素，其物理存储位置是随机的。HashMap在1.7就是通过单链表来解决hash冲突的。
02.线性表之链表LinkedList - 图3

节点

在上图中无法提现出元素之间的逻辑关系，对此，链表的解决方案是，每个数据元素在存储时都配备一个指针，用于指向自己的直接后继元素。表示一个节点如下：

  1. //节点信息
  2. class Node {
  3.     E data;
  4.     Node next;
  6.     public Node(E element, Node next) {
  7.         this.data = element;
  8.         this.next = next;
  9.     }
  11.     public Node(E data) {
  12.         this.data = data;
  13.     }
  14. }

02.线性表之链表LinkedList - 图4
因此，在链表中，每个数据的存储有以下2部分组成

  • 数据本身，其所在的区域叫做数据域

  • 指向后继元素的指针，叫指针域
    02.线性表之链表LinkedList - 图5

上图所示的结构在链表中称为节点。也就是说，链表实际存储的是一个一个的节点，真正的数据元素包含在这些节点中
02.线性表之链表LinkedList - 图6

单链表—-增

02.线性表之链表LinkedList - 图7

  1.  /**
  2.   * 头部添加节点
  3.   *
  4.   * @param e
  5.   */
  6.  public void add(E e) {
  7.      //头结点
  8.      Node cur = new Node(e, list);
  9.      list = cur;
  10.      size++;
  11.  }
  13.  /**
  14.    * 指定位置添加节点
  15.    *
  16.    * @param index
  17.    * @param e     0 1 2 3 4
  18.    */
  19.  public void add(int index, E e) {
  20.        //越界检查
  21.      checkElementIndex(index);
  22.      Node preNode = list;
  23.      for (int i = 0; i < index - 1; i++) {
  24.          //找到插入位置的前一个节点
  25.          preNode = preNode.next;
  26.      }
  27.      Node node = new Node(e);
  28.      node.next = preNode.next;
  29.      preNode.next = node;
  30.      size++;
  31.  }

单链表—-删

02.线性表之链表LinkedList - 图8

  1. /**
  2.  * 删除头部节点
  3.  */
  4. public void remove() {
  5.     if (list != null) {
  6.         Node node = list;
  7.         list = node.next;
  8.         //GC
  9.         node.next = null;
  10.         size--;
  11.     }
  12. }
  14. /**
  15.  * 删除指定位置节点
  16.  * 1 2 3 4 5
  17.  * 0 1 2 3 4
  18.  *
  19.  * @param index
  20.  */
  21. public void remove(int index) {
  22.     checkElementIndex(index);
  23.     Node preNode = list;
  24.     for (int i = 0; i < index - 1; i++) {
  25.         //找到指定位置元素的前一个节点
  26.         preNode = preNode.next;
  27.     }
  28.     //指定位置的节点
  29.     Node next = preNode.next;
  30.     preNode.next = next.next;
  31.     //GC
  32.     next = null;
  33.     size--;
  34. }
  36. /**
  37.  * 删除最后一个节点
  38.  */
  39. public void removeLast() {
  40.     if (list != null) {
  41.         //当前节点
  42.         Node cur = list;
  43.         //最后一个节点的前一个节点
  44.         Node preNode = list;
  45.         while (cur.next != null) {
  46.             preNode = cur;
  47.             cur = cur.next;
  48.         }
  49.         preNode = null;//此时cur已经为null
  50.         size--;
  51.     }
  52. }

单链表—-改

02.线性表之链表LinkedList - 图9

  1. /**
  2.  * 修改指定索引的元素
  3.  *
  4.  * @param index
  5.  * @param e
  6.  */
  7. public void set(int index, E e) {
  8.     checkElementIndex(index);
  9.     Node cur = list;
  10.     for (int i = 0; i < index; i++) {
  11.         cur = cur.next;
  12.     }
  13.     cur.data = e;
  14. }

单链表—-查

02.线性表之链表LinkedList - 图10

  1.  /**
  2.   * 获取头部节点
  3.   */
  4.  public E get() {
  5.      if (list != null) {
  6.          return list.data;
  7.      } else {
  8.          return null;
  9.      }
  10.  }
  12.   /**
  13.    * 获取指定位置的元素
  14.    *
  15.    * @param index
  16.    * @return
  17.    */
  18.   public E get(int index) {
  19.       checkElementIndex(index);
  20.       Node cur = list;
  21.       for (int i = 0; i < index; i++) {
  22.           cur = cur.next;
  23.       }
  24.       return cur.data;
  25.   }

完整代码

  2. /**
  3.  * 单链表
  4.  *
  5.  */
  6. public class SingleLinkedList<E> {
  8.     int size = 0;
  10.     /**
  11.      * 指向第一个节点的指针
  12.      */
  13.     Node list;
  15.     /**
  16.      * 头部添加节点
  17.      *
  18.      * @param e
  19.      */
  20.     public void add(E e) {
  21.         //头结点
  22.         Node cur = new Node(e, list);
  23.         list = cur;
  24.         size++;
  25.     }
  27.     /**
  28.      * 指定位置添加节点
  29.      *
  30.      * @param index
  31.      * @param e     0 1 2 3 4
  32.      */
  33.     public void add(int index, E e) {
  34.         checkElementIndex(index);
  35.         Node preNode = list;
  36.         for (int i = 0; i < index - 1; i++) {
  37.             //找到插入位置的前一个节点
  38.             preNode = preNode.next;
  39.         }
  40.         Node node = new Node(e);
  41.         node.next = preNode.next;
  42.         preNode.next = node;
  43.         size++;
  44.     }
  47.     /**
  48.      * 删除头部节点
  49.      */
  50.     public void remove() {
  51.         if (list != null) {
  52.             Node node = list;
  53.             list = node.next;
  54.             //GC
  55.             node.next = null;
  56.             size--;
  57.         }
  58.     }
  60.     /**
  61.      * 删除指定位置节点
  62.      * 1 2 3 4 5
  63.      * 0 1 2 3 4
  64.      *
  65.      * @param index
  66.      */
  67.     public void remove(int index) {
  68.         checkElementIndex(index);
  69.         Node preNode = list;
  70.         for (int i = 0; i < index - 1; i++) {
  71.             //找到指定位置元素的前一个节点
  72.             preNode = preNode.next;
  73.         }
  74.         //指定位置的节点
  75.         Node next = preNode.next;
  76.         preNode.next = next.next;
  77.         //GC
  78.         next = null;
  79.         size--;
  80.     }
  82.     /**
  83.      * 删除最后一个节点
  84.      */
  85.     public void removeLast() {
  86.         if (list != null) {
  87.             //当前节点
  88.             Node cur = list;
  89.             //最后一个节点的前一个节点
  90.             Node preNode = list;
  91.             while (cur.next != null) {
  92.                 preNode = cur;
  93.                 cur = cur.next;
  94.             }
  95.             preNode = null;//此时cur已经为null
  96.             size--;
  97.         }
  98.     }
  100.     /**
  101.      * 修改指定索引的元素
  102.      *
  103.      * @param index
  104.      * @param e
  105.      */
  106.     public void set(int index, E e) {
  107.         checkElementIndex(index);
  108.         Node cur = list;
  109.         for (int i = 0; i < index; i++) {
  110.             cur = cur.next;
  111.         }
  112.         cur.data = e;
  113.     }
  115.     /**
  116.      * 获取头部节点
  117.      */
  118.     public E get() {
  119.         if (list != null) {
  120.             return list.data;
  121.         } else {
  122.             return null;
  123.         }
  124.     }
  126.     /**
  127.      * 获取指定位置的元素
  128.      *
  129.      * @param index
  130.      * @return
  131.      */
  132.     public E get(int index) {
  133.         checkElementIndex(index);
  134.         Node cur = list;
  135.         for (int i = 0; i < index; i++) {
  136.             cur = cur.next;
  137.         }
  138.         return cur.data;
  139.     }
  142.     class Node {
  143.         E data;
  144.         Node next;
  146.         public Node(E element, Node next) {
  147.             this.data = element;
  148.             this.next = next;
  149.         }
  151.         public Node(E data) {
  152.             this.data = data;
  153.         }
  155.         public Node() {
  156.         }
  158.         @Override
  159.         public String toString() {
  160.             return "Node{" +
  161.                     "data=" + data +
  162.                     ", next=" + next +
  163.                     '}';
  164.         }
  165.     }
  167.     /**
  168.      * 判断参数是否为现有元素的索引  即边界
  169.      *
  170.      * @param index
  171.      */
  172.     private void checkElementIndex(int index) {
  173.         if (!(index >= 0 && index < size))
  174.             throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
  175.     }
  177.     @Override
  178.     public String toString() {
  179.         Node node = list;
  180.         for (int i = 0; i < size; i++) {
  181.             System.out.print(node.data + " ");
  182.             node = node.next;
  183.         }
  184.         return super.toString();
  185.     }
  187.     public static void main(String[] args) {
  188.         SingleLinkedList<Integer> list = new SingleLinkedList<>();
  189.         list.add(5);
  190.         list.add(4);
  191.         list.add(3);
  192.         list.add(2);
  193.         list.add(1);
  194.         list.toString();
  195.         System.out.println();
  196.         list.add(2, 5);
  197.         list.toString();
  198.         list.removeLast();
  199.         System.out.println();
  200.         list.toString();
  201.         list.set(1, 1);
  202.         System.out.println();
  203.         list.toString();
  204.         System.out.println();
  205.         System.out.println(list.get());
  206.     }
  207. }

双链表LinkedList源码分析

双链表，指各节点之间的逻辑关系是双向的。

02.线性表之链表LinkedList - 图11

节点

02.线性表之链表LinkedList - 图12
因此，在双向链表中各节点包含以下 3 部分信息

  • 指针域：用于指向当前节点的直接前驱节点；
  • 数据域：用于存储数据元素。
  • 指针域：用于指向当前节点的直接后继节点；
  1. private static class Node<E> {
  2.     E item;
  3.     Node<E> next;
  4.     Node<E> prev;
  6.     Node(Node<E> prev, E element, Node<E> next) {
  7.     this.item = element;
  8.     this.next = next;
  9.     this.prev = prev;
  10.     }
  11. }

如果理解了单链表，双项链表其实也没有太多的差别，主要在于限制条件。不仅仅是双向链表，还有很多分类，比如静态链表，动态链表，循环链表等等。这里可以就增删给出对应的过程，源码可以自己去研究研究。

类的继承关系

02.线性表之链表LinkedList - 图13

双链表—-增

02.线性表之链表LinkedList - 图14

  1. public void add(int index, E element) {
  2.     checkPositionIndex(index);
  3.     //如果索引和size相等直接尾部插入
  4.     if (index == size)
  5.         linkLast(element);
  6.     else
  7.         linkBefore(element, node(index));
  8. }
  11. /**
  12.  * first 指向第一个节点的指针
  13.  * @param e 要插入的元素
  14.  * @param succ index位置的节点
  15.  *  a1        a3
  16.  * 在a3索引出插入新的元素  a2
  17.  *  a1    a2    a3
  18.  */
  19. void linkBefore(E e, Node<E> succ) {
  20.     // succ：原a3的前置节点a1
  21.     final Node<E> pred = succ.prev;
  22.     //pred(a1) e(a2) succ(a3)形成新的节点
  23.     //即把e(a2)prev指向pred(a1)节点，把e(a2)next指向succ(a3)节点
  24.     final Node<E> newNode = new Node<>(pred, e, succ);
  25.     //把succ(a3)的prev指向新的节点newNode
  26.     succ.prev = newNode;
  27.     //pred为空代表newNode为首节点
  28.     if (pred == null)
  29.         first = newNode;
  30.     else
  31.         //a1的next节点由a3变为a2
  32.         pred.next = newNode;
  33.     size++;
  34.     modCount++;
  35. }

双链表—-删

02.线性表之链表LinkedList - 图15

  1. public E remove(int index) {
  2.     checkElementIndex(index);
  3.     return unlink(node(index));
  4.     }
  6. /**
  7.  * Unlinks non-null node x.
  8.  */
  9.  E unlink(Node<E> x) {
  10.      // assert x != null;
  11.      //获取该节点的值
  12.      final E element = x.item;
  13.      //获取该节点的next节点
  14.      final Node<E> next = x.next;
  15.      //获取该节点的prev节点
  16.      final Node<E> prev = x.prev;
  17.      //把该节点的前节点的next指向该节点的next节点，并清除该节点的prev指向
  18.      if (prev == null) {
  19.          first = next;
  20.      } else {
  21.          prev.next = next;
  22.          x.prev = null;
  23.      }
  24.      //把该节点的next节点的prev指向该节点的prev节点，并清除该节点的next指向
  25.      if (next == null) {
  26.          last = prev;
  27.      } else {
  28.          next.prev = prev;
  29.          x.next = null;
  30.      }
  31.      x.item = null;//gc清除
  32.      size--;
  33.      modCount++;
  34.      return element;
  35.  }

总结

前面讲过ArrayList源码分析及扩容机制,如果你看了应该知道不管是用ArrayList还是LinkedList主要是看场景，LinkedList增删快，因为只用调整指向即可，对于ArrayList而言却要移动整个数组，但是如果说是在尾部插入的话，使用两者都可以。而查找和修改却要ArrayList只需要知道下标即可，而对于LinkedList却要通过循环查找。

对于LinkendList，其中还有很多方法，例如addFirst，addLast，remove等，如果你学会了单链表，其实双链表也是一样的，主要在于思维。

参考

拓展延伸

  • ArrayList和LinkedList有什么区别？
  • 什么时候用ArrayList,什么时候用LinkedList？