LinkedList
ArrayList是通过数组实现存储,而LinkedList则是通过链表来存储数据,而且他实现的是一个双向链表,简单的说一下什么是双向链表。双向链表是数据结构的一种形式,他的每个节点维护两个指针,prev指向上一个节点,next指向下一个节点。这种结构有什么特点呢?他可以实现双向遍历,这使得在链表中的数据读取变得非常灵活自由。同时,LinkedList中维护了两个指针,一个指向头部,一个指向尾部。维护这两个指针后,可以使得元素从头部插入,也可以使元素从尾部插入。基于方式,用户很容易就能实现FIFO(队列),LIFO(栈)等效果。那么下面我们来看一下源码中的具体实现。
1.Node节点定义:
2.FIFO(队列)实现原理:
队列的原理就是每次都从链表尾部添加元素,从链表头部获取元素,就像生活中的排队叫号,总是有个先来后到。
// 队列尾部添加一个元素,建议使用这个,约定俗成吧。
public boolean offer(E e) {
return add(e);
}
// 队列尾部添加一个元素
public boolean offerLast(E e) {
addLast(e);
return true;
}
// offer和offerLast底层调用的都是linkLast这个方法,顾名思义就是将元素添加到链表尾部。
void linkLast(E e) {
final Node<E> l = last;
// 创建一个节点,将prev指针指向链表的尾节点。
final Node<E> newNode = new Node<>(l, e, null);
// 将last指针指向新创建的这个节点。
last = newNode;
if (l == null)
// 如果当前链表为空,那么将头指针也指向这个节点。
first = newNode;
else
// 将链表的尾节点的next指针指向新建的节点,这样就完整的实现了在链表尾部添加一个元素的功能。
l.next = newNode;
size++;
modCount++;
}
// 在链表头部删除一个元素,建议用这个,别问我为什么,我也不知道
public E poll() {
return (f == null) ? null : unlinkFirst(f);
}
public E pollFirst() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}
// poll和pollFirst底层调用的就是这个方法,将链表的头元素删除。
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;
}
// 获取头元素,但是不会删除他。
public E peek() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
以上就是LinkedList实现的两种功能,这里包含了大部分关于链表操作的方法,但不仅限于这几种。不管是栈也好,队列也好,元素都是从头部删除的unlinkFirst方法。但是用户在使用的过程中并不只用到上面两张方式,我们也可以从链表尾部删除元素如removeLast,peekLast,pollLast,unlinkLast等方法。
上文讲到的功能,其实是实现了Deque接口,而现在要讲述的是实现与List的部分功能。那么最典型的操作就是直接对容器元素的读取,因为List容器的一大特点就是顺序存储,元素在容器中的位置和存入时是保持一致的,那么用户在读取元素的时候理所当然就可以通过元素下标来获取,下面就具体介绍这几种方法。
1.将元素插入容器的指定位置
// 将元素插入指定位置
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
else
// 如果不是位于末尾,那么就将元素插入指定位置的元素之前,
linkBefore(element, node(index));
}
// 将元素插入指定元素前,链表插入元素是数据结构中最基础的知识,这里就不再赘述了。
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++;
}
LinkedList的迭代器实现有两个,一个是实现了Iterator接口的DescendingIterator,另一个则是实现了ListIterator接口的ListItr。
1.ListItr
ListItr遍历需要指定一个起始值
public ListIterator<E> listIterator(int index) {
checkPositionIndex(index);
return new ListItr(index);
}
ListItr会创建一个以index为起始值的迭代器,然后用户便可以以这个位置为起点,实现向前或者向后遍历。
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();