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?

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

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

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

• Many other problems on LeetCode
• Remove n-th node from end of LinkedList
• Worth going through “easy” ones sooner rather than later!