Data Structures

Professor Abdul-Quader

Lesson 3

Review

  • Iterators: next, hasNext, and remove.
    • Keep a “pointer” to current list item.
    • Advance it each time you call next.
  • LinkedList
    • Data kept in “nodes”.
    • Implementing get / remove / insert / etc: similar idea!

LinkedList

  • Node class is an inner class. Why?
  • Static. Why?

Video

JUnit in IntelliJ

  • Setting up
  • Right-click on class-name: show context actions.
  • Create test.
  • Need to download JUnit 5 / add to project.
  • Annotate tests with @Test above.

Questions?

  • Iterators?
  • LinkedLists?
  • HW 1?

Stacks and Queues

Stack of plates
Queue of people

Idea

  • Both are restrictions of list ADT.
  • Neither allow: iteration, random access, insertions/deletions in middle
  • Main two operations: insert and remove
  • Also: “peek”, “size”, “isEmpty”

Operations

Stack:

  • push: insert an item “on top” of the stack.
  • pop: remove the top item.
  • LIFO “Last In, First Out”.

Queue:

  • enqueue: add to the end of the queue
  • dequeue: remove from the beginning of the queue.
  • FIFO: “First In, First Out”

Questions

  • How might you implement each of these ADTs with an array / ArrayList?
  • How might you implement each of these ADTs with a LinkedList?

Exercise: Describe (pseudocode / English / to each other) implementations in which all the operations listed above are \(O(1)\).

Warning: never use the built-in java.util.Stack class. There are better implementations: in particular, ArrayDeque and LinkedList.

Deques

  • deque: doubly-ended queue.
  • Supports all of the operations: push / pop and enqueue / dequeue.
  • In Java: Deque is an interface (as is Queue)
  • Implementations: ArrayDeque, LinkedList

Video

Challenge Questions

Some problems to think about. Try to find the best algorithms to solve these problems. I don’t expect you to do all of these now, or even to implement any of them, but do your best to come up with an algorithm that would solve it (at least on paper). Then we can discuss some of our solutions on Thursday.

Reverse a Singly Linked List

Given a singly LinkedList, how might you implement a reverse method? Moreover, how might you do this in-place: that is, without using a secondary list or additional storage?

Middle element of a Linked List

Given a singly LinkedList, how might you find the middle element in one loop? (ie in N steps, not in 2N steps).

Collate Iterators

Suppose we have an array of Iterators. Implement an Iterator which “collates” these. That is, suppose we have iterators for the following lists:

  • [0, 1, 2]
  • [3, 4 ]
  • [5, 6, 7, 8, 9]

Collate Iterators

Then the result of

Iterator<Integer> iter = new CollatedIterator(iterArray);
while (iter.hasNext()) {
  int i = iter.next();
  System.out.println(i);
}

would be 0, 3, 5, 1, 4, 6, 2, 7, 8, 9 (on separate lines, without commas).

Bracket Matching

The following strings of brackets are perfectly matched:

  • {}([])
  • [(()())]

The following are not:

  • {(})
  • (][)

Devise an algorithm which, given a string of brackets, determines if the brackets are perfectly matched.

Base Counting

Devise an algorithm which, given an input \(n\), outputs all numbers from 1 to \(n\) in binary. Example: if \(n = 5\), then we write 1, 10, 11, 100, 101, 110. (The format of the output doesn’t matter, they can all be on separate lines.)

LeetCode

// reveal.js plugins