Cartoon Guide to Data Structures — Singly Linked Lists

Rajesh Pillai
Nov 5 · 11 min read

The tutorial aims to record all important information on the foundation data structure, Linked List.

There is null at the end of the list.

This is part 1 of the series and future sequences will be documented here.

The source code will be in JavaScript, but the concepts can be applied using any other programming language.

The video tutorial will be published on my youtube channel at https://www.youtube.com/user/tekacademylabs (Please subscribe to get the notification)

Linked List

Linked List is a sequentially access dynamic data structure where every node points to the next node in the chain. Unlike arrays, which have a fixed size (nowadays arrays too are dynamic depending on the programming language of choice), a linked list is dynamic by nature and can allocate and deallocate memory at runtime.

So, in the above figure, we have some fruits being represented as a linked list. Now, this data could be anything, simple numbers, text, or even complex types as well.

The interesting thing is that every node has a pointer to its next node and the last node points to null in case of a singly linked list.

Linked List is a linear data structure and it doesn’t store nodes in contiguous location.

Linked List comes in various forms as outlined below.

  • Singly Linked List

Singly Linked List

The singly linked list is the easiest form of the linked list. Here every node in the list points to the next node in the chain. The last node point to null.

The code for the singly linked list is available at the below URL.

The application when executed looks like the below figure.

The running application

Before we get into the code, let's take a look at the API that we intend to use to manage the list.

To create a new List

let list = new LinkedList();

To add data at the end of the list

list.insert(1);
list.insert(2);

To insert data at the beginning of the list. The insertAt methods take in the data and the index of the location to insert. The index begins with 0;

list.insertAt(10, 0);

To insert data at a certain index.

// The index can be any valid starting from 1 to size of the list
list.insertAt(30, index);

To remove the 1st element in the list.

list.removeAt(0);

Code Explanation

The basic node in the linked list will be represented by a constructor function or by using the es6 class feature. We will be using the modern ES6 features for all code demonstration. (You can also use TypeScript or Babel as well).

Every node is represented by a Node class as shown below.

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

Every node in a linked list will contain the data as well as a pointer to the next node.

Let’s now code the LinkedList class. The LinkedList class will manage the creation, insertion, deletion of nodes.

class LinkedList {
head = null;
length = 0;
}

The above is the basic layout of the LinkedList class. It contains a pointer to the head/start node and we are also creating a property, length, which will come in handy for list manipulation.

insert(data) method

The insert method inserts the node at the end of the list

The logic for the insert method.

  1. Create a new node with the data

Case 1 — When List is empty

When the list is empty, create a new node with the data and point the head variable to the newly created node.

Case 2— When List is not empty

Create a new node variable called newNode, with data. Create a temp node called current and store reference of head into the current variable. Loop the linked list using the current variable till current.next points to null.

Store the newNode as current.next;

List has one item
A list having more than one item

The insert method code

  // Adds data to the end of the list
insert(data) {
const newNode = new Node(data);
if (this.head == null) {
this.head = newNode;
} else {
let current = this.head;
while (current.next !== null) {
current = current.next;
}
current.next = newNode;
}
this.length++;
this.render();
}

insertAt(data, index) method

The insertAt method inserts the data at the specified index.

The logic for the insert method.

  1. If index less than 1 then return (invalid index check)

Case 1- Inserting at 0 (head position)

Insert new node at 0th position

Case 2 — Inserting anywhere other than head position (0th index)

Inserting new node anywhere other than 0th index

The insertAt method code

// insert element at the specified index
insertAt(element, index) {
if (index < 0) return;
let newNode = new Node(element);
let currentNode = this.head;
let prevNode = null;
let currentIndex = 0;
if (index == 0) {
newNode.next = this.head;
this.head = newNode;
this.length++;
this.render();
return;
}
while (currentIndex < index) {
prevNode = currentNode;
currentNode = currentNode.next;
currentIndex++;
}
newNode.next = currentNode;
prevNode.next = newNode;
this.length++;
this.render();
}

removeAt(data, index) method

The removeAt method deletes a node at the specified index.

The logic for the removeAt method.

  1. If index less than 0 or greater than the length of the list then return (invalid index check)

Case 1 — Remove 0th element (head)

Remove 0th/head element

Case 2— Remove any element other than 0th/head

Remove any element other than that at 0th index

