linkedList几个核心方法是linkFirst(E),linkLast(E),linkBefore(E),unlinkFirst(),unlinkLast(),unlink(Node)
linkedList是双向链表，四个重要的成员变量是pre,next,first,last
pre是前驱节点，next是后继节点，first是第一个节点，last是最后一个节点
linkFirst(E)是把节点添加到链表头部
linkLast(E)是把节点添加到链表尾部
linkBefore(succ)是把节点添加到指定节点的前面
unlinkFirst()是移除链表第一个节点
unlinkLast()是移除链表最后一个节点
unlink(Node)是移除指定节点
插入操作
private void linkFirst(E e) {
final Node f = first; //头结点
final Node 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 l = last;//尾节点
final Node newNode = new Node<>(l, e, null);//新节点前驱指向l即尾节点
last = newNode; //自身设置为尾结点
if (l == null) //为空的话，说明原来的linkedList为空，所以同时也需要把新节点设置为头节点
first = newNode;
else //不空就把l的next设置为newNode 尾节点后继指向新节点
l.next = newNode;
size++;
modCount++;
}
void linkBefore(E e, Node succ) {
// assert succ != null;
final Node pred = succ.prev; //获取succ节点的前驱节点 0->1->2->4 succ是4 e是3 pred是2
final Node newNode = new Node<>(pred, e, succ); //用e新建节点前驱指向2 后继指向4
succ.prev = newNode; //succ前驱指向pred 4指向2
if (pred == null) //pred为null说明该节点插入在头节点之前，要重置first头节点
first = newNode;
else
pred.next = newNode; //否则pred后继指向新建节点
size++;
modCount++;
}
删除操作
private E unlinkFirst(Node f) {
// assert f == first && f != null;
final E element = f.item; //头结点元素
final Node 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;
}
private E unlinkLast(Node l) {
// assert l == last && l != null;
final E element = l.item;//取出尾结点元素
final Node 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;
}
E unlink(Node x) {
// assert x != null;
final E element = x.item;
final Node next = x.next;//指定节点的后继节点
final Node 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;
}
这个方法是根据索引获取节点
Node node(int index) {
// assert isElementIndex(index);
//index小于size的一半就从头开始找
if (index < (size >> 1)) {
Node x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else { //index大于size的一半就从尾开始找
Node x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
其他方法都是基于linkFirst(),linkLast(),linkBefore(),unlinkFirst(),unlinkLast(),unlink()这几个方法的
offer，add，addLast基于linkLast(E)，add(index)基于linkBefore()
poll()，remove()基于unlinkFirst(),remove(index)基于unlink(Node)
addFirst基于linkFirst(E)
removeLast()基于unlinkLast()
poll和remove的区别是元素不存在poll会返回null，remove抛异常
//这个方法是把集合c添加到指定的位置
public boolean addAll(int index, Collection c) {
checkPositionIndex(index);//判断传进来的参数是否合法
Object[] a = c.toArray();//先把集合转化为数组，然后为该数组添加一个新的引用
int numNew = a.length;
if (numNew == 0)//如果待添加的集合为空，直接返回，无需进行后面的步骤。后面都是用来把集合中的元素添加到
return false;
//1->4->5 在4插入2 3 pred是1 succ是4 index为1因为是从0开始
Node pred, succ;//succ是待添加节点的位置 pred是待添加节点的前一个节点 succ是4 pred是1
if (index == size) { //如果index==size;说明此时需要添加linkedList中的集合中的每一个元素都是在linkedList的最后面
succ = null; //所以把succ设置为空，pred指向尾节点。
pred = last;
} else {
succ = node(index);//否则的话succ指向插入待插入位置的节点 node(index) 根据index找到待插入位置
pred = succ.prev;
}
//接着遍历数组中的每个元素
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;
Node newNode = new Node<>(pred, e, null);//使用当前值新建一个节点然后指向pred 1<-2
if (pred == null) //pred为空即linkedList为空，把新建节点设为头结点
first = newNode;
else
pred.next = newNode; //否则pred指向新建节点 1->2
pred = newNode; //最后把pred指向当前节点，即pred后移一位，以便后续新节点的添加
}
// 如果是从尾部开始插入的，则把last置为最后一个插入的元素
if (succ == null) {
last = pred;//此时pred指向的是linkedList中的最后一个元素，所以把last指向pred指向的节点。
} else { // 如果不是从尾部插入的，则把尾部的数据和之前的节点连起来 1->4->5 在4插入2 3
pred.next = succ; //pred指向succ pred是3 3->4
succ.prev = pred; //succ指向pred 4指向3 3<-4
}
size += numNew;//最后把集合的大小设置为新的大小。
modCount++;
return true;
}
linkedList源码文件
package java.util; import java.util.function.Consumer; public class linkedListextends AbstractSequentialList implements List , Deque , Cloneable, java.io.Serializable { transient int size = 0; transient Node first; transient Node last; public linkedList() { } public linkedList(Collection c) { this(); addAll(c); } private void linkFirst(E e) { final Node f = first; //头结点 final Node 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 l = last;//尾节点 final Node newNode = new Node<>(l, e, null);//新节点前驱指向l即尾节点 last = newNode; //自身设置为尾结点 if (l == null) //为空的话，说明原来的linkedList为空，所以同时也需要把新节点设置为头节点 first = newNode; else //不空就把l的next设置为newNode 尾节点后继指向新节点 l.next = newNode; size++; modCount++; } void linkBefore(E e, Node succ) { // assert succ != null; final Node pred = succ.prev; //获取succ节点的前驱节点 0->1->2->4 succ是4 e是3 pred是2 final Node newNode = new Node<>(pred, e, succ); //用e新建节点前驱指向2 后继指向4 succ.prev = newNode; //succ前驱指向pred 4指向2 if (pred == null) //pred为null说明该节点插入在头节点之前，要重置first头节点 first = newNode; else pred.next = newNode; //否则pred后继指向新建节点 size++; modCount++; } private E unlinkFirst(Node f) { // assert f == first && f != null; final E element = f.item; //头结点元素 final Node 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; } private E unlinkLast(Node l) { // assert l == last && l != null; final E element = l.item;//取出尾结点元素 final Node 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; } E unlink(Node x) { // assert x != null; final E element = x.item; final Node next = x.next;//指定节点的后继节点 final Node 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; } public E getFirst() { final Node f = first; if (f == null) throw new NoSuchElementException(); return f.item; } public E getLast() { final Node l = last; if (l == null) throw new NoSuchElementException(); return l.item; } public E removeFirst() { final Node f = first; if (f == null) throw new NoSuchElementException(); return unlinkFirst(f); } public E removeLast() { final Node l = last; if (l == null) throw new NoSuchElementException(); return unlinkLast(l); } public void addFirst(E e) { linkFirst(e); } public void addLast(E e) { linkLast(e); } public boolean contains(Object o) { return indexOf(o) != -1; } public int size() { return size; } public boolean add(E e) { linkLast(e);//将元素添加到链表尾部 return true; } public boolean remove(Object o) { if (o == null) { for (Node x = first; x != null; x = x.next) { if (x.item == null) { unlink(x); return true; } } } else { for (Node x = first; x != null; x = x.next) { if (o.equals(x.item)) { unlink(x); return true; } } } return false; } public boolean addAll(Collection c) { return addAll(size, c); } public boolean addAll(int index, Collection c) { checkPositionIndex(index);//判断传进来的参数是否合法 Object[] a = c.toArray();//先把集合转化为数组，然后为该数组添加一个新的引用 int numNew = a.length; if (numNew == 0)//如果待添加的集合为空，直接返回，无需进行后面的步骤。后面都是用来把集合中的元素添加到 return false; //1->4->5 在4插入2 3 pred是1 succ是4 index为1因为是从0开始 Node pred, succ;//succ是待添加节点的位置 pred是待添加节点的前一个节点 succ是4 pred是1 if (index == size) { //如果index==size;说明此时需要添加linkedList中的集合中的每一个元素都是在linkedList的最后面 succ = null; //所以把succ设置为空，pred指向尾节点。 pred = last; } else { succ = node(index);//否则的话succ指向插入待插入位置的节点 node(index) 根据index找到待插入位置 pred = succ.prev; } //接着遍历数组中的每个元素 for (Object o : a) { @SuppressWarnings("unchecked") E e = (E) o; Node newNode = new Node<>(pred, e, null);//使用当前值新建一个节点然后指向pred 1<-2 if (pred == null) //pred为空即linkedList为空，把新建节点设为头结点 first = newNode; else pred.next = newNode; //否则pred指向新建节点 1->2 pred = newNode; //最后把pred指向当前节点，即pred后移一位，以便后续新节点的添加 } // 如果是从尾部开始插入的，则把last置为最后一个插入的元素 if (succ == null) { last = pred;//此时pred指向的是linkedList中的最后一个元素，所以把last指向pred指向的节点。 } else { // 如果不是从尾部插入的，则把尾部的数据和之前的节点连起来 1->4->5 在4插入2 3 pred.next = succ; //pred指向succ pred是3 3->4 succ.prev = pred; //succ指向pred 4指向3 3<-4 } size += numNew;//最后把集合的大小设置为新的大小。 modCount++; return true; } public void clear() { // Clearing all of the links between nodes is "unnecessary", but: // - helps a generational GC if the discarded nodes inhabit // more than one generation // - is sure to free memory even if there is a reachable Iterator for (Node x = first; x != null; ) { //从头结点开始遍历 Node next = x.next; x.item = null; x.next = null; x.prev = null; x = next; //遍历下一节点 } first = last = null; size = 0; modCount++; } // Positional Access Operations public E get(int index) { checkElementIndex(index);//检查越界 return node(index).item; } public E set(int index, E element) { checkElementIndex(index); Node x = node(index); E oldVal = x.item; x.item = element; return oldVal; } public void add(int index, E element) { checkPositionIndex(index); if (index == size) //在链表尾部添加 linkLast(element); else linkBefore(element, node(index)); } public E remove(int index) { checkElementIndex(index); return unlink(node(index)); } private boolean isElementIndex(int index) { return index >= 0 && index < size; } private boolean isPositionIndex(int index) { return index >= 0 && index <= size; } private String outOfBoundsMsg(int index) { return "Index: "+index+", Size: "+size; } private void checkElementIndex(int index) { if (!isElementIndex(index)) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } private void checkPositionIndex(int index) { if (!isPositionIndex(index)) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } Node node(int index) { // assert isElementIndex(index); //index小于size的一半就从头开始找 if (index < (size >> 1)) { Node x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { //index大于size的一半就从尾开始找 Node x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } } // Search Operations public int indexOf(Object o) { int index = 0; if (o == null) { for (Node x = first; x != null; x = x.next) { if (x.item == null) return index; index++; } } else { for (Node x = first; x != null; x = x.next) { if (o.equals(x.item)) return index; index++; } } return -1; } public int lastIndexOf(Object o) { int index = size; if (o == null) { for (Node x = last; x != null; x = x.prev) { index--; if (x.item == null) return index; } } else { for (Node x = last; x != null; x = x.prev) { index--; if (o.equals(x.item)) return index; } } return -1; } // Queue operations. public E peek() { final Node f = first; return (f == null) ? null : f.item; } public E element() { return getFirst(); } public E poll() { final Node f = first; return (f == null) ? null : unlinkFirst(f); } public E remove() { return removeFirst(); } public boolean offer(E e) { return add(e); } // Deque operations public boolean offerFirst(E e) { addFirst(e); return true; } public boolean offerLast(E e) { addLast(e); return true; } public E peekFirst() { final Node f = first; return (f == null) ? null : f.item; } public E peekLast() { final Node l = last; return (l == null) ? null : l.item; } public E pollFirst() { final Node f = first; return (f == null) ? null : unlinkFirst(f); } public E pollLast() { final Node l = last; return (l == null) ? null : unlinkLast(l); } public void push(E e) { addFirst(e); } public E pop() { return removeFirst(); } public boolean removeFirstOccurrence(Object o) { return remove(o); } public boolean removeLastOccurrence(Object o) { if (o == null) { for (Node x = last; x != null; x = x.prev) { if (x.item == null) { unlink(x); return true; } } } else { for (Node x = last; x != null; x = x.prev) { if (o.equals(x.item)) { unlink(x); return true; } } } return false; } public ListIterator listIterator(int index) { checkPositionIndex(index); return new ListItr(index); } private class ListItr implements ListIterator { private Node lastReturned; private Node next; //当前遍历元素 1->2->3 index为0 next就为1 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(); lastReturned = next = (next == null) ? last : next.prev; nextIndex--; return lastReturned.item; } public int nextIndex() { return nextIndex; } public int previousIndex() { return nextIndex - 1; } public void remove() { checkForComodification(); if (lastReturned == null) throw new IllegalStateException(); Node lastNext = lastReturned.next; unlink(lastReturned); 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); nextIndex++; expectedModCount++; } public void forEachRemaining(Consumer action) { Objects.requireNonNull(action); while (modCount == expectedModCount && nextIndex < size) { action.accept(next.item); lastReturned = next; next = next.next; nextIndex++; } checkForComodification(); } final void checkForComodification() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); } } 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 Iterator descendingIterator() { return new DescendingIterator(); } private class DescendingIterator implements Iterator { private final ListItr itr = new ListItr(size()); public boolean hasNext() { return itr.hasPrevious(); } public E next() { return itr.previous(); } public void remove() { itr.remove(); } } @SuppressWarnings("unchecked") private linkedList superClone() { try { return (linkedList ) super.clone(); } catch (CloneNotSupportedException e) { throw new InternalError(e); } } public Object clone() { linkedList clone = superClone(); // Put clone into "virgin" state clone.first = clone.last = null; clone.size = 0; clone.modCount = 0; // Initialize clone with our elements for (Node x = first; x != null; x = x.next) clone.add(x.item); return clone; } public Object[] toArray() { Object[] result = new Object[size]; int i = 0; for (Node x = first; x != null; x = x.next) result[i++] = x.item; return result; } @SuppressWarnings("unchecked") public T[] toArray(T[] a) { if (a.length < size) a = (T[])java.lang.reflect.Array.newInstance( a.getClass().getComponentType(), size); int i = 0; Object[] result = a; for (Node x = first; x != null; x = x.next) result[i++] = x.item; if (a.length > size) a[size] = null; return a; } private static final long serialVersionUID = 876323262645176354L; private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException { // Write out any hidden serialization magic s.defaultWriteObject(); // Write out size s.writeInt(size); // Write out all elements in the proper order. for (Node x = first; x != null; x = x.next) s.writeObject(x.item); } @SuppressWarnings("unchecked") private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException { // Read in any hidden serialization magic s.defaultReadObject(); // Read in size int size = s.readInt(); // Read in all elements in the proper order. for (int i = 0; i < size; i++) linkLast((E)s.readObject()); } @Override public Spliterator spliterator() { return new LLSpliterator (this, -1, 0); } static final class LLSpliterator implements Spliterator { static final int BATCH_UNIT = 1 << 10; // batch array size increment static final int MAX_BATCH = 1 << 25; // max batch array size; final linkedList list; // null OK unless traversed Node current; // current node; null until initialized int est; // size estimate; -1 until first needed int expectedModCount; // initialized when est set int batch; // batch size for splits LLSpliterator(linkedList list, int est, int expectedModCount) { this.list = list; this.est = est; this.expectedModCount = expectedModCount; } final int getEst() { int s; // force initialization final linkedList lst; if ((s = est) < 0) { if ((lst = list) == null) s = est = 0; else { expectedModCount = lst.modCount; current = lst.first; s = est = lst.size; } } return s; } public long estimateSize() { return (long) getEst(); } public Spliterator trySplit() { Node p; int s = getEst(); if (s > 1 && (p = current) != null) { int n = batch + BATCH_UNIT; if (n > s) n = s; if (n > MAX_BATCH) n = MAX_BATCH; Object[] a = new Object[n]; int j = 0; do { a[j++] = p.item; } while ((p = p.next) != null && j < n); current = p; batch = j; est = s - j; return Spliterators.spliterator(a, 0, j, Spliterator.ORDERED); } return null; } public void forEachRemaining(Consumer action) { Node p; int n; if (action == null) throw new NullPointerException(); if ((n = getEst()) > 0 && (p = current) != null) { current = null; est = 0; do { E e = p.item; p = p.next; action.accept(e); } while (p != null && --n > 0); } if (list.modCount != expectedModCount) throw new ConcurrentModificationException(); } public boolean tryAdvance(Consumer action) { Node p; if (action == null) throw new NullPointerException(); if (getEst() > 0 && (p = current) != null) { --est; E e = p.item; current = p.next; action.accept(e); if (list.modCount != expectedModCount) throw new ConcurrentModificationException(); return true; } return false; } public int characteristics() { return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED; } } }
