Java集合：关于LinkedList类

怼烎@ 2024-03-31 12:24 90阅读 0赞

#### 文章目录 ####

*  一、LinkedList概念
 *  二、LinkedList常用方法
 *   *  2.1作为List集合
     *  2.2作为队列
     *  2.3作为栈
     *  2.4代码演示
 *  三、LinkedList源码分析

## 一、LinkedList概念 ##

LinkedList实现类：是一个List集合， 底层数据结构是**链表**，在内存中可能并不是一个连续的地址，而是在每个节点里存放下一个节点的地址。

LinkedList是基于双向链表实现的，除了可以当作链表操作外，它还可以当作栈、队列和双端队列来使用。

LinkedList同样是非线程安全的，只在单线程下适合使用。

*  LinkedList 继承了 AbstractSequentialList 类。
 *  LinkedList 实现了 Queue 接口，可作为队列使用。
 *  LinkedList 实现了 List 接口，可进行列表的相关操作。
 *  LinkedList 实现了 Deque 接口，可作为队列使用。
 *  LinkedList 实现了 Cloneable 接口，可实现克隆。
 *  LinkedList 实现了 java.io.Serializable 接口，即可支持序列化，能通过序列化去传输。

**特点：**

1.  增删元素效率快。

**缺点：**

1.  遍历数据很慢，每次获取数据都需要从头开始。

**链表分为单向链表、双向链表、循环链表。**

**单向链表：**

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

**双向链表：**

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

**循环表链：** 头节点和尾节点被连接在一起的链表称为循环链表，这种方式在单向和双向链表中皆可实现。循环链表中第一个节点之前就是最后一个节点，反之亦然。  
![在这里插入图片描述][adc8cca958504f46afe72de82f4ffca7.png_pic_center]

LinkedList 类位于 java.util 包中，使用前需要引入它，**语法格式如下：**

// 引入 LinkedList 类
    import java.util.LinkedList; 
    
    LinkedList<E> list = new LinkedList<E>();   // 普通创建方法
    或者
    LinkedList<E> list = new LinkedList(Collection<? extends E> c); // 使用集合创建链表

## 二、LinkedList常用方法 ##

### 2.1作为List集合 ###

<table> 
 <thead> 
  <tr> 
   <th>方法</th> 
   <th>描述</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>public boolean add(E e)</td> 
   <td>链表末尾添加元素，返回是否成功，成功为 true，失败为 false。</td> 
  </tr> 
  <tr> 
   <td>public void add(int index, E element)</td> 
   <td>向指定位置插入元素。</td> 
  </tr> 
  <tr> 
   <td>public boolean addAll(Collection c)</td> 
   <td>将一个集合的所有元素添加到链表后面，返回是否成功，成功为 true，失败为 false。</td> 
  </tr> 
  <tr> 
   <td>public boolean addAll(int index, Collection c)</td> 
   <td>将一个集合的所有元素添加到链表的指定位置后面，返回是否成功，成功为 true，失败为 false。</td> 
  </tr> 
  <tr> 
   <td>public void addFirst(E e)</td> 
   <td>元素添加到头部。</td> 
  </tr> 
  <tr> 
   <td>public void addLast(E e)</td> 
   <td>元素添加到尾部。</td> 
  </tr> 
  <tr> 
   <td>public void clear()</td> 
   <td>清空链表。</td> 
  </tr> 
  <tr> 
   <td>public E removeFirst()</td> 
   <td>删除并返回第一个元素。</td> 
  </tr> 
  <tr> 
   <td>public E removeLast()</td> 
   <td>删除并返回最后一个元素。</td> 
  </tr> 
  <tr> 
   <td>public boolean remove(Object o)</td> 
   <td>删除某一元素，返回是否成功，成功为 true，失败为 false。</td> 
  </tr> 
  <tr> 
   <td>public E remove(int index)</td> 
   <td>删除指定位置的元素。</td> 
  </tr> 
  <tr> 
   <td>public E remove()</td> 
   <td>删除并返回第一个元素。</td> 
  </tr> 
  <tr> 
   <td>public boolean contains(Object o)</td> 
   <td>判断是否含有某一元素。</td> 
  </tr> 
  <tr> 
   <td>public E get(int index)</td> 
   <td>返回指定位置的元素。</td> 
  </tr> 
  <tr> 
   <td>public E getFirst()</td> 
   <td>返回第一个元素。</td> 
  </tr> 
  <tr> 
   <td>public E getLast()</td> 
   <td>返回最后一个元素。</td> 
  </tr> 
  <tr> 
   <td>public int indexOf(Object o)</td> 
   <td>查找指定元素从前往后第一次出现的索引。</td> 
  </tr> 
  <tr> 
   <td>public int lastIndexOf(Object o)</td> 
   <td>查找指定元素最后一次出现的索引。</td> 
  </tr> 
  <tr> 
   <td>public E element()</td> 
   <td>返回第一个元素。</td> 
  </tr> 
  <tr> 
   <td>public Object clone()</td> 
   <td>克隆该列表。</td> 
  </tr> 
  <tr> 
   <td>public int size()</td> 
   <td>返回链表元素个数。</td> 
  </tr> 
  <tr> 
   <td>public Iterator descendingIterator()</td> 
   <td>返回倒序迭代器。</td> 
  </tr> 
  <tr> 
   <td>public ListIterator listIterator(int index)</td> 
   <td>返回从指定位置开始到末尾的迭代器。</td> 
  </tr> 
  <tr> 
   <td>public Object[] toArray()</td> 
   <td>返回一个由链表元素组成的数组。</td> 
  </tr> 
 </tbody> 
