lesson-notes

Linked Lists

Learning Objectives

• Be able to describe what is a node
• Be able to describe what is a linked list
• Be able to compare and contrast a linked list to an array
• Be able to build a simple linked list using JavaScript
• Be able to describe one real-world example of a linked list
• Be able to build some basic general methods for linked lists like insertion, deletion, counting the size, and getting the value of a particular node

Linked List

A linked list is a linear data structure comprised of nodes that point to the next node in a singly-linked list.

It is similar to an array, but there are a few differences. One is chosen over the other depending on the functionality/speed of certain operations for specific tasks. For example, a browser's forward and back buttons typically store data in a linked list.

Based on your reading, what are the main differences?

JavaScript has built-in arrays, but there is no linked list. Let's build one.

NOTE: There are several approaches to building methods for linked lists. These approaches were predominantly from Introduction to Algorithms. Other methods were chosen to show different approaches to working with linked lists that hopefully help develop your understanding. The most important thing is to find a solution and then improve upon it.

Node

First, let's build a node. A node must, at minimum, have some data and a pointer to the next node.

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

We can create a pair of nodes and link them.

const firstNode = new Node(1);
const secondNode = new Node(2);
firstNode.next = secondNode;

console.log(firstNode);

Linked List

Much like our DeckOfCards, a class that interacted with our Cards objects and had methods for utilizing the cards, our list will follow a similar pattern.

class LinkedList {
  constructor(head = null) {
    this.head = head;
  }
}

So now we can create a new linked list with our firstNode

const firstList = new LinkedList(firstNode);
console.log(firstList);

Depending on our terminal settings, the output should look more or less like so

Linked List Methods

Some standard methods are helpful to build for linked lists:

• Search
• size
• clear
• get last
• insert
• delete

Let's quickly create a linked list that has the months in order so we can use it to test our methods.

const months = [
  "Feb",
  "March",
  "April",
  "May",
  "June",
  "July",
  "Aug",
  "Sept",
  "Oct",
  "Nov",
  "Dec",
];

let previousNode = new Node("Jan");
let list = new LinkedList(previousNode);
for (let i = 0; i < months.length; i++) {
  let currentNode = new Node(months[i]);
  previousNode.next = currentNode;
  previousNode = currentNode;
}

Size

This will tell us how long our linked list is.

Let's write some pseudo-code. How would we go about writing a size method for the linked list?

class LinkedList {
  constructor(head = null) {
    this.head = head;
  }

  size() {
    let count = 0;
    let node = this.head;
    while (node) {
      count++;
      node = node.next;
    }
    return count;
  }
}

How do we test this method?

Search

This will allow us to search for a matching piece of data.

Let's write some pseudo-code. How would we go about writing a search method for the linked list?

Search

class LinkedList {
  constructor(head = null) {
    this.head = head;
  }

  search(key) {
    let node = this.head;
    while (node !== null && node.data !== key) {
      node = node.next;
    }
    return node;
  }
}

How do we test this method?

Clear

This will clear our linked list of all the nodes.

Let's write some pseudo-code. How would we go about writing a clear method for the linked list?

Clear

class LinkedList {
  constructor(head = null) {
    this.head = head;
  }

  clear() {
    this.head = null;
  }
}

How do we test this method?

Get Last

This will get the last node of our linked list.

Let's write some pseudo-code. How would we go about writing a getLast method for the linked list?

Get Last

class LinkedList {
 constructor(head = null) {
 this.head = head;
 }

 getLast() {
 let node = this.head;
 if (!this.head) return null;
 while (node.next) {
 node = node.next;
 }
 return node;
 }

How do we test this method?

Insert

This insert will insert at the head.

Let's write some pseudo-code. How would we go about writing an insert method for the linked list?

Insert

class LinkedList {
  constructor(head = null) {
    this.head = head;
  }

  insert(data) {
    let newNode = new Node(data);
    if (!this.head) {
      this.head = newNode;
    } else {
      newNode.next = this.head;
      this.head = newNode;
    }
  }
}

How do we test this method?

How would you approach inserting it in the middle of the linked list?

Delete

Let's delete a node with a specific key.

First, let's write some pseudo-code. How would we go about writing a delete method for the linked list?

• use similar logic to search for the matching key, keep count of how many nodes we go through
• store the found node
• loop through up to the previous node of the found node
• set the previous node's next property to be found node's next property

Delete

class LinkedList {
  constructor(head = null) {
    this.head = head;
  }

  delete(data) {
    let node = this.head;
    let counter = 0;
    while (node.data !== data && node.next) {
      counter++;
      node = node.next;
    }
    let foundNode = node;
    node = this.head;
    for (let i = 1; i < counter; i++) {
      node = node.next;
    }
    node.next = foundNode.next;
  }
}

How do we test this method?

It may be hard to see our linked list, but we can bring in a node.js utility to help us and use its inspect method to expand what we see in our console.log.

const { inspect } = require("util");

list.delete("June");
console.log(inspect(list, { showHidden: true, colors: true, depth: 12 }));

Get first

By now, you should be pretty comfortable creating methods for linked lists. Be sure to think of your strategy before coding. If you don't understand what you are supposed to code, you will not be able to succeed. Sometimes it feels like there is no time to stop and think or look something up, but much more time can quickly be sunk into the state of 'fuzzy thinking/fuzzy coding'.

Get first

class LinkedList {
  constructor(head = null) {
    this.head = head;
  }

  getFirst() {
    return this.head;
  }
}

Bonus

Doubly-linked list

Further Reading

JavaScript class syntax is syntactic sugar, meaning it is a newer, easier-to-read/write syntax that does the same thing as an older one.

When training on Codewars or Leetcode, you will likely encounter the older syntax in example code or as some starter code for a problem.

When you are ready to learn the alternative syntax to help you solve those problems, check out this readme:

JavaScript Prototypal Inheritance