The removeAt method code

/* Removes an element at index
index: greater than 0
*/
removeAt(index) {
if (index < 0 || index > this.length) return;
let currentNode = this.head;
let prevNode;
let currentIndex = 0;
if (index == 0) {
this.head = currentNode.next;
this.length--;
this.render();
return;
}
while (currentIndex < index) {
currentIndex++;
prevNode = currentNode;
currentNode = currentNode.next;
};
prevNode.next = currentNode.next;
this.length--;
currentNode = null;
this.render();
}

search(data) method

Finds the data if it exists and returns the data and the index. Null if not found.

The logic for the search method.

  1. Store the head in the variable current
Search in action

The search method code

search(element) {
// Clear animation
$(".item").removeClass("active");
let current = this.head;
let index = 0;
while (current.next != null) {
if (current.data == element) {
$(`#i${index}`).addClass('active');
return { current, index };
}
current = current.next;
index++;
}
return null;
}

reverse() method — Iterative method

Reverses a linked list and make the head point to the end of the list.

The logic for the search method.

  1. Initialize prev to null and current to this.head
Reverse a singly linked list

The reverse() method source code

reverse() {
let prev = null;
let current = this.head;
let next = null;
while (current != null) {
next = current.next;
current.next = prev;
prev = current;
current = next;
}
this.head = prev;
console.log("rev:", prev);
this.render();
}

The complete code is shown below.

The HTML code

<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<meta name="viewport" content="width=device-width">
<title>Data Structures and Algorithms</title>
<script src="https://code.jquery.com/jquery-3.1.0.js"></script>
</head>
<body>
<div id="root">
<h1>Singly Linked List</h1>

<button class="button primary" onclick="insertAtStart()"
id="btnInsertAtStart">Insert at Beginning</button>
<button class="button primary" onclick="addNewItem()"
id="btnAddNewItem">Append (last)</button>
<button class="button primary" onclick="insertAt()"
id="btnInsertAt">Insert At Index</button>
<button class="button negative" onclick="removeAt()"
id="btnInsertAfter">Remove At (index)</button>

<button class="button negative" onclick="removeFirst()"
id="btnRemoveFirst">Remove 1st Element</button>

<button class="button primary" onclick="reverse()"
id="btnReverse">Reverse</button>
<button class="button primary" onclick="search()"
id="btnSearch">Search</button>


<ul id="linked-list" class="root">
</ul>
</div>
</body>
</html>

The JavaScript Code

