LinkedList源码解析
底层数据结构
LinkedList底层通过双向链表实现，双向链表的每个节点用内部类Node表示。LinkedList通过first和last引用分别指向链表的第一个和最后一个元素，当链表为空的时候first和last都指向null。
内部结构分析：
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;
}
}
实现接口:
List接口和Deque接口
LinkedList底层的链表结构使它支持高效的插入和删除操作，另外它实现了Deque接口，使得LinkedList类也具有队列的特性; LinkedList是线程不安全的，如果想使LinkedList变成线程安全的，可以调用静态类Collections类中的synchronizedList方法：
List list=Collections.synchronizedList(new LinkedList(...));
Cloneable标记接口
Cloneable:是一个标记接口,按照约定，实现Cloneable的类应当重写Object.clone()方法,但是此接口不包含clone方法，在不实现Cloneable接口的对象上调用Object的clone方法会抛CloneNotSupportedException异常。
Serializable序列化接口
说明此类可以序列化，网络传输需要序列化，只要实现了Serilizable接口，这个对象就可以被序列化，java的这种序列化模式为开发者提供了很多便利，我们可以不必关系具体序列化的过程，这个类的所有属性和方法都会自动序列化
成员属性：
//元素个数
transient int size = 0;
//指向第一个节点的指针
transient Node<E> first;
//指向最后一个节点的指针
transient Node<E> last;
//序列化版本号
private static final long serialVersionUID = 876323262645176354L;
构造函数：
/**
* 构造一个空列表。
*/
//无参构造函数构造空链表
public LinkedList() {
}
/**
*传入一个集合构造一个包含指定集合元素的列表。
* @param c 其元素将被放入此列表的集合
* @throws NullPointerException 如果指定的集合为 null抛出空指针异常
*/
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
方法函数：
getFirst()
返回此列表中的第一个元素
/**
返回此列表中的第一个元素
。 @return 此列表中的第一个元素
@throws NoSuchElementException 如果此列表为空抛出空指针异常
*/
public E getFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
}
getLast
*返回此列表中的最后一个元素。
/**
返回此列表中的最后一个元素。
@return 此列表中的最后一个元素
@throws NoSuchElementException 如果此列表为空
*/
public E getLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return l.item;
}
removeFirst()和unlinkFirst(Node f)
移除并返回此列表中的第一个元素
/**
* 移除并返回此列表中的第一个元素。
* @return 此列表中的第一个元素
* @throws NoSuchElementException 如果此列表为空
*/
public E removeFirst() {
//引用f指向first结点
final Node<E> f = first;
//如果f为空抛出异常
if (f == null)
throw new NoSuchElementException();
//不为空调用unlinkFirst方法
return unlinkFirst(f);
}
/**
*删除第一个节点 f。
*/
private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
//保存第一个结点值
final E element = f.item;
//创建指向时首节点的下一个结点的指针next
final Node<E> next = f.next;
//头结点初始化，值设为空，后继指针设为空
f.item = null;
f.next = null; // help GC
//头指针后移
first = next;
//如果next指针为空，说明移除结点后 链表变为空链表
if (next == null)
//空链表 first last都为空
last = null;
else
//不为空则将头结点的前驱结点设空
next.prev = null;
//元素个数-1
size--;
//改动次数+1
modCount++;
//返回删除结点值
return element;
}
removeLast()和unlinkLast(Node l)
返回此列表中的最后一个元素。
/**
从此列表中删除并返回最后一个元素。
@return 此列表中的最后一个元素
@throws NoSuchElementException 如果此列表为空
*/
public E removeLast() {
//引用l指向last结点
final Node<E> l = last;
//如果l为空抛出异常
if (l == null)
throw new NoSuchElementException();
//不为空调用unlinkLast方法
return unlinkLast(l);
}
/**
* 删除的最后一个节点 l。
*/
private E unlinkLast(Node<E> l) {
// assert l == last && l != null;
//保存结点值
final E element = l.item;
//创建引用prev指向尾结点的前驱结点
final Node<E> prev = l.prev;
//初始化清空尾结点
l.item = null;
l.prev = null; // help GC
//尾结点前移
last = prev;
// //如果prev指针为空，说明移除结点后 链表变为空链表
if (prev == null)
//空链表 first last都为空
first = null;
else
//不为空则将prev的后继结点设空
prev.next = null;
//元素个数-1
size--;
//改动次数+1
modCount++;
//返回删除结点值
return element;
}
add(E e)和linkLast(E e)
将指定的元素附加到此列表的末尾。 这个方法相当于 addLast()
/**
将指定的元素附加到此列表的末尾。 这个方法相当于 addLast()
@param e 要附加到此列表的元素
@return {@code true} （由 {@link Collectionadd} 指定）
*/
public boolean add(E e) {
linkLast(e);
return true;
}
/**
* 链接 e 作为最后一个元素。
*/
void linkLast(E e) {
//创建引用常量l指向尾结点
final Node<E> l = last;
//用有参构造创建新节点，前驱指针指向尾结点，结点值由e赋值
final Node<E> newNode = new Node<>(l, e, null);
//尾指针指向新结点
last = newNode;
//如果链表为空
if (l == null)
//头指针指向新结点
first = newNode;
else
//不为空则将原来的尾结点指向新节点
l.next = newNode;
//元素个数+1
size++;
//改动次数+1
modCount++;
}
addAll(Collection<? extends E> c)
将指定集合中的所有元素追加到此列表的末尾
/**
将指定集合中的所有元素追加到此列表的末尾。
@param c 包含要添加到这个列表的元素的集合
@throws 如果指定的集合为 null，则为 NullPointerException
*
*/
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
addAll(int index, Collection<? extends E> c)
将指定集合中的所有元素插入到指定下标
/**
从指定位置开始，将指定集合中的所有元素插入此列表。将当前在该位置的元素（如果有）和任何后续元素向右移动（增加它们的索引）。
@param 索引索引，在该索引处插入指定集合中的第一个元素
@param c 包含要添加到此列表的元素的集合如果指定的集合为 null，
则 @throws NullPointerException
*/
public boolean addAll(int index, Collection<? extends E> c) {
//检查下标是否越界
checkPositionIndex(index);
//将集合转化为Object[]数组
Object[] a = c.toArray();
//记录a的长度
int numNew = a.length;
//如果参数a数组长度为0 返回false
if (numNew == 0)
return false;
//创建结点指针pred指向要插入位置的前一个结点, succ表示要插入位置的那个结点
Node<E> pred, succ;
//如果要插入的位置为最后一个
if (index == size) {
succ = null;
pred = last;
} else {
//不为最后一个先找到对应index的结点赋值给succ
succ = node(index);
//要传入位置的前一个结点地址赋给pred
pred = succ.prev;
}
//遍历a数组
for (Object o : a) {
//强转类型
@SuppressWarnings("unchecked") E e = (E) o;
//创建新结点前驱指针指向pred，结点值赋值
Node<E> newNode = new Node<>(pred, e, null);
//如果pred等于空相当于链表为空，头指针指向新结点
if (pred == null)
first = newNode;
else
//否则pred的next指向新结点
pred.next = newNode;
//pred指针后移
pred = newNode;
}
//在末尾插入时，succ为空，为空则尾指针指向pred
if (succ == null) {
last = pred;
} else {
//否则将插入的新链表的尾部双向连接被插入的位置的结点
pred.next = succ;
succ.prev = pred;
}
//元素个数=原个数+传入集合的长度
size += numNew;
//改动次数+1
modCount++;
//返回true
return true;
}
addLast()
将指定的元素附加到此列表的末尾
/**
将指定的元素附加到此列表的末尾。 <p>这个方法相当于{@link add}。
@param e 要添加的元素
*/
public void addLast(E e) {
linkLast(e);
}
/**
* 链接 e 作为最后一个元素。
*/
void linkLast(E e) {
//创建引用常量l指向尾结点
final Node<E> l = last;
//用有参构造创建新节点，前驱指针指向尾结点，结点值由e赋值
final Node<E> newNode = new Node<>(l, e, null);
//尾指针指向新结点
last = newNode;
//如果链表为空
if (l == null)
//头指针指向新结点
first = newNode;
else
//不为空则将原来的尾结点指向新节点
l.next = newNode;
//元素个数+1
size++;
//改动次数+1
modCount++;
}
addFirst()和linkFirst(E e)
将指定的元素附加到此列表的开头
/**
* 在此列表的开头插入指定的元素。
*
* @param e the element to add
*/
public void addFirst(E e) {
linkFirst(e);
}
/**
* 链接 e 作为第一个元素。
*/
private void linkFirst(E e) {
//创建常量f指向头指针
final Node<E> f = first;
//创建新结点，e赋值给结点值，next指针指向头指针
final Node<E> newNode = new Node<>(null, e, f);
//头指针指向新结点
first = newNode;
//如果链表为空，则f为空
if (f == null)
//尾结点盒指向新结点
last = newNode;
else
//f(相当于原来的头结点)的前驱指针指向新结点
f.prev = newNode;
//元素个数+1
size++;
//改动次数+1
modCount++;
}
contains(Object o)和indexOf(Object o)
查找列表中是否包含元素o，如果此列表包含指定的元素返回true
/**
如果此列表包含指定的元素，则返回 {@code true}。
@param o 要测试此列表中是否存在的元素
@return {@code true} 如果此列表包含指定的元素
*/
public boolean contains(Object o) {
return indexOf(o) != -1;
}
/**
返回此列表中指定元素第一次出现的索引，如果此列表不包含该元素，则返回 -1。
@param o 要搜索的元素
@return 此列表中第一次出现指定元素的索引，如果此列表不包含该元素，则为 -1
*/
public int indexOf(Object o) {
int index = 0;
//如果o等于空遍历链表
if (o == null) {
//创建引用x指向头结点,循环条件为x不为空，每一次循环后x后移
for (Node<E> x = first; x != null; x = x.next) {
//如果结点值为空返回下标
if (x.item == null)
return index;
//下标++
index++;
}
} else {
//创建引用x指向头结点,循环条件为x不为空，每一次循环后x后移
for (Node<E> x = first; x != null; x = x.next) {
//如果结点与o相等，返回下标
if (o.equals(x.item))
return index;
//下标++
index++;
}
}
//没找到返回-1
return -1;
}
get(int index)
返回此列表中指定位置的元素。
/**
返回此列表中指定位置的元素。
@param index 要返回的元素索引
@return 此列表中指定位置的元素
@throws IndexOutOfBoundsException {@inheritDoc}
*/
public E get(int index) {
//检查下标是否越界
checkElementIndex(index);
//返回对应位置的结点值
return node(index).item;
}
Node<E> node(int index) {
// assert isElementIndex(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;
}
}
set(int index, E element)
*返回此列表中的最后一个元素。
/**
用指定的元素替换此列表中指定位置的元素。
@param index 要替换的元素的索引
@param element 要存储在指定位置的元素
@return 之前在指定位置的元素
@throws IndexOutOfBoundsException {@inheritDoc}
*/
public E set(int index, E element) {
//检查下标是否越界
checkElementIndex(index);
//找到对应下标的结点赋值给x
Node<E> x = node(index);
//保存原结点的值
E oldVal = x.item;
//新值替换旧值
x.item = element;
//返回旧值
return oldVal;
}
Node<E> node(int index) {
// assert isElementIndex(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;
}
}
总结：
1. LinkedList
- LinkedList底层的链表结构使它支持高效的插入和删除操作，
- 实现了Deque接口（双端队列），使得LinkedList类也具有队列的特性
- 线程不安全，性能高
- 可作为队列，栈使用
2. 与 ArrayList 的比较
ArrayList 基于动态数组实现。ArrayList 和 LinkedList 的区别可以归结为数组和链表的区别：
- 数组支持随机访问，但插入删除的代价很高，需要移动大量元素；
- 链表不支持随机访问，但插入删除只需要改变指针。