(二)LinkedList集合解析及手写集合

2019 年 10 月 3 日
筆記

一、LinkedList集合特点

问题	结论
LinkedList是否允许空	允许
LinkedList是否允许重复数据	允许
LinkedList是否有序	有序
LinkedList是否线程安全	非线程安全

　　 LinkedList集合底层是由双向链表组成，而不是双向循环链表。

有一个头结点和一个尾结点，我们可以从头开始正向遍历，或者是从尾开始逆向遍历，并且可以针对头部和尾部进行相应的操作。

二、LinkedList集合底层实现

1.什么是链表

链表原是一种线性的存储结构，意思是将要存储的数据存在一个存储单元里面，这个存储单元里面除了存放有待存储的数据以外，还存储有其下一个存储单元的地址（下一个存储单元的地址是必要的，有些存储结构还存放有其前一个存储单元的地址），每次查找数据的时候，通过某个存储单元中的下一个存储单元的地址寻找其后面的那个存储单元。

2. 什么是双向链表

双向链表也是链表的一种，它每个数据结点中都有两个结点，分别指向其直接前驱和直接后继。所以我们从双向链表的任意一个结点开始都可以很方便的访问其前驱元素和后继元素。

3.双向链表的定义

4.双向链表的存储结构

双向链表也是采用的链式存储结构，它与单链表的区别就是每个数据结点中多了一个指向前驱元素的指针域，它的存储结构如下图

当双向链表只有一个结点的时候它的存储结构如下：

头节点和尾结点指向同一个元素。

三.LinkedList源码分析

1.构造方法，无参构造，有参构造。

