Understanding Linked Lists
What are Linked Lists?
They are a way to organize data. It is a list that is made of nodes where every node only has access to its data and knows where the next element in the list is.
In code, a typical linked list looks like this
The challenging part about linked lists is that you can’t use methods that work for arrays or objects, and you can’t iterate, add, remove or any other common operation in the same way. They are different and require a different way of thinking.
Why use linked lists instead of arrays?
In memory, when you create an array, you have to separate space that is together equal to the size of the array. If that size changes (you add an element), then you have to relocate that whole array if there isn’t space for it where it is.
Linked lists are more efficient memory-wise. Since they know where their neighbors are, you can store them separately in memory.
There are four types of linked lists:
- Singly Linked Lists — the last node points to null.
2. Circular Linked Lists — the last node points to the first node.
3. Doubly Linked Lists — every node has a next and a previous. The first node’s previous is set to null. The last node’s next is set to null.
4. Circular Doubly Linked Lists — every node has a next and a previous. The first node’s previous is set to the last node. The last node’s next is set to the first node.
Creating a list of elements using linked lists
You create all the nodes and set their next node to the correct one.
Iterating over linked lists
To iterate over linked lists, while loops are very useful. The only thing you have access to is a given node. Which means, you only have its data and it’s next. You can keep calling each node’s next until you reach the last node. Like so:
Adding elements to linked lists
To add elements is a little tricky. You need a node in the linked list so that you can add a node. In this case, I will insert a new node after a given node in three steps.
- Create a new node with the given value
- Assign the new node’s next to be equal to the given node’s next
- Assign the given node’s next to be equal the new node
© Kenneth Young Castro 2019