Overview

There are a lot of variations on the linear data structures that we’ve thought about so far. Today, we’ll focus on two that give us some helpful additional functionality: double-ended queues (“deques” pronounced “decks”) and doubly-linked lists.

Basic Learning Objectives

Before class, you should be able to:

  • Describe what a doubly-linked list is
  • Describe what a double-ended queue is

Advanced Learning Objectives

After class, you should be able to:

  • Describe the steps of each doubly-linked list operation
  • Describe the steps of each double-ended queue operation
  • Explain the time complexity of each operation

Readings

Read the following:

Checks

Submit answers to the following on Moodle. For the following questions, compare the Double-Ended Queue, Singly-Linked List, Queue implementations in Kotlin.

  1. Which double-ended queue operation and Singly-Linked List operation perform the same task as the Queue enqueue() operation?
  2. What is the Big-O time complexity of the Queue enqueue() operation? Of its analogous Double-Ended Queue and Singly-Linked List operations?
  3. Which Double-Ended Queue operation and Singly-Linked List operation perform the same task as the Queue dequeue() operation?
  4. What is the Big-O time complexity of the Queue dequeue() operation? Of its analogous Double-Ended Queue and Singly-Linked List operations?
  5. Between the Queue and Double-Ended Queue implementations, which one do you think takes up more space in memory? Why?
    • Hint: Consider the variables and their respective types used in each implementation. You can see how much space each type takes in the Kotlin documentation.

Acknowledgements

The check questions and diagram are from Prof Jean Salac.