Part 1: Linked Lists

Learning Objectives

• Students Will Be Able To:

  • Define linked lists
  • Explain the time complexity of linked list operations
  • Compare and contrast linked lists to Arrays
  • Visualize a linked list
  • Traverse a singly linked list
  • Remove nodes from a singly linked list

Roadmap

• Setup
• Defining a linked list
• Linked list operation time complexity
• Comparing linked lists to arrays
• Review JS class syntax
• Linked list visualization
• Meet the walker

• Use the walker to remove nodes

  ---

Defining a Linked List

Linked lists are a foundational, "array-like" data structure which appears in other complex data structures

• Linked lists are a collection of nodes

  • nodes are also seen in other data structures, but for linked lists, they contain:
  • a data property, that stores the node's value
  • a next property, also known as the "pointer", which points to the next item in the linked list
  • the last node will have a next property set to null, so it is sometimes referred to as the "null next node", or the "tail"

Because of the pointers, the order of nodes within a linked list are not given by their physical placement in memory

Linked List Operation Time Complexity

Comparing Linked Lists to Arrays

It seems that linked lists are very similar to arrays, but have natural drawbacks

• ❓ What is the time complexity of indexing for an array?
• ❓ Is it possible for us to look backwards through a linked list where each node only has a data and next property?

But for us to understand the advantages of linked lists, we'll have to do a bit of a review of arrays

For this lesson, we'll be discussing dynamic arrays, instead of static arrays

• A dynamic array stores all elements consecutively in memory, and keeps a count of the current number of elements

  • arrays are allocated space when defined
  • if the space reserved for the dynamic array is exceeded, it is reallocated and (possibly) copied

• If we want to insert something into an array, we have to make space by "scooting over" every element, starting at the index we want to insert at
• ❓ What must we do if we want to delete an element in the middle of the array?
• ❓ What are some of the advantages of linked lists over arrays?

Review of JS Class Syntax

Talking about theory is a lot of fun, but what better way is there for us to understand linked lists than by creating them ourselves?

If you were to implement a linked list, you would create instances of linked lists, much like you create instances of arrays and objects. Although we are used to using literals to create arrays ([]) and objectss ({}), remember that we are able to instantiate them using "classes" as well!

let myArr = new Array();
let myObj = new Object();

When you do your exercises, your goal will be to create a LinkedList class, which you would then be able to invoke with the below syntax to create shiny new linked list objects.

let myLinkedList = new LinkedList();

JS Class Syntax

