某团技术拷问：LinkedList源码看过吗？

一、LinkedList 的剖白

大家好，我是 LinkedList，和 ArrayList 是同门师兄弟，但我俩练的内功却完全不同。师兄练的是动态数组，我练的是链表。

员工经过长期磨合与沉淀，具备了协作精神，得以通过团队的力量开发出优质的产品。创新互联坚持“专注、创新、易用”的产品理念，因为“专注所以专业、创新互联网站所以易用所以简单”。公司专注于为企业提供成都网站制作、网站设计、外贸网站建设、微信公众号开发、电商网站开发，小程序设计，软件按需网站开发等一站式互联网企业服务。

问大家一个问题，知道我为什么要练链表这门内功吗?

举个例子来讲吧，假如你们手头要管理一推票据，可能有一张，也可能有一亿张。

该怎么办呢?

申请一个 10G 的大数组等着?那万一票据只有 100 张呢?

申请一个默认大小的数组，随着数据量的增大扩容?要知道扩容是需要重新复制数组的，很耗时间。

关键是，数组还有一个弊端就是，假如现在有 500 万张票据，现在要从中间删除一个票据，就需要把 250 万张票据往前移动一格。

遇到这种情况的时候，我师兄几乎情绪崩溃，难受的要命。师父不忍心看到师兄这样痛苦，于是打我进入师门那一天，就强迫我练链表这门内功，一开始我很不理解，害怕师父偏心，不把师门最厉害的内功教我。

直到有一天，我亲眼目睹师兄差点因为移动数据而走火入魔，我才明白师父的良苦用心。从此以后，我苦练“链表”这门内功，取得了显著的进步，师父和师兄都夸我有天赋。

链表这门内功大致分为三个层次：

  • 第一层叫做“单向链表”，我只有一个后指针，指向下一个数据;
  • 第二层叫做“双向链表”，我有两个指针，后指针指向下一个数据，前指针指向上一个数据。
  • 第三层叫做“二叉树”，把后指针去掉，换成左右指针。

但我现在的功力还达不到第三层，不过师父说我有这个潜力，练成神功是早晚的事。

二、LinkedList 的内功心法

好了，经过我这么样的一个剖白后，大家对我应该已经不陌生了。那么接下来，我给大家展示一下我的内功心法。

我的内功心法主要是一个私有的静态内部类，叫 Node，也就是节点。

 
 
 
 
    
  
  
  
  
  1. private static class Node { 
    2.   
  
  
  
  2.     E item; 
    3.   
  
  
  
  3.     Node next; 
    4.   
  
  
  
  4.     Node prev; 
    5.   
  
  
  
  5.  
    6.   
  
  
  
  6.     Node(Node prev, E element, Node next) { 
    7.   
  
  
  
  7.         this.item = element; 
    8.   
  
  
  
  8.         this.next = next; 
    9.   
  
  
  
  9.         this.prev = prev; 
    10.   
  
  
  
  10.     } 
    11.   
  
  
  
  11. } 
    12.

它由三部分组成：

  • 节点上的元素
  • 下一个节点
  • 上一个节点

我画幅图给你们展示下吧。

  • 对于第一个节点来说，prev 为 null;
  • 对于最后一个节点来说，next 为 null;
  • 其余的节点呢，prev 指向前一个，next 指向后一个。

我的内功心法就这么简单，其实我早已经牢记在心了。但师父叮嘱我，每天早上醒来的时候，每天晚上睡觉的时候，一定要默默地背诵一遍。虽然我有些厌烦，但我对师父的教诲从来都是言听计从。

三、LinkedList 的招式

和师兄 ArrayList 一样，我的招式也无外乎“增删改查”这 4 种。在此之前，我们都必须得初始化。

 
 
 
 
    
  
  
  
  
  1. LinkedList list = new LinkedList(); 
    2.

师兄在初始化的时候，默认大小为 10，也可以指定大小，依据要存储的元素数量来。我就不需要。

1)招式一：增

可以调用 add 方法添加元素：

 
 
 
 
    
  
  
  
  
  1. list.add("沉默王二"); 
    2.   
  
  
  
  2. list.add("沉默王三"); 
    3.   
  
  
  
  3. list.add("沉默王四"); 
    4.

add 方法内部其实调用的是 linkLast 方法：

 
 
 
 
    
  
  
  
  
  1. public boolean add(E e) { 
    2.   
  
  
  
  2.     linkLast(e); 
    3.   
  
  
  
  3.     return true; 
    4.   
  
  
  
  4. } 
    5.

