Cartoon Guide to Data Structures — Singly Linked Lists

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
• Doubly Linked List
• Circular 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.

JS Bin

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
2. If the head is null (means it is the first record), set the new node as head.
3. If the head is not null store a reference to head in a variable called current.
4. Loop until current.next is not null
5. Once outside the loop, the current variable will point to end of the list
6. Set the current.next to the new node
7. Increment the length

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)
2. Create a new Node with the data(element)
3. Assign the head variable to the currentNode variable.
4. Assign a prevNode variable to null.
5. Assign 0 to currentIndex. The currentindex will track the loop variable.
6. If index of insertion is 0 meaning, insert as 1st element then
7. Assign head to newNode.next
8. Set the newNode as the new head
9. Increment the length and return
10. Loop till the target index is found
11. Find the insertion position by looping until currentIndex is less than the index
12. Set prevNode to currentNode
13. Move the currentNode to point to the next node in the chain
14. Increment the currentIndex
15. Outside loop (once the current index is found)
16. Set the newNode.next to currentNode;
17. Set the prevNode.next to newNode
18. Increment length

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)
2. Assign the head to currentNode variable.
3. Assign prevNode (to null)
4. Assing currentIndex to 0
5. if index to be removed is 0 (first element)
6. Set the head to currentNode.next;
7. Decrement the length
8. exit the function
9. Otherwise loop till currentIndex reaches index
10. Increment currentIndex
11. Set prevNode to currentNode
12. Set currentNode to currentNode.next
13. Outside the loop the prevNode should point to the index one less than the element to be removed
14. Set prevNode.next to currentNode.next
15. Decrement length
16. Set currentNode to null

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
2. Initialize index to 0
3. Loop while current.next is not null
4. if current.data matches input data (element)
5. return current node and index
6. Otherwise, move the current node to point to the next node in the list
7. Increment the index
8. If the code reaches outside the loop it means the data is not found and null is returned.

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
2. Loop while current is not null
3. Store current.next into next variable
4. Store prev into current.next
5. Store current into prev
6. Store next into current
7. Store prev to this.head (as prev will point to the last node in the list)

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
• More error checking and comments
• More Diagrams

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

History

• 31st October 2019 — First version