JDK源码-LinkedList源码

1，LinkedList： -1，实现了List接口，允许null元素。LinkedList还为链表开头和结尾提供了操作，所以使用LinekedList可以用作堆栈、列队或双端队列。
-2，LinkedList实现Deque接口，提供了基于队列的先进先出序列的实现。
-3，所有的操作都是按照双重链表来实现的。
-4，操作为非线程安全的，如果多个线程中，存在修改链表结构的操作，则必须保证线程安全。
2，LinkedList继承AbstractSequentialList实现Lise、Deque、Cloneable、Serializable接口。

public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable

-1，AbstractSequentialList继承AbstractList，AbstractList属于ArrayList的父类。
-2，Deque继承自Queue，定义了队列接口操作。Queue接口继承Collection接口。
3，AbstractSequentialList类详解：此类提供了List接口的主要实现。
要实现一个列表，程序猿只需要扩展此类，并提供listIterator和size方法的实现即可。对于不可修改的列表，只需要实现迭代器对应的方法即可。
该类主要方法有：get set add remove addAll iterator listIterator方法。其中，get set add remove addAll方法均是基于 iterator listIterator方法实现。

 public E remove(int index) {try { ListIterator<E> e = listIterator(index); E outCast = e.next(); e.remove(); return outCast;} catch (NoSuchElementException exc) { throw new IndexOutOfBoundsException("Index: "+index);} }

 public E set(int index, E element) {try { ListIterator<E> e = listIterator(index); E oldVal = e.next(); e.set(element); return oldVal;} catch (NoSuchElementException exc) { throw new IndexOutOfBoundsException("Index: "+index);} }

3，LinkedList成员变量： -1，header：Entry属性的变量。Entry内部类，定义了一个链表的数据结构。

 private static class Entry<E> {E element;Entry<E> next;Entry<E> previous; Entry(E element, Entry<E> next, Entry<E> previous) { this.element = element; this.next = next; this.previous = previous;} }

-2，size：LinkedList元素长度。
4，第一类方法，对Entry对象的操作： -1，addBefore(E e, Entry<E> entry)：增加e元素至entry链表中。

 private Entry<E> addBefore(E e, Entry<E> entry) { Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);//生成新的Entry对象，Entry对象的前置指向当前entry的前置元素。 newEntry.previous.next = newEntry; newEntry.next.previous = newEntry; size++; modCount++; return newEntry; }

插入操作可参考下图： JDK源码-LinkedList源码

主要操作涉及，new元素的p指向了old元素，所以下一步将old元素的next指向new元素，然后奖new元素的next的p元素指向new元素本身。基本就是单链表的删除操作而已。 -2，remove：链表元素的删除

private E remove(Entry<E> e) {if (e == header) throw new NoSuchElementException();  E result = e.element; e.previous.next = e.next; e.next.previous = e.previous; e.next = e.previous = null; e.element = null; size--; modCount++; return result; }

remove操作，则是将e元素的p指向e的next，将e的next的p指向e的p。使 e的p和n都指向为null，将e元素指向为null。 5，第二类方法，构造方法。 public LinkedList()：默认构造函数，初始化链表头。

 public LinkedList() { header.next = header.previous = header; }

public LinkedList(Collection<? extends E> c)：构造List包含c中所有元素。

 public LinkedList(Collection<? extends E> c) { this(); addAll(c); }

6，单链表的基本操作： -1，add：

 public boolean add(E e) {addBefore(e, header); return true; }

-2，remove(Object o)：移除对应元素。

 public boolean remove(Object o) { if (o==null) { for (Entry<E> e = header.next; e != header; e = e.next) { if (e.element==null) { remove(e); return true; } } } else { for (Entry<E> e = header.next; e != header; e = e.next) { if (o.equals(e.element)) { remove(e); return true; } } } return false; }

我们可以看到如果元素为null直接用的==判断相等，否则调用对应对象的equals方法移除。 7，队列方法： -1.addFirst(E e)：在链表开头增加元素。

 public void addFirst(E e) {addBefore(e, header.next); }

-2，addLast：在链表末尾增加元素

 public void addLast(E e) {addBefore(e, header); }

-3，removeFirst：首元素出队。

public E removeLast() {return remove(header.previous); }

8，ListIterator：构造适用与LinkedList的迭代器。

private class ListItr implements ListIterator<E>

private Entry<E> lastReturned = header;private Entry<E> next;private int nextIndex;private int expectedModCount = modCount; ListItr(int index) { if (index < 0 || index > size)throw new IndexOutOfBoundsException("Index: "+index+ ", Size: "+size); if (index < (size >> 1)) {next = header.next;for (nextIndex=0; nextIndex<index; nextIndex++) next = next.next; } else {next = header;for (nextIndex=size; nextIndex>index; nextIndex--) next = next.previous; }} public boolean hasNext() { return nextIndex != size;} public E next() { checkForComodification(); if (nextIndex == size)throw new NoSuchElementException();  lastReturned = next; next = next.next; nextIndex++; return lastReturned.element;} public boolean hasPrevious() { return nextIndex != 0;} public E previous() { if (nextIndex == 0)throw new NoSuchElementException();  lastReturned = next = next.previous; nextIndex--; checkForComodification(); return lastReturned.element;} public int nextIndex() { return nextIndex;} public int previousIndex() { return nextIndex-1;} public void remove() { checkForComodification(); Entry<E> lastNext = lastReturned.next; try { LinkedList.this.remove(lastReturned); } catch (NoSuchElementException e) { throw new IllegalStateException(); } if (next==lastReturned) next = lastNext; elsenextIndex--; lastReturned = header; expectedModCount++;} public void set(E e) { if (lastReturned == header)throw new IllegalStateException(); checkForComodification(); lastReturned.element = e;} public void add(E e) { checkForComodification(); lastReturned = header; addBefore(e, next); nextIndex++; expectedModCount++;} final void checkForComodification() { if (modCount != expectedModCount)throw new ConcurrentModificationException();} }

秒客网

JDK源码-LinkedList源码

相关文章