Linked List Construction

Tags

Linked List Construction

Category

Linked Lists

Difficulty

Medium

Problem Statement

Implement a doubly linked list class that supports the following operations:

  • setHead(node): Set the head of the list.
  • setTail(node): Set the tail of the list.
  • insertBefore(node, nodeToInsert): Insert nodeToInsert before node.
  • insertAfter(node, nodeToInsert): Insert nodeToInsert after node.
  • insertAtPosition(position, nodeToInsert): Insert at a 1-indexed position.
  • removeNodesWithValue(value): Remove all nodes with the given value.
  • remove(node): Remove the given node from the list.
  • containsNodeWithValue(value): Check if a value exists in the list.

Intuition

A doubly linked list maintains prev and next pointers on each node, plus head and tail references on the list itself. The key challenge is correctly updating all affected pointers during insertions and removals, especially when the operation involves the head or tail of the list. By implementing a robust remove helper and using it within other methods, we reduce code duplication and bugs.

Approach

  1. Maintain head and tail pointers on the list.
  2. Each node has value, prev, and next properties.
  3. For remove(node): update the previous node's next and the next node's prev. Handle head/tail cases.
  4. For insertion methods: first remove the node if it is already in the list (to avoid duplicates), then wire it into the correct position by updating the surrounding pointers.
  5. For insertAtPosition: traverse from the head to find the node at the given position, then use insertBefore.

Pseudocode

class DoublyLinkedList:
    head = null
    tail = null

    function remove(node):
        if node == head: head = head.next
        if node == tail: tail = tail.prev
        if node.prev: node.prev.next = node.next
        if node.next: node.next.prev = node.prev
        node.prev = null
        node.next = null

    function insertBefore(node, nodeToInsert):
        if nodeToInsert == head and nodeToInsert == tail: return
        remove(nodeToInsert)
        nodeToInsert.prev = node.prev
        nodeToInsert.next = node
        if node.prev is null:
            head = nodeToInsert
        else:
            node.prev.next = nodeToInsert
        node.prev = nodeToInsert

    function insertAfter(node, nodeToInsert):
        if nodeToInsert == head and nodeToInsert == tail: return
        remove(nodeToInsert)
        nodeToInsert.prev = node
        nodeToInsert.next = node.next
        if node.next is null:
            tail = nodeToInsert
        else:
            node.next.prev = nodeToInsert
        node.next = nodeToInsert

    function setHead(node):
        if head is null:
            head = node
            tail = node
        else:
            insertBefore(head, node)

    function setTail(node):
        if tail is null:
            setHead(node)
        else:
            insertAfter(tail, node)

    function insertAtPosition(position, nodeToInsert):
        if position == 1:
            setHead(nodeToInsert)
            return
        current = head
        p = 1
        while current and p < position:
            current = current.next
            p++
        if current is not null:
            insertBefore(current, nodeToInsert)
        else:
            setTail(nodeToInsert)

    function removeNodesWithValue(value):
        current = head
        while current is not null:
            toRemove = current
            current = current.next
            if toRemove.value == value:
                remove(toRemove)

    function containsNodeWithValue(value):
        current = head
        while current is not null:
            if current.value == value: return true
            current = current.next
        return false

Time & Space Complexity

  • setHead, setTail, insertBefore, insertAfter, remove: O(1) time, O(1) space.
  • insertAtPosition: O(n) time (must traverse to the position), O(1) space.
  • removeNodesWithValue: O(n) time (must check all nodes), O(1) space.
  • containsNodeWithValue: O(n) time, O(1) space.

Key Insights

  • Always remove a node before re-inserting it to handle the case where the node is already in the list.
  • Guard against the edge case where the node to insert is already the only node in the list (it is both head and tail).
  • Updating head and tail pointers is the most error-prone part — always check if the affected node is the head or tail.
  • A doubly linked list enables O(1) removal given a direct reference to the node, unlike a singly linked list which requires O(n) to find the predecessor.

Edge Cases

  • Operating on an empty list.
  • Inserting a node that is already in the list (should move, not duplicate).
  • Removing the head or the tail.
  • Removing the only node in the list.
  • Inserting at position 1 (becomes the new head) or at a position beyond the tail (becomes the new tail).
  • Calling removeNodesWithValue when no nodes match.

Linked mentions