A linked list is much like any other list implementation in computer science but for the fact that the nodes carry references (also called pointers) to their next (and sometimes previous) nodes as well as the value attribute (also called the cargo or payload). Linked lists are one of the most commonly used data structures as this property allows for efficient removal and insertion of elements at any point along the list, unlike arrays which require reorganizing the entire structure and the possible need to allocate more space to it altogether as array elements must be stored continuously in memory. In addition, they are tools for implementing other common abstract data types like associative arrays, queues, stacks and S-structures, only adding to their popularity.
The first element in a linked list is known as its head while the last is its tail, though some use 'tail' to refer to every node after the head. The common linked list operations are as follows:
- create a linked list (add a head node)
- add a node:
- delete a node:
- change the order of two nodes
- count the number of items in the list
One must be quite careful with pointers when removing and inserting nodes to make sure the order is not perturbed.