Linked lists are a relatively common type of data structure that you may run into throughout your programming journey. They are especially common in technical job interviews as well as acting as building blocks for some more complex data structures. As a result, they are very important for budding programmers to familiarize themselves with.
Linked lists can be compared to arrays, as they have similar structures and functions. However, each will have its own distinct advantages and disadvantages that will dictate how and when you utilize them.
As shown above, you can visualize an array as one large "box" that is partitioned into several smaller sections that each contain a data point, such as an integer. Linked lists are very similar--instead of one big box, think of a linked list as several small boxes that are connected to each other. Each box will contain data and "point" to the next box in the list, hence the name: linked lists:
Each "box" in a linked list is oftentimes referred to as a node. Additionally, the first and last node in a linked list are usually called the head and tail nodes respectively.
Now that we know what a linked list is, how do we implement it with code? With object-oriented programming in mind, we will want to eventually have a class for both our Node and our Linked List, but for simplicity's sake, we will be building a simple linked list with only Node objects. Starting with our Node class, we want to define a Node to have two properties: data and next. Data will hold the actual data within the node, and next will hold the pointer to the next node in the list (which will be initialized as null).
class Node {
constructor(data)
{
this.data = data;
this.next = null
}
}
If we wanted to recreate the linked list pictured above, we would create our first Node and assign it to a new variable, head, with its initial value of 1. We would then have to create the rest of the nodes and assign their pointers to each other, as shown below:
const head = new Node(1);
const nodeB = new Node(2);
const nodeC= new Node(3);
const nodeD = new Node(4);
const nodeE= new Node(5);
head.next = nodeB;
nodeB.next = nodeC;
nodeC.next = nodeD;
nodeD.next = nodeE;
Note that nodeE never has its .next assigned to a Node and remains null. We have created a singly linked list, which means our linked list is one-directional and only points forward. This makes it easy for us to write code that will recognize when the end of the linked list has been reached. For example, if we wanted to write a function that counted the number of nodes in a linked list (think 'length of an array' as a comparison), we could implement it as such:
function countNodes(head) {
let counter = 1;
let currentNode = head;
while (currentNode.next != null) {
currentNode = currentNode.next;
counter += 1;
}
}
We have just implemented a function that steps through a linked list from its head node and increments a counter variable each time a node successfully points to another node that is not null! The code snippets above are oversimplified, and creating a LinkedList class would clean up our code and allow us to write more complex functions for other purposes, such as inserting and removing nodes from a linked list. However, the basics of linked lists include the structure of a node and how the pointers affect the interactions between nodes.
The next question you may have is, "when would I use a linked list?" A small disadvantage of linked lists is that indexing or searching through a linked list takes linear time, meaning that it has to traverse the entire structure (and therefore every element) while indexing or searching. However, linked lists are able to insert and delete nodes with more efficient time complexity than arrays. They are also used as a foundation for other complex data structures, such as trees. Try and see if you can recognize the linked list structure in the tree pictured below!
Top comments (0)