A linked list consists of nodes, each containing a value and a pointer to the next node (and optionally the previous node).
| Operation | Singly Linked | Doubly Linked |
|---|---|---|
| Access head | O(1) | O(1) |
| Access tail | O(n) | O(1) |
| Access by index | O(n) | O(n) |
| Insert at head | O(1) | O(1) |
| Insert at tail | O(n) | O(1) |
| Delete by value | O(n) | O(n) |
When to use: Frequent insertions/deletions at the beginning, or when size is unknown. Otherwise, prefer arrays/lists.
public class ListNode {
public int val;
public ListNode next;
public ListNode(int val = 0, ListNode next = null) {
this.val = val;
this.next = next;
}
}
// C# also has built-in LinkedList<T> (doubly linked)
var list = new LinkedList<string>();
list.AddFirst("c");
list.AddLast("d");
list.AddBefore(list.First, "b");
// But for interviews, you'll usually implement the node classReversal is the most common linked list operation. The key: track three nodes — prev, current, and next — and reverse the pointer direction at each step.
// Reverse a singly linked list — O(n), O(1) space
ListNode ReverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode next = curr.next; // save next
curr.next = prev; // reverse pointer
prev = curr; // move prev forward
curr = next; // move curr forward
}
return prev; // new head
}Two pointers traverse the list at different speeds. The slow pointer moves 1 step, the fast pointer moves 2 steps.
Applications:
// Detect cycle — O(n), O(1) space
bool HasCycle(ListNode head) {
ListNode slow = head, fast = head;
while (fast?.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) return true;
}
return false;
}
// Find middle node — O(n), O(1) space
ListNode FindMiddle(ListNode head) {
ListNode slow = head, fast = head;
while (fast?.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}