Java API 분석__LinkedList

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

1. LinkedList 는 배열보다 메모리 공간 측면에서 훨씬 유리하다. 

- 배열과 같은 ArrayList 와 Vector 는 각 위치가 정해져있고, 그 위치로 데이터를 찾는다. 

그래서 추가 삭제를 하면 메모리 위치를 이동해야 한다!

- 그에 반해 LinkedList 는 중간에 있는 데이터를 삭제하면, 지운 데이터의 앞에 있는 데이터와 뒤에 있는 데이터를 연결하면 그만이다.

위치를 맞추기 위해서 값을 이동하는 단계를 거칠 필요가 없다는 뜻!

2. LinkedList 는 List 뿐 아니라 Queue 와 Deque 인터페이스도 구현한다.

때문에 앞, 뒤 모두에서 값을 넣거나 빼는 작업이 자유롭다.

3. ArrayList 와 Vector, Stack 은 AbstractList를,  LinkedList 는 AbstractSequentialList 를 상속받는다. 

AbstractList 를 상속받는 클래스는 RandomAccess 인터페이스를,  AbstractSequentialList 를 상속받는 클래스는 Queue와 Deque를 인터페이스를 구현한다.

AbstractSequentialList<E>

public abstract class AbstractSequentialList<E>
extends AbstractList<E>

This class provides a skeletal implementation of the List interface to minimize the effort required to implement this interface backed by a "sequential access" data store (such as a linked list). For random access data (such as an array), AbstractList should be used in preference to this class. (...) This implementation first gets a list iterator pointing to the indexed element (with listIterator(index)). Then, it inserts the specified element with ListIterator.add.

Sequential Access 

AbstractSequentialList 를 상속받은 경우 동일한 List<E> 인터페이스 구현한 동일한 기능의 메소드라도 구현방식이 사뭇 다르다. 

List Iterator 를 통해 인덱스 순서대로 접근한다. 그래서 느리단다. 

The best algorithms for manipulating random access lists (such as ArrayList) can produce quadratic behavior when applied to sequential access lists (such as LinkedList). 

// Random Access 
for (int i=0, n=list.size(); i < n; i++)
list.get(i);

// Sequential Access
for (Iterator i=list.iterator(); i.hasNext(); )
i.next();