linkLast，顾名思义，就是在链表的尾部链接：

 
 
 
 
    
  
  
  
  
  1. void linkLast(E e) { 
    2.   
  
  
  
  2.     final Node l = last; 
    3.   
  
  
  
  3.     final Node newNode = new Node<>(l, e, null); 
    4.   
  
  
  
  4.     last = newNode; 
    5.   
  
  
  
  5.     if (l == null) 
    6.   
  
  
  
  6.         first = newNode; 
    7.   
  
  
  
  7.     else 
    8.   
  
  
  
  8.         l.next = newNode; 
    9.   
  
  
  
  9.     size++; 
    10.   
  
  
  
  10.     modCount++; 
    11.   
  
  
  
  11. } 
    12.
  • 添加第一个元素的时候，first 和 last 都为 null。
  • 然后新建一个节点 newNode，它的 prev 和 next 也为 null。
  • 然后把 last 和 first 都赋值为 newNode。

此时还不能称之为链表，因为前后节点都是断裂的。

  • 添加第二个元素的时候，first 和 last 都指向的是第一个节点。
  • 然后新建一个节点 newNode，它的 prev 指向的是第一个节点，next 为 null。
  • 然后把第一个节点的 next 赋值为 newNode。

此时的链表还不完整。

  • 添加第三个元素的时候，first 指向的是第一个节点，last 指向的是最后一个节点。
  • 然后新建一个节点 newNode，它的 prev 指向的是第二个节点，next 为 null。
  • 然后把第二个节点的 next 赋值为 newNode。

此时的链表已经完整了。

我这个增的招式，还可以演化成另外两个：

  • addFirst() 方法将元素添加到第一位;
  • addLast() 方法将元素添加到末尾。

addFirst 内部其实调用的是 linkFirst：

 
 
 
 
    
  
  
  
  
  1. public void addFirst(E e) { 
    2.   
  
  
  
  2.     linkFirst(e); 
    3.   
  
  
  
  3. } 
    4.

linkFirst 负责把新的节点设为 first，并将新的 first 的 next 更新为之前的 first。

 
 
 
 
    
  
  
  
  
  1. private void linkFirst(E e) { 
    2.   
  
  
  
  2.     final Node f = first; 
    3.   
  
  
  
  3.     final Node newNode = new Node<>(null, e, f); 
    4.   
  
  
  
  4.     first = newNode; 
    5.   
  
  
  
  5.     if (f == null) 
    6.   
  
  
  
  6.         last = newNode; 
    7.   
  
  
  
  7.     else 
    8.   
  
  
  
  8.         f.prev = newNode; 
    9.   
  
  
  
  9.     size++; 
    10.   
  
  
  
  10.     modCount++; 
    11.   
  
  
  
  11. } 
    12.

addLast 的内核其实和 addFirst 差不多，就交给大家自行理解了。

2)招式二：删

我这个删的招式还挺多的：

  • remove()：删除第一个节点
  • remove(int)：删除指定位置的节点
  • remove(Object)：删除指定元素的节点
  • removeFirst()：删除第一个节点
  • removeLast()：删除最后一个节点

remove 内部调用的是 removeFirst，所以这两个招式的功效一样。

remove(int) 内部其实调用的是 unlink 方法。

 
 
 
 
    
  
  
  
  
  1. public E remove(int index) { 
    2.   
  
  
  
  2.     checkElementIndex(index); 
    3.   
  
  
  
  3.     return unlink(node(index)); 
    4.   
  
  
  
  4. } 
    5.

unlink 方法其实很好理解，就是更新当前节点的 next 和 prev，然后把当前节点上的元素设为 null。

 
 
 
 
    
  
  
  
  
  1. E unlink(Node x) { 
    2.   
  
  
  
  2.     // assert x != null; 
    3.   
  
  
  
  3.     final E element = x.item; 
    4.   
  
  
  
  4.     final Node next = x.next; 
    5.   
  
  
  
  5.     final Node prev = x.prev; 
    6.   
  
  
  
  6.  
    7.   
  
  
  
  7.     if (prev == null) { 
    8.   
  
  
  
  8.         first = next; 
    9.   
  
  
  
  9.     } else { 
    10.   
  
  
  
  10.         prev.next = next; 
    11.   
  
  
  
  11.         x.prev = null; 
    12.   
  
  
  
  12.     } 
    13.   
  
  
  
  13.  
    14.   
  
  
  
  14.     if (next == null) { 
    15.   
  
  
  
  15.         last = prev; 
    16.   
  
  
  
  16.     } else { 
    17.   
  
  
  
  17.         next.prev = prev; 
    18.   
  
  
  
  18.         x.next = null; 
    19.   
  
  
  
  19.     } 
    20.   
  
  
  
  20.  
    21.   
  
  
  
  21.     x.item = null; 
    22.   
  
  
  
  22.     size--; 
    23.   
  
  
  
  23.     modCount++; 
    24.   
  
  
  
  24.     return element; 
    25.   
  
  
  
  25. } 
    26.

