SLLs

SLLs, short for singly linked lists, are a class of linear data structures composed of nodes. Each node contains two fields: a data element and a reference to the next node in the sequence. The list is accessed via a reference to the first node, called the head. The final node’s next reference typically points to null, indicating the end of the list. Some variants are circular, where the last node points back to the head.

Key properties and operations

- Traversal: starting at the head, follow next references until reaching null (or the loop in circular variants).

- Insertion: can be performed at the head in constant time, or after a specified node in constant time if a direct reference to that node is available. Inserting at the tail is constant time if the list maintains a tail reference; otherwise it requires a full pass.

- Deletion: removing the head is O(1); deleting after a given node is O(1) if the previous node is known. Deleting arbitrary nodes typically requires searching for the node and its predecessor, which is O(n).

Performance and design

- Access time for a specific position is O(n) since nodes must be traversed sequentially.

- SLLs use dynamic memory and do not require contiguous storage, but each node carries an extra reference, increasing per-element memory.

- Variants include circular singly linked lists and the use of a dummy head (sentinel) to simplify edge cases. A tail pointer or a circular design can improve tail operations or enable certain queue implementations.

Use cases and trade-offs

SLLs are well-suited for scenarios requiring frequent insertions and deletions, such as stacks, queues, or dynamic graph representations (adjacency lists). They offer flexible, non-contiguous memory usage but sacrifice fast random access and data locality compared with arrays. Compared with doubly linked lists, SLLs use less memory per node at the cost of slower backward traversal.