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.
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 :
The complete source code for data structure’s including the unit tests for this implementation are included here.
Insertion and Deletion can be achieved in constant time.
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.