remove(Object) 内部也调用了 unlink 方法，只不过在此之前要先找到元素所在的节点：

 
 
 
 
    
  
  
  
  
  1. public boolean remove(Object o) { 
    2.   
  
  
  
  2.     if (o == null) { 
    3.   
  
  
  
  3.         for (Node x = first; x != null; x = x.next) { 
    4.   
  
  
  
  4.             if (x.item == null) { 
    5.   
  
  
  
  5.                 unlink(x); 
    6.   
  
  
  
  6.                 return true; 
    7.   
  
  
  
  7.             } 
    8.   
  
  
  
  8.         } 
    9.   
  
  
  
  9.     } else { 
    10.   
  
  
  
  10.         for (Node x = first; x != null; x = x.next) { 
    11.   
  
  
  
  11.             if (o.equals(x.item)) { 
    12.   
  
  
  
  12.                 unlink(x); 
    13.   
  
  
  
  13.                 return true; 
    14.   
  
  
  
  14.             } 
    15.   
  
  
  
  15.         } 
    16.   
  
  
  
  16.     } 
    17.   
  
  
  
  17.     return false; 
    18.   
  
  
  
  18. } 
    19.

这内部就分为两种，一种是元素为 null 的时候，必须使用 == 来判断;一种是元素为非 null 的时候，要使用 equals 来判断。equals 是不能用来判 null 的，会抛出 NPE 错误。

removeFirst 内部调用的是 unlinkFirst 方法：

 
 
 
 
    
  
  
  
  
  1. public E removeFirst() { 
    2.   
  
  
  
  2.     final Node f = first; 
    3.   
  
  
  
  3.     if (f == null) 
    4.   
  
  
  
  4.         throw new NoSuchElementException(); 
    5.   
  
  
  
  5.     return unlinkFirst(f); 
    6.   
  
  
  
  6. } 
    7.

unlinkFirst 负责的就是把第一个节点毁尸灭迹，并且捎带把后一个节点的 prev 设为 null。

 
 
 
 
    
  
  
  
  
  1. private E unlinkFirst(Node f) { 
    2.   
  
  
  
  2.     // assert f == first && f != null; 
    3.   
  
  
  
  3.     final E element = f.item; 
    4.   
  
  
  
  4.     final Node next = f.next; 
    5.   
  
  
  
  5.     f.item = null; 
    6.   
  
  
  
  6.     f.next = null; // help GC 
    7.   
  
  
  
  7.     first = next; 
    8.   
  
  
  
  8.     if (next == null) 
    9.   
  
  
  
  9.         last = null; 
    10.   
  
  
  
  10.     else 
    11.   
  
  
  
  11.         next.prev = null; 
    12.   
  
  
  
  12.     size--; 
    13.   
  
  
  
  13.     modCount++; 
    14.   
  
  
  
  14.     return element; 
    15.   
  
  
  
  15. } 
    16.

3)招式三：改

可以调用 set() 方法来更新元素：

 
 
 
 
    
  
  
  
  
  1. list.set(0, "沉默王五"); 
    2.

来看一下 set() 方法：

 
 
 
 
    
  
  
  
  
  1. public E set(int index, E element) { 
    2.   
  
  
  
  2.     checkElementIndex(index); 
    3.   
  
  
  
  3.     Node x = node(index); 
    4.   
  
  
  
  4.     E oldVal = x.item; 
    5.   
  
  
  
  5.     x.item = element; 
    6.   
  
  
  
  6.     return oldVal; 
    7.   
  
  
  
  7. } 
    8.

首先对指定的下标进行检查，看是否越界;然后根据下标查找原有的节点：

 
 
 
 
    
  
  
  
  
  1. Node node(int index) { 
    2.   
  
  
  
  2.     // assert isElementIndex(index); 
    3.   
  
  
  
  3.  
    4.   
  
  
  
  4.     if (index < (size >> 1)) { 
    5.   
  
  
  
  5.         Node x = first; 
    6.   
  
  
  
  6.         for (int i = 0; i < index; i++) 
    7.   
  
  
  
  7.             x = x.next; 
    8.   
  
  
  
  8.         return x; 
    9.   
  
  
  
  9.     } else { 
    10.   
  
  
  
  10.         Node x = last; 
    11.   
  
  
  
  11.         for (int i = size - 1; i > index; i--) 
    12.   
  
  
  
  12.             x = x.prev; 
    13.   
  
  
  
  13.         return x; 
    14.   
  
  
  
  14.     } 
    15.   
  
  
  
  15. } 
    16.

