Imagine keeping a playlist in order. You could place every song in numbered slots, or give each song a note pointing to the next one. Those are the central ideas behind arrays and linked lists.
Arrays keep elements together
An array stores elements in indexed positions. Because an index can be calculated directly, reading the item at position i takes constant time, O(1). Arrays are compact and cache-friendly, which makes scanning them fast. In a dynamic array, appending is usually amortized O(1), though an occasional resize copies the elements.
Inserting near the beginning is different: later elements must shift, so that operation takes O(n).
Linked lists connect separate nodes
A linked list stores each value in a node with a reference to another node. In a doubly linked list, nodes also point backward. Once you already have a node reference, adding or removing a neighbor can be O(1). But finding the node at position i requires walking from the head, taking O(n).
How to choose
- Choose an array when you need fast indexing, compact storage, or frequent iteration.
- Choose a linked list when you already have node references and frequently insert or remove nearby items.
- Do not choose by Big O alone: memory use, cache behavior, and the operations your program actually performs matter too.
Before selecting a structure, list the operations your program needs and how often each occurs. That small habit often makes the best choice clear.