Doubly-Linked Lists and LinkedList<T>
A linked list is a data structure that holds a sequence of values. In a doubly-linked list, each item in the collection includes a pointer to the previous and next elements. This allows insertions and deletions to be performed quickly and efficiently.
A linked list holds a series of nodes, each of which includes several pieces of data. Primarily, each node holds a value that has been added to the list. In addition, each of a singly-linked list's nodes includes a link to the next node in the sequence. In a doubly-linked list, the nodes also hold pointers to their predecessors. This makes it easy to traverse a linked list by following the pointers. It also means that insertions and deletions are fast, as items do not need to be shuffled around in memory to retain the correct ordering; only the pointers need to be updated.
The diagram below shows a representation of a linked list. Here we have three nodes, holding the values 5, 10 and 15. The arrows on the right of the diagram indicate the pointers to the next items. The arrows on the left show the references to previous elements in the list. You can see that the node with a value of 10 has 15 as its next item and 5 as its previous. The two black circles indicate the positions of sentinel nodes. These are not usually real nodes in the list. They are pointed to in order to signify the position of the first and last value nodes.
NB: In a .NET linked list, pointers to the sentinel nodes will generally be represented by null references. The linked list structure itself will usually include two references that identify the first and last nodes in the series.
Inserting a Node
When you use a simple list to store a sequence of values, inserting a new element at a specific position can be an expensive operation. Every item from the desired location onwards needs to be moved to make space for the new element to be inserted. This can be an O(n) operation.
With a linked list, new items can be inserted at any free position in memory, perhaps far from any other element in the list. All that needs to be updated for the existing nodes is a number of pointers. The item that needs to appear before the new node will have its "next" pointer changed to point to the new node. The item that should directly follow the new value has its "previous" reference updated. These two altered nodes become the targets for the new node's pointers. This means that the number of items already present in the linked list has no bearing on the performance of the insertion. Adding an item is, therefore, O(1).
If you wish to insert an item at the start or end of a linked list the process is similar. In such cases only one existing node's pointer needs to be updated. The new node will include a reference to the updated node and a pointer to a sentinel node.
The diagram below shows what happens when a new value is inserted into an existing linked list. Here we are inserting the number eight between the nodes holding values of five and ten. The lighter arrows show unchanged pointers. The darker ones show new or updated references. You can see that the five node now points to the eight node as its next item and a link back from the eight node has been added. The ten node's previous pointer now links to the eight node, which points to the ten node as its successor. Following the "next" arrows on the right of the diagram gives the sequence: 5, 8, 10, 15. The reverse sequence of 15, 10, 8, 5 can be obtained using the "previous" arrows on the left.
3 November 2013