文章目录
实现了{@code list}和{@code Deque}接口的双链表。
实现所有可选列表操作，并允许所有元素(<mark>包括{@code null}</mark>)。
所有操作的执行都与doubly-linkedlist的预期相同。
索引到列表中的操作将从头到尾遍历列表，以更接近指定索引的操作为准。
注意，这个<mark>实现不是同步的</mark>。
如果多个线程同时访问一个链表，并且其中至少有一个线程从结构上修改链表，那么它必须在外部同步。(结构修改是添加或删除一个或多个元素的任何操作;仅仅设置元素的值并不是结构上的修改。)
这通常是通过对一些自然封装列表的对象进行同步来实现的。
如果不存在这样的对象，则应该使用{@link Collections#synchronizedList}“包装”列表。
这最好在创建时完成，以防止对列表的意外非同步访问:
<mark>List list = Collections.synchronizedList(new LinkedList(…))</mark>;
该类的{@code iterator}和{@code listIterator}方法返回的迭代器是<mark>支持快速失败的</mark>:
如果在创建迭代器之后，以任何方式(除了通过迭代器自己的{@code remove}或{@code add}方法)对列表进行结构修改，迭代器将抛出一个{@link ConcurrentModificationException}。
因此，在面对并发修改时，迭代器会快速而干净地失败，而不是在未来不确定的时间，冒着任意的、不确定的行为的风险。
注意，不能保证迭代器的快速故障行为，因为通常来说，在存在非同步并发修改的情况下，不可能做出任何严格的保证。
故障快速迭代器以最大的努力抛出{@code ConcurrentModificationException}。
因此，<mark>编写一个依赖于此异常来判断其正确性的程序是错误的</mark>：迭代器的快速故障行为应该只用于检测bug。
成员变量
/** * list大小，也就是node数量 */
transient int size = 0;
/** * 指向第一个node * Invariant: (first == null && last == null) || * (first.prev == null && first.item != null) */
transient Node<E> first;
/** * 指向最后一个node * Invariant: (first == null && last == null) || * (last.next == null && last.item != null) */
transient Node<E> 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;
}
}
基本就是这么个结构了~
构造方法
/** * 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);
}
无参构造啥都不干，所以成员变量first和last就都是null了~
看下有参构造，支持直接添加一个集合
/** * 按指定集合的迭代器返回的顺序，将指定集合中的所有元素追加到此列表的末尾。 * 如果在操作进行期间修改了指定的集合，则此操作的行为未定义。 * (注意，如果指定的集合是这个列表，并且它不是空的，则会发生这种情况。) * * @param c collection containing elements to be added to this list * @return {@code true} if this list changed as a result of the call * @throws NullPointerException if the specified collection is null */
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
/** * 从指定位置开始，将指定集合中的所有元素插入此列表。 * 将当前位于该位置的元素(如果有的话)和随后的任何元素移动到右边(增加它们的索引)。 * 新元素将按指定集合的迭代器返回它们的顺序出现在列表中。 * * @param index index at which to insert the first element * from the specified collection * @param c collection containing elements to be added to this list * @return {@code true} if this list changed as a result of the call * @throws IndexOutOfBoundsException {@inheritDoc} * @throws NullPointerException if the specified collection is null */
@Override
public boolean addAll(int index, Collection<? extends E> c) {
//检查这个index是否合法 0 < index <= size
checkPositionIndex(index);
//参数中的目标集合转数组
Object[] a = c.toArray();
int numNew = a.length;
if (numNew == 0)
//如果参数根本就是空，直接返回false
return false;
//succ : index处的node
//pred : succ的前一个节点
Node<E> pred, succ;
if (index == size) {
succ = null;
//这里注意，如果index=0,并且原先linkedlist就没有数据的话，last就是null
pred = last;
} else {
//获取index处的node
succ = node(index);
pred = succ.prev;
}
//遍历目标数组
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;
//每一个数组中的对象，创建一个新的节点（注意这里的pred可能为null）
Node<E> newNode = new Node<>(pred, e, null);
if (pred == null)
//如果index处前一个节点为null,说明这是一个空的linkedlist
first = newNode;
else
//将新创建的节点指向原先index前一个节点的next ,
pred.next = newNode;
pred = newNode;
}
if (succ == null) {
last = pred;
} else {
//这一步之前的节点顺序是 0,...,index-1,newNode
//下边两行代码将新的newNode与原先的index处node链接起来 0,...,index-1,newNode,oleIndexNode,...
pred.next = succ;
succ.prev = pred;
}
size += numNew;
modCount++;
return true;
}
modCount干嘛的
到下面迭代器的时候一起说
add(E e)
这个方法可以参照上边的图看一下，意思就是那个意思~
/** * 将指定的元素追加到此列表的末尾。 * * <p>这个方法等价于 {@link #addLast}. * * @param e element to be appended to this list * @return {@code true} (as specified by {@link Collection#add}) */
@Override
public boolean add(E e) {
linkLast(e);
return true;
}
/** * Links e as last element. */
void linkLast(E e) {
//先获取当前最后的一个node
final Node<E> l = last;
//将e作为item创建一个新的node, l作为这个node的prev node,注意这个next 是null
final Node<E> newNode = new Node<>(l, e, null);
//新的node作为链表的最后一个node
last = newNode;
if (l == null) {
//如果最开始获取的last node 是null , 那么说明这个链表中其实之前是没有数据的
//也可以看出，如果链表中只有一个node , 那么 fast 和 last 都指向这一个node
first = newNode;
} else {
//因为l现在是倒数第二个node，所以把l的next指向现在的最后一个node
l.next = newNode;
}
size++;
modCount++;
}
get(int index)
/** * 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);
//这里挺有意思，判断index是在前半段还是后半段，这样只需要检索一半数据，但其实要是数据很多，这个方法还是有点浪费时间啊
//但是话说回来，一个likedlist，放大量数据要想干嘛？快速检索效率很低的呀~
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;
}
}
indexOf(Object o)
/** * 返回此列表中指定元素的第一个出现项的索引，如果该列表不包含该元素，则返回-1。 * * @param o element to search for * @return the index of the first occurrence of the specified element in * this list, or -1 if this list does not contain the element */
public int indexOf(Object o) {
int index = 0;
//这个方法比较干燥，就是把null单独拿出来做了一个分支
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;
}
//顺便看下lastIndexOf方法，就是index的初始值不是0了而是linkedlist的size，然后通过判断做index--操作
public int lastIndexOf(Object o) {
int index = size;
if (o == null) {
for (Node<E> x = last; x != null; x = x.prev) {
index--;
if (x.item == null)
return index;
}
} else {
for (Node<E> x = last; x != null; x = x.prev) {
index--;
if (o.equals(x.item))
return index;
}
}
return -1;
}
删除操作
//这个方法基本是所有删除操作都最终会调用的，也是很干燥，
//可以根据添加操作的那个图，反推一下就是流程了
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;
}
迭代器（有点意思的东西）
/** * 返回此列表中元素的列表迭代器(按适当的顺序)，从列表中的指定位置开始。 * 遵守{@code List.listIterator(int)}的通用契约。 * * list-Iterator是快速故障的:如果在创建了list-Iterator之后，以任何方式对列表进行结构修改， * 除了通过list- Iterator自己的{@code remove}或{@code add}方法，list- Iterator将抛出一个{@code ConcurrentModificationException}。 * 因此，在面对并发修改时，迭代器会快速而干净地失败，而不是在将来某个不确定的时间冒着任意的、不确定的行为的风险。 * * @param index index of the first element to be returned from the * list-iterator (by a call to {@code next}) * @return a ListIterator of the elements in this list (in proper * sequence), starting at the specified position in the list * @throws IndexOutOfBoundsException {@inheritDoc} * @see List#listIterator(int) */
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 E next() {
checkForComodification();
if (!hasNext())
throw new NoSuchElementException();
lastReturned = next;
next = next.next;
nextIndex++;
return lastReturned.item;
}
...
public void remove() {
checkForComodification();
if (lastReturned == null)
throw new IllegalStateException();
Node<E> lastNext = lastReturned.next;
unlink(lastReturned);
if (next == lastReturned)
next = lastNext;
else
nextIndex--;
lastReturned = null;
expectedModCount++;
}
...
public void add(E e) {
checkForComodification();
lastReturned = null;
if (next == null)
linkLast(e);
else
linkBefore(e, next);
nextIndex++;
expectedModCount++;
}
....
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
expectedModCount：迭代器API对集合的修改(添加、删除)次数。
modCount：集合本身API和迭代器API对集合的修改(添加、删除)次数。
在checkForComodification()方法中我们可以看到，在比对两个值不一致的时候就跑出并发修改异常。
至于为哈会有这么一个异常的出现，很基本的并发问题，这里就不多**了~
不总结写了干嘛
1、LinkedList不是同步的，多线程下一定要使用同步api包装下( Collections.synchronizedList)。
2、在查找和删除某元素时，区分该元素为 null和不为 null 两种情况来处理，LinkedList 中允许元素为 null。
3、查找时先判断该节点位于前半部分还是后半部分，加快了速度。
4、基于链表实现不存在扩容问题。
5、因为基于链表，所以插入删除极快，查找比较慢。
6、使用迭代器的时候呀，只能使用迭代器的remove | add方法对LinkedList进行元素数据的新增删除，否则CME。
6、实现了栈和队列的相关方法，所以可作为栈，队列，双端队列来用。
京公网安备 11010502036488号