LinkedList
是Java Collections Framework
中List
接口一种实现。LinkedList
是有序并且可以元素重复的集合,底层是基于双向链表的。因为是链表,所以也就没有动态扩容的步骤了。类结构
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
AbstractSequentialList
AbstractSequentialList
类是AbstractList
子类,同时也提供了一个基本的list
接口的实现,为顺序访问的数据存储结构(链表)提供了最小化的实现。而对于随机访问的数据存储结构(数组)要优先考虑使用AbstractList
。AbstractSequentiaList
是在迭代器基础上实现的get
、set
、add
等方法。Deque / Queue 接口
Deque
接口继承Queue
接口,两端都允许插入和删除元素,即双向队列。
List接口
实现了list接口,实现了get(int location)、remove(int location)
等根据索引值来获取、删除节点的函数。
Cloneable接口
实现了Cloneable
接口,能被克隆。
Serializable接口
实现了Serializable
接口,支持序列化
源码分析
属性
LinkedList 提供了以下三个成员变量。size,first,last。
transient int size = 0;
transient Node<E> first;
transient Node<E> last;
其中 size
为 LinkedList
的大小,first
和last
均是Node
类的实例。first
指向头结点,last
指向的尾节点。
Node 为节点对象。Node 是 LInkedList 的内部类,定义了存储的数据元素,前一个节点和后一个节点,典型的双链表结构。
private static class Node<E> {
E item; //结点的值
Node<E> next; //结点的后向指针
Node<E> prev; //结点的前向指针
//构造方法中已完成Node成员的赋值
Node(Node<E> prev, E element, Node<E> next) {
this.item = element; //结点的值赋值为element
this.next = next; //后向指针赋值
this.prev = prev; //前向指针赋值
}
}
Node
类有3个成员变量:
item
:代表数据元素本身;next
:指向数据的后节点;prev
:指向数据的前节点;
构造函数
//默认构造方法,生成一个空的链表
public LinkedList() {
}
//根据c里面的元素生成一个LinkedList
public LinkedList(Collection<? extends E> c) {
//调用空的构造方法
this();
//将c里面的元素添加到空链表尾部
addAll(c);
}
LinkedList
提供了两个构造方法:LinkedList()
和 LinkedList(Collection<? extends E> c)
。
LinkedList()
仅仅构造一个空的列表,size = 0
,first
和 last
都为 null,
没有任何元素。LinkedList(Collection<? extends E> c)
构造方法构造一个包含指定 Collection
中所有元素的列表,该构造方法首先会调用空的构造方法,然后通过 addAll()
的方式把 Collection
中的所有元素添加进去。
addAll
//将c中的元素都添加到当前链表中
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);//添加到链表尾部
}
//在序号为index处,添加c中所有的元素到当前链表中(后向添加)
public boolean addAll(int index, Collection<? extends E> c) {
checkPositionIndex(index);//判断index是否超出界
Object[] a = c.toArray();//将集合转换为数组
int numNew = a.length;
if (numNew == 0)
return false;
Node<E> pred, succ;
if (index == size) {//如果index为元素个数,即index个结点为尾结点
succ = null;
pred = last;//指向为结点
} else {
succ = node(index); //succ指向第index个结点
pred = succ.prev; //pred指向succ的前向结点
}
//for循环结束后,a里面的元素都添加到当前链表里面,后向添加
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;
//新生成一个结点,结点的前向指针指向pred,后向指针为null
Node<E> newNode = new Node<>(pred, e, null);
if (pred == null)
//如果pred为null,则succ为当前头结点
first = newNode;
else
//pred的后向指针指向新结点
pred.next = newNode;
pred = newNode;//pred移动到新结点
}
if (succ == null) {
last = pred;//succ为null,这表示index为尾结点之后
} else {
//pred表示所有元素添加之后的最后结点,此时pred的后向指针指向之前的记录的结点
pred.next = succ;
succ.prev = pred;//之前记录的结点指向添加元素之后的最后结点
}
size += numNew;//元素个数+num
modCount++;//修改次数+1
return true;
}
add操作
添加元素到链表末尾
public boolean add(E e) {
linkLast(e);//添加到链表尾部
return true;
} //尾部增加结点,结点的值为e
void linkLast(E e) {
final Node<E> l = last; //l指向尾结点
//生成一个新结点,结点的值为e,其前向指针为l,后向指针为null
final Node<E> newNode = new Node<>(l, e, null);
//last指向新生成的结点,l保存着旧的尾结点信息
last = newNode;
if (l == null)
//如果l为null,则表示整个链表目前是空的,则头结点也指向新结点
first = newNode;
else
//l(旧的尾结点)的后向指针指向最新的结点信息
l.next = newNode;
size++;//元素个数+1
modCount++;//修改次数+1
}
add 方法直接调用了 linkLast 方法,而 linkLast 方法是不对外开放的。该方法做了三件事情,新增一个节点,改变其前后引用,将 size 和 modCount 自增 1。其中 modCount 是记录对集合操作的次数。
在指定的位置插入元素
//第index个结点之前添加结点
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
private void checkPositionIndex(int index) {
if (!isPositionIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
//判断index是否是链表中的元素的索引
private boolean isPositionIndex(int index) {
return index >= 0 && index <= size;
}
//非空结点succ之前插入新结点,新结点的值为e
void linkBefore(E e, Node<E> succ) {
// assert succ != null; //外界调用需保证succ不为null,否则程序会抛出空指针异常
final Node<E> pred = succ.prev;//pred指向succ的前向结点
//生成一个新结点,结点的值为e,其前向指针指向pred,后向指针指向succ
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;//succ的前向指针指向newNode
if (pred == null)
//如果pred为null,则表示succ为头结点,此时头结点指向最新生成的结点newNode
first = newNode;
else
//pred的后向指针指向新生成的结点,此时已经完成了结点的插入操作
pred.next = newNode;
size++;//元素个数+1
modCount++;//修改次数+1
}
首先检查下标是否越界,然后判断如果 index == size 则添加到末尾,否则将该元素插入的 index 的位置。其中 node(index) 是获取 index 位置的节点,linkBefore 负责把元素 e 插入到 succ 之前。
//定位链表中的第index个结点
Node<E> node(int index) {
// assert isElementIndex(index);//确保是合法的索引,即0<=index<=size
//index小于size的一半时,从头向后找
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {//index大于size的一半时,从尾向前找
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
可以看出 node() 方法是将 index 与 当前链表的一半做对比,比一半小从头遍历,比一半大从后遍历。对于数据量很大时能省下不少时间。
remove操作
移除指定位置的元素
先检查下标是否越界,然后调用 unlink 释放节点。
//删除第index个结点
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
//删除结点x
E unlink(Node<E> x) {
// assert x != null; //需确保x不为null,否则后续操作会抛出空指针异常
final E element = x.item; //保存x结点的值
final Node<E> next = x.next;//next指向x的后向结点
final Node<E> prev = x.prev;//prev指向x的前向结点
if (prev == null) {
//如果prev为空,则x结点为first结点,此时first结点指向next结点(x的后向结点)
first = next;
} else {
prev.next = next;//x的前向结点的后向指针指向x的后向结点
x.prev = null; //释放x的前向指针
}
if (next == null) {
//如果next结点为空,则x结点为尾部结点,此时last结点指向prev结点(x的前向结点)
last = prev;
} else {
next.prev = prev;//x的后向结点的前向指针指向x的前向结点
x.next = null; //释放x的后向指针
}
x.item = null; //释放x的值节点,此时x节点可以完全被GC回收
size--; //元素个数-1
modCount++; //修改次数+1
return element;
}
移除指定元素
//移除值为o的元素,o可以为null,找到一个删除即返回
public boolean remove(Object o) {
if (o == null) {//元素为null
for (Node<E> x = first; x != null; x = x.next) {//从结点开始遍历
if (x.item == null) {//找到一个结点
unlink(x); //删除元素
return true;
}
}
} else {//元素不为空
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
判断要移除的元素是否为 null,然后在遍历链表,找到该元素第一次出现的位置,移除并返回 true。
其他方法
//移除头结点
public E removeFirst() {
final Node<E> f = first;//获得头结点
if (f == null)//如果链表为空
throw new NoSuchElementException();
return unlinkFirst(f); //摘除头结点
}
//移除尾结点
public E removeLast() {
final Node<E> l = last;//获得尾结点
if (l == null)//如果链表为空
throw new NoSuchElementException();
return unlinkLast(l);//摘除尾结点
}
//添加到头结点,结点的值为e
public void addFirst(E e) {
linkFirst(e);//添加到头部
}
//添加到尾结点
public void addLast(E e) {
linkLast(e);//添加到尾部
}
//返回元素个数
public int size() {
return size;
}//清除链表里面的所有元素
public void clear() {
for (Node<E> x = first; x != null; ) {
Node<E> next = x.next;
x.item = null; //释放值结点,便于GC回收
x.next = null; //释放前向指针
x.prev = null; //释放后向指针
x = next; //后向遍历
}
first = last = null;//释放头尾结点
size = 0;
modCount++;
}//获得第index个结点的值
public E get(int index) {
checkElementIndex(index);
return node(index).item; //点位第index结点,返回值信息
}
//设置第index元素的值
public E set(int index, E element) {
checkElementIndex(index);
Node<E> x = node(index);//定位第index个结点
E oldVal = x.item;
x.item = element;
return oldVal;
}//实现队列操作,返回第一个元素的值
public E peek() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
//实现队列操作,返回第一个结点
public E element() {
return getFirst();
}//实现队列操作,弹出第一个结点
public E poll() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}//添加结点
public boolean offer(E e) {
return add(e);
}
//添加头结点
public boolean offerFirst(E e) {
addFirst(e);
return true;
}
总结
- LinkedList的实现是基于双向链表的,且头结点中不存放数据,如上图
- 注意两个不同的构造方法。无参构造方法直接建立一个仅包含head节点的空链表;包含Collection的构造方法,先调用无参构造方法建立一个空链表,而后将Collection中的数据加入到链表的尾部后面。
- 在查找和删除某元素时,源码中都划分为该元素为null和不为null两种情况来处理,LinkedList中允许元素为null。
- LinkedList是基于链表实现的,因此不存在容量不足的问题,所以这里没有扩容的方法。
- Node node(int index)方法。该方法返回双向链表中指定位置处的节点,而链表中是没有下标索引的,要指定位置出的元素,就要遍历该链表,从源码的实现中,我们看到这里有一个加速动作。源码中先将index与长度size的一半比较,如果index<(size<<1),就只从位置0往后遍历到位置index处,而如果index>(size<<1),就只从位置size往前遍历到位置index处。这样可以减少一部分不必要的遍历,从而提高一定的效率(实际上效率还是很低)。
- LinkedList是基于链表实现的,插入删除效率高,查找效率低(虽然有一个加速动作)。
- 要注意源码中还实现了栈和队列的操作方法,因此也可以作为栈、队列和双端队列来使用