Java集合源码学习(7)_List接口的实现_LinkedList

1：LinkedList实现了顺序存储的List，并且实现了双端队列Deque接口；可以用作LIFO的栈，FIFO的队列和双端队列；允许null值；不是线程安全类；

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

2：LinkedList继承自AbstractSequentialList，
java doc推荐，如果是基于"顺序访问"的数据结构(比如链表)实现的List，都继承AbstractSequentialList而非AbstractList;
如果想要实现一个只读的List，只要实现listIterator()（实现hasNext, next, hasPrevious, previous 和index）和size()方法即可；

如果想要实现一个可以修改的List，就要实现ListIterator的remove和add方法；

3：List接口的实现

      内部的实现的数据结构是双向队列

      成员变量：

   private transient Entry<E> header = new Entry<E>(null, null, null);//双向队列的头节点
   private transient int size = 0;

     其中Entry是双向队列的一个节点，代码如下:

private static class Entry<E> {E element;//实际数据Entry<E> next;//下一个数据EntryEntry<E> previous;//前一个数据EntryEntry(E element, Entry<E> next, Entry<E> previous) {this.element = element;this.next = next;this.previous = previous;}}

所有关于位置index的操作，都有可能要遍历了一遍链表，通过entry(index)方法来获取第index位置的entry；

private Entry<E> entry(int index) {
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
Entry<E> e = header;
if (index < (size >> 1)) {
for (int i = 0; i <= index; i++)
e = e.next;
} else {
for (int i = size; i > index; i--)
e = e.previous;
}
return e;
}

比如，删除操作：

public E remove(int index) {
      <span style="white-space:pre"></span>return remove(entry(index));
}<pre name="code" class="java">private E remove(Entry<E> e) {//删除entry，就是双向链表删除某一个节点
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;
}

ListIterator的实现：

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;
else
nextIndex--;
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();
}
}

4：Deque接口的实现

      接口方法的实现都是基于List中的基本方法实现的，只是限制了操作的位置；

      例如，

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