1 of 12

Tips and Common Points of Confusion

2 of 12

How to Get Started

Stuck on LinkedListDeque and/or ArrayDeque? One great first step is implementing SList and/or AList. Starter code can be found in:

  • SList: lec4/DIY
  • AList: lec6/DIY

​

To make this more time efficient:

  • Work with a friend or two or three.
  • See solutions (available on github) (for when you get stuck or just want to compare).

​

​

​

3 of 12

How to Get Started (Part 2)

Try implementing just the empty Deque, and compare your data structure to the idea developed in class.

  • e.g. your LinkedListDeque() constructor should probably build either:
    • The top figure from this slide (if you’re doing two sentinel nodes).
    • The top figure from this slide (if you’re going circular).

​

Compare the output of your code using the visualizer.

  • Make sure to set “prefer non-nesting and vertical layouts”

4 of 12

Other General Tips

Take things a little at a time.

  • Writing tons of code all at once is going to lead to misery and only misery.
  • If you wrote too much stuff and feel overwhelmed, comment out whatever is unnecessary.

​

If your first try goes badly, don’t be afraid to scrap your code and start over.

  • The amount of code for each class isn’t actually that much (my solution is about 130 lines for each .java file, including all comments and whitespace).

​

Consider not doing resizing at all until you know your code works without it.

  • Resizing is a performance optimization (and is required for full credit).

5 of 12

Common Point of Confusion

Any time I drew an arrow in class that pointed at an object, the pointer was to the ENTIRE object, not a particular field of an object.

  • For example, the bits in the “sentinel” box do not point at the “next” field of the leftmost node. They instead point to the ENTIRE node.
  • (in fact it is impossible for a reference to point to the fields of an object in Java)

sentinel

5

2

size

17

??

next

item

prev

insertBack()

getBack()

size()

deleteBack()

Examples:

  • sentinel.next.next is the node with item=17.
  • sentinel.next.next.next is the sentinel node.
  • The arrow in purple is sentinel.next.next.next

6 of 12

Circular ArrayDeque Demo

7 of 12

ArrayDeque Tips

Starting from an empty ArrayDeque:

addLast()

addFirst()

items

4

nextFirst

5

nextLast

0 1 2 3 4 5 6 7

0

size

8 of 12

ArrayDeque Tips

Starting from an empty ArrayDeque:

  • addLast(“a”)

addLast()

addFirst()

items

4

nextFirst

a

6

nextLast

0 1 2 3 4 5 6 7

1

size

9 of 12

ArrayDeque Tips

Starting from an empty ArrayDeque:

  • addLast(“a”)
  • addLast(“b”)

addLast()

addFirst()

items

4

nextFirst

a

b

7

nextLast

0 1 2 3 4 5 6 7

2

size

10 of 12

ArrayDeque Tips

Starting from an empty ArrayDeque:

  • addLast(“a”)
  • addLast(“b”)
  • addFirst(“c”)

addLast()

addFirst()

items

3

nextFirst

c

a

b

7

nextLast

0 1 2 3 4 5 6 7

3

size

11 of 12

ArrayDeque Tips

Starting from an empty ArrayDeque:

  • addLast(“a”)
  • addLast(“b”)
  • addFirst(“c”)
  • addLast(“d”)

addLast()

addFirst()

items

3

nextFirst

c

a

b

d

0

nextLast

0 1 2 3 4 5 6 7

4

size

12 of 12

ArrayDeque Tips

Starting from an empty ArrayDeque:

  • addLast(“a”)
  • addLast(“b”)
  • addFirst(“c”)
  • addLast(“d”)
  • addLast(“e”)

​

addLast()

addFirst()

items

e

3

nextFirst

c

a

b

d

1

nextLast

0 1 2 3 4 5 6 7

5

size