The easiest way for us to create JS "classes" is to use the class declaration syntactic sugar (because classes don't actually exist in JS):

 class LinkedList {

 }

Now you have a class which can be used to create shiny new objects that are instances of our LinkedList class. However, if we were to create an instance of this class, it would just be an empty object. If we want our objects to hold properties, we will use the constructor method to assign properties to them!

The constructor is a method that you add to your class, in which you provide the properties for your objects to have. You should always use the this keyword to define the property, and then the value can be whatever you want it to be.

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

Well, what if you wanted your properties to have values that can be provided when instantiated? A typical example of this would be assigning a name to an instance of the Human class. Or for linked lists, our nodes would have data. For that, we will create parameters for the constructor!

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

let myNode = new Node(4);

One thing to note here is that you can call your parameters whatever you want. If you wanted to define the parameter as dinosaur, that would be totally fine. You would then say this.data = dinasaur. But how are multiple parameters assigned from arguments? Positionally!

class Human {
    constructor(name, age) {
        this.name = name;
        this.age = age;
    }
}

let me = new Human('Shaw', 34);

Finally, let's talk about instance methods. Some famous instance methods you know might be the array.push() and array.pop() methods. These are functions that you invoke on specific instances of your class, and they can be defined like this:

class Human {
    constructor(name, age) {
        this.name = name;
        this.age = age;
    }
    speak() {
        console.log(`hello my name is ${this.name} and I am ${this.age} years old!`)
    }
}

let me = new Human('Shaw', 34);
me.speak();

If you ever need to refer to properties of the object that we are using, you must preface the property name with this!

Visualizing a Linked List

• When we create a linked list, we initialize it with a head property, which will refer to the first node

  • When you initialize a linked list, head will not point to anything yet, so it will point to null

• The easiest place to add more nodes to the linked list is at the end of the list

  • ❓ How do we know if you have reached the end of a linked list?

We will be referring to this graphic for the below sections

Traversing a Linked List with the Walker

Looking at the time complexity graphic, we are aware that accessing a node in a linked list has linear time complexity

• This is because we have to traverse (or walk through) the list until we get to the node we are looking for
• Since we are walking through the linked list, we often call our iterator walker

In order to traverse a linked list, we will need to start at head, and use the next pointers to iterate through the list

let walker = this.head;
while (walker.next) {
    walker = walker.next;
}

❓ In our handy little graphic above, where will walker end up?

❓ How could we edit the condition such that walker will become the final null value?

Removing Nodes from a Linked List

Let's go back to our example with 4, 7, and 12

If we wanted to remove our node with data of 7, how hard would it be?

• Can't we just tell our node with data of 4 to look at the node with data of 12?

Heck yes we can! Let's see it in action with some code

// we will have our walker again, and it will be the node with data of 4

// so let's just remove 7 by doing
walker.next = walker.next.next

❓ Assume walker is now the node with data of 7, would the code change if we wanted to remove the node with data of 12?

Essential Questions

1. When we want to add a node to a linked list, do we have to scoot over the subsequent nodes (like we do for arrays)?
2. Can we do index access like we can with arrays with linked lists?

BONUS: Swapping Nodes in a Linked List

One of the operations that might be performed in a linked list is the swapping of nodes

Using the below image, what if we wanted to swap the node with a data of 7 with the node with a data of 12

The end goal would be:

Let's visualize the swap where we first move out the node with a data of 12 and it's next pointer

• At this point, we haven't done any attachments yet, but here are some of the things that much be done

  • the node with data of 7 should point to what the node with data of 12 was previously pointing at
  • The node with a data of 12 should now point to our node with data of 7
  • the node with a data of 4 should now point to our node with data of 12

Let's try connecting our arrows

If we were to convert this to code, it will look something like this

// assume that walker is the node with data of 4
// therefore, walker.next would be the node with data of 7
// and walker.next.next is the node with data of 12

// first, we should "move" out the node with data of 12
// we are just saving the node to a variable
let temp = walker.next.next;
// point node with data of 7 to what node with data of 12 was looking at
walker.next.next = temp.next;
// point the node with data of 12 to node with data of 7
temp.next = walker.next;
// connect walker to node with data of 12
walker.next = temp;

❓ Is it possible to swap 7 and 12 without having a reference to what precedes 7?

❓ How would this code change if we wanted to swap the head node with what comes after it?

❓ Isn't putting the node with data of 12 back to the linked list a lot like inserting?

Part 2: Stacks & Queues

Overview

This lesson covers an introduction to the concept of Stacks and Queues.

Learning Objectives

By the end of this lesson, you will be able to:

• Distinguish between the behavior of a stack and a queue.
• Determine situations in which you’d use a stack or queue versus another data structure.
• Build a stack and a queue using a linked list or an array.

What are Stacks & Queues?

Stacks and queues in computer science are a lot like stacks and queues in real life. It helps if you think of stacks of pancakes and queues, or lines, of people.

Queues

Let’s take a look. It’s Saturday morning, and out of the kindness of your heart you decide to make pancakes for your family. You’re gathering all the ingredients when you check the fridge and discover you’re out of eggs! You rush to the grocery store, grab the eggs, and of course the line to check out — the queue — is five-people deep. You move to the back and wait your turn.

Waiting in line for the cash register mirrors how a queue works in computer science. They’re defined by first-in, first-out behavior. That is, the first thing that’s added to a queue will be the first thing removed; the first person in line will be the first person who gets to check out.

Queues operate on "first-in, first-out" (aka, FIFO) behavior. Items are removed in the order they were added, from first to last.

Computer processing unit (CPU) scheduling is based on a queue. Tasks are executed in the order in which they were called, while the execution of tasks further down in the queue is put on hold until resources are available, on a first in, first out basis.

Stacks

Now for stacks. You’ve made it home and the pancakes are coming together beautifully. As you cook, you flip the pancakes off the griddle and onto a plate. You finish up the last batch and bring the pancakes to the table to serve your family. Which pancakes are going to be taken first? The hot, fresh pancakes on the top of the stack? Or the pancake on the bottom that’s now cold and getting smushed? We know which one we’d take — the hot one on the top.

Watching your family take the fresh pancakes off the top of the plate is how a stack works. A stack is defined by last-in, first-out behavior — the opposite of how a queue works. The last thing added to the stack — the freshest pancake — is the first thing to be removed.

Stacks operate on “last-in, first-out” (aka, LIFO) behavior. The last, most recently added item, is the first to be removed.

The function call stack is a common example of stacks in programming. When you call a function to execute, it’s pushed to the top of the stack and runs until we add another function to the stack, which then runs until it returns (or another function is pushed to the top), on a last in, first out basis. You can keep adding functions until you’ve run out of space in the stack, in which case you’ve reached stack overflow. (Mmm, pancake stack overflow... 😋)

❓ What data structure would be represented by the 'back' button in the browser?

❓ What data structure would be represented by sending documents to the printer?

❓ What data structure would be represented by the 'undo' or Cmd-Z function?

Operations in Stacks & Queues

Stacks and queues might seem totally different, but they actually have a lot in common.

One important similarity is that we can perform the same relatively limited set of actions on them.

The trade-off for limited functionality? Great runtimes, which are the same for stacks and queues! Check it out:

❓ Imagine that you started with an empty stack and perform the following operations:

1. PUSH 0
2. POP
3. PUSH 2
4. PUSH 4
5. PUSH 6
6. POP
7. PUSH 8

...What would the stack look like at the end? (Hint: It might help to sketch this out on a piece of paper!)

❓ Imagine that you start with an empty queue and perform the following operations:

1. ENQUEUE 15
2. DEQUEUE
3. ENQUEUE "Popcorn"
4. ENQUEUE 515
5. ENQUEUE "GA"
6. DEQUEUE
7. ENQUEUE "Smile!"

...What would your queue end up looking like?

Implementing Stacks & Queues

The other thing that stacks and queues have in common is that they can both be implemented as an array or as a linked list.

Other than using different underlying data structures, there’s no major difference between array and linked list implementation. Which you use depends on how your data is already structured and how you expect to be inserting or removing elements.

For the implementations in this exercise, we'll be using array-based implementations.

❓ Quick refresher: The major difference between a linked list and an array is how they store data in a computer’s memory.

Which of the following statements is true about how linked lists and arrays store data? 🧐

• Linked lists store data in one continuous block of memory.
• Arrays store data in one continuous block of memory.
• Linked lists can store data anywhere in a computer's memory using pointers.
• Arrays can store data anywhere in a computer's memory using the index.

Queue Variations

Queues have a couple of unique implementations that we'll touch on.

Priority Queues

These have three rules in addition to regular queues:

1. Every item has a priority associated with it.
2. An element with high priority is dequeued before an element with low priority.
3. If two elements have the same priority, they are served according to their order in the queue.

Examples: Airport priority boarding, CPU scheduling

Double-Ended Queues

A double-ended queue, or "deque", perform insertions and deletions at both ends of the queue. They're usually implemented with doubly-linked lists or dynamic arrays.

Have you ever been last in a long line at the grocery store only to see a cashier one lane over open up their register? Typically, that cashier will beckon to you to jump into their lane so you can be checked out right away. That’s basically what happens in a deque.

Example: spreading tasks between different servers as equally as possible

Essential Questions

❓ You're working on building a message board and want to display only the 10 most recent messages a user posted, in the order they were posted. Which data structure should you use?

❓ You and your partner are going out for your anniversary dinner. When you arrive, you ask the host for a table for two and your name goes on the waiting list. While you’re waiting, a group of seven people walks right in and gets seated. What gives?!

Interviews

If stacks or queues come up in an interview, you’ll likely be asked to perform operations such as sorting, inserting, and finding values — and it only gets more complicated from there.

• This article on stacks outlines some standard problems that could come up in interviews.
• The same article, but for queues.
• Don’t forget to review priority queues and deques. (You might not be asked to build one of these, mostly to explain how they work and their uses.)

Use these visualization tools to practice building stacks and queues:

• Stacks: array implementation and linked list implementation.
• Queues: array implementation and linked list implementation.

Additional Resources

• A deep dive into Stacks and Queues with plenty of diagrams!
• This overview investigates JavaScript implementations of stacks and queues.
• Looking for more comp sci resources? Check out Khan Academy's tutorials on algorithms and the science of the Internet.