Beginner LevelData Structures & Algorithms
What is the difference between an Array and a Linked List?
ā Interview Prompt: Compare Arrays and Linked Lists in terms of memory layout, time complexities for access, insertion, and deletion, and when to prefer each.
Arrays store elements in contiguous memory blocks; Linked Lists store elements in nodes scattered in memory, connected via pointers.
Time Complexity Comparison:
| Operation | Array | Linked List |
|---|---|---|
| Access by index | $O(1)$ | $O(N)$ |
| Search | $O(N)$ | $O(N)$ |
| Insert at head | $O(N)$ (shift) | $O(1)$ |
| Insert at tail | $O(1)$ amortized | $O(N)$ (singly) / $O(1)$ (doubly with tail ptr) |
| Delete at head | $O(N)$ (shift) | $O(1)$ |
When to Use:
ā¢
Array: Random index access is frequent; cache locality matters; fixed or slowly growing data.
ā¢
Linked List: Frequent insertions/deletions at the head/middle; size is highly dynamic.
Code Implementation Example
typescript
// Singly Linked List Node
class ListNode<T> {
value: T;
next: ListNode<T> | null = null;
constructor(value: T) { this.value = value; }
}
// O(1) head insertion ā impossible at O(1) with an array
function insertAtHead<T>(head: ListNode<T> | null, value: T): ListNode<T> {
const node = new ListNode(value);
node.next = head;
return node; // new head
}š”O(1) head insertion with a Singly Linked List.
šÆ Interview Key Takeaway
Arrays provide O(1) random access; Linked Lists provide O(1) head insertions. Choose based on the dominant operation in your algorithm.
#DSA#Array#Linked List#Data Structures#Beginner
Back to all Data Structures & Algorithms Questionsā