Java LinkedList类详解

怼烎@ 2023-10-16 12:33 1阅读 0赞

**目录**

什么是LinkedList

LinkedList的使用

LinkedList的构造

LinkedList的其他常用方法的介绍

LinkedList的遍历

ArrayList和LinkedList的区别

--------------------

## 什么是LinkedList ##

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

![8e2c49ce2e1841fbb411bd1e07765f93.png][]

在集合框架中，LinkedList也实现了List接口。

说明：

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

## LinkedList的使用 ##

### LinkedList的构造 ###

<table style="width:700px;"> 
 <tbody> 
  <tr> 
   <td>方法</td> 
   <td>解释</td> 
  </tr> 
  <tr> 
   <td>LinkedList()</td> 
   <td>无参构造</td> 
  </tr> 
  <tr> 
   <td>public LinkedList(Collection&lt;? extends E&gt; c)</td> 
   <td> <p>使用其它集合容器中元素构造List</p> </td> 
  </tr> 
 </tbody> 
</table>

举个例子：

import java.util.ArrayList;
    import java.util.LinkedList;
    import java.util.List;
    
    public class Test {
        public static void main(String[] args) {
            //构造一个空的LinkedList
            List<Integer> list1 = new LinkedList<>();
            
            //构建一个ArrayList数组，并添加元素
            List<String> list2 = new ArrayList<>();
            list2.add("JavaSE");
            list2.add("JavaWeb");
            list2.add("JavaEE");
            //使用ArrayList构造LinkedList
            List<String> list3 = new LinkedList<>(list2);
        }
    }

### LinkedList的其他常用方法的介绍 ###

<table style="width:700px;"> 
 <tbody> 
  <tr> 
   <td>方法</td> 
   <td>解释</td> 
  </tr> 
  <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&lt;E&gt; subList(int fromIndex, int toIndex)</td> 
   <td>截取部分list</td> 
  </tr> 
 </tbody> 
</table>

import java.util.LinkedList;
    import java.util.List;
    
    public class Test {
        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());//7
            System.out.println(list);//1 2 3 4 5 6 7
    
            //在起始位置插入零
            list.add(0, 0);//add(elem):在index位置插入elem
            System.out.println(list);//0 1 2 3 4 5 6 7
    
            list.remove();//remove():删除第一个元素，内部调用的是removeFirst()
            list.removeFirst();//removeFirst():删除第一个元素
            list.removeLast();//removeLast():删除最后一个元素
            list.remove(1);//remove(index):删除index位置的元素
            System.out.println(list);//2 4 5 6
    
            
            //contains(elem):检测elem元素是否存在，如果存在返回true,否则返回false
            if(!list.contains(1)) {
                list.add(0, 1);
            }
            list.add(1);
            System.out.println(list);//1 2 4 5 6 1
            System.out.println(list.indexOf(1));//indexOf(elem):从前往后找到第一个elem的位置
            //0
            System.out.println(list.lastIndexOf(1));//lastIndexOf(elem):从后向前找第一个1的位置
            //5
            int elem = list.get(0);
            list.set(0, 100);//将index位置的元素设置为elem
            System.out.println(list);//100 2 4 5 6 1
            //subList(from, to):用list中的(from, to)之间的元素构造一个新的LinkedList返回
            List<Integer> copy = list.subList(0,3);
            System.out.println(list);
            System.out.println(copy);//100 2 4:注意java中是左闭右开的，所以不包含序号为三的结点
            list.clear();//将list中的元素清空
            System.out.println(list.size());//0
        }
    }

### LinkedList的遍历 ###

import java.util.LinkedList;
    import java.util.ListIterator;
    
    public class Test {
        public static void main(String[] args) {
            LinkedList<Integer> list = new LinkedList<>();
            list.add(1);
            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();
        }
    }

补充：迭代器的是使用

import java.util.ArrayList;
    import java.util.Iterator;
    import java.util.List;
    
    public class IteratorTest {
        public static void main(String[] args) {
            List<String> list = new ArrayList<>();
            //添加元素到集合中
            Iterator<String> iterator = list.listIterator();
    
            while(iterator.hasNext()) {
                String element = iterator.next();
                //处理元素
            }
            iterator.remove();
        }
    }

> 使用流程
> 
> **1.获取集合的迭代器对象：通过调用集合的iterator方法获取迭代器对象。例如，对于ArrayList集合，可以使用iterator()方法获取迭代器对象。**
> 
> **2.遍历集合元素：通过使用迭代器的hasNext()和next()方法来遍历集合中的元素。hasNext()方法用于检查是否还有下一个元素，next()方法用于获取下一个元素的值。**

## ArrayList和LinkedList的区别 ##

<table> 
 <tbody> 
  <tr> 
   <td>不同点</td> 
   <td>ArrayList</td> 
   <td>LinkedList</td> 
  </tr> 
  <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>

[8e2c49ce2e1841fbb411bd1e07765f93.png]: https://img-blog.csdnimg.cn/8e2c49ce2e1841fbb411bd1e07765f93.png