Data Structures: Linked List
Last week I dove in to the hash table data structure, and while the implementation is pretty straight-forward, it often hinges on another popular data structure, the linked list. The concept of a linked list has boundless applications and variations to help you organize data in useful ways. I’ll go through some of these variations and how they can help you in creating complex algorithmic solutions.
Linked List Basics
A linked list is a relatively simple set of objects. They are typically set up as an object class, with a data attribute and a next attribute, pointing to the next item in the list.
You can think of each of these objects as a ‘node’, with their own data, and a reference to the next item in the list. Your node class can look something like this:
class ListNode {
constructor(data) {
this.data = data
this.next = null
}
}Now we can create a few nodes in our list:
const nodeOne = new ListNode(’foo’)
const nodeTwo = new ListNode(’bar’)
const nodeThree = new ListNode(’pan’)nodeOne.next = nodeTwo
nodeTwo.next = nodeThree
and our linked class can be set up like this:
class LinkedList {
constructor(head = null) {
this.head = head
}
}Let’s put our whole list object together:
const list = new LinkedList(nodeOne)We are setting out first node as the head of the linked list, and we effectively have an object that looks like this:
// list{
head: {
value: ’foo’
next: {
value: ’bar’
next: {
value: ’pan’
next: null
}
}
}
}
}
Linked List Benefits
What does organizing our data like this do for us? Well since our list is not organized by indeces, we can add or remove items easily without reorganizing and rebuilding the entire list. With an array, this wouldn’t be possible.
Linked List Drawbacks
On the other side of the coin, because we don’t have and index associated with each item, we can’t use random lookup strategies for retrieval. We always need to start at the head node, and iterate down the list until we reach the node we are interested in. We also need to store the ‘pointer’ in memory as we iterate, so this extra memory needs to be allocated.
Other Types of Linked Lists
- Circular Linked List
If our final node references the first node, then it allows us to start from anywhere in the list and loop around, as long as we are sure to stop when we reach the node we started at.
These become incredibly useful if you need to loop around a list and perform as action on each node. For example, if an operating system needs to loop through a number of running applications, and give each one an allocation of time to perform its actions, it will keep these in a linked list. We can always return to the top of the list by referencing the next of the final node.
2) Doubly Linked List
If we add a prev attribute to our nodes, we gain the ability to move in either direction along our linked list. This doesn’t add much more complexity to the nodes, but gives us more flexibility in how we deal with the object.
Deletion from a doubly linked list is more efficient, and inserting a node behind a particular node now becomes much easier, as we don’t need to traverse through the entire list again to reach it.
However, even more memory will need to be allocated for the extra pointer using the doubly linked list. We would need to modify previous as well as next pointers for every operation, compared to a singly linked list.
Conclusion
Linked lists in all of thier forms can be useful to implement in our solutions. I hope you enjoyed this introduction to the data structure and happy coding!
