Linked List
A Linked List is a linear data structure in which elements (called nodes) are connected using pointers.
Each node contains- A value (the actual data).
- A reference (or pointer) to the next node (and optionally to the previous node in doubly linked lists).
Types of Linked Lists
- Value: The data part
- Next: a pointer/reference to the next node.
- It moves only in one direction (forward).
- Structure: Structure: [value | next] -> [value | next] -> [value | null]
- Value: The data
- next: pointer to the next node
- prev: pointer to the previous node
- Allows bidirectional traversal
- Structure: null <- [prev | value | next] <-> [prev | value | next] -> null
Key Terminologies
Head:The first node of a linked list. It marks the entry point and points to the next node.Tail:The last node of a linked list. It points to null because there’s no node after it.Linked List Representation:It is typically represented using its head node.
Array vs Linked List — Comparison Table:
| Feature | Array | Linked List |
|---|---|---|
| Type | Linear data structure where elements are arranged in a sequence using indexes. | Linear data structure where each element (node) points to the next, forming a chain. |
| Memory Layout | Elements are stored in a contiguous (adjacent) block of memory. | Each node is stored separately and connected via pointers, allowing scattered memory locations. |
| Size | Size must be known or defined initially. Resizing is expensive if needed later. | Size is dynamic. Nodes can be added or removed without knowing the size in advance. |
| Data Stored | Only values are stored (e.g., integers, strings, etc.) | Each node stores a value along with one or more pointers (to next and/or previous nodes). |
| Access Time (Indexing) | Direct access using index (e.g., arr[3]) is fast with time complexity O(1). |
Sequential access only. To get a value, you must start at the head and traverse node by node. Time complexity O(n). |
| Insertion/Deletion | Inserting or deleting in the middle requires shifting elements. Can be time-consuming. | Insertion and deletion are faster, especially at the beginning or end, as it only involves pointer changes. |
| Memory Efficiency | Efficient memory usage as no extra space is needed for pointers. | Extra memory is used to store pointers (next/prev), making it less memory efficient. |
Use Cases: When to Use What?
| Use Case | Prefer |
|---|---|
| Access elements by index fast | Array – Arrays provide direct access to elements using an index, making it very fast (O(1)). Ideal when random access is frequent. |
| Frequent insertions/deletions at head or tail | Linked List – Inserting or removing nodes at the beginning or end is efficient in linked lists since you just change a few pointers (O(1)). |
| Static-sized data with memory-efficient storage | Array – Arrays are more memory-efficient as they don’t use extra space for pointers. Best when the number of elements is fixed or predictable. |
| Unknown size or avoid resizing overhead | Linked List – Since linked lists grow as needed, they are a better choice when the size of the data is not known upfront or changes frequently. |
| Do a lot of traversal or manipulation | Linked List – When you need to move around, insert or remove nodes repeatedly, linked lists offer better flexibility for such operations. |
