Data Structures 4/7: Linked Lists

Note: Check out the entire supplemental source code for this blog series.

Linked Lists

Linked lists are very much a general-purpose data structure. They perform decently well at nearly every operation, but they don’t really excel at any one of them. Linked lists can be implemented as singly linked or doubly linked. In a singly linked list, each element (called a node) has a pointer or reference to its successor. In a doubly linked list, each node has a pointer or reference to both its successor and predecessor at the cost of slightly more memory, but at the benefit of increased deletion performance.

Implementation

There are many different ways to implement a linked list, but they all involve nodes linked to each other through references. Usually, a reference to the root node is stored and the list can be traversed from there by following the pointers repeatedly.

This implementation is a circular doubly linked list that uses what’s known as a sentinel node to make the code a little more manageable. The sentinel acts as a dummy node and represents the beginning/end of the circular list.

LinkedList.cs

LinkedListNode.cs

Pros

• Unlike stacks and queues, linked lists provide Θ(1) insertion and deletion in even the worst case.

• Unlike stacks and queues, linked lists can grow and shrink to any size without ever needing reconstruction. Because they grow dynamically, they will never allocate more memory than needed.

Cons

• Unlike stacks and queues, linked lists require overhead of one or two pointers or references for each element.

• Unlike stacks and queues, linked lists do NOT store elements in sequential memory. Therefore, they will not receive optimized performance on most hardware and operating systems.

Use Cases

• Because linked lists never need to be rebuilt, they will be performant in situations when there will be many insertions and/or deletions.

Linked Lists in C#

• The built-in C# generic implementation of the linked list is System.Collections.Generic.LinkedList<T>. This implementation is a doubly linked list, but it is not circular.

Performance