java中LinkedList与链表

曾经终败给现在 2023-10-05 23:41 95阅读 0赞

#### LinkedList与链表 ####

#### 1.ArrayList当中的缺陷 ####

> ArrayList由于其底层是一段连续空间，当**在ArrayList任意位置插入或者删除元素时，就需要将后序元素整体往前或者往后搬移，时间复杂度为O(n)**，效率比较低，因此**ArrayList不适合做任意位置插入和删除比较多的场景**。因此：java  
> 集合中又引入了LinkedList，即链表结构。

#### 2.链表结构 ####

##### 2.1链表的概念及结构 #####

> 链表是一种**物理存储结构上非连续**存储结构，数据元素的**逻辑顺序**是通过链表当中的**引用链接**次序实现的。

![在这里插入图片描述][679a917c3103409db900373cce763d16.png]

> **注意**  
> **1.从上图可看出，链式结构在逻辑上是连续的，但在物理上是不连续的**  
> **2.现实中的结点一般都是从堆上申请出来的**  
> **3，从堆上申请空间，是按一定策略来分配的，两次申请的空间可能是连续，也可能不连续**

实际中的链表的结构非常多样，以下情况组合起来就有8种链表结构。  
**1.单向或者双向**  
![在这里插入图片描述][34e7da4135dd4ffc821426d1d435339e.png]  
**2.带头或者不带头**  
![在这里插入图片描述][5424028a2cc54d648e342d5981bd5a83.png]  
**3.循环或者不循环**  
![在这里插入图片描述][32c1932bbd164219b824d3bfe82b3c1b.png]

#### 3.LinkedList的使用 ####

##### 3.1什么是LinkedList #####

> LinkedList的底层是双向链表结构，由于链表没有将元素存储在连续的空间中，元素存储在单独的节点中，然后通过引用将节点连接起来了，因此在在任意位置插入或者删除元素时，不需要搬移元素，效率比较高。

![在这里插入图片描述][a8a2e85992ec4dac9660de601c7d7f07.png]

> 在集合框架中，LinkedList也实现了List接口，具体如下：

![在这里插入图片描述][fa18d86e721d4fd6bfd488e728297210.png]

> **【说明】**
> 
> 1.  LinkedList实现了List接口
> 2.  LinkedList的底层使用了双向链表
> 3.  LinkedList没有实现RandomAccess接口，因此LinkedList不支持随机访问
> 4.  LinkedList的任意位置插入和删除元素时效率比较高，时间复杂度为O(1)

##### 3.2LinkedList的使用 #####

1.  LinkedList的构造

<table> 
 <thead> 
  <tr> 
   <th>方法</th> 
   <th>解释</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>LinkedList()</td> 
   <td>无参构造</td> 
  </tr> 
  <tr> 
   <td>public LinkedList(Collection&lt;? extends E&gt; c)</td> 
   <td>使用其他集合容器中元素构造List</td> 
  </tr> 
 </tbody> 
</table>

1.  LinkedList的其他常用方法介绍

<table> 
 <thead> 
  <tr> 
   <th>方法</th> 
   <th>解释</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>boolean add(E e)</td> 
   <td>尾插 e</td> 
  </tr> 
  <tr> 
   <td>void add(int index, E element)</td> 
   <td>将 e 插入到 index 位置</td> 
  </tr> 
  <tr> 
   <td>boolean addAll(Collection&lt;? extends E&gt; c)</td> 
   <td>尾插 c 中的元素</td> 
  </tr> 
  <tr> 
   <td>E remove(int index)</td> 
   <td>删除 index 位置元素</td> 
  </tr> 
  <tr> 
   <td>boolean remove(Object o)</td> 
   <td>删除遇到的第一个 o</td> 
  </tr> 
  <tr> 
   <td>E get(int index)</td> 
   <td>获取下标 index 位置元素</td> 
  </tr> 
  <tr> 
   <td>E set(int index, E element)</td> 
   <td>将下标 index 位置元素设置为 element</td> 
  </tr> 
  <tr> 
   <td>void clear()</td> 
   <td>清空</td> 
  </tr> 
  <tr> 
   <td>boolean contains(Object o)</td> 
   <td>判断 o 是否在线性表中</td> 
  </tr> 
  <tr> 
   <td>int indexOf(Object o)</td> 
   <td>返回第一个 o 所在下标</td> 
  </tr> 
  <tr> 
   <td>int lastIndexOf(Object o)</td> 
   <td>返回最后一个 o 的下标</td> 
  </tr> 
  <tr> 
   <td>List subList(int fromIndex, int toIndex)</td> 
   <td>截取部分 list</td> 
  </tr> 
 </tbody> 
</table>

1.  LinkedList的遍历

public static void main(String[] args) {
        
            LinkedList<Integer> list = new LinkedList<>();
            list.add(1);
            // add(elem): 表示尾插 
            list.add(2);
            list.add(3);
            list.add(4);
            list.add(5);
            list.add(6);
            list.add(7);
            System.out.println(list.size());
            // foreach遍历 
            for (int e : list) {
        
                System.out.print(e + " ");
            }
            System.out.println();
            // 使用迭代器遍历---正向遍历 
            ListIterator<Integer> it = list.listIterator();
            while (it.hasNext()) {
        
                System.out.print(it.next() + " ");
            }
            System.out.println(); 
            // 使用反向迭代器---反向遍历 
            ListIterator<Integer> rit = list.listIterator(list.size());
            while (rit.hasPrevious()) {
        
                System.out.print(rit.previous() + " ");
            }
            System.out.println();

#### 4.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>支持O(1)</td> 
   <td>不支持：O(N)</td> 
  </tr> 
  <tr> 
   <td>头插</td> 
   <td>需要搬移元素，效率低O(N)</td> 
   <td>只需修改引用的指向，时间复杂度为O(1）</td> 
  </tr> 
  <tr> 
   <td>插入</td> 
   <td>空间不够时需要扩容</td> 
   <td>没有容量的概念</td> 
  </tr> 
  <tr> 
   <td>应用场景</td> 
   <td>元素高效存储+频繁访问</td> 
   <td>任意位置插入和删除频繁</td> 
  </tr> 
 </tbody> 
</table>

[679a917c3103409db900373cce763d16.png]: https://img-blog.csdnimg.cn/679a917c3103409db900373cce763d16.png
[34e7da4135dd4ffc821426d1d435339e.png]: https://img-blog.csdnimg.cn/34e7da4135dd4ffc821426d1d435339e.png
[5424028a2cc54d648e342d5981bd5a83.png]: https://img-blog.csdnimg.cn/5424028a2cc54d648e342d5981bd5a83.png
[32c1932bbd164219b824d3bfe82b3c1b.png]: https://img-blog.csdnimg.cn/32c1932bbd164219b824d3bfe82b3c1b.png
[a8a2e85992ec4dac9660de601c7d7f07.png]: https://img-blog.csdnimg.cn/a8a2e85992ec4dac9660de601c7d7f07.png
[fa18d86e721d4fd6bfd488e728297210.png]: https://img-blog.csdnimg.cn/fa18d86e721d4fd6bfd488e728297210.png