LinkedList 的特点及优缺点

àì夳堔傛蜴生んèń 2023-10-09 18:43 91阅读 0赞

现在来讲 LinkedList

![在这里插入图片描述][789454a278764b90a2cd85768b069a4c.png_pic_center]

LinkedList 是链表集合，基于链表去存储数据，每一个数据视作一个节点

private static class Node<E> {
        
    		// 存放的数据
            E item;
            // 下一个节点
            Node<E> next;
            // 上一个节点
            Node<E> prev;
    
            Node(Node<E> prev, E element, Node<E> next) {
        
                this.item = element;
                this.next = next;
                this.prev = prev;
            }
        }

效果如图示意：  
![在这里插入图片描述][a1e3ac538bf844b7b1cc4b92ebb4562a.png_pic_center]

LinkedList 封装的是一个双向链表，如果是单向链表则只有 next 节点

public class LinkedList<E> {
        
    	/**
         * Pointer to first node.
         */
        transient Node<E> first;
    
        /**
         * Pointer to last node.
         */
        transient Node<E> last;
    }

在 LinkedList 中，使用 first 来记录第一个节点，使用 last 来记录第二个节点，当只有一个元素的时候，两个节点的值一样

效果如图示意：  
![在这里插入图片描述][432fd3d06df84338986f87c9fd268f0d.png_pic_center]  
LinkedList 默认从尾部添加元素，当然也可以从头部添加元素  
![在这里插入图片描述][7e045625360e4685ab07f6ff2e459c67.png_pic_center]

LinkedList 的特点：有序、可重复、可存 null 值

LinkedList 的优点：增删快，不需要考虑扩容，只需要记住前一个和后一个节点就可以了

LinkedList 的缺点：查询慢，即便是知道索引，也得从头或者从尾一个个查询

LinkedList 的继承实现关系  
![在这里插入图片描述][e21b5557f7ff49c69cc825004fb21de6.png_pic_center]  
因为以上继承实现关系，所以说 LinkedList 的方法特别多，但是主要的有9个常用方法

![在这里插入图片描述][213052162538442986f1ffe197b1a5c7.png_pic_center]

#### ArrayList 和 LinkedList 的区别 ####

<table> 
 <thead> 
  <tr> 
   <th>分类</th> 
   <th>ArrayList</th> 
   <th>LinkedList</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>数据结构</td> 
   <td>数组</td> 
   <td>链表</td> 
  </tr> 
  <tr> 
   <td>查询速度</td> 
   <td>快</td> 
   <td>慢</td> 
  </tr> 
  <tr> 
   <td>增删速度</td> 
   <td>慢</td> 
   <td>快</td> 
  </tr> 
  <tr> 
   <td>存储相同数据所需要的空间</td> 
   <td>小</td> 
   <td>大</td> 
  </tr> 
  <tr> 
   <td>应用场景</td> 
   <td>查询较多</td> 
   <td>增删较多</td> 
  </tr> 
 </tbody> 
</table>

[789454a278764b90a2cd85768b069a4c.png_pic_center]: https://img-blog.csdnimg.cn/789454a278764b90a2cd85768b069a4c.png#pic_center
[a1e3ac538bf844b7b1cc4b92ebb4562a.png_pic_center]: https://img-blog.csdnimg.cn/a1e3ac538bf844b7b1cc4b92ebb4562a.png#pic_center
[432fd3d06df84338986f87c9fd268f0d.png_pic_center]: https://img-blog.csdnimg.cn/432fd3d06df84338986f87c9fd268f0d.png#pic_center
[7e045625360e4685ab07f6ff2e459c67.png_pic_center]: https://img-blog.csdnimg.cn/7e045625360e4685ab07f6ff2e459c67.png#pic_center
[e21b5557f7ff49c69cc825004fb21de6.png_pic_center]: https://img-blog.csdnimg.cn/e21b5557f7ff49c69cc825004fb21de6.png#pic_center
[213052162538442986f1ffe197b1a5c7.png_pic_center]: https://img-blog.csdnimg.cn/213052162538442986f1ffe197b1a5c7.png#pic_center