LinkedList implements a List as a doubly-linked list, with both forward and backward pointers.

This provides a good implementation of a linked list, stack, queue, and deque (pronounced ``deck'') or double-ended queue.

Advantage:

• getFirst, addFirst, removeFirst, getLast, addLast, removeLast are O(1).

Disadvantages:

• get, set, add and remove are O(n) for random positions: it is necessary to step down the list to the correct position. However, a remove during an iteration is O(1).

• contains is O(n).

Contents    Page-10    Prev    Next    Page+10    Index