A Linked List is a sequence of nodes, it can be single linked or double linked. Nodes on a single linked lists have a reference to their successor, on doubly linked lists each node also has a reference to their predecessor.

The implementation

To make the basic operations simpler, every instance of the Doubly Linked List will hold a reference to the first and last elements in the list, it will also keep track of the number of nodes it holds.

The linked list will implement the following basic operations :

Insert (Append/Prepend)

Delete

Search

String representation

The complete source code for data structure’s including the unit tests for this implementation are included here.

Complexity

Operation

Complexity

Search

O(n)

Insert

O(1)

Delete

O(1)

Max/Min

O(n)

Predecessor

O(1)

Successor

O(1)

The Good

Insertion and Deletion can be achieved in constant time.

The Bad

Searching is slow since we can’t leverage fast searching algorithms such as Binary Search.

Extra memory is required to store references to predecesors/sucesors.