Linked list and its basic operations

A linked list is a linear dynamic data structure made of nodes. Each node contains a data part (info) and a pointer (next) to the following node. The list is accessed through an external pointer start (head) and the last node's pointer is NULL. Nodes can be anywhere in memory, so the list grows and shrinks at run time.

start -> [10|*]->[20|*]->[30|NULL]

Basic operations

1. Creation: build the list by repeatedly allocating nodes.
2. Traversal: visit each node from start until NULL (display, count, sum).
3. Insertion: at the beginning (new->next = start; start = new), at the end, or after/before a given node (change links only).
4. Deletion: from the beginning (start = start->next), end, or a given node (bypass the node with prev->next = p->next and free(p)).
5. Searching: move node by node comparing info with the key; O(n).
6. Others: counting nodes, reversing, sorting, merging two lists, copying.

Insertion/deletion at a known position take O(1) with no shifting, but access to the k-th node needs O(k) traversal.