Linked-List Insertion, Traversal and Deletion

The head refers to the first node, or is null/None for an empty list. Each node stores data and a next reference; the final node’s next is null. Nodes need not occupy neighbouring physical memory locations. Traversal follows references until the end, rather than adding one to a contiguous array address.

To insert at the head, first make a new node whose next refers to the old head, then replace head with the new node. Losing the old reference before linking it can make the previous chain unreachable. Inserting after a known node similarly links the new node to its former successor before replacing that node’s next.

Deleting a node means making the predecessor refer to the target’s successor. If the target is the head, head must change instead. The example uses a temporary dummy node before the head so that both situations use the same predecessor update. It returns the possibly changed head to the caller.

Search stops at the first matching value under this contract. If no match exists, leave the chain unchanged. Deleting an empty list must not dereference a missing node. Multiple equal values need a stated policy: deleting the first match differs from deleting every match. Unlinking in this Python example does not manually free a memory address; object reclamation is handled by the runtime.

Scroll the diagram to see the full view.

Given the head alone, finding a particular position or value generally requires following up to n links, giving linear time. A local insertion or deletion with a known predecessor can update links in constant time, but finding that predecessor can still cost linear time. Do not quote the local update cost as the cost of an entire search-and-delete request.

Arrays offer direct indexed access under their model, while linked structures can grow through separately allocated nodes. Linked nodes need reference storage and can have less favourable memory locality. A correct implementation preserves reachability and termination; introducing a cycle can make an ordinary null-terminated traversal loop forever. Trace arrows as well as values when debugging.

class Node:
    def __init__(self, value, next_node=None):
        self.value = value
        self.next = next_node

def delete_first(head, target):
    dummy = Node(None, head)
    previous = dummy
    while previous.next is not None:
        if previous.next.value == target:
            previous.next = previous.next.next
            break
        previous = previous.next
    return dummy.next

def values(head):
    result = []
    while head is not None:
        result.append(head.value)
        head = head.next
    return result

head = Node(3, Node(5, Node(7)))
head = delete_first(head, 5)
print(values(head))
head = delete_first(head, 3)
print(values(head))

Attempt the task before opening its worked response. Record each change of state, explain the rule used, and check the result against the original requirements. Code examples labelled Python 3 use that language’s conventions; pseudocode states its own assumptions.