Java集合 —— LinkedList详解（源码）

在学习LinkedList之前先来了解一下链表

链表

概念

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序通过链表中的指针链接次序实现的

图中的1、2、3、4、5都是结构体，称为结点；结构体包含所存的数据和下一结点的地址。顺序表中的地址是连续的，而链表中的地址是随机分配的

头结点：在单链表的开始结点之前设立一个结点称之为头结点，头结点的数据域中可以不存放任何信息，也可以存放链表长度等附加信息，头结点的指针域指向存储指向第一个结点的指针

头指针：链表中指向第一个结点的指针（无论链表是否为空，头结点都不为空）

首元结点：第一个元素所在的结点，如果是带头链表，首元结点就是头结点后的第一个结点

分类

单向链表

单向链表包含两个值，当前结点的值和指向下一个结点的链接

双向链表

双向链表中有三个值，当前结点的值、向后的结点链接、向前的结点链接

不带头

带头

循环

非循环

LinkedList

LinkedList底层是双向链表的存储结构，在LinkedList内部有size、first、last属性，以及一个内部类Node，在Node中又维护了item、next、prev

transient int size = 0;

/**

* Pointer to first node.

* Invariant: (first == null && last == null) ||

* (first.prev == null && first.item != null)

*/

transient Node first;

/**

* Pointer to last node.

* Invariant: (first == null && last == null) ||

* (last.next == null && last.item != null)

*/

transient Node last;

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

private static class Node {

E item;

Node next;

Node prev;

Node(Node prev, E element, Node next) {

this.item = element;

this.next = next;

this.prev = prev;

}

}

LinkedList 继承了 AbstractSequentialList 类

LinkedList 实现了 Queue 接口，可作为队列使用

LinkedList 实现了 List 接口，可进行列表的相关操作

LinkedList 实现了 Deque 接口，可作为队列使用

LinkedList 实现了 Cloneable 接口，可实现克隆

LinkedList 实现了 java.io.Serializable 接口，即可支持序列化，能通过序列化去传输

public class LinkedList

extends AbstractSequentialList

implements List, Deque, Cloneable, java.io.Serializable

添加

尾插法

相当于public void addLast(E e)

头插法

在指定位置插入