1 public LinkedList() {  2 }  3 public LinkedList(Collection<? extends E> c) {  4         // 调用无参构造函数  5         this();  6         // 添加集合中所有的元素  7         addAll(c);  8     }

2.Node结点组成

 1 private static class Node<E> {   2         E item; // 数据域   3         Node<E> next; // 后继   4         Node<E> prev; // 前驱   5   6         // 构造函数，赋值前驱后继   7         Node(Node<E> prev, E element, Node<E> next) {   8             this.item = element;   9             this.next = next;  10             this.prev = prev;  11         }  12     }

3.添加元素 add方法

 1 public boolean add(E e) {   2         linkLast(e);// // 添加元素到末尾   3         return true;   4     }   5 void linkLast(E e) {   6         // 保存尾结点，l为final类型，不可更改   7         final Node<E> l = last;   8         // 新生成结点的前驱为l,后继为null   9         final Node<E> newNode = new Node<>(l, e, null);  10         // 重新赋值尾结点  11         last = newNode;  12         if (l == null) // 尾结点为空  13             first = newNode; // 赋值头结点  14         else // 尾结点不为空  15             l.next = newNode; // 尾结点的后继为新生成的结点  16         // 大小加1      17         size++;  18         // 结构性修改加1  19         modCount++;  20     }

3.查询元素E get(int index)获取指定节点数据

 1 public E get(int index) {   2     checkElementIndex(index);   3     return node(index).item;   4 }   5  Node<E> node(int index) {   6         // 判断插入的位置在链表前半段或者是后半段   7         if (index < (size >> 1)) { // 插入位置在前半段   8             Node<E> x = first;   9             for (int i = 0; i < index; i++) // 从头结点开始正向遍历  10                 x = x.next;  11             return x; // 返回该结点  12         } else { // 插入位置在后半段  13             Node<E> x = last;  14             for (int i = size - 1; i > index; i--) // 从尾结点开始反向遍历  15                 x = x.prev;  16             return x; // 返回该结点  17         }  18     }

4.remove移除结点时

 1 E unlink(Node<E> x) {   2         // 保存结点的元素   3         final E element = x.item;   4         // 保存x的后继   5         final Node<E> next = x.next;   6         // 保存x的前驱   7         final Node<E> prev = x.prev;   8   9         if (prev == null) { // 前驱为空，表示删除的结点为头结点  10             first = next; // 重新赋值头结点  11         } else { // 删除的结点不为头结点  12             prev.next = next; // 赋值前驱结点的后继  13             x.prev = null; // 结点的前驱为空，切断结点的前驱指针  14         }  15  16         if (next == null) { // 后继为空，表示删除的结点为尾结点  17             last = prev; // 重新赋值尾结点  18         } else { // 删除的结点不为尾结点  19             next.prev = prev; // 赋值后继结点的前驱  20             x.next = null; // 结点的后继为空，切断结点的后继指针  21         }  22  23         x.item = null; // 结点元素赋值为空  24         // 减少元素实际个数  25         size--;  26         // 结构性修改加1  27         modCount++;  28         // 返回结点的旧元素  29         return element;  30     }

四.手写LinkedList代码：

手写源码主要是为了便于对LinkedList集合的更好理解，主要对add(),remove,add(index,element) ,get(i)这些方法进行简单的写法，写法比较通俗更便于理解。具体可以参考下面的代码。

1.自定义LinkedList集合。

  1 package com.zzw.cn.springmvc.linkList;    2    3 /**    4  * @author Simple    5  * @date 16:58 2019/9/5    6  * @description 手写LinkList集合    7  * 思路:    8  * 1.集合add    9  * 2.remove   10  * 3.add(index,element)   11  */   12   13 public class AnLinkeList<E> {   14     private Node first;//第一个节点值   15     private Node last;//最后一个节点值   16     int size;//集合长度   17   18     /**   19      * 添加   20      *   21      * @param e   22      */   23     public void add(E e) {   24         Node node = new Node();   25         //增加时判断集合是否为null 1.为null时候位置指向不同   26         node.object = e;   27         if (null == first) {   28   29             //第一个元素添加是第一个节点和最后一个节点指向位置都为第一个   30             first = node;   31         } else {   32             //存放上一个节点内容   33             node.prev = last;   34             //将上一个节点值指向当前节点   35             last.next = node;   36         }   37         //对最后一个节点赋值   38         last = node;   39         size++;   40     }   41   42     public E get(int index) {   43         Node node = null;   44         if (null != first) {   45             node = first;   46             //循环遍历指向最后一个节点   47             for (int i = 0; i < index; i++) {   48                 node = node.next;   49             }   50             return (E) node.object;   51         }   52         return null;   53     }   54   55     public Node getNode(int index) {   56         Node node = null;   57         if (null != first) {   58             node = first;   59             //循环遍历指向最后一个节点   60             for (int i = 0; i < index; i++) {   61                 node = node.next;   62             }   63             return node;   64         }   65         return null;   66     }   67   68     //删除   69     public void remove(int index) {   70         //1找到当前元素  删除时，将当前元素B的pre指向上一个A节点，将上一个元素A的节点指向当前元素B的next节点。   71         checkElementIndex(index);   72         Node node = getNode(index);   73         Node prevNode = node.prev;   74         Node nextNode = node.next;   75         if (prevNode.next != null) {   76             prevNode.next = nextNode;   77         }   78         if (nextNode != null) {   79             nextNode.prev = prevNode;   80         }   81         size--;   82   83     }   84   85     private boolean isElementIndex(int index) {   86         return index >= 0 && index <= size;   87     }   88   89     private void checkElementIndex(int index) {   90         if (!isElementIndex(index))   91             throw new IndexOutOfBoundsException("越界啦!");   92     }   93   94     private void add(int index, E e) {   95         checkElementIndex(index);   96         if (index == size)   97             add(e);   98         else   99             addEle(index, e);  100  101     }  102  103     private void addEle(int index, E e) {  104         /**  105          *  106          *   新增E  上一个节点是A   下一个节点是B  107          *   A->next=E  108          *   E->pre=A  109          *   E->next=B  110          *   B->pre=E  111          */  112         Node newNode = new Node();  113         newNode.object = e;  114         Node oldNode = getNode(index);  115         Node oldPrev = oldNode.prev;  116         //当前节点上一个对应新节点  117         oldNode.prev = newNode;  118         //如果当前节点为第一个时候  119         if (oldPrev == null) {  120             first = newNode;  121         } else {  122             //新节点的下一个对应当前节点  123             oldPrev.next = newNode;  124         }  125         //新节点的上一个对应老节点之前的  126         newNode.prev = oldPrev;  127         //老节点的下一个对应新节点  128         newNode.next = oldNode;  129         size++;  130  131     }  132  133 }

2.节点的定义

 1 package com.zzw.cn.springmvc.linkList;   2   3 /**   4  * @author Simple   5  * @date 17:01 2019/9/5   6  * @description 定义节点   7  */   8 public class Node {   9     Node prev;//上一个节点  10     Node next;//下一个节点  11     Object object;//节点值  12 }

3.测试类的编写。

 1 package com.zzw.cn.springmvc.linkList;   2   3 /**   4  * @author Simple   5  * @date 19:45 2019/9/5   6  * @description   7  */   8 public class TestLinkeList {   9     public static void main(String[] args) {  10         AnLinkeList<String> list = new AnLinkeList<>();  11         list.add("1");  12         list.add("2");  13         list.add("3");  14         System.out.println("add方法后结果");  15         for (int i = 0; i < list.size; i++) {  16             System.out.print(list.get(i)+" ");  17         }  18         System.out.println();  19         list.remove(2);  20         System.out.println("remove方法后结果");  21         for (int i = 0; i < list.size; i++) {  22             System.out.print(list.get(i)+" ");  23         }  24         System.out.println("根据索引值添加的");  25         list.add(1,"3");  26         for (int i = 0; i < list.size; i++) {  27             System.out.print(list.get(i)+" ");  28         }  29     }  30 }

4.运行结果

五、LinkedList和ArrayList的对比

1、顺序插入速度ArrayList会比较快，因为ArrayList是基于数组实现的，数组是事先new好的，只要往指定位置塞一个数据就好了；

LinkedList则不同，每次顺序插入的时候LinkedList将new一个对象出来，如果对象比较大，那么new的时间势必会长一点，再加上一些引用赋值的操作，所以顺序插入LinkedList必然慢于ArrayList

2、基于上一点，因为LinkedList里面不仅维护了待插入的元素，还维护了Entry的前置Entry和后继Entry，如果一个LinkedList中的Entry非常多，那么LinkedList将比ArrayList更耗费一些内存

3、有些说法认为LinkedList做插入和删除更快，这种说法其实是不准确的：

（1）LinkedList做插入、删除的时候，慢在寻址，快在只需要改变前后Entry的引用地址

（2）ArrayList做插入、删除的时候，慢在数组元素的批量copy，快在寻址