100行代码手写模拟一个LinkedList

矫情吗；* 2022-04-17 04:50 581阅读 0赞

前言：

首先先说一下昨天的模拟ArrayList中的remove（)方法，昨晚思考了一下，那么实现不太好，所以又想了一个新的算法，具体如下，假如现在需要remove的index是2，那么就从index+1位置到数组最后的size开始循环，依次把下一个值赋给上一个，比如说4赋值给3的位置，5到4的位置依次进行，这样3就被移除了。代码如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyOTY3NjY1_size_16_color_FFFFFF_t_70][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyOTY3NjY1_size_16_color_FFFFFF_t_70 1][]

一、LinkedList、ArrayList

<table> 
 <tbody> 
  <tr> 
   <td style="vertical-align:top;">&nbsp;</td> 
   <td style="vertical-align:top;">&nbsp; &nbsp; &nbsp; &nbsp;查询</td> 
   <td style="vertical-align:top;">&nbsp; &nbsp; &nbsp; 添加</td> 
   <td style="vertical-align:top;">&nbsp; &nbsp; &nbsp; &nbsp;删除</td> 
   <td style="vertical-align:top;">&nbsp; &nbsp;实现原理</td> 
  </tr> 
  <tr> 
   <td style="vertical-align:top;">ArrayList</td> 
   <td style="vertical-align:top;">&nbsp; &nbsp; 效率高</td> 
   <td style="vertical-align:top;">&nbsp; &nbsp;效率低</td> 
   <td style="vertical-align:top;">&nbsp; &nbsp; &nbsp;效率低</td> 
   <td style="vertical-align:top;">&nbsp; &nbsp; &nbsp; 数组</td> 
  </tr> 
  <tr> 
   <td style="vertical-align:top;">LinkedList</td> 
   <td style="vertical-align:top;">&nbsp; &nbsp; 效率低</td> 
   <td style="vertical-align:top;">&nbsp; &nbsp;效率高</td> 
   <td style="vertical-align:top;">&nbsp; &nbsp; 效率高</td> 
   <td style="vertical-align:top;">&nbsp; &nbsp; &nbsp; 链表</td> 
  </tr> 
 </tbody> 
</table>

二、LinkedList的实现

在JDK中LinkedList的实现是基于双向循环列表，学过数据结构我们就知道链表的特点，在进行查询的时候它不能向数组一样，直接根据下标index来取值，而是需要从第一个节点到index节点遍历，因此查询效率是极其低下的。

进行插入的时候，ArrayList如果不需要扩容那效率没什么问题，但是如果要扩容的话，那首先会创建一个新的数组，然后把原来的数据复制到新数组中去，这样数据量大的话，效率是很低下的。而LinkedList是基于双向链表的实现，我们知道双向链表的头节点（Header）是直接可以指到最后的节点的，这样在添加的时候，只需要在最后一个节点后面再加一个节点（新值）就可以了，所以LinkedList的添加效率极快。

ArrayList循环删除元素的时候，从后往前遍历来进行删除（效率比从前往后要高），对比前言里面的图大家体会下，总体来说ArrayList的删除元素很慢。

LinkedList删除元素的时候，从前和从后的效率都很快，因为Header可以指向最后同时也是最前的节点，反而是删除中间比较慢，但即使是这样，综合来说LinkedList的效率也要比ArrayList高的多。因为LinkedList最坏的结果也就是循环到中间，而ArrayList最坏是要循环除第一个节点外的其他节点。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyOTY3NjY1_size_16_color_FFFFFF_t_70 2][]

三、使用单向链表模拟LinkedList

使用单向链表来模拟LinkedList时，我们的准备工作当然是要创建一个节点Node对象。需要设置一个Object类型的value值，另一个是指向下一个节点的指针，但是Java中没有指针这个概念，怎么办呢？我们采用引用来解决，定义一个Node类型的引用用来指向下一个节点。代码如下：截图省略了setter、getter方法。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyOTY3NjY1_size_16_color_FFFFFF_t_70 3][]

接下来的工作就是使用链表实现了，在链表中由于我们使用的是单向的链表，因此只需要定义size（长度）和Node head（头节点），接下来我们来看下add方法

解释一下：在添加的时候，首先判断添加的节点是不是头节点，如果是说明是第一个节点，就直接把node设置为head。如果不是第一个节点，那么我们就把它设置到接下来的节点，需要注意的是temp保留的是头节点的值，相当于从头节点开始寻找不为空的节点，然后设置进去。如果temp的下一个节点是空节点那么表示是最后一个节点，因为在单向链表中最后节点没有下一个节点了，这时就直接把node设置进去。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyOTY3NjY1_size_16_color_FFFFFF_t_70 4][]

接下来是set（) 方法，分析一下，在设置值的时候从0开始到index位置进行循环，循环后便找到了index，接着把value直接赋给这个节点。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyOTY3NjY1_size_16_color_FFFFFF_t_70 5][]

而get（) 的时候和set原理基本一致，只是将找到的值返给用户。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyOTY3NjY1_size_16_color_FFFFFF_t_70 6][]

clear(）就不多做解释了直接将Head赋值为空，size为0就可以

![20181113125539386.png][]

重点看下remove

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyOTY3NjY1_size_16_color_FFFFFF_t_70 7][]

解释：如果要移除的是第一个节点，那么将第一个节点指向下一个节点，也就相当于head这个引用指向下一个节点，不指向第一个节点，也就代表第一个节点不存在了，因为没引用了。

如果删除的不是第一个节点，那么就从head开始遍历到index-1，也就是要删除元素的上一个元素，然后将index-1位置的节点和index+1位置的节点连接起来，之后size--就好。还是画个图解释下如果现在要删除是3这个节点。所以你需要把2的位置和4连接起来对吧，因此就是2位置的下一个的下一个。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyOTY3NjY1_size_16_color_FFFFFF_t_70 8][]

四、测试

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyOTY3NjY1_size_16_color_FFFFFF_t_70 9][]

![20181113125629224.png][]

五、总结

有时候从实现上去比较他们之前的原理会更便于理解。

更多内容请关注公众号：

![20181113125722610.png][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyOTY3NjY1_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20181113125220393.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyOTY3NjY1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyOTY3NjY1_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20181113125236140.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyOTY3NjY1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyOTY3NjY1_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20181113125300939.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyOTY3NjY1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyOTY3NjY1_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20181113125325309.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyOTY3NjY1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyOTY3NjY1_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20181113125338107.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyOTY3NjY1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyOTY3NjY1_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20181113125358556.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyOTY3NjY1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyOTY3NjY1_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20181113125526196.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyOTY3NjY1,size_16,color_FFFFFF,t_70
[20181113125539386.png]: https://img-blog.csdnimg.cn/20181113125539386.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyOTY3NjY1_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/20181113125549120.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyOTY3NjY1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyOTY3NjY1_size_16_color_FFFFFF_t_70 8]: https://img-blog.csdnimg.cn/20181113125602404.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyOTY3NjY1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyOTY3NjY1_size_16_color_FFFFFF_t_70 9]: https://img-blog.csdnimg.cn/20181113125618687.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyOTY3NjY1,size_16,color_FFFFFF,t_70
[20181113125629224.png]: https://img-blog.csdnimg.cn/20181113125629224.png
[20181113125722610.png]: https://img-blog.csdnimg.cn/20181113125722610.png