A linked list is a sequence of nodes where each node stores a value and a pointer to the next node. Unlike arrays, nodes are not contiguous in memory — they can be scattered anywhere, connected only by pointers.
This structure makes insertion and deletion at the head O(1) — just redirect a pointer. But it makes random access O(n) — you must walk from the head every time. It is the fundamental trade-off of linked lists versus arrays.
Each node holds its value and a 'next' pointer to the following node. The last node points to null. The list is accessed only through the head pointer — lose that and you lose the list.
O(1) prepend & head removal Prepending (adding to the front) and removing the head both just update a single pointer. No shifting, no copying — constant time regardless of list length.
To reach index k, you must follow k 'next' pointers from the head. There is no formula like arrays. This makes random access slow — O(n) in the worst case.
Every node stores at least one extra pointer. For a list of 1000 integers, that is 1000 extra pointers. Arrays have zero per-element overhead. Linked lists use more memory but gain flexible O(1) head operations.
TIPTry prepend vs append — notice how prepend is instant (one pointer update) while append must walk to the tail first. Then search for a value and watch the traversal animate node by node. This is why linked lists are O(n) for search.