Arrays & Linked Lists
These are the two fundamental linear data structures.
Arrays
Contiguous block of memory with fixed-size elements.
| Operation | Time |
|---|---|
| Access by index | O(1) |
| Search | O(n) |
| Insert at end | O(1) amortized |
| Insert at beginning | O(n) |
| Delete | O(n) |
Linked Lists
Chain of nodes where each node points to the next.
class ListNode<T> {
value: T;
next: ListNode<T> | null = null;
constructor(value: T) {
this.value = value;
}
}
class LinkedList<T> {
head: ListNode<T> | null = null;
prepend(value: T): void {
const node = new ListNode(value);
node.next = this.head;
this.head = node;
}
find(value: T): ListNode<T> | null {
let current = this.head;
while (current) {
if (current.value === value) return current;
current = current.next;
}
return null;
}
}
When to Use Which?
- Arrays: Random access needed, mostly reading data
- Linked Lists: Frequent insertions/deletions at the beginning