在学习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<E> first;
/**
* Pointer to last node.
* Invariant: (first == null && last == null) ||
* (last.next == null && last.item != null)
*/
transient Node<E> last;
---------------------------------------------------------------------------------
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;
}
}
-
LinkedList 继承了 AbstractSequentialList 类
-
LinkedList 实现了 Queue 接口，可作为队列使用
-
LinkedList 实现了 List 接口，可进行列表的相关操作
-
LinkedList 实现了 Deque 接口，可作为队列使用
-
LinkedList 实现了 Cloneable 接口，可实现克隆
-
LinkedList 实现了 java.io.Serializable 接口，即可支持序列化，能通过序列化去传输
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
添加
尾插法
相当于
public void addLast(E e)
头插法
在指定位置插入
