Overview

There are a lot of variations on the linear data structures that we’ve thought about so far. Today, we’ll focus on one that give us some helpful additional functionality: double-ended queues (“deques” pronounced “decks”). We’ll also revisit linked lists again to think about how we could implement a deque with a custom linked list.

Basic Learning Objectives

Before class, you should be able to:

  • Describe what a deque is
  • Describe the steps of each deque operation

Advanced Learning Objectives

After class, you should be able to:

  • Implement a deque with a doubly-linked-list
  • Explain the time complexity of each operation

Readings

Read the following:

Checks

Submit your to the following on Moodle.

  • What modifications would be necessary to a linked list class to use it to implement a deque?