Java集合-LinkedList源码分析

2022-10-31 15:52:31

1.数据结构-链表
2.ArrayList结构特性
3.构造方法
4.成员变量
5.常用的成员方法
6.Node节点
7.序列化原理
8.迭代器
9.总结

1.数据结构-链表

链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。

使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。

链表的类型：

单向链表：单向链表包含两个域，一个信息域和一个指针域。这个链接指向列表中的下一个节点，而最后一个节点则指向一个空值。
双向链表：双向链表每个节点有两个连接：一个指向前一个节点，（当此“连接”为第一个“连接”时，指向空值或者空列表）；而另一个指向下一个节点，（当此“连接”为最后一个“连接”时，指向空值或者空列表）
循环链表：在一个循环链表中, 首节点和末节点被连接在一起。

2.ArrayList结构特性

LinkedList 与 ArrayList 一样实现 List 接口，只是 ArrayList 是 List 接口的大小可变数组的实现，LinkedList 是 List 接口链表的实现。有以下特性：

允许包含重复的元素
允许包含null元素
保存了元素添加的顺序
不是线程安全的

3.构造方法

// 1.构造一个空列表

LinkedList()

// 2.构造一个包含指定集合元素的列表

LinkedList(Collection<? extends E> c)

4.成员变量

// 1.链表中的元素数

transient int size

// 2.指向第一个元素的指针

transient Node<E> first

// 3.指向最后一个元素的指针

transient Node<E> last

5.常用的成员方法

// 1.添加一个元素到列表的尾部

boolean add(E e)

// 2.添加一个元素到列表的指定位置

void add(int index, E element)

// 3.将指定集合中的所有元素追加到此列表的末尾。

boolean addAll(Collection<? extends E> c)

// 4.添加一个元素到列表的头部

void addFirst(E e)

// 5.添加一个元素到列表的尾部

addLast(E e)

// 6.检查列表中包含指定的元素

boolean contains(Object o)

// 7.返回列表的第一个元素

E element()

// 8.返回列表指定位置的元素

E get(int index)

// 9.返回指定元素在列表中首次出现的索引

int indexOf(Object o)

// 10.返回指定元素在列表中最后一次出现的索引

int lastIndexOf(Object o)

// 11.添加一个元素到列表的尾部

boolean offer(E e)

// 12.返回列表的第一个元素

E peek()

// 13.删除并返回此列表的第一个元素

E poll()

// 14.删除并返回此列表的第一个元素

E pop()

// 15.添加一个元素到列表的头部

void push(E e)

// 16.移除列表的第一个元素

E remove()

// 17.设置指定位置的元素

E set(int index, E element)

// 18.返回列表中的元素数

int size()

// 19.返回一个数组，包含列表中所有元素

Object[] toArray()

6.Node节点

// 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;

      }

  }

7.序列化原理

1.LinkedList 实现了Serializable接口，支持对象序列化

public class LinkedList<E>

    extends AbstractSequentialList<E>

    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

{

      ......

}

2.序列化时调用 writeObject 方法，将 size 和 node 节点列表写入 ObjectOutputStream。

private void writeObject(java.io.ObjectOutputStream s)

        throws java.io.IOException {

    // Write out any hidden serialization magic

    s.defaultWriteObject();

    // 序列化 size

    s.writeInt(size);

    // 从第一个元素开始，将链表中所有的元素序列化

    for (Node<E> x = first; x != null; x = x.next)

        s.writeObject(x.item);

}

3.反序列化时调用 readObject 方法，恢复 size 和 node 节点列表。

private void readObject(java.io.ObjectInputStream s)

        throws java.io.IOException, ClassNotFoundException {

    // Read in any hidden serialization magic

    s.defaultReadObject();

    // 恢复size

    int size = s.readInt();

    // 恢复链表

    for (int i = 0; i < size; i++)

        linkLast((E)s.readObject());

}

4.成员变量 size、first 和 last 使用 transient 关键字修饰，不会序列化到目的地中，从而节省时间和空间。

8.迭代器

1.由LinedList内部类ListItr实现ListIterator 接口，间接实现Iterator 接口。

public ListIterator<E> listIterator(int index) {

    checkPositionIndex(index);

    return new ListItr(index);

}

private class ListItr implements ListIterator<E> {

    // 最近返回的节点引用

    private Node<E> lastReturned;

    // 下一个节点的引用

    private Node<E> next;

    // 下一个节点的位置索引

    private int nextIndex;

    private int expectedModCount = modCount;

    ......

}

2.ListItr实现迭代器的成员方法

// 检查指针索引指向链表的边界

public boolean hasNext() {

      return nextIndex < size;

}

// 返回next 指向的节点，同时next偏移下一个节点

public E next() {

      ......

}

// 移除最近返回的节点（lastReturned引用）

public void remove() {

      ......

}

9.总结

以上就是对LinkedList的理解，如果有不正确的地方，欢迎指正，最后，补一张脑图：

码农公寓