The Linked List Data Structure
So you’re interested in data structures, and you come across linked lists. You wonder to yourself, “what the heck is that?”.
What if I told you that you’ve already been exposed to linked lists? If you’ve ever used a music playlist app, most of them have: “previous track”, “current track”, and “next track”. Another example would be the browser you’re using to read this article! Again there is a: “previous page”, “current page”, and “next page”.
Great! We’re already familiar with the real-life applications of linked lists. Now let’s break it down into smaller pieces and understand what happens behind the scenes, just like any good developer should do.
Before understanding what a linked list is and why it is important, we must ask a few questions to dig deeper.
1. Is it a linear or non-linear data structure?
2. How does it perform in comparison to other data structures?
3. What are the advantages and disadvantages (if any)?
4. When should we use it, and why?
5. How do we go about creating one?
Linear vs non-linear data structures
As simple as it might sound, a linked list describes itself very well in its name. It is a list (of nodes) that are linked together, similar to the image above illustrating a metal chain linked together in sequence. Since the nodes are linked together, that also means they reference each other which is ultimately what makes it a list.
That being said, a linked list is most certainly a linear data structure. If you’re not too familiar with what the difference is between a linear vs non-linear data structure, click here to read more and familiarize yourself before moving on.
Types of data structures
There are many data structures out there, some include:
- Linear — arrays, queues, stacks, linked lists
- Non-linear — graphs, trees
Since linked lists are linear, we’ll be primarily focusing on comparing it to other linear data structures such as an array. We are all familiar with arrays, as this is one of the most commonly used ways to store data. But why would we use a linked list over an array? The answer to that depends on what you’re trying to do with your code, and how large your computer program is.
If you plan to have a large data set, that means there might be larger concerns around efficiency. We should ask ourselves how often we’ll need to insert or delete items from our data sets. Another good question would be whether or not we need to access specific items in our data, and if so how frequently?
Below is a table that compares arrays and linked lists:
If you notice in the table, there’s no column that highlights “pros and cons”. That’s because again, we must really think about what we are trying to accomplish here. Since technology is so diverse and programs will vary from developer to developer, a good way to think about this could be through a logical flow chart to make sure we aren’t missing anything. Stack overflow is a great resource — you can access this flow chart here.
Creating a linked list and implementing methods
Instead of trying to re-create a linked list on our own right off the bat, let’s first take a look at CS Dojo’s guide since it already has hundreds of thousands of trusted viewers (let alone millions of YouTube subscribers):
Now that we have a better understanding, let’s try this on our own. We will build a singly linked list which has its nodes linked in one direction from head-to-tail (there are several other linked list types, but let’s start with the basics).
We can use a beginner-friendly language to build the linked list, in this case Javascript. Although before building the linked list, we need to create the individual nodes themselves with a new Node class. Go ahead and run this following code in your console:
class Node {
constructor(data, next = null) {
this.data = data;
this.next = next;
}
}const firstNode = new Node("I am a node");console.log(firstNode)
// Node { data: 'I am a node', next: null }
After logging the output to the console we can see that the Node gets printed out and contains a string that says ‘I am a node’ for its data value, and the next value is null because we haven’t created that yet. Before creating a second node, let’s go ahead and create a new LinkedList class.
class LinkedList {
constructor() {
this.head = null;
this.size = 0;
}
}
The above code will have a constructor which creates a head and sets it to null, based on the value of “this”. If using “this” is unfamiliar to you, have a look at this video from YouTuber Fun Fun Function here. He takes a fun approach to object creation.
Okay that was the easy part, but it isn’t really doing anything just yet. All it tells us is the head is null, and the size of the list is zero because there are no linked nodes. To cover the basics we will create a few more class methods:
- Insert node (at first and last positions, as well as any given index)
- Return data at given index
- Print entire data list to the console
- Clear all nodes
class LinkedList {
constructor() {
this.head = null;
this.size = 0;
} insertAtHead(data) {
this.head = new Node(data, this.head);
this.size++;
}
}const myLinkedList = new LinkedList;
myLinkedList.insertAtHead("jellybeans")console.log(myLinkedList)
// LinkedList { head: Node { data: 'jellybeans', next: null },
// size: 1}
The above code snippet will now create a new linked list and insert a new node at the head of the list. For the next steps, it unfortunately gets more complex but no worries — the computer will be doing all the hard work so we don’t have to write everything manually as we traverse through our linked list. To do that, we’re going to implement a while loop for our method that prints the data at a given node index.
class LinkedList {
... for brevity
printList() {
let current = this.head
while(current) {
console.log(current.data)
current = current.next
}
}
}
So what’s going on here? Our newly created method printList is looping through the entire linked list, logging each data value it iterates over, and then setting the current value to the next node ahead of itself. Remember, this all happens in a linear sequence so we can literally think of it as moving from one node to the next. The loop stops once it reaches the end of the list, because it will throw a TypeError since the value is null.
If you’ve been following along with your own code, you should now be able to create as many nodes as you’d like using the first method we created to insert nodes at the head of the list, then call the printList method on our linked list variable to get all of the data from each node logged to the console. Next, we can implement a method to insert a new node at the tail.
class LinkedList {
... for brevity
insertAtTail(data) {
let node = new Node(data)
let current;
// 1. Edge case
if (!this.head) this.head = node;
// 2. While loop
current = this.head;
while(current.next) {
current = current.next;
}
// 3. Insert the tail
current.next = node;
this.size++;
}
}myLinkedList.insertAtHead("1 jellybean")
myLinkedList.insertAtHead("2 jellybeans")
myLinkedList.insertAtHead("3 jellybeans")
myLinkedList.insertAtTail("4 jellybeans")
console.log(myLinkedList.printList())
// OUTPUT:
// 3 jellybeans
// 2 jellybeans
// 1 jellybeans
// 4 jellybeans
// undefinedconsole.log(myLinkedList)
// OUTPUT:
// LinkedList {
// head:
// Node {
// data: '3 jellybeans',
// next: Node { data: '2 jellybeans', next: [Object] } },
// size: 4 }
The numbers below refer to the comments in the code snippet above so the code is kept relatively clean and easy to read. Sample outputs have been provided to ensure your code is equivalent to the code we’ve created so far.
- Edge case: if there is no head, our linked list is empty. We will need to create a head
- While loop: If a head exists, loops through the linked list until we find the tail which should be once we find the next node equals to null.
- Insert the tail: Once the loop ends, set the current value to the next value. This now becomes the tail.
You’ve made it this far, you’re doing great! Let’s keep the momentum going and implement the remaining features.
class LinkedList {
... for brevity
insertAtIndex(data, index) {
// 1. Edge case outside of range
if(index > 0 && index > this.size) return;
// 2. Edge case at first index
if(index === 0) {
this.head = new Node(data, this.head);
return;
}
// 3. Non-edge case
const node = new Node(data);
let current, previous;
let counter = 0;
current = this.head;
while(index > counter) {
previous = current;
current = current.next
counter++;
}
node.next = current;
previous.next = node;
this.size++;
}
}
- Edge case: If index is outside the range, immediately return
- Edge case: If we are at the very first index, create the new head node and set the previous head node to the next node
- Non-edge case: If we do not come across an edge case, set the current node to the head and the counter to zero so we can use that to find out once we’ve reached the given index. Then we loop until the index is reached.
This method is interesting because it affects both the previous, and next nodes. Just remember because we are working in a linear fashion which means the maximum amount of nodes we can work with per each iteration is three: The previous, current, and next nodes.
Okay now that we have that cleared up, it would be best if you tried these last methods on your own (getAt, deleteAt, clearAllNodes). There will be final code provided with minimal explanations and your goal is to just get the methods working while taking into account edge cases. It’s important at this point to have full understanding, and the only way to get better is to practice. Give it a try and when you’re done, feel free to compare your solution against the final code below:
class LinkedList {
... for brevity
getAtIndex(index) {
let current = this.head;
let counter = 0;
while(current) {
if(counter === index) {
console.log(current.data);
}
counter++;
current = current.next;
}
return null;
} deleteAt(index){
if(index > 0 && index > this.size) return;
let previous;
let current = this.head;
let counter = 0;
if(index === 0) {
this.head = current.next;
} else {
while(counter < index) {
previous = current;
current = current.next;
counter++;
}
previous.next = current.next;
}
this.size--;
} clearList() {
this.head = null;
this.size = 0;
}
}
Hopefully you had success at doing this on your own. The clearList method is slightly different, in that all it does is unlink all the other nodes because the head is now set to null (which is essentially starting from the beginning when we created our first node without a linked list). There may still be nodes stored in memory, but the purpose of this method is to just clear the linked list itself. If you did struggle a bit, you should review the previous examples and try again.
Did you follow the same principles as the previous examples? Ask yourself the following questions. If you had more answers that were “yes”, then you are on the right track.
- Did I compare the current node with the affected surrounding nodes?
- Did I modify the values of each affected node?
- If working with an index, did I keep track with a counter?
- Did I create and test for edge cases if I returned a value?
- Did I either solidify my understanding or learn something new?
- Do I understand how I can create other methods by using the principles above?
That was exciting, but we should keep on learning!
We’ve now learned what a linked list is, how we should decide on whether or not we should use it versus an alternative data structure, and how to create one step-by-step while accounting for major edge cases.
If we take a step back and look at the bigger picture, instead of focusing on linked lists directly we made sure we understood the problem we are trying to solve by going through a step-by-step flow chart for choosing a data structure. We didn’t focus on why linked lists are better or worse than other data structures, instead we asked ourselves questions of what we are trying to accomplish and thought about potential future issues dependent on how we are planning to use our data.
I encourage you to take this problem-solving approach often when you are learning something new, because it is important to have a fundamental understanding of your goals and the steps you need to take to achieve them. Keep in mind this was an introduction to linked lists, however if you wish to continue your learning journey you should definitely check out these resources:
- Doubly linked lists
- Circular linked lists
- Doubly circular linked lists
- Time and space complexity of linked lists
- Can we apply merge sort (binary search) to linked lists? — Give it some thought
- Linked list challenges from Algodeck
- Stacks and queues — Exploring other linear data structures with last in/first out (LIFO) and first in/first out (FIFO)