jdk1.8源码阅读LinkedList
LikedList实现采用了双向链表，并且LinkedList实现了Dqueue接口，所以LinkedList可以当作普通队列和双端队列使用，首先看一下LinkedList的类关系图
LinkedList和ArrayList的区别就是继承了AbstractSequentialList，并且实现了Dqueue接口，AbstractSequentialList和AbstractList的主要区别是采用迭代器实现了get、set、add和remove方法。所以这个适合链表遍历，但是LinkedList对这些方法都进行了重写，Deque接口主要定义了普通队列，双端队列，栈的操作方法，所以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;
}
}采用的是静态内部类。
LinkedList成员变量和构造方法如下：
/**
* LinkedList实现了双向链表各种操作，并且实现了普通队列的操作，和栈的操作
*/
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
//链表大小
transient int size = 0;
//链表头结点
transient Node<E> first;
/**
* 链表尾节点
*/
transient Node<E> last;
/**
* 无参构造方法
*/
public LinkedList() {
}
/**
* 将链表初始化为一个集合对象
*/
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
}其中带参构造方法我们可以将一个实现了Collection接口的类的集合转换成双向链表。
插入操作主要包括在头部插入，尾部插入和指定结点前插入
/**
* 在链表头插入一个结点
*/
private void linkFirst(E e) {
final Node<E> f = first;
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;
//如果此时是空链表则头指针和尾指针同时指向新元素
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}
/**
* 在链表尾部插入新节点
*/
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
/**
* 在succ前插入新结点，并且保证succ一定不能为空
*/
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
final Node<E> pred = succ.prev;
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}链表节点移除也包括头部移除，尾部移除，指定节点移除
/**
* 移除链表头结点，必须保证f是头结点，不为空
*/
private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
final E element = f.item;
final Node<E> next = f.next;
f.item = null;
f.next = null; // help GC
first = next;
//如果移除头节点后，变成空链表
if (next == null)
last = null;
else
next.prev = null; //头结点前驱变为null
size--;
modCount++;
return element;
}
/**
* 移除尾结点，保证是尾结点且不为空
*/
private E unlinkLast(Node<E> l) {
// assert l == last && l != null;
final E element = l.item;
final Node<E> prev = l.prev;
l.item = null;
l.prev = null; // help GC
last = prev;
if (prev == null)
first = null;
else
prev.next = null;
size--;
modCount++;
return element;
}
/**
* 移除指定的结点，保证结点不为null
*/
E unlink(Node<E> x) {
// assert x != null;
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
//prev等于null说明是头结点
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
if (next == null) { //如果是尾节点
last = prev;
} else {
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}获取指定位置结点方法，采用了二分查找的思想：
/**
* 获取指定位置的结点
*/
Node<E> node(int index) {
// assert isElementIndex(index);
//这一步用了二分查找的思想，如果index在前半段，就从前往后遍历
//如果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;
}
}LinkedList的队列操作主要包括以下：
// 普通队列操作，普通队列特性就是FIFO(先进先出),队头出来，队尾进入
/**
* 普通队列操作，获取队头
*/
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 E remove() {
return removeFirst();
}
/**
* 向队列尾部添加元素
*/
public boolean offer(E e) {
return add(e);
}
// 双端队列操作，双端队列可以在队列两端进行插入和删除
/**
* 队列头部插入元素
*/
public boolean offerFirst(E e) {
addFirst(e);
return true;
}
/**
* 队列尾部插入元素
*/
public boolean offerLast(E e) {
addLast(e);
return true;
}
/**
* 获取队列头
*/
public E peekFirst() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
/**
* 获取队列尾
*/
public E peekLast() {
final Node<E> l = last;
return (l == null) ? null : l.item;
}
/**
* 获取队头，并且移除队头
*/
public E pollFirst() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}
/**
* 获取队尾并且移除队尾
*/
public E pollLast() {
final Node<E> l = last;
return (l == null) ? null : unlinkLast(l);
}栈操作如下：
//栈操作，栈是一种LIFO(后进先出)的结构
/**
* 压栈操作，在链表头插入，一串数据压栈过程就是链表的头插法
*/
public void push(E e) {
addFirst(e);
}
/**
* 出栈操作，先进的会后出
*/
public E pop() {
return removeFirst();
}LinkedList的迭代器是内部类ListItr 实现了ListIterator，可以在链表迭代过程中对链表进行增删改
/**
* 创建一个链表迭代器，参数index是迭代起始位置
*/
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; //期望修改次数
ListItr(int index) {
// assert isPositionIndex(index);
next = (index == size) ? null : node(index);
nextIndex = index;
}
public boolean hasNext() {
return nextIndex < size;
}
//返回结点值
public E next() {
checkForComodification();
if (!hasNext())
throw new NoSuchElementException();
lastReturned = next;
next = next.next;
nextIndex++;
return lastReturned.item;
}
//是否有前驱
public boolean hasPrevious() {
return nextIndex > 0;
}
//从后往前遍历返回当前遍历到的值
public E previous() {
checkForComodification();
if (!hasPrevious())
throw new NoSuchElementException();
//如果next = null说明index在最后一个位置
lastReturned = next = (next == null) ? last : next.prev;
nextIndex--;
return lastReturned.item;
}
/**
* 从前往后，返回下一个要遍历的位置
*/
public int nextIndex() {
return nextIndex;
}
//从后往前遍历，返回下一个要遍历的位置，所以nextIndex - 1
public int previousIndex() {
return nextIndex - 1;
}
/**
* 移除当前刚遍历过的结点
*/
public void remove() {
checkForComodification();
if (lastReturned == null)
throw new IllegalStateException();
Node<E> lastNext = lastReturned.next;
unlink(lastReturned);
//如果从后往前遍历，则next == lastReturned，所以next的值要往后移动一个
if (next == lastReturned)
next = lastNext;
else
nextIndex--;
lastReturned = null;
expectedModCount++;
}
public void set(E e) {
if (lastReturned == null)
throw new IllegalStateException();
checkForComodification();
lastReturned.item = e;
}
//在链表里追加元素
public void add(E e) {
checkForComodification();
lastReturned = null;
//如果是末尾，则调用加入末尾的方法
if (next == null)
linkLast(e);
else
linkBefore(e, next); //否则加入到next之前
nextIndex++;
expectedModCount++;
}
}LinkedList还有一个内部类用适配器模式实现了一个从后往前遍历的操作
/**
* @since 1.6
*/
public Iterator<E> descendingIterator() {
return new DescendingIterator();
}/**
* 采用适配器模式实现了后续遍历链表
*/
private class DescendingIterator implements Iterator<E> {
private final ListItr itr = new ListItr(size());
public boolean hasNext() {
return itr.hasPrevious();
}
public E next() {
return itr.previous();
}
public void remove() {
itr.remove();
}
}所以LinkedList返回 的DescendingIterator对象可以逆序遍历链表。
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018-05-29，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读