Linked Lists

To download the demo code for this lecture, run:

$ dmget wb-linked-lists --demo

Introduction

Strengths and Limitations of Arrays

You could use an array to implement either a stack or a queue.

But one of those would be inefficient. Which one, and why?

• It would be inefficient to use an array for a queue.

  • In a queue, items are added to the end which is O(1)

  • But items are removed from the beginning which is O(n)

• It would be good to use an array for a stack.

  • Items are added and removed at the end which is O(1)

In an array, items are stored at contiguous addresses in memory.

• Strengths of arrays:

  • Get an item by index in O(1)

  • Adding or removing items at end is O(1)

• Limitations of arrays:

  • Checking if an item is in the array is O(n)

  • Adding or removing items at the beginning is O(n) because all other items must be shifted.

Why Linked Lists?

• Linked lists are better for queues than regular arrays

  • Adding/removing items at the beginning is O(1)

• Linked lists are a component of other data structures

• Linked lists are a popular topic for interviews

Linked Lists

Linked Lists

Items aren’t stored in contiguous memory; instead, each item references the next item in the sequence.

Can rearrange without having to move other items in memory.

This is a lot faster than having to move everything around in a big list.

Linked List Nodes

The basic unit of a linked list is a node.

apple, berry, and cherry are nodes.

A basic Node has two attributes:

• data: the information the node contains (could be string, number, object, etc)

• next: reference to next node (for last item, this is null)

console.log(apple_node.data);  // "apple"

console.log(apple_node.next);
// Node object with data = "berry"

console.log(cherry_node.next); // null

The Node Class

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

const appleNode = new Node('apple');
const berryNode = new Node('berry');
const cherryNode = new Node('cherry');

appleNode.next = berryNode;
berryNode.next = cherryNode;

console.log(appleNode.data); // 'apple'
console.log(appleNode.next); // Node {data: 'berry', next: {data: 'cherry'}}
console.log(cherryNode.next); // null

The LinkedList Class

A Linked List is just a bunch of nodes linked sequentially.

The only thing we need in the LinkedList class is a reference to the first node, called the head.

If the list is empty, we can set the head to null.

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

An empty Linked List:

A Linked List with nodes in it:

Things you might want to do

• Print each node

• Find a node by its data

• Append a node

• Remove a node

Traversing a Linked List

Traversing

Let’s assume we’ve already built the list. We’re just going to traverse the list and print it.

class LinkedList {
  printList() {
    let current = this.head;
    while (current !== null) {
      console.log(current.data);

      current = current.next;
    }
  }

Searching

This is going to look an awful lot like printing the list, but we’re going to stop searching once we find what we’re looking for.

class LinkedList {
  find(data) {
    let current = this.head;

    while (current !== null) {
      if (current.data === data) {
        return current;
      }

      current = current.next;
    }
    return null;
  }

Appending/Removing Nodes

Append a Node

How do we most easily append a node to the end of a linked list?

Walk to the end and add it there.

If we “knew” the end, though, appending would be O(1) instead of O(n).

We can accomplish this by adding a tail attribute to the linked list.

What do we need to do to add “durian”?

• make new node durianNode with data 'durian'

• make cherryNode.next a reference to durianNode

• make list.tail a reference to durianNode

Success!

Edge Case: Appending to Empty List

One special case is if the list is empty. What do we need to do to add “apple”?

• make new node appleNode

• make list.head a reference to appleNode

• make list.tail a reference to appleNode

The head and the tail will now be pointing to the same node:

Code for LinkedList.append

class LinkedList {
  append(data) {
    const newNode = new Node(data);

    if (this.head === null) {
      this.head = newNode;
    }

    if (this.tail !== null) {
      this.tail.next = newNode;
    }

    this.tail = newNode;
  }

Removing a Node (by value)

What would you need to change to remove:

• “apple”?

• “berry”?

• “cherry”?

The code is fairly complex, because there are quite a few cases:

• Removing only item in linked list

  • Don’t forget to update head and tail to null

• Removing first item

  • Don’t forget to update the head!

• Removing the last item

  • Don’t forget to update the tail!

• Removing an item in the middle

class LinkedList {
  remove(value) {
    // If removing head, make 2nd item (if any) the new .head
    if (this.head && this.head.data === value) {
      this.head = this.head.next;
      if (this.head === null) {
        this.tail = null; // we just removed the only item
      }
      return;
    }

    // If we get here, we're removing something other than the head
    let current = this.head;

    // We need to stop at the node BEFORE the one we want to remove
    while (current.next !== null) {
      if (current.next.data === value) {
        current.next = current.next.next;
        if (current.next === null) {
          this.tail = current; // If removing last item, update tail
        }
      } else {
        current = current.next;
      }
    }
  }
}

Runtime

Runtime Characteristics of Linked Lists

• Insert at beginning

  • O(1)

• Append at end

  • O(1)

• Delete from beginning

  • O(1)

• Pop from end

  • O(n) (we have to update the tail, and we can’t go backwards!)

• Get item by index

  • O(n)

Further Exploration

Other Methods For You To Try

• Remove by index

  ll.removeByIndex(2)
  

• Insert into list at particular index

  ll.insert(2, 'cardamom')
  

Doubly-Linked Lists

Sometimes, linked list nodes have next and a prev:

These are fairly common in industry but interviewers rarely ask about them.

Coming Up

• Trees

• Recursion