本文共 1635 字，大约阅读时间需要 5 分钟。

LinkedList讲解与源码分析

1.学习LinkedList的必要性

Arraylist和LinkedList都是Java中List接口的实现，而ArrayList作为动态数组的实现，在插入和删除操作上存在性能短板。为了更高效地实现队列操作，我们来深入研究LinkedList。

2.LinkedList简介

2.1 LinkedList定义

LinkedList是List接口的链表实现，是一个双向链表，继承于AbstractSequentialList类。同时，它还实现了Deque接口，提供先进先出的队列操作。LinkedList和ArrayList一样，不是线程安全的。

2.2 LinkedList的数据结构

java.lang.Object    ↳ java.util.AbstractCollection        ↳ java.util.AbstractList            ↳ java.util.AbstractSequentialList                ↳ java.util.LinkedList

LinkedList的核心成员包括：

• header：表示链表的表头，包含两个指针：previous和next，分别指向上一个节点和下一个节点。
• size：表示链表中节点的总数。

3.AbstractSequentialList介绍

AbstractSequentialList是一个抽象类，用于提供List接口的基本实现，主要支持随机访问操作。LinkedList作为其子类，继承了这些接口，如get(int index)、set(int index,E element)、add(int index,E element)和remove(int index)等。

4.LinkedList源码解析

4.1 LinkedList的实现原理

• LinkedList采用双向链表结构，实现了一系列插入、删除、 random-access等操作。
• 其内部使用一个特殊的内部类Entry存储节点信息，通过头尾指针实现快速的插入和删除。

4.2 内部类Entry

private static class Entry {    E element;    Entry next;    Entry previous;}Entry类中的三个成员：- element：当前节点存储的值。- next、previous：分别指向下一个和上一个节点。

4.3源码关键部分

• 构造函数：

  • 默认构造：初始化一个空链表。
  • 构造函数：初始化链表的表头节点，并设置其next和previous指针。

• 元素操作：

  • add(E e)：默认插入节点到链表的指定位置。
  • remove(Object o)：从链表中删除指定的节点或元素。
  • get(int index)：随机访问链表中的指定位置节点。
  • set(int index, E element)：修改链表中指定位置的节点值。

• 高级操作：

  • addFirst、addLast：将元素添加到链表开头或结尾。
  • removeFirst、removeLast：从链表头或尾部删除元素。
  • poll：执行fail-fast机制，确保多线程环境下操作的 thread-safety。

5.Important Methods（重要方法）

• addFirst和addLast：向链表头或尾部添加节点，提供类似栈和队列的操作。
• removeFirst和removeLast：从链表头或尾部删除节点，支持队列操作。
• peek和poll：实现类似集合的查看操作。
• toContain：判断链表中是否包含指定元素。

6.总结

• 优点：
  • LinkedList的随机访问效率较低，但插入和删除操作效率很高。
  • 可以灵活使用作为栈、队列或双端队列。
• 应用场景：
  • 需要频繁插入和删除元素，但不需要随机访问。
  • 如IDEA的任务栏、聊天记录等场景。

转载地址：http://ukwfk.baihongyu.com/