LinkedList

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 (often 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 find the correct position. However, a remove during an iteration is O(1).

• contains is O(n).

• LinkedList seems more like an array than a true linked list. There is no method equivalent to setrest, so the structure of a LinkedList cannot be changed. It is not possible to write the destructive merge sort for linked lists that we saw earlier.