Linked List
Linked list is a linear data structure
A linked list is a type of data structure in which elements are connected to each other through links or pointers. Each element (called a node) has two parts - the data and a link pointing to the next node.
A linked list is a linear data structure that includes a series of connected nodes. Here, each node stores the data and the address of the next node.
Now what is this linear data structure means?
A linear data structure stores elements sequentially, one after another, in a specific order. In a linked list, each node points to the next, forming a chain.
Key Points:
- Move in one direction.
- Elements follow a sequence, one after another.
- Unlike arrays, elements in a linked list are not necessarily stored in contiguous memory locations.
Examples:
- Array (fixed-size, contiguous memory allocation)
- Linked List (dynamic size, non-contiguous memory allocation)
- Stack (LIFO - Last In First Out)
- Queue (FIFO - First In First Out)
Non-linear: Trees, Graphs (multiple connections).
Here’s a better way to understand a linked list
Here are some real-life examples to understand linked list easily:
Think of a train! It has numerous bogies connected to each other. If we have to add a new bogie X somewhere in the middle of two bogies, say L and R, we can simply disconnect L and R and add the new one in the middle. Now L will be connected to X, and X will be connected to R.
This kind of insertion wouldn’t be possible in an array-like setup where you’d have to shift all bogies to make space for a new one.
Other examples are:
- Web Browser History 🌐 - Your browsing history stores visited pages in a linked list. You can go back and forward, just like a doubly linked list.
- Undo/Redo in Text Editors ⌨️ - Each change is stored as a node. Pressing Undo moves to the previous change, just like traversing a linked list.
- Call Logs on Phones 📞 - Your recent call history follows a linked list structure, with new calls added at the top and old calls removed when memory is full.
Why do we need linked lists?
Q - If we have a linear data structure in arrays, why do we even need linked lists?
Q - Who had the free time to come up with linked lists? 🤯
I think, it was a programmer who got tired of shifting array elements around like a game of Tetris?
Jokes aside, now we already knew the benefits of linked lists.
But why? because, in an array, it’s much more difficult to insert or add an element. Even in a dynamic array, all the other elements would have to shift in order to make space if we have to add an element at the start of the index.
Also, there is a possibility that you’d need to allocate more memory space to the array before inserting an element.
Arrays are better when random access is needed, but linked lists shine when modifications are frequent.
Comparison with arrays for better clarity 🚀
| Array | Linked List |
|---|---|
| Elements are stored in contiguous memory locations | Elements are connected using pointers |
| Supports random access to elements | Only supports sequential access, one after another to elements |
| Insertions/deletions are tricky: elements need to be shifted | Insertions/deletions can be done efficiently without shifting |
| Fixed memory: static memory allocation | Dynamic memory allocation at runtime |
| Elements are independent of each other | Each node points to the next node or both the next and the prev node |