Nodes connected through links
Each node in a singly linked list holds an item and a link to the next node. A head reference identifies the first node; an empty list has none. Sequence order follows links rather than requiring consecutive storage slots for all nodes.
Traversal repeatedly follows next until an end marker is reached. Links are part of the structure’s state: losing one necessary connection can make later nodes unreachable from the head even though their contents still exist.
References: [1]
Maintaining local links at the ends
Inserting at the front points a new node to the old first node and updates the head. Removing the front makes its successor the new head. These changes touch a fixed number of links, supporting a stack without work proportional to list length.
A saved tail reference also supports queue insertion at the end and removal from the front. Transitions between empty and nonempty states must keep both references consistent, including when the final node is removed.
References: [1]
Finding a position still costs work
Constant-time insertion assumes that the location and required predecessor are already known. Finding the kth item normally requires traversing earlier nodes. A tail reference alone likewise does not reveal the predecessor needed to remove the last node of a singly linked list.
Lists and arrays can implement the same collection interface while distributing costs differently. Links need extra storage; arrays can need resizing or shifting. Choosing a representation requires the actual access and update pattern, not only one local pointer change.