Lists Abstract Data Type (ADT) Revisited

Recall from our previous lecture that an ADT, or Abstract Data Type, defines the requirements of a particular data structure.

It is not an exact implementation, but rather defines what an implementation would look like.

For a List, the ADT includes the following characteristics:

• It keeps multiple items
• It can insert and delete items at any position
• It can contain duplicates
• It preserves the order of items

An Example: Selling Tickets

Let's take a look at a code snippet:

// list, in order, of people who want tickets
ticketBuyers = ["Elie", "Alissa", "Matt", "Michael"];

// ... lots of code

// sell tickets, in order
while (ticketBuyers.length) {
  buyer = ticketBuyers.pop();
  purchase(buyer);
}

In the case above, we're selling tickets out of order.

The person who has most recently gotten in line gets sold a ticket first, which is probably not what we'd expect (and the person who got in line first? Not happy!).

An Example: Print Jobs

Let's consider another problem.

Say we're building a print job-queuing system. Our application looks as follows:

// list of print jobs
jobs = ["resume.doc", "budget.xls", "plan.pdf", "css.css"];

// process list of print jobs in order
while (jobs.length) {
  let job = jobs.shift();
  printJob(job);
}

But we have a performance consideration to take into account.

When a print job is taken from the front of our list, every subsequent item must shift by one index, resulting in a runtime of O(n).

How might we improve the performance of our implementation?

In the case above, since we'd like to remove an item from the an end, a Linked List would be the better choice.

Considering Constraints

In both cases provided above, we need only some of the capabilities we outlined in the list ADT above. Namely:

1. We need to be able to add a new item to the end of the list
2. We need to be able to remove the first item from the list

With these two requirements identified, we can now pick a more suitable data structure for the problem at hand.

And, if we do it well, we can prevent accidental misuse (like the buying of tickets out of order from our first example).

Let's learn about two new ADTs.

Queues

Our first new ADT is a queue.

Just like the word we use to describe a line of people, we add items to the end of the queue and remove from the beginning.

Queues are like Lists/Arrays except that new items are only added to the queue by adding them at the end of the collection. The term for this is called enqueueing.

Conversely, items are only taken from the queue by removing them at the front of the collection, referred to as dequeueing.

Enqueue = adding to the end of the queue. Dequeue = removing from the front of the queue.

Older items are at the front of the queue, newer items are at the back, with the last item being the very newest item of all.

We refer to this structure and behavior as FIFO, or "First-In, First-Out": items that were added first will be removed first.

Typical Methods

The methods typical to a queue data structure are as follows:

• enqueue(item). Adds an item to the end
• dequeue(). Removes and returns the first item
• peek(). Returns the first item, but doesn't remove it
• isEmpty(). A boolean that tells us if there are any items
• length(). The number of items in the queue

Sometimes enqueue and dequeue are named push and pop, respectively.

Queue Implementation

Given all the data structure options we have available to us, which is best suited for a queue?

Arrays? Linked Lists? Doubly-Linked Lists? Objects?

Let's consider each.

Array - O(n)

As we pointed out in our earlier example of a print-job application, dequeing an item from the Array would be O(n).

Why O(n)? When the first item is removed, all subsequent items must shift over by an index of 1.

Linked List - O(1)

As we've learned, one of the benefits of a Linked List is that removing from the front and the back of the collection is constant runtime, or O(1).

As part of this data structure, we have a reference to both the first item (head) and the last item (tail).

When we remove the first item in the collection, we just need to redirect the head to point to the next item in line.

Doubly-Linked List - O(1)

Our Doubly-Linked List is exactly like our Linked List, but with each node containing not only a reference to the next item in line, but also the item that came before it.

And, like Linked Lists, both enqueue and dequeue are O(1).

Object - O(n)

Though possible to create a queue using an object, like an Array, dequeuing would require scanning all keys in the object in order to locate the correct item for removal.

Stacks

When you hear the term "stacks" in the context of data structures, I want to picture in your mind a tall stack of pancakes.

I promise this will be useful when considering which data structure to reach for when you're asked to implement an algorithm!

Let's consider an example.

Say we've identified an end goal of some sort. For our case, we'd like to order pizza for a company party.

There are a series of steps that must happen, in order, to reach that end.

• Call the restaurant

  • The employee asks how many pizzas we'd like

    • We ask them to hold while we ask our boss about the budget

      • We're told an amount in CAD, but the pizza place takes USD

        • We look up the USD -> CAD conversion rate
      • We convert the budget to CAD
    • We tell the pizza place the budget
  • ...

Similar to a function being called, when processing each item on a stack, we return to the "previous state" (in this case, previously queued action) when we remove a task.

Revisiting the mental image of the delicious pancake stack, as we make each pancake, we place them on top of one another. And when we sit down to eat them (one at a time!), we eat the top one -- the most recently added one -- first.

Items are only added to the stack by pushing them onto the top and are only removed from the stack by popping them off the top.