/*-----------------------------------------------------------------------------*
* Project: Data Structures and Algorithms
* File: singly-linked-list.js
* Author: Rajesh Pillai(Twitter: @rajeshpillai, Medium: @rajeshpillai)
*
* Description:
* This program demonstrates a Singly Linked List
*
* This contains implemntation of following functions
* insert() adds a new node to the tail of the list
* insertAt() adds a new node to the index specified
* removeAt() removes a node at the index specified
* search() searches the list and returns the node along with index
* reverse() reverses the linked list
*
*
* Revision History:
* 2019-Nov-4:
*
*
* Copyright (c) 2019 Rajesh Pillai
*
*----------------------------------------------------------------------------*/
console.clear();const rootElement = document.querySelector("#root");var loopIndex = 0; // infinite loop protection;// Protect from loop getting into infinite execution
// Useful when working with online editors like jsbin, codepen,
// jsfiddle to avoid your system getting crashed
function loopProtect() {
loopIndex++;
if (loopIndex > 100) {
throw Error("Possible infinite loop...");
}
}
class Node {
data = null;
next = null;
constructor(data) {
this.data = data;
this.next = null;
}
}
class LinkedList {
head = null;
length = 0;
// Adds data to the end of the list
insert(data) {
const newNode = new Node(data);
if (this.head == null) {
this.head = newNode;
} else {
let current = this.head;
while (current.next !== null) {
current = current.next;
}
current.next = newNode;
}
this.length++;
this.render();
}
// insert element at the specified index
insertAt(element, index) {
if (index < 0) return;
let newNode = new Node(element);
let currentNode = this.head;
let prevNode = null;
let currentIndex = 0;
if (index == 0) {
newNode.next = this.head;
this.head = newNode;
this.length++;
this.render();
return;
}
while (currentIndex < index) {
prevNode = currentNode;
currentNode = currentNode.next;
currentIndex++;
}
newNode.next = currentNode;
prevNode.next = newNode;
this.length++;
this.render();
}
/* Removes an element at index
index: greater than 0
*/
removeAt(index) {
if (index < 0 || index > this.length) return;
let currentNode = this.head;
let prevNode;
let currentIndex = 0;
if (index == 0) {
this.head = currentNode.next;
this.length--;
this.render();
return;
}
while (currentIndex < index) {
currentIndex++;
prevNode = currentNode;
currentNode = currentNode.next;

loopProtect();
};
prevNode.next = currentNode.next;
this.length--;
currentNode = null;
this.render();
}
search(element) {
// Clear animation
$(".item").removeClass("active");
let current = this.head;
let index = 0;
while (current.next != null) {
if (current.data == element) {
$(`#i${index}`).addClass('active');
return { current, index };
}
current = current.next;
index++;
}
return null;
}
reverse() {
let prev = null;
let next = null;
let current = this.head;
while (current != null) {
next = current.next;
current.next = prev;
prev = current;
current = next;
loopProtect();
}
this.head = prev;
console.log("rev:", prev);
this.render();
}
render() {
let current = this.head;
//console.log("Size: ", this.length);
let html = ''; // `<ul class='root'>`;
$("#linked-list").empty();
let index = 0;
while (current != null) {
html = `
<li class="item" id="i${index}">${current.data}</li>
<span>→</span>
`;
$("#linked-list").append(html);
current = current.next;
index++;
}
}
}
// Event handler setup
function addNewItem() {
let item = random(1, 100);
list.insert(item);
}
function insertAtStart() {
let item = random(1, 100);
list.insertAt(item, 0);
}
function insertAt() {
let index = prompt("Enter index to insert after(starts from 0)");
let item = random(1, 100);
list.insertAt(item, parseInt(index, 10));
}
function removeAt() {
let index = prompt("Enter index to remove(starts from 0)");
list.removeAt(index);
}
function removeFirst() {
list.removeAt(0);
}
function search() {
let data = prompt("Enter data to search.");
const node = list.search(data);
console.log('found: ', node);
}
function reverse() {
list.reverse();
}
function random(min, max) {
min = Math.ceil(min);
max = Math.floor(max);
return Math.floor(Math.random() * (max - min + 1)) + min;
}
// Test Cases
var list = new LinkedList();
list.insert(1);
list.insert(2);
list.insert(3);
list.insert(4);
list.insert(5);
list.insert(6);
list.insert(7);
list.insert(8);
list.insert(9);

The CSS code

body{
margin:10px;
}
.root {
display: flex;
list-style-type: none;
flex-wrap: wrap;
}
.root li {
min-width: 30px;
height:30px;
background-color: yellow;
margin:5px;
line-height: 30px;
text-align:center;
animation-name: appear;
animation-duration:5s;
animation-fill-mode:forwards;
}
.root span {
height:30px;
display:inline-block;
line-height:35px;
}
li.active {
background-color: green;
color: white;
animation: spin 4s linear;
}
.button {
margin-bottom: 1rem;
border: 0;
letter-spacing: .1rem;
font-size: 11px;
font-weight: 600;
height: 38px;
line-height: 38px;
padding: 0 15px;
box-shadow: none;
border-radius: 4px;
white-space:nowrap;
cursor: pointer;
}
.button.negative {
color: #FFF;
background-color: red;
border-color: #33C3F0;
}
.button.primary {
color: #FFF;
background-color: #33C3F0;
border-color: #33C3F0;
}
.button.primary:hover {
color: #333;
border-color: #888;
outline: 0; }
}
@keyframes appear {
from {background-color: white;}
to {background-color: yellow;}
}
@keyframes spin {
0% {
transform: rotateZ(0);
}
100% {
transform: rotateZ(360deg);
}
}

Info: All drawings are created by me and forgive my poor scribblings

Todo

  • Space and Time Complexity

P.S: More explanations and visuals will be added.

History

  • 31st October 2019 — First version

Full Stack Engineering

Our open source initiative to create a comprehensive content for full stack engineering.

Rajesh Pillai

Written by

Founder and Director of Algorisys Technologies. Passionate about nodejs, deliberate practice, .net, databases, data science and all things javascript.

Full Stack Engineering

Our open source initiative to create a comprehensive content for full stack engineering.

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