size >> 1：也就是右移一位，相当于除以 2。对于计算机来说，移位比除法运算效率更高，因为数据在计算机内部都是二进制存储的。

换句话说，node 方法会对下标进行一个初步判断，如果靠近前半截，就从下标 0 开始遍历;如果靠近后半截，就从末尾开始遍历。

找到指定下标的节点就简单了，直接把原有节点的元素替换成新的节点就 OK 了，prev 和 next 都不用改动。

4)招式四：查

我这个查的招式可以分为两种：

  • indexOf(Object)：查找某个元素所在的位置
  • get(int)：查找某个位置上的元素

indexOf 的内部分为两种，一种是元素为 null 的时候，必须使用 == 来判断;一种是元素为非 null 的时候，要使用 equals 来判断。因为 equals 是不能用来判 null 的，会抛出 NPE 错误。

 
 
 
 
    
  
  
  
  
  1. public int indexOf(Object o) { 
    2.   
  
  
  
  2.     int index = 0; 
    3.   
  
  
  
  3.     if (o == null) { 
    4.   
  
  
  
  4.         for (Node x = first; x != null; x = x.next) { 
    5.   
  
  
  
  5.             if (x.item == null) 
    6.   
  
  
  
  6.                 return index; 
    7.   
  
  
  
  7.             index++; 
    8.   
  
  
  
  8.         } 
    9.   
  
  
  
  9.     } else { 
    10.   
  
  
  
  10.         for (Node x = first; x != null; x = x.next) { 
    11.   
  
  
  
  11.             if (o.equals(x.item)) 
    12.   
  
  
  
  12.                 return index; 
    13.   
  
  
  
  13.             index++; 
    14.   
  
  
  
  14.         } 
    15.   
  
  
  
  15.     } 
    16.   
  
  
  
  16.     return -1; 
    17.   
  
  
  
  17. } 
    18.

get 方法的内核其实还是 node 方法，这个之前已经说明过了，这里略过。

 
 
 
 
    
  
  
  
  
  1. public E get(int index) { 
    2.   
  
  
  
  2.     checkElementIndex(index); 
    3.   
  
  
  
  3.     return node(index).item; 
    4.   
  
  
  
  4. } 
    5.

其实，查这个招式还可以演化为其他的一些，比如说：

  • getFirst() 方法用于获取第一个元素;
  • getLast() 方法用于获取最后一个元素;
  • poll() 和 pollFirst() 方法用于删除并返回第一个元素(两个方法尽管名字不同，但方法体是完全相同的);
  • pollLast() 方法用于删除并返回最后一个元素;
  • peekFirst() 方法用于返回但不删除第一个元素。

四、LinkedList 的挑战

说句实在话，我不是很喜欢和师兄 ArrayList 拿来比较，因为我们各自修炼的内功不同，没有孰高孰低。

虽然师兄经常喊我一声师弟，但我们之间其实挺和谐的。但我知道，在外人眼里，同门师兄弟，总要一较高下的。

比如说，我们俩在增删改查时候的时间复杂度。

也许这就是命运吧，从我进入师门的那天起，这种争论就一直没有停息过。

无论外人怎么看待我们，在我眼里，师兄永远都是一哥，我敬重他，他也愿意保护我。

好了，LinkedList 这篇就到这了。

本文转载自微信公众号「沉默王二」，可以通过以下二维码关注。转载本文请联系沉默王二公众号。

网站标题：某团技术拷问：LinkedList源码看过吗？
网站URL：http://www.shufengxianlan.com/qtweb/news12/23462.html

网站建设、网络推广公司-创新互联，是专注品牌与效果的网站制作，网络营销seo公司；服务项目有等

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联

猜你还喜欢下面的内容

Google知识

分类信息网

成都网站建设推广　　 　防护网厂　　 　自适应网站建设　　 　物流公司网站建设方案　　 　成都托管服务器　　 　SF双层罐　　 　成都网站制作　　 　成都免费做网站公司　　 　雅安做网站　　 　顺泽窗帘　　 　乐山电信机房　　 　企业网站制作　　 　成都纯水机　　 　成都营销网站制作　　 　瑞杰企业管理　　 　企业网站设计　　 　达州主机托管　　 　温江做网站公司　　 　古巴雪茄　　 　APP定制