</table>

### 2.2作为队列 ###

<table> 
 <thead> 
  <tr> 
   <th>方法</th> 
   <th>描述</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>public boolean offer(E e)</td> 
   <td>向链表末尾添加元素，返回是否成功，成功为 true，失败为 false。</td> 
  </tr> 
  <tr> 
   <td>public boolean offerFirst(E e)</td> 
   <td>头部插入元素，返回是否成功，成功为 true，失败为 false。</td> 
  </tr> 
  <tr> 
   <td>public boolean offerLast(E e)</td> 
   <td>尾部插入元素，返回是否成功，成功为 true，失败为 false。</td> 
  </tr> 
  <tr> 
   <td>public E peek()</td> 
   <td>返回第一个元素。</td> 
  </tr> 
  <tr> 
   <td>public E peekFirst()</td> 
   <td>返回头部元素。</td> 
  </tr> 
  <tr> 
   <td>public E peekLast()</td> 
   <td>返回尾部元素。</td> 
  </tr> 
  <tr> 
   <td>public E poll()</td> 
   <td>删除并返回第一个元素。</td> 
  </tr> 
  <tr> 
   <td>public E pollLast()</td> 
   <td>E pollLast()：</td> 
  </tr> 
 </tbody> 
</table>

### 2.3作为栈 ###

<table> 
 <thead> 
  <tr> 
   <th>方法</th> 
   <th>描述</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>push(E e)</td> 
   <td>将一个元素压入栈顶，也就是向列表头部插入一个元素；</td> 
  </tr> 
  <tr> 
   <td>E pop()：</td> 
   <td>弹出栈顶元素，即移除列表第一个元素。</td> 
  </tr> 
 </tbody> 
</table>

### 2.4代码演示 ###

public class DemoTest {
        
    
        public static void main(String[] args) {
        
            LinkedList<String> list = new LinkedList<String>();
            //添加元素到链表尾部
            list.add("xiaoming");
            //添加元素到链表头部
            list.addFirst("xiaoliang");
            //加元素到链表尾部
            list.addLast("xiaodu");
            System.out.println(list);//[xiaoliang, xiaoming, xiaodu]
            //移除元素头部元素
            list.remove();
            System.out.println(list);//[xiaoming, xiaodu]
            //遍历
            for (int size = list.size(), i = 0; i < size; i++) {
        
                System.out.println(list.get(i));
                /*结果：
                xiaoming
    		   xiaodu		
                */
            }
        }
    }

## 三、LinkedList源码分析 ##

