I always think that the linked-list data structure sounds a little scarier than the likes of the Queue or Stack. I can admit I struggled with some of the first assignments that we were given in University as I hadn’t quite grasped the underlying concepts just yet.
Hopefully though, in this video we’ll demystify what linked lists are and what they can be used for. This should set us up nicely for tackling the implementation of a linked list in the next video!
Linked Lists
In the previous section, we looked at how we could implement the stack data structure. If you remember, this data structure adhered to LIFO or Last-In-First-Out when it came to retrieving elements from the stack and placing elements onto the stack.
Linked Lists follow this same principle. However, instead of a slice of elements, they are instead implemented using a series of nodes that are linked together.
Think of linked lists like a metal chain. Each link is directly connected to the next element in this chain.
- Singly-Linked Lists - in singly linked lists, each link in the chain only has knowledge about the next link in the chain and doesn’t know anything about the previous link in the chain.
- Doubly Linked Lists - doubly linked lists know about both the next link in the chain and the previous.