What is a Linked List? How does it differ from an Array?
Linked List vs Array
A Linked List is a linear data structure composed of nodes, where each node stores data and one or more references to other nodes. Unlike an array, linked-list nodes do not need to occupy contiguous memory. This makes insertion and deletion efficient when the relevant node or predecessor is already known, but random access is inefficient.
- 1
Array: contiguous memory and O(1) indexed access.
- 2
Linked List: non-contiguous nodes connected through references.
- 3
Array insertion/deletion in the middle is generally O(n).
- 4
Linked List insertion/deletion can be O(1) when the required position or node reference is already available.
- 5
Linked Lists have additional memory overhead for node references.
- 6
Arrays generally provide better cache locality.
Scenario Questions
0-2 years experience
- 1If you need to store a list of user IDs that can grow and shrink frequently, would you choose an array or a linked list, and how would you implement insertion at the front?
- 2Imagine you have an array of size 10 and you need to insert an element at index 3; what steps does the runtime take, and how would that differ if you used a singly linked list?
- 3What happens internally when you try to access the 5th element of a singly linked list?
2-5 years experience
- 1We have a feature that streams log entries into a buffer that occasionally needs to drop the oldest entry. How would you use a linked list to implement this, and why might an array be problematic?
- 2During a code review, a teammate replaced a linked list with a dynamic array to improve cache performance, but the system started crashing when the list grew beyond a certain size. What could be the cause?
- 3You need to reverse a linked list in place. Walk me through your approach and its time/space complexity compared to reversing an array.
5-8 years experience
- 1Our service maintains a large in‑memory graph where adjacency lists are stored as linked structures. At scale, what are the memory and performance implications of using linked lists versus contiguous arrays for adjacency storage?
- 2Design a memory‑pool allocator for a high‑throughput messaging queue that uses linked lists for free‑node management. What trade‑offs do you consider versus a simple array‑based free list?
- 3We need to support fast random access to elements while also allowing O(1) insertions/deletions in the middle. How would you combine linked list and array concepts, and what are the pitfalls?
8+ years experience
- 1Our legacy codebase stores transaction logs in fixed‑size arrays, causing frequent reallocations. Propose a migration plan to a linked‑list based storage that minimizes downtime and ensures data integrity.
- 2Across multiple services, some teams use arrays for ordered data while others use linked lists, leading to inconsistent performance characteristics. How would you establish a unified data‑structure strategy at the architecture level?
- 3Considering future scaling to billions of records, evaluate the long‑term maintainability and operational costs of choosing a linked list over an array for a persistent on‑disk index structure.
Follow-up Questions
- What are the time and space complexities for common operations on each structure?
- How does cache locality influence performance in real workloads?
- Can you describe any edge cases that often cause bugs when using linked lists?