In the world of software development, when it comes to organizing data, there are many tools that could do the job. The trick is to know which tool is the right one to use for our given purpose.
As a reminder: regardless of which language we start coding in, one of the first things that we encounter are data structures, which we should be familiar with by now.
Data structures are objects that use different ways to structure and "shape" our data. They are usually built up of primitives like variables, arrays, hashes, or objects. However, these are just the tip of the iceberg when it comes to the possibilities. There are many more which may start to sound complicated as you learn more about their properties.
One of the data structures that sounds complicated at first is that of a linked list.
The more you hear about linked lists, the more intimidating they can get. Linked lists are actually super simple, but they seem to have this reputation of being complex. The more you learn about them, the more you realize it isn't necessarily the structure of linked lists that's confusing. Rather, it takes a while to fully grok the logic that goes into deciding when to use them and how to use them.
Linear Data Structures
To understand what a linked list is, it's important to discuss the type of data structure they are. A major characteristic of linked lists is that they are linear data structures. This means that there is a sequence and an order to how they can be traversed and constructed.
We can visualize a linear data structure like the chalk lines in a game of hopscotch. To get to the end of the list we have to go through all the items sequentially.
What is a Linked List?
A linked list is a linear data structure consisting of a group of nodes where each node points to the next node by using a pointer. You can think of a pointer as the address/location of some thing in programming.
Each node is composed of data and a pointer to the next node. See below for the definition of a Node in various languages:
1class Node {
2 constructor(val, next) {
3 this.val = val;
4 this.next = next;
5 }
6}Here are some quick definitions to make sure we're on the same page:
A
data structureis a collection of data that can be implemented in any programming language.A
pointerstores the address of a value in memory. They can also point to nothing (NULL). Areferenceis very similar, though they cannot point to nothing.
A linked list can be small or large. Regardless of the size, the elements that make it up are just nodes. Linked lists are just a series of nodes (, which are the elements of the list.
As shown in the image above, the starting point of the list is a reference to the first node, which is referred to as the head. The last node of the list is often referred to as it's tail. The end of the list isn't a node but rather a node that points to null or an empty value.
Are you sure you're getting this? Click the correct answer from the options.
What are the basic components of a linked list node?
Click the option that best answers the question.
- Head and Tail are the only important components
- Data members for the information to be stored and a link to the next node
- Indices and elements in the node
- Nodes and roots
Common Types of Linked Lists
Singly linked list
As shown in the below image, singly linked lists contain nodes that have data and a reference that points to the next node.
Doubly linked list
A doubly linked list has nodes that contain three fields: a data value, a reference forward to the next node, and a reference back to the previous node.
Circular Linked List
A circular linked list is similar to a singly linked list, but the difference lies in the last node of the list whose tail node points to the head node. The advantage lies in its ability to traverse the full list starting at any given node.
Build your intuition. Fill in the missing part by typing it in.
A ___ linked list is one where every node points to its next node in the sequence, but the last node points to the first node in the list.
Write the missing line below.
Linked List vs Array
Linked lists are used to store collections of data but we have already seen that mechanism for doing this in an array. An array is a sequential structure, meaning that it is a group of memory elements located in contiguous locations(located next to one another in a group). So why would you use a linked list instead of an array?
Arrays technically allow you to do all the things linked lists do, but the biggest difference comes to light when we look at the insertions and removals. Since arrays are indexed, when you perform insertions or removals from the middle of the array, you have to reset the position of all the values to their new indices.
But withlinked lists, it's much easier to shift elements around. You can insert a node anywhere in the physical memory that has an open space for it since it does not need to be localized.
Alternatively, arrays are beneficial when it comes to finding items since they are indexed. If you know the position of an item you can access it in constant or O(1) time. But since the nodes are scattered throughout memory, there is no easy way to access a specific node in a linked list. You would need to start traversing from the head and go through each node until you find the node you need. This would take linear or O(n) time.
Build your intuition. Is this statement true or false?
An array is fixed in size but a linked list is dynamically size-able.
Press true if you believe the statement is correct, or false otherwise.
Example 1: Reversing a linked list
Order in a singly linked list is determined by a node's next property. The next pointer can refer to another node or it can point to null.
Reversing a linked list means reassigning all the next properties on every node. So we are going from this:
To this:
There are many ways to reverse a linked list however the way I will demonstrate a simple way using 3 pointers. The idea is to use the three pointers: next, current, and prev.
In the reverse(Node head) method, the current is the main pointer running down the list. The next pointer leads it and the prev pointer trails it. In each iteration, the current pointer is reversed and then advance all three to get the next node.
xxxxxxxxxxprint(reversed);function reverseList(head) { let prev = null; let current = head;​ while (current != null) { const next = current.next;​ current.next = prev;​ prev = current; current = next; }​ return prev;}​function print(head) { let finalStr = ""; let current = head; while (current != null) { finalStr += current.val + " -> "; current = current.next; } finalStr += "null"; console.log(finalStr);}​class Node { constructor(val, next) {Are you sure you're getting this? Click the correct answer from the options.
What does the print(Node head) function do in previous code?
Click the option that best answers the question.
- Prints all nodes of the linked list
- Prints all nodes of the linked list in reverse order
- Prints alternate nodes of the linked list
- Prints alternate nodes of the linked list in reverse order
Try this exercise. Fill in the missing part by typing it in.
The Node class is missing a snippet of code. Fill in the missing snippet for the Node class of a linked list.
1public class Node {
2
3 int data;
4
5 ______________________
6
7 Node() {}
8
9 public Node(int data, Node next) {
10 this.data = data;
11 this.next = next;
12
13 }
14}Write the missing line below.
Example 2: Clone a Linked List
The ptr pointer is used only in the special case where it is null. The tail pointer is then used in the standard way to create copies after the special case is done.
The idea is to iterate over the original linked list and maintain 2 pointers, ptr and tail to keep track of the new linked list.
xxxxxxxxxxprint(cloned);function cloneList(head) { let current = head; let newPointer = null; let tail = null;​ while (current != null) { if (newPointer == null) { newPointer = new Node(current.val, null); tail = newPointer; } else { tail.next = new Node(current.val, null); tail = tail.next; } current = current.next; } return newPointer;}​function print(head) { let finalStr = ""; let current = head; while (current != null) { finalStr += current.val + " -> "; current = current.next; } finalStr += "null"; console.log(finalStr);}​Conclusion
It is important to understand the advantages and drawbacks when you're deciding whether or not to use a linked list. One thing we didn't include was the implementation of a linked list. The implementation isn't overly difficult, and it's a good way to test your understanding of linked lists.
One Pager Cheat Sheet
- Understanding the fundamentals of
data structuresand when to appropriately use alinked listis essential in software development. - Linked lists are linear data structures, meaning elements are traversed and constructed in a sequence and order, similar to a game of hopscotch.
- A
linked listis a linear data structure composed ofnodes that usepointersto reference the next element in sequence and the starting and ending point of the list is marked by theheadandtail, respectively. - A
nodein alinked listcontains two essential parts: data members storing information and a link providing apointerto the nextnode. - A singly linked list consists of
nodesthat storedataand areferencepointing to the next node. - A doubly linked list has nodes with a
data value, a reference to thepreviousnode, and a reference to thenextnode. - A
circularlinked listallows efficient traversal of a full list beginning at any node. - A circular linked list consists of a set of
nodeswhich link to one another in an unbrokencircular sequence, with the tail node pointing back to the head node. - Linked lists are beneficial for shifting elements around, while arrays allow for faster item lookup in
constanttime. - A linked list is
dynamically size-abledue to itspointersthat reference thenextmemory address, making it easier to add and remove nodes compared to an array, which must be shifted around. - Reversing a
linked listinvolves reassigning thenextproperty of each node and iterating through the list with three pointers (current,next, andprev) to achieve the desired reversal. - The
print(Node head)functionloopsthrough thelinked liststarting from theheadnode and prints out the values of eachnodeto the console. - The
Nodeclass needs to be given the pointer to thenextNodein order to link them together in a linked list. - We use a
ptrpointer to handle the special case when it isnull, and then use atailpointer to iterate over the originallinked listand create a copy. - Deciding whether or not to use a
linked listrequires consideration of both the advantages and drawbacks, and one can further their understanding by implementing one.
