Linear Structures: Lists, Stacks, Queues, and Hash Tables

A linked list stores its elements as separate nodes scattered across memory, with each node holding a piece of data together with a pointer to the next node in the sequence, rather than relying on contiguous storage the way an array does. In a singly linked list, each node points only to its successor, so traversal moves in a single direction from the head toward the end; inserting or removing a node at the head is an O(1) operation, while reaching an arbitrary position still requires walking the list from the start, an O(n) operation. A doubly linked list adds a second pointer to each node, referencing the previous node as well as the next one, which allows traversal in both directions and makes deleting a node given a direct reference to it much simpler, at the cost of the extra memory each pointer requires.