LinkedList源码解析
LinkedList是基于双向链表形式的List实现。
类继承实现
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
可知继承一个类,实现4个接口。
核心变量
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;
size表示当前链表的元素个数,first指向链表的头指针,last指向链表的尾指针。
Node数据结构
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;
}
}
Node用来构造链表的每一个节点,item表示元素,next指向下一个节点,prev指向上一个节点。其具体结构如下所示:
构造函数
两种构造函数,第一种构造一个空List,第二种从一个Collection初始化构
/**
* Constructs an empty list.
*/
public LinkedList() {
}
/**
* Constructs a list containing the elements of the specified
* collection, in the order they are returned by the collection's
* iterator.
*
* @param c the collection whose elements are to be placed into this list
* @throws NullPointerException if the specified collection is null
*/
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
核心方法
1.add方法
在链表末尾添加一个元素
/**
* Appends the specified element to the end of this list.
*
* <p>This method is equivalent to {@link #addLast}.
*
* @param e element to be appended to this list
* @return {@code true} (as specified by {@link Collection#add})
*/
public boolean add(E e) {
linkLast(e);
return true;
}
/**
* Links e as last element.
*/
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++;
}
具体操作如下所示:
指针l指向last节点,新建newNode节点通过构造函数使prev指针指向last节点
last指针指向newNode节点 如果l为空,说明链表初始状态为空,则first指向newNode,否则l节点next指针指向newNode节点
2.get方法获取某一个位置元素
/**
* Returns the element at the specified position in this list.
*
* @param index index of the element to return
* @return the element at the specified position in this list
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
/**
* Returns the (non-null) Node at the specified element index.
*/
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;
}
}
判断待查询元素索引位置与链表长度一半大小关系,当索引位置小于长度一半时,从头指针开始遍历寻找,否则从尾指针遍历寻找。
3.indexOf返回某个元素首次出现位置
public int indexOf(Object o) {
int index = 0;
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null)
return index;
index++;
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item))
return index;
index++;
}
}
return -1;
}
4.remove删除某个元素
public boolean remove(Object o) {
if (o == 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;
}
首先找到该元素,然后执行unlink方法
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;
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;
}
如下图所示,将某一个节点删除需要修改4处指针
prev指向X的上一个节点 next指向X的下一个节点
如果prev==null,说明X为头指针,则first=next;否则prev.next=next 断开X与prev的连接
如果next==null,说明X为尾指针,则last=prev 否则next.prev = prev 断开X与next的连接
此外LinkedList可以用来模拟栈以及队列的运行机制
获取链表头部以及尾部数据
public E getFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
}
public E getLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return l.item;
}
在头部删除元素与在尾部添加元素可以用来模拟队列
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
public void addLast(E e) {
linkLast(e);
}
在头部添加以及在头部删除可以用来模拟栈
public void addFirst(E e) {
linkFirst(e);
}
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
其核心方法linkFirst linkLast unlinkFirst unlinkLast linkBefore unlink 方法实现了对于链表的各种添加与删除操作。
在链表头部添加一个元素
/**
* Links e as first element.
*/
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++;
}
指针f指向first 新建newNode其next指针指向f
first指向newNode,如果f==null说明链表原来为空,此时last指向newNode
否则f的prev指向newNode
在链表尾部添加一个元素
/**
* Links e as last element.
*/
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++;
}
在某一个节点前添加一个元素
/**
* Inserts element e before non-null Node 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++;
}
删除链表头结点
/**
* Unlinks non-null first node 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;
size--;
modCount++;
return element;
}
删除链表的尾节点
/**
* Unlinks non-null last node l.
*/
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;
}
LinkedList是一个双向链表,对于节点的增删性能较好,对于随机访问性能较差。利用其双向链表的头尾指针可以分别从头尾增加删除元素,从而可以用来模拟栈与队列的运行。其核心方法是linkFirst linkLast unlinkFirst unlinkLast linkBefore unlink。