本文共 7483 字，大约阅读时间需要 24 分钟。
LinkedList基于双端链表实现;对元素的定位由秩(rank,index)到位置(position);
public class LinkedListextends AbstractSequentialList implements List , Deque , Cloneable, java.io.Serializable
可以认为:LinkedList中对方法的定义是由List,Deque(读音同deck)定义的,而方法的实现是由AbstractSequentialList定义的(源码见文章末尾);
一个节点由前驱节点,后继节点和此节点指向的元素组成;
private static class Node{ E item; Node next; Node prev; Node(Node prev, E element, Node next) { this.item = element; this.next = next; this.prev = prev; } }
public boolean add(E e) { linkLast(e); return true; } /** * Links e as last element. */ void linkLast(E e) { final Node l = last;//指向链表尾部 final Node newNode = new Node<>(l, e, null);//以尾部为前驱节点创建一个新节点 last = newNode;//将链表尾部指向新节点 if (l == null)//如果链表为空，那么该节点既是头节点也是尾节点 first = newNode; else//链表不为空，那么将该结点作为原链表尾部的后继节点 l.next = newNode; size++;//size加一 modCount++;//fail-fast 机制 可见每次插入都是移动指针，和 ArrayList 的拷贝数组来说效率要高上不少。
public void add(int index, E element) { checkPositionIndex(index); //检查索引是否处于[0-size]之间 if (index == size)//添加在链表尾部 linkLast(element); else//添加在链表中间 linkBefore(element, node(index)); } remove分为removeFirst()和removeLast();两者类似;以removeLast为例看一下其源码:
public E removeLast() { final Node l = last; if (l == null) throw new NoSuchElementException(); return unlinkLast(l); } /** * Unlinks non-null last node l. */ private E unlinkLast(Nodel) { // assert l == last && l != null; final E element = l.item;//节点所指向元素 final Node prev = l.prev;//节点前驱节点 l.item = null;//将节点所指向元素和与前驱节点的关联置空,便于GC l.prev = null; // help GC last = prev;//前驱节点定义为新的末节点last if (prev == null) first = null;//前驱节点为空;则首节点first定义为null,此时列表为空 else prev.next = null;//前驱节点存在的话,将其后继设为null size--;//size-1 modCount++; return element; }
public E set(int index, E element) { checkElementIndex(index); Node x = node(index); E oldVal = x.item; x.item = element; return oldVal; } public E get(int index) { checkElementIndex(index); return node(index).item; } Node node(int index) { // assert isElementIndex(index); if (index < (size >> 1)) { //index位于列表的前半部分,则从前往后遍历 Node x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { Node x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } } AbstractSequentialList源码:
package java.util;public abstract class AbstractSequentialListextends AbstractList { protected AbstractSequentialList() { } public E get(int index) { try { return listIterator(index).next(); } catch (NoSuchElementException exc) { throw new IndexOutOfBoundsException("Index: "+index); } } public E set(int index, E element) { try { ListIterator e = listIterator(index); E oldVal = e.next(); e.set(element); return oldVal; } catch (NoSuchElementException exc) { throw new IndexOutOfBoundsException("Index: "+index); } } public void add(int index, E element) { try { listIterator(index).add(element); } catch (NoSuchElementException exc) { throw new IndexOutOfBoundsException("Index: "+index); } } public E remove(int index) { try { ListIterator e = listIterator(index); E outCast = e.next(); e.remove(); return outCast; } catch (NoSuchElementException exc) { throw new IndexOutOfBoundsException("Index: "+index); } } public boolean addAll(int index, Collection c) { try { boolean modified = false; ListIterator e1 = listIterator(index); Iterator e2 = c.iterator(); while (e2.hasNext()) { e1.add(e2.next()); modified = true; } return modified; } catch (NoSuchElementException exc) { throw new IndexOutOfBoundsException("Index: "+index); } } public Iterator iterator() { return listIterator(); } public abstract ListIterator listIterator(int index);}
允许元素为null
Doubly-linked list implementation of the List and Deque interfaces. Implements all optional list operations, and permits all elements (including null).
All of the operations perform as could be expected for a doubly-linked list. Operations that index into the list will traverse the list from the beginning or the end, whichever is closer to the specified index.
Note that this implementation is not synchronized.不是线程安全的;可以使用如下方式转换成线程安全的list:
List list = Collections.synchronizedList(new LinkedList(...));
Note that this implementation is not synchronized. If multiple threads access a linked list concurrently, and at least one of the threads modifies the list structurally, it must be synchronized externally. (A structural modification is any operation that adds or deletes one or more elements; merely setting the value of an element is not a structural modification.) This is typically accomplished by synchronizing on some object that naturally encapsulates the list. If no such object exists, the list should be “wrapped” using the Collections.synchronizedList method. This is best done at creation time, to prevent accidental unsynchronized access to the list:
List list = Collections.synchronizedList(new LinkedList(…));fail-fast
The iterators returned by this class’s iterator and listIterator methods are fail-fast: if the list is structurally modified at any time after the iterator is created, in any way except through the Iterator’s own remove or add methods, the iterator will throw a ConcurrentModificationException. Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future.
Note that the fail-fast behavior of an iterator cannot be guaranteed as it is, generally speaking, impossible to make any hard guarantees in the presence of unsynchronized concurrent modification. Fail-fast iterators throw ConcurrentModificationException on a best-effort basis. Therefore, it would be wrong to write a program that depended on this exception for its correctness: the fail-fast behavior of iterators should be used only to detect bugs.
转载地址：http://llwji.baihongyu.com/