6.3 - Linked Lists
A linked list is a linear data structure where elements are stored in nodes, and each node points to the next node in the sequence. Unlike arrays, linked lists do not store elements in contiguous memory locations, which allows for efficient insertions and deletions. This section explores linked lists in detail, including their types, implementations, operations, and applications in C#.
6.3.1 - Singly Linked Lists
A singly linked list is the simplest type of linked list where each node points only to the next node in the sequence.
In a singly linked list, each node contains a data element and a reference (or pointer) to the next node in the sequence. The last node points to null, indicating the end of the list.
[Data1|Next] -> [Data2|Next] -> [Data3|Next] -> null
6.3.2 - Doubly Linked Lists
In a doubly linked list, each node contains a data element and two references: one to the next node and one to the previous node. This allows for traversal in both directions.
null <- [Prev|Data1|Next] <-> [Prev|Data2|Next] <-> [Prev|Data3|Next] -> null
6.3.3 - Circular Linked Lists
In a circular linked list, the last node points back to the first node, creating a circle. This can be implemented with either singly or doubly linked lists.
Singly Circular:
[Data1|Next] -> [Data2|Next] -> [Data3|Next] -+
^ |
+----------------------------------------+
Doubly Circular:
+----------------------------------------+
| v
[Prev|Data1|Next] <-> [Prev|Data2|Next] <-> [Prev|Data3|Next]
^ |
+---------------------------------------------------------+
6.3.4 - LinkedList<T> Implementation
C# provides a built-in generic LinkedList<T> class in the System.Collections.Generic namespace, which implements a doubly linked list:
using System.Collections.Generic;
// Creating a linked list
LinkedList<int> linkedList = new LinkedList<int>();
// Adding elements
linkedList.AddLast(1);
linkedList.AddLast(2);
linkedList.AddLast(3);
linkedList.AddFirst(0);
// Accessing elements
LinkedListNode<int> firstNode = linkedList.First; // 0
LinkedListNode<int> lastNode = linkedList.Last; // 3
// Traversing the list
foreach (int value in linkedList)
{
Console.WriteLine(value);
}
// Finding a node
LinkedListNode<int> node = linkedList.Find(2);
// Inserting elements
linkedList.AddAfter(node, 2.5);
linkedList.AddBefore(node, 1.5);
// Removing elements
linkedList.Remove(2);
linkedList.RemoveFirst();
linkedList.RemoveLast();
// Checking if the list contains an element
bool contains = linkedList.Contains(1);
// Getting the number of elements
int count = linkedList.Count;
// Clearing the list
linkedList.Clear();
6.3.5 - Custom Linked List Implementations
While C# provides a built-in LinkedList<T> class, it's instructive to implement custom linked lists to understand their inner workings.
6.3.5.1 - Singly Linked List
public class SinglyLinkedList<T>
{
private class Node
{
public T Value { get; set; }
public Node Next { get; set; }
public Node(T value)
{
Value = value;
Next = null;
}
}
private Node head;
private int count;
public int Count => count;
public bool IsEmpty => Count == 0;
public void AddFirst(T value)
{
Node newNode = new Node(value);
newNode.Next = head;
head = newNode;
count++;
}
public void AddLast(T value)
{
Node newNode = new Node(value);
if (IsEmpty)
{
head = newNode;
}
else
{
Node current = head;
while (current.Next != null)
{
current = current.Next;
}
current.Next = newNode;
}
count++;
}
public bool RemoveFirst()
{
if (IsEmpty)
return false;
head = head.Next;
count--;
return true;
}
public bool RemoveLast()
{
if (IsEmpty)
return false;
if (head.Next == null)
{
head = null;
count = 0;
return true;
}
Node current = head;
while (current.Next.Next != null)
{
current = current.Next;
}
current.Next = null;
count--;
return true;
}
public bool Remove(T value)
{
if (IsEmpty)
return false;
if (EqualityComparer<T>.Default.Equals(head.Value, value))
{
head = head.Next;
count--;
return true;
}
Node current = head;
while (current.Next != null && !EqualityComparer<T>.Default.Equals(current.Next.Value, value))
{
current = current.Next;
}
if (current.Next == null)
return false;
current.Next = current.Next.Next;
count--;
return true;
}
public bool Contains(T value)
{
Node current = head;
while (current != null)
{
if (EqualityComparer<T>.Default.Equals(current.Value, value))
return true;
current = current.Next;
}
return false;
}
public void Clear()
{
head = null;
count = 0;
}
public IEnumerator<T> GetEnumerator()
{
Node current = head;
while (current != null)
{
yield return current.Value;
current = current.Next;
}
}
}
6.3.5.2 - Doubly Linked List
public class DoublyLinkedList<T>
{
private class Node
{
public T Value { get; set; }
public Node Next { get; set; }
public Node Previous { get; set; }
public Node(T value)
{
Value = value;
Next = null;
Previous = null;
}
}
private Node head;
private Node tail;
private int count;
public int Count => count;
public bool IsEmpty => Count == 0;
public void AddFirst(T value)
{
Node newNode = new Node(value);
if (IsEmpty)
{
head = newNode;
tail = newNode;
}
else
{
newNode.Next = head;
head.Previous = newNode;
head = newNode;
}
count++;
}
public void AddLast(T value)
{
Node newNode = new Node(value);
if (IsEmpty)
{
head = newNode;
tail = newNode;
}
else
{
newNode.Previous = tail;
tail.Next = newNode;
tail = newNode;
}
count++;
}
public bool RemoveFirst()
{
if (IsEmpty)
return false;
if (head == tail)
{
head = null;
tail = null;
}
else
{
head = head.Next;
head.Previous = null;
}
count--;
return true;
}
public bool RemoveLast()
{
if (IsEmpty)
return false;
if (head == tail)
{
head = null;
tail = null;
}
else
{
tail = tail.Previous;
tail.Next = null;
}
count--;
return true;
}
public bool Remove(T value)
{
if (IsEmpty)
return false;
Node current = head;
while (current != null && !EqualityComparer<T>.Default.Equals(current.Value, value))
{
current = current.Next;
}
if (current == null)
return false;
if (current == head)
return RemoveFirst();
if (current == tail)
return RemoveLast();
current.Previous.Next = current.Next;
current.Next.Previous = current.Previous;
count--;
return true;
}
public bool Contains(T value)
{
Node current = head;
while (current != null)
{
if (EqualityComparer<T>.Default.Equals(current.Value, value))
return true;
current = current.Next;
}
return false;
}
public void Clear()
{
head = null;
tail = null;
count = 0;
}
public IEnumerator<T> GetEnumerator()
{
Node current = head;
while (current != null)
{
yield return current.Value;
current = current.Next;
}
}
public IEnumerator<T> GetReverseEnumerator()
{
Node current = tail;
while (current != null)
{
yield return current.Value;
current = current.Previous;
}
}
}
6.3.5.3 - Circular Linked List
public class CircularLinkedList<T>
{
private class Node
{
public T Value { get; set; }
public Node Next { get; set; }
public Node(T value)
{
Value = value;
Next = null;
}
}
private Node head;
private Node tail;
private int count;
public int Count => count;
public bool IsEmpty => Count == 0;
public void AddFirst(T value)
{
Node newNode = new Node(value);
if (IsEmpty)
{
head = newNode;
tail = newNode;
newNode.Next = newNode; // Point to itself
}
else
{
newNode.Next = head;
head = newNode;
tail.Next = head; // Update the tail's next to point to the new head
}
count++;
}
public void AddLast(T value)
{
Node newNode = new Node(value);
if (IsEmpty)
{
head = newNode;
tail = newNode;
newNode.Next = newNode; // Point to itself
}
else
{
newNode.Next = head;
tail.Next = newNode;
tail = newNode;
}
count++;
}
public bool RemoveFirst()
{
if (IsEmpty)
return false;
if (head == tail)
{
head = null;
tail = null;
}
else
{
head = head.Next;
tail.Next = head;
}
count--;
return true;
}
public bool RemoveLast()
{
if (IsEmpty)
return false;
if (head == tail)
{
head = null;
tail = null;
}
else
{
Node current = head;
while (current.Next != tail)
{
current = current.Next;
}
current.Next = head;
tail = current;
}
count--;
return true;
}
public bool Remove(T value)
{
if (IsEmpty)
return false;
if (EqualityComparer<T>.Default.Equals(head.Value, value))
return RemoveFirst();
if (EqualityComparer<T>.Default.Equals(tail.Value, value))
return RemoveLast();
Node current = head;
while (current.Next != head && !EqualityComparer<T>.Default.Equals(current.Next.Value, value))
{
current = current.Next;
}
if (current.Next == head)
return false;
current.Next = current.Next.Next;
count--;
return true;
}
public bool Contains(T value)
{
if (IsEmpty)
return false;
Node current = head;
do
{
if (EqualityComparer<T>.Default.Equals(current.Value, value))
return true;
current = current.Next;
} while (current != head);
return false;
}
public void Clear()
{
head = null;
tail = null;
count = 0;
}
public IEnumerator<T> GetEnumerator()
{
if (IsEmpty)
yield break;
Node current = head;
do
{
yield return current.Value;
current = current.Next;
} while (current != head);
}
}
6.4.4 - Linked List Operations
Here are the common operations performed on linked lists:
6.4.4.1 - Insertion
Insertion in a linked list can be done at the beginning, end, or at a specific position:
// Insertion at the beginning
public void AddFirst(T value)
{
Node newNode = new Node(value);
newNode.Next = head;
head = newNode;
count++;
}
// Insertion at the end
public void AddLast(T value)
{
Node newNode = new Node(value);
if (IsEmpty)
{
head = newNode;
}
else
{
Node current = head;
while (current.Next != null)
{
current = current.Next;
}
current.Next = newNode;
}
count++;
}
// Insertion at a specific position
public void InsertAt(T value, int position)
{
if (position < 0 || position > count)
throw new ArgumentOutOfRangeException(nameof(position));
if (position == 0)
{
AddFirst(value);
return;
}
Node newNode = new Node(value);
Node current = head;
for (int i = 0; i < position - 1; i++)
{
current = current.Next;
}
newNode.Next = current.Next;
current.Next = newNode;
count++;
}
6.4.4.2 - Deletion
Deletion in a linked list can be done at the beginning, end, or at a specific position:
// Deletion at the beginning
public bool RemoveFirst()
{
if (IsEmpty)
return false;
head = head.Next;
count--;
return true;
}
// Deletion at the end
public bool RemoveLast()
{
if (IsEmpty)
return false;
if (head.Next == null)
{
head = null;
count = 0;
return true;
}
Node current = head;
while (current.Next.Next != null)
{
current = current.Next;
}
current.Next = null;
count--;
return true;
}
// Deletion at a specific position
public bool RemoveAt(int position)
{
if (position < 0 || position >= count)
return false;
if (position == 0)
return RemoveFirst();
Node current = head;
for (int i = 0; i < position - 1; i++)
{
current = current.Next;
}
current.Next = current.Next.Next;
count--;
return true;
}
6.4.4.3 - Traversal
Traversal in a linked list involves visiting each node in the list:
// Traversal
public void Traverse(Action<T> action)
{
Node current = head;
while (current != null)
{
action(current.Value);
current = current.Next;
}
}
6.4.4.4 - Searching
Searching in a linked list involves finding a node with a specific value:
// Searching
public bool Contains(T value)
{
Node current = head;
while (current != null)
{
if (EqualityComparer<T>.Default.Equals(current.Value, value))
return true;
current = current.Next;
}
return false;
}
public int IndexOf(T value)
{
Node current = head;
int index = 0;
while (current != null)
{
if (EqualityComparer<T>.Default.Equals(current.Value, value))
return index;
current = current.Next;
index++;
}
return -1;
}
6.4.4.5 - Reversal
Reversing a linked list involves changing the direction of the links:
// Reversal
public void Reverse()
{
if (IsEmpty || head.Next == null)
return;
Node previous = null;
Node current = head;
Node next = null;
while (current != null)
{
next = current.Next;
current.Next = previous;
previous = current;
current = next;
}
head = previous;
}
6.4.5 - Linked List Applications
Linked lists are used in various applications:
- Dynamic Memory Allocation: Linked lists are used in memory management systems to keep track of free memory blocks.
- Implementation of Other Data Structures: Linked lists are used to implement stacks, queues, and hash tables.
- Undo Functionality: Linked lists can be used to implement undo functionality in applications.
- Music Player: Linked lists can be used to create playlists in music players.
- Browser History: Linked lists can be used to implement browser history.
6.4.6 - Linked List Algorithms
Here are some common algorithms used with linked lists:
6.4.6.1 - Detecting a Cycle
Floyd's Cycle-Finding Algorithm (also known as the "tortoise and hare" algorithm) can be used to detect a cycle in a linked list:
public bool HasCycle()
{
if (head == null || head.Next == null)
return false;
Node slow = head;
Node fast = head;
while (fast != null && fast.Next != null)
{
slow = slow.Next;
fast = fast.Next.Next;
if (slow == fast)
return true;
}
return false;
}
6.4.6.2 - Finding the Middle Node
The "slow and fast pointer" technique can be used to find the middle node of a linked list:
public T FindMiddle()
{
if (IsEmpty)
throw new InvalidOperationException("List is empty");
Node slow = head;
Node fast = head;
while (fast != null && fast.Next != null)
{
slow = slow.Next;
fast = fast.Next.Next;
}
return slow.Value;
}
6.4.6.3 - Merging Two Sorted Linked Lists
Two sorted linked lists can be merged into a single sorted linked list:
public static SinglyLinkedList<T> MergeSorted<T>(SinglyLinkedList<T> list1, SinglyLinkedList<T> list2) where T : IComparable<T>
{
SinglyLinkedList<T> result = new SinglyLinkedList<T>();
// Implementation details omitted for brevity
return result;
}
6.4.7 - Linked List vs. Array
Here's a comparison of linked lists and arrays:
| Feature | Linked List | Array |
|---|---|---|
| Memory Allocation | Dynamic | Static |
| Access Time | O(n) | O(1) |
| Insertion/Deletion Time | O(1) (with reference to the node) | O(n) |
| Memory Overhead | Higher (due to pointers) | Lower |
| Random Access | No | Yes |
| Cache Locality | Poor | Good |
6.4.8 - Performance Considerations
When working with linked lists, consider the following performance aspects:
- Access Time: Linked lists have O(n) access time, which is slower than arrays' O(1) access time.
- Insertion/Deletion Time: Linked lists have O(1) insertion/deletion time (with reference to the node), which is faster than arrays' O(n) insertion/deletion time.
- Memory Overhead: Linked lists have higher memory overhead due to the storage of pointers.
- Cache Locality: Linked lists have poor cache locality, which can affect performance on modern processors.
6.4.9 - Best Practices
Here are some best practices for working with linked lists in C#:
- Choose the Right Type: Use singly linked lists for forward-only traversal, doubly linked lists for bidirectional traversal, and circular linked lists for cyclic operations.
- Handle Edge Cases: Always handle edge cases, such as empty lists and single-element lists.
- Use Built-in Collections When Possible: Use the built-in LinkedList<T> class for most applications, as it is well-tested and optimized.
- Implement Custom Linked Lists When Needed: Implement custom linked lists when you need specific behavior not provided by the built-in collections.
- Be Mindful of Memory Management: Be aware of memory management issues, especially when implementing custom linked lists.
In the next section, we'll explore hash tables and dictionaries, which provide efficient key-value pair storage and retrieval.