Linked List vs Arrays

Arrays give O(1) index access but costly middle insert/delete; linked lists give O(1) insert/delete at a known node (with pointer setup) but O(n) search by value without extra structure. The table below summarizes common differences (typical implementations in C-style terms).

Arrays vs linked lists — comparison

Aspect	Array	Linked list
Memory layout	Elements stored in one contiguous block; index maps directly to address.	Nodes can be anywhere in memory; each node links to the next (and maybe previous).
Size	Length often fixed at creation (static) or managed by resizing a dynamic array (may copy whole block).	Grows/shrinks by allocating or freeing nodes; no need to predeclare final size.
Per-element overhead	Usually data only (no extra pointers inside the sequence itself).	Each node stores data + pointer(s) (`next`, and `prev` if doubly linked).
Access by index / position	O(1) random access: `arr[i]`.	O(n) in the worst case: walk from head (no constant-time index).
Search (unsorted, by value)	O(n) linear scan.	O(n) linear scan from the head.
Insert / delete at front	O(n) if you must shift all elements to keep order.	O(1) if you only update head pointer (singly list).
Insert / delete in the middle	O(n) to shift elements after the position.	O(1) pointer rewiring if you already hold a pointer to that node; finding the spot is still often O(n).
Insert / delete at end	O(1) amortized for a dynamic array with spare capacity; O(n) if resize/copy is needed.	O(1) with a tail pointer; O(n) if you must walk from head each time.
Cache & locality	Usually better: sequential access hits cache-friendly contiguous memory.	Often worse: chasing pointers jumps around memory.