/**
     *用于记录链表的大小
     */
    transient int size = 0;
    /**
     * 链表第一个节点的引用
     */
    transient Node<E> first;
    /**
     * 链表最后一个节点的引用
     */
    transient Node<E> last;
    /**
     * 私有的静态内部类，用于描述双向链表的节点
     */
    private static class Node<E> {
        
        E item; // 节点的值，也就是List中的元素
        Node<E> next; // 直接前驱节点
        Node<E> prev; // 直接后继节点
    
        Node(Node<E> prev, E element, Node<E> next) {
        
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }
    /**
     * 向指定索引处插入元素
     */
     public void add(int index, E element) {
        
         // 检查index是否合法，index >= 0 && index <= size
         checkPositionIndex(index);
         if (index == size)
             linkLast(element); // 追加到链表尾部
         else
             linkBefore(element, node(index)); 
     }
     /**
     * 将元素添加到链表尾部。
     */
    void linkLast(E e) {
        
        final Node<E> l = last; // 记录链表的最后一个节点
        // 创建新节点，设置其前驱节点为l，值为e，后继节点为null
        final Node<E> newNode = new Node<>(l, e, null); 
        last = newNode; // last指向新创建的这个节点
        /*如果l指向的是null（注意，此时l和last指向的已经不是同一个对象了），
          说明newNode既是第一个节点，又是最后一个节点，也就是说newNode是链表中唯一的一个节点*/
        if (l == null) 
            first = newNode;
        else
            l.next = newNode; // l的后继节点设置为newNode
        size++;
        modCount++;
    }
     /**
      * 返回指定索引处的节点
      */
     Node<E> node(int index) {
        
         // assert isElementIndex(index);
    	 // 可以看出这里是通过遍历的方式查找index处的节点。
    	 // 为了减少遍历的节点个数，提高查找效率，这里判断了index是在链表的前半段还是后半段，
    	 // 从而实现从半个链表中查找index处的节点
         if (index < (size >> 1)) {
        
             Node<E> x = first;
             for (int i = 0; i < index; i++)
                 x = x.next;
             return x;
         } else {
        
             Node<E> x = last;
             for (int i = size - 1; i > index; i--)
                 x = x.prev;
             return x;
         }
     }
     /**
      * 将元素包装成链表节点插入到指定节点的前面
      */
     void linkBefore(E e, Node<E> succ) {
        
         // assert succ != null;
         final Node<E> pred = succ.prev; // 记录succ的前驱节点
         final Node<E> newNode = new Node<>(pred, e, succ); // 创建新节点newNode，值为e
         succ.prev = newNode; // 将succ的前驱节点设置为newNode
         if (pred == null) // 此时链表的第一个节点是newNode
             first = newNode;
         else
             pred.next = newNode;
         size++;
         modCount++;
     }
     /**
      * 获取指定索引处的元素
      */
     public E get(int index) {
        
         // 索引合法性检查。index >= 0 && index < size
         checkElementIndex(index);
         return node(index).item; // 通过遍历查找节点并获取元素
     }
     /**
      * 替换列表中指定位置的元素，返回被替换的元素。
      * 核心代码依旧是通过遍历查找节点
      */
     public E set(int index, E element) {
        
         checkElementIndex(index);
         Node<E> x = node(index);
         E oldVal = x.item;
         x.item = element;
         return oldVal;
     }
     /**
      * 移除列表中指定位置的元素
      */
     public E remove(int index) {
        
         checkElementIndex(index);
         // 先遍历查找index处的节点，再调用unlink方法
         return unlink(node(index));
     }
     /**
      * 从链表中删除一个节点
      */
     E unlink(Node<E> x) {
        
         // assert x != null;
         final E element = x.item; // 记录被删除节点的元素
         final Node<E> next = x.next; // 记录被删除节点的后继节点
         final Node<E> prev = x.prev; // 记录被删除节点的前驱节点
    
         if (prev == null) {
         // 被删除节点的前驱节点为null，说明被删除节点是链表的第一个节点
             first = next; // 此时链表的第一个节点是被删除节点的后继节点
         } else {
        
             prev.next = next; 
             x.prev = null; 
         }
    
         if (next == null) {
         // 被删除节点的后继节点为null，说明被删除节点是链表的最后一个节点
             last = prev; // 此时链表的最后一个节点是被删除节点的前驱节点
         } else {
        
             next.prev = prev;
             x.next = null;
         }
    
         x.item = null; // 彻底释放被删除节点
         size--; // 表长减一
         modCount++;
         return element;
     }

[b9b6f89a802344b787ce4875b08c750e.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/630794e8d13e4f1e89a68308a4f76b12.png
[f699df12319f4eba977a4230c3d281b0.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/4e19a07f351d43f1824d6f138dd0085a.png
[adc8cca958504f46afe72de82f4ffca7.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/6b7e201189dd43b29eb9aa4b540daaa4.png