Beginner · INTERACTIVE LESSON

Singly linked list

Follow stable node identities, next links and head/tail updates while inserting, deleting and traversing a singly linked list.

The interactive player is loading. If it does not appear, you can still read the explanation below.

THE IDEA BEHIND THE STEPS

How it works

A singly linked list stores values in nodes with a next reference. Head identifies the first node; tail identifies the last, whose next is null. Empty lists have null head and tail. Duplicate values remain distinct: IDs follow insertion operation numbers and are never reused. Indices describe current traversal positions, not memory addresses.

Start empty and enter at most 32 operations with integer values -999 through 999. insertHead(value) and insertTail(value) add at either end. insert(index, value) allows positions 0 through size; delete(index) allows 0 through size-1 and returns the removed value. traverse() outputs values in link order. Negative or out-of-range indices (within the teaching input bound -32 to 32) return invalid index without mutation, then later operations continue. Malformed operations are rejected before creating a trace.

Each operation shows its initial check, predecessor visits where needed, the planned link update, and the resulting chain. Insertion initializes new.next before connecting it to head or the predecessor; deletion bypasses its victim. Head/tail changes are shown explicitly, including deletion of the only node.

With maintained head and tail and constant-time allocation, head insertion/deletion and tail insertion take O(1) best/worst time. Indexed insertion/deletion use O(n) worst time to find the predecessor, O(1) at the head. Deleting the tail still needs a scan for its predecessor. Traversal takes O(n) time. Storage is O(n) for the nodes with O(1) auxiliary operation space, excluding traversal output and replay traces. The simulator uses a map and copies snapshots; rendering and snapshot overhead are not the conceptual linked-list complexity.

Visits count nodes read during predecessor search or output by traverse, not direct head/tail accesses. Link assignments count initialization of new.next and every assignment to head, tail or an existing next, excluding size, temporary pointers, allocation and replay copying. Completed operations include rejected attempts. Reduced motion preserves every state without movement.