Linked Lists

John Peña
Nov 4 · 4 min read

Before we start diving into the importance of what linked lists are and why we need them let me start by saying this article is going to focus on one type of Linked List, Singly linked lists. Just by looking at the name of the Singly Linked Lists, it means that for this article we’ll be dealing with a one directional list. We are only traversing and pointing to the next node. There are also, circular linked lists and doubly linked lists but we’ll cover that another time.

What are singly linked lists?

Singly Linked Lists are a type of data structure. A linked list provides an alternative to an array-based structure. The usefulness of a linked list is its constant time insertion and deletion for any arbitrary node. A linked list is basically is a collection of nodes that collectively form a linear sequence.

Each node stores a reference to an object that is an element of the sequence, as well as a reference to the next node of the list. It does not store any pointer or reference to the previous node.

Let’s start off by explaining how it works and we’ll jump into some code. Successive nodes are connected by pointers. The last node points to null. A head pointer is created which points to the first node on the list. A linked list can grow and shrink in size during execution of the program.

Now let’s jump into a little bit of code by defining a node class and see how this node class, along with the linked list class will help in building a linear list of nodes.

class Node{
constructor(data, next = null){
this.data = data,
this.next = next
}
}

Here we are creating a class and initializing it with the data and a pointer named next as parameters. The pointer next is initialized with a default value of null, incase no value is passed as an argument.

Now let’s start the next process by creating our LinkedList class wich maintains the head pointer of the list.

class LinkedList{
constructor() {
this.head = null
}
}
const list = new LinkedList();
list.head // null

To add to this LinkedList at the beginning of the class lets create a function to do just that.

LinkedList.prototype.insertAtBeginning = function(data){
// A newNode object is created with property data and next = null let newNode = new Node(data);
// The pointer next is assigned head pointer so that both pointers now point at the same node.
newNode.next = this.head;
// As we are inserting at the beginning the head pointer needs to now point at the newNode.

this.head = newNode;
return this.head;
}

If we wanted to add to the tail(end) of the list we create this function.

LinkedList.prototype.insertAtEnd = function(data){let newNode = new Node(data);// When head = null i.e. the list is empty, then head itself will point to the newNode.    if(!this.head){
this.head = newNode;
return this.head;
}
// Else, traverse the list to find the tail (the tail node will initially be pointing at null), and update the tail's next pointer.
let tail = this.head;
while(tail.next !== null){
tail = tail.next;
}
tail.next = newNode;
return this.head;
}

If we wanted to delete from the beginning of the list we do the following:

LinkedList.prototype.deleteFirstNode = function(){
if(!this.head){
return;
}
this.head = this.head.next;
return this.head;
}

To delete a node at the end of the list we will first have to traverse the list to find the last node and at the same time maintain an extra pointer to point at the node before the last node. To delete the last node, we will then set the next pointer of the node before the last node to null.

LinkedList.prototype.deleteLastNode = function(){
if(!this.head){
return null;
}
// if only one node in the list

if(!this.head.next){
this.head = null;
return;
}
let previous = this.head;
let tail = this.head.next;

while(tail.next !== null){
previous = tail;
tail = tail.next;
}

previous.next = null;
return this.head;
}

What are the benefits of using linked lists?

If we were to see how linked lists worked, we’d soon find out the main benefit to using a linked list is we can easily insert or remove nodes from the list without reorganization of the entire data structure. It doesn’t need additional memory that array resizing would require, making memory allocation more predicable for a given input.

What that means it if you want to insert/delete the element in the beginning of the linked list then there is no need to traverse the list. Just make the newly created node as head node and hence the time complexity will be O(1). If you need to delete/insert at the beginning of the list you would run a O(n) time complexity.

If you take a look at queues, they also benefit greatly from this feature, since they aren’t searching for an item, and only inserting/deleting at the ends of the list.

That’s it for now but there are also other methods that we can run on linked lists but for time complexity we’ll stick with deleting and inserting at the beginning and ends of lists for now.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade