thesarfo

Reference

Linked List Operations: Pseudocode & Boundary Conditions

Add/remove at head and tail, traversal, and node deletion, with the boundary conditions each operation needs to handle.

views 0

Adding to the Head

  1. Node creation — create a new node with the given data.
  2. Store current head — keep a reference to the current head of the list.
  3. Update head — set the new node as the new head of the list.
  4. Link nodes — if the list wasn’t empty (the current head isn’t null), link the new head node to the previous head node.
function addToHead(data):
    newHead = new Node(data)         // Create a new node with the given data
    currentHead = head               // Store the current head of the list
    head = newHead                   // Set the new node as the head of the list
    if currentHead is not null:      // If the list was not empty
        head.setNextNode(currentHead) // Link the new head to the previous head

Adding to the Tail

  1. Initialization — start with the head of the list.
  2. Empty list check — if the list is empty, create a new node and set it as the head.
  3. Traversal — if the list is not empty, traverse to the last node.
  4. Addition — create a new node and add it as the next node of the current last node.
function addToTail(data):
    tail = head                    // initialize a variable tail to the head
    if tail is null:                  // Check if the list is empty
        head = new Node(data)         // Create a new node as the head
    else:
        while tail.getNextNode() is not null:
            tail = tail.getNextNode() // Traverse to the last node
        tail.setNextNode(new Node(data)) // Add the new node at the end

Removing the Head

  1. Store reference to current head — keep a reference to the current head of the list.
  2. Check for empty list — if the list is empty (current head is null), return null; there’s no head to remove.
  3. Update head — set the head of the list to the next node after the current head.
  4. Return removed node’s data — return the data of the removed head node.
function removeHead():
    currentHead = head                  // Store a reference to the current head node
    if currentHead is null:             // If the list is empty
        return null                     // Return null as there's no head to remove
    head = currentHead.getNextNode()    // Update the head to the next node
    return currentHead.getData()        // Return the data of the removed head node

Traversing a Linked List

class Node<TreeNode> {
    TreeNode data;
    Node next;


    Node(TreeNode data) {
        this.data = data;
    }


    void traverse(Node head) {
        Node curr = head;


        while (curr != null) {
            print(curr.data);
            curr = curr.next;
        }
    }


    // using the traverse function
    void main() {
        traverse(head);
    }
}

Deleting a Node at a Position

  1. Check if the node to delete is the head.
  2. Traverse to the node just before the target position.
  3. Remove the target node.
void main() {
    delete(head, 3);
}


void delete(Node head, int pos) {
    if (pos == 0) {
        head = head.next;
        return;
    }
    Node currentNode = head;


    for (int i = 0; i < pos - 1; i++) {
        currentNode = currentNode.next;
    }
    currentNode.next = currentNode.next.next;
}

Removing All Occurrences of a Value

  1. Skip all nodes at the beginning of the list that have the value k.
  2. If, after that loop, the list is null, it was entirely composed of nodes with value k — return null.
  3. Traverse the rest of the list: if the next node’s value equals k, remove it; otherwise advance to the next node.
ListNode<Integer> solution(ListNode<Integer> l, int k) {
    while (l != null && l.value == k) {
        l = l.next;
    }


    if (l == null) {
        return null;
    }


    ListNode<Integer> current = l;
    while (current.next != null) {
        if (current.next.value == k) {
            current.next = current.next.next;
        } else {
            current = current.next;
        }
    }


    return l;
}

Boundary Conditions to Consider

(Notes below adapted from Rob Edwards’ data structures lecture material.)

Things to consider whenever you’re working with any data structure:

  1. Empty data structure
  2. A single element in the data structure
  3. Adding/removing from the beginning
  4. Adding/removing from the end
  5. Working in the middle of the data structure

Adding to the Head

  1. Create a new node.
  2. Make node.next point to the same node the head currently points to.
  3. Make head point to the new node.
public void addFirst(E obj) {
    Node<E> node = new Node<E>(obj);
    node.next = head;


    head = node;
    currentSize++; // keep track of the size of the linked list by incrementing or decrementing it
}

Adding to the Tail

  1. Introduce a dummy/temp node that points to the head of the linked list.
  2. temp is not the last node as long as its .next is not null.
  3. Loop while temp.next is not null, advancing temp to temp.next each time.
  4. Once temp.next is null, we’ve reached the end of the list.
  5. Make the last node point to our new node.
public void addLast(E obj) {
    Node<E> temp = head;
    Node<E> newNode = new Node<E>(obj);


    while (temp.next != null) {
        temp = temp.next;
    }
    temp.next = newNode;
}
  1. If the list is empty, head points to null — so temp.next throws a null pointer exception.
  2. We need to check for the empty-list case first, and point head at the new node directly.
public void addLast(E obj) {
    if (head == null) {
        head = newNode;
        currentSize++;
        return;
    }
    Node<E> temp = head;
    Node<E> newNode = new Node<E>(obj);


    while (temp.next != null) {
        temp = temp.next;
    }
    temp.next = newNode;
}

The above is still O(n) — the loop runs once per element in the list. To optimize, keep a tail pointer to the last element, so addLast never has to traverse at all:

public void addLast(E obj) {
    Node<E> newNode = new Node<E>(obj);
    if (head == null) {
        head = tail = node;
        currentSize++;
        return;
    }


    tail.next = newNode;
    tail = newNode;
    currentSize++;
    return;
}

Removing the Head (and Returning Its Data)

  1. The first node is whatever head points to.
  2. To remove it, make head point to the second node — the old first node becomes garbage collected: head = head.next.
  3. But on an empty list, head is already null, so head = head.next throws a null pointer exception — guard against that first.
public E removeFirst() {
    if (head == null) {
        return null;
    }
}
  1. When the list isn’t empty, we need the removed node’s data before we lose the reference to it, so store it in a temp variable.
public E removeFirst() {
    if (head == null) {
        return null;
    }
    E temp = head.data;
}
  1. If there’s only one element, both head and tail need to be updated.
public E removeFirst() {
    if (head == null) {
        return null;
    }
    E temp = head.data;


    if (head == tail) {
        head = tail = null;
    } else {
        head = head.next;
    }
    currentSize--;


    return temp;
}

Removing the Tail

We can’t just move tail backwards in a singly linked list — there’s no previous-pointer to walk. So we start from the front instead, using two pointers, previous and current. previous starts at null and current starts at the head; both advance together until current.next is null (or equals tail), at which point previous sits right before current — so previous.next = null removes the last element.

public E removeLast() {
    if (head == null) {
        return null;
    }


    // single element
    if (head == tail) {
        return removeFirst();
    }


    Node<E> current = head;
    Node<E> previous = null;


    while (current.next != null) {
        previous = current;
        current = current.next;
    }
    previous.next = null;
    tail = previous;
    currentSize--;
    return current.data;
}