A General Overview of Linked Lists
For Beginners
Linked lists are an important concept for any aspiring programmer to grasp. You may want to use lists as a data structure in a program. You may be asked about lists during a tech interview. Or, you may just want to have a better understanding of pointers. Whatever your reason, having a solid general overview of lists is a great place to start.
What exactly is a linked list?
A linked list is a chain of nodes, or elements. Each node refers to the next sequentially. As such, a linked list is a linear data structure, as opposed to a nonlinear structure such as a tree or a graph.
A single node contains two things: data and a next (a pointer). A node’s pointer contains a reference to the following node. It’s the component that puts the link in linked lists… Pointers are central to lists and an important concept to grasp. As Stanford Professor Nick Parlante writes:
“You may never use a linked list in a real program, but you are certain to use lots of pointers.”
So! Take note of pointers…
The list in the diagram above has a length of four, because there are four nodes. The head contains a reference (pointer) to the first node. It’s the entry point of the list. The last node of the list contains a reference set to null, which indicates the end of the list. If the head doesn’t reference a first node, its pointer is set to null and the value of the linked list is null.
Let’s take a look at some code! We’ll build a linked list in JavaScript:
To get started, we have a node constructor on line 1 and a linked list constructor on line 6. The function on line 10 adds a node to a linked list. The argument given to the function becomes the added node, initialized on line 11 from the node constructor. On line 13, if the head of the linked list is null, the node gets assigned to the head of the list. Otherwise, on line 20, the function finds the last node of the linked list and on line 23, assigns the new node to the end of the list.
Now let’s create the linked list!
On line 27, we’re creating a linked list from the linked list constructor and calling it “list”. On line 28, we’re adding a node to the list by passing “2” as an argument. The first result visible in the terminal is the list with a single node containing “2”:
LinkedList { head: Node { data: 2, next: null } }
Notice that the node contains the data “2” as well as a reference to the next node, which is null. The list’s next is null because the second node doesn’t exist (yet). On line 30, we’re adding another node to the list by passing “10” as an argument. The second result is the list with both sets of inputted data, “2” and “10”:
LinkedList { head: Node { data: 2, next: Node { data: 10, next: null } } }
Three Types of Linked Lists
There are three types of linked lists that you may come across.
1. A singly-linked list can only move forward, which is the type of linked list described above.
2. A doubly-linked list can move forwards and backwards. This can be done when a given node contains two pointers: a next pointer referencing the following node and a previous pointer referencing the node behind it.
3. A circular linked list circles back around to the first element so that the last element and the head or the first node are connected.
Manipulating a List
Operations can be performed on a linked list. Find a few described below.
Insertion:
An element is added to the list by finding the two nodes that it will be placed in between. In order to place it in the list, the pointer for the preexisting left node in the list must be ‘rearranged’ so that the pointer to the left is now referring to the new node and the new node is now referring to the node on the right. If a node is being placed at the end of the list, the node that was previously pointing to null should now be pointing to the new node, and the new node should now be pointing to null, as we saw in the code example above.
Deletion:
An element can be deleted from a list first by finding the element to be deleted. Similarly, with insertion, the pointers must be rearranged. The node on the left will no longer be linked to the deleted node. Instead, it will need to be linked to the node that the deleted node was referring to.
Reversal:
It’s possible to reverse a linked list. In order to do so, all node pointers except for the head node and the node it links to (the first node) must be ‘redirected’ one by one to point to the node behind it. Once the list has been traversed and all pointers have been redirected, what was once the first node becomes the last node, and must refer to null. The head goes all the way to the other side and links to what was once the last node (now the first node) and becomes the head of the list once again.
In the diagram below, pointers 1, 2 and 3 are ‘redirecting’ each node to the one behind it. Pointer 4 is redirecting what is becoming the last node of the list to null. Pointer 5 is redirecting the head to what is becoming the first node of the list.
It’s possible to perform several additional actions such as displaying a list or searching for a particular element in a list, among others…
Lists and Arrays
Lists are often compared to their competing linear data structure: arrays. Both lists and arrays are linear and both store data. But what’s the difference?
- Unlike arrays, the elements of a list aren’t stored at particular indexes of the list. Elements of a list are only accessible via pointers from the node that came before it. Elements cannot be accessed randomly: they can only be accessed from the first node onwards. This is a drawback because operations become slower as the line progresses and moves further away from the front. For this reason, arrays are more efficient.
- Lists are dynamic structures. This allows them to be flexible with the number of elements they can contain. A list’s size expands and contracts depending on whether a node is added or deleted. Memory is stored in each individual node during runtime. On the other hand, arrays are static structures. An array stores all of its data in a single block of memory, limiting the amount of data it can take. The size of an array must be specified at compile-time and so remains fixed depending on whether elements are inserted or deleted. The memory constraints of an array are one of its bigger drawbacks — as memory is either wasted on extra preventative space (allocated when the array was created) or in a lack thereof when the array becomes full.
- Inserting and deleting elements from a linked list only impacts the nodes to the left and to the right of the insertion or deletion. This has significantly less impact on the rest of the nodes in the list than it would the elements in an array. Inserting and deleting elements into and from an array is both expensive, because space is limited, and disrupting because all other elements after the inserted or deleted element must be shifted (altering their indexes). Let’s look at a quick example of how elements can be disrupted in an array:
An array is defined on line 1 with a length of 5. On line 6, the element at index 2 is searched and the result is 3, as printed in the terminal.
On line 9, one element is spliced (removed) from the array at index 1. At this point, the length of the array decreases by 1 (when checked on line 12), and when index 2 is checked again (on line 15), the value has also changed — it now holds the element 4. Element 3 is now at index 1, whereas before it occupied index 2.
The important thing to notice here is that all the elements after the spliced element move back one space. Similarly, if an element is added at a particular index, all the elements after the added element move forward one space. On the other hand, nodes of a linked list don’t occupy indexes and so they aren’t disrupted in the same fashion by a change in the list.
In Sum
We’ve only covered a general overview of linked lists in this article but it’s enough to start getting comfortable with the concept. Linked lists are fairly straightforward… (because they’re linear)… as described here. That being said, don’t be afraid to dive deeper with the resource(s) listed below. And enjoy the learning process!
References
- Linked List Basics
Nick Parlante, 2001 - Linked Lists
Victor S. Adamchik, CMU, 2009 - Data Structures: Linked List
Joe Birch, 2016
Special thanks to Jacob Carlone for contributing the code examples and to Michael Matich, Caryn Kaftal and Felice Panagrosso for their edits.