As such, newer items are at the top of the stack, whereas older items are at the bottom.

This adding/removing behavior is referred to as LIFO, or "Last-In, First-Out".

Typical Methods

The methods typical to a stack data structure are as follows:

• push(item). Adds an item to the top
• pop(). Removes and returns the top item
• peek(). Returns the top item, but doesn't remove it
• isEmpty(). A boolean that tells us if there are any items

Stack Implementation

Which data structure is best suited for a stack implementation?

Keeping in mind that we need to only push and pop to one end of the collection (the end, or top), let's consider our options.

Array - O(1)

Pushing and popping from an Array are both constant-time operations since we're only accessing the last item in the collection.

Linked List - O(1)

Since we have a reference to the last item (tail) when using a Linked List, adding or removing the last ("top") item from the stack would be a constant-time operation.

Doubly-Linked List - O(1)

Like Linked Lists, both push and pop are O(1).

Object - O(n)

In the case of an object, we'd have to scan every key to find the most recently added item, meaning that the runtime would be O(N), making this a less-than-ideal choice for a stack data structure.

Deques

Though not as common as a stack or queue, a Deque, or a Double-Ended Queue, is another Abstract Data Type to be aware of.

In addition to push and pop methods, this data structure also features the abilit to shift (remove from the front) and unshift add a new item to the front.

An Example: Buying Tickets

Let's revisit our previous example of buying tickets.

Customers enter the queue (at the end) when they'd like to buy tickets.

Once it's their turn, they are removed from the front of the queue.

But if it's the case that they don't buy right away, say if they have a question or concern about their purchase, it wouldn't be fair to make them wait all over again.

Instead of being placed at the back again, they are pushed to the front of the queue since they've already waited their turn.

Some task or job allocation systems work in this way. If an attempt to process a job fails, it doesn't get put at the back of the queue again, but rather is set as the next-to-process job in line.

Typical Methods

Method names vary across implementations, but generally speaking, the following methods can be expected for a deque:

• appendLeft(item). Add to the beginning
• appendRight(item). Add to the end
• popLeft(). Remove from the beginning
• popRight(). Remove from the end
• peekLeft(). Return first item, but don't remove
• peekRight(). Return last item, but don't remove
• isEmpty(). A boolean that tells us if there are any items

Deque Implementation

For a deque, which is the best data structure to reach for?

Array - O(n)

Adding to the end of an Array might be a constant-time operation (O(1)), but as we've reviewed, adding or removing an item to the front (appendLeft and popLeft) would result in an O(n) operation.

Linked List - O(n)

With Linked Lists, recall that we have references to both the head and tail.

But, any given node has no reference to the item that came before it.

What this means is that when we popRight(), or remove an item from the end of the queue, we would have to traverse the entire List to get to the second-to-last node in order to set the new tail reference (O(n)).

Doubly-Linked List - O(1)

With a Doubly-Linked List, liked a Linked List, we have references to both the head and the tail of the queue.

But, unlike Linked Lists, each node also has a reference to the node that came before it.

What this means is that we can easily grab the last item and also set our tail reference to point to the node that comes before the last node.

Because of this, appendLeft, appendRight, popLeft and popRight are all O(1).

Object - O(n)

And, as we've seen with every consideration up to this point, an Object would be a poor choice since we'd have to iterate over each key to find what we're looking for.

Priority Queue

Last but not least, let's look at another ADT: the Priority Queue.

The characteristics that a Priority Queue must have include:

• It can add an item (with a designated priority)
• It can remove the highest-priority item

Typical Methods

Common methods for Priority Queues include:

• add(priority, item). Add to the queue, based on priority
• poll(). Remove and return top-priority item
• peek(). Return top-priority item, but don't remove
• isEmpty(). A boolean that tells us if there are any items

Priority Queue Implementation

The Priority Queue is a bit different when tackling implementation since we can go about it in different ways depending on our strategy.

Consider the two following approaches:

• Keep it unsorted, add new items to the end, and find the top priority item through our poll method
• Keep it sorted, add in the appropriate place, and the top priority item is always at the front of the queue

Strategy: Unsorted

For our unsorted-queue strategy:

Array - O(n)

Finding the highest priority item (peek()) is an O(n) operation, as is the removal of that item (poll()).

However, adding an item to the queue is O(1).

Linked List - O(n)

As with an Array, peek() and poll() are both O(n).

Doubly-Linked List - O(n)

Again, peek() and poll() are O(n).

Strategy: Sorted

For our sorted-queue strategy:

Array - O(n)

Adding an item to the correct place in this queue would be O(n), as we'd have to traverse each node in order to determine where the new item should sit.

Additionally, the removal portion of poll() would result in all nodes being shifted (O(n)).

Linked List - O(n)

With a Linked List, adding an item to the queue would be an O(n) operation because we would need to traverse the List in order to find the proper placement of the item.

Doubly-Linked List - O(n)

And, similar to the example above, we would still need to traverse the entire collection in order to properly place the newly added node based on its priority.