CS 61B | Project 1 | Data Structures (Deque API)


Project 1A - Deque (Linked List & Array)

Code: link
Guide: link
Tips (not too much!): link

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.

Work out what your data structures will look like on paper before you try implementing them in code! If you can find a willing friend, have them give commands, while you attempt to draw everything out. Try to come up with operations that might reveal problems with your implementation.

Sentinel nodes make life much easier, once you understand them.

Circular data structures make life easier for both implementations (but especially the ArrayDeque, e.g., MOD operation).

The Deque API

The double ended queue is very similar to the SLList and AList classes that we’ve discussed in class.

Deque (usually pronounced like “deck”) is an irregular acronym of double-ended queue. Double-ended queues are sequence containers with dynamic sizes that can be expanded or contracted on both ends (either its front or its back).

Generally implemented as a dynamic array, it allows direct access to any element in the sequence and provides relatively fast addition/removal of elements at the beginning or the end of the sequence.

  • addFirst(T x)
  • addLast(T x)
  • isEmpty()
  • size()
  • printDeque()
  • T removeFirst()
  • T removeLast(T)
  • T get(int index)

LinkedListDeque

Code (see above link)

Compared to array deque, this one is not difficult. Just pay attention to special cases and the way to loop.

Note: there is a circular sentinel.

get

  • get (iterative version)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    // 0 1 2 3 4 5
    // 3 5 9 5 3 8
    public T get(int index) {
    // if (isEmpty()) { return null; }
    /* could be removed, since we set sentinel.item == null */
    Node p = sentinel.next; /* the 1st real node */
    while (index > 0 && p != sentinel) { /* p != sentinel stops outofbound cases */
    p = p.next;
    index--;
    }
    return p.item; /* when index is out of bound, returns null (sentinel) */
    }
  • get (recursive version)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    /** getRecursive - LinkedListDeque class */
    public T getRecursive(int index) {
    /** sentinel.next won't be null */
    Node firstNode = sentinel.next;
    return firstNode.get(index); /* Node.get */
    }

    /** Helper Method (Recursive) - Node class */
    public T get(int index) {
    if (index <= 0) {
    return item;
    } else if (this == sentinel) { /* what if index is very large */
    /** Returns null if index is out of bound */
    return null;
    }
    return next.get(index - 1); /* better */
    }

addFirst

1
2
3
4
5
6
public void addFirst(T item) {
Node newNode = new Node(item, sentinel, sentinel.next);
sentinel.next = newNode;
newNode.next.prev = newNode;
size += 1;
}

addLast

1
2
3
4
5
6
public void addLast(T item) {
Node newNode = new Node(item, sentinel.prev, sentinel);
sentinel.prev = newNode;
newNode.prev.next = newNode;
size += 1;
}

removeFirst

1
2
3
4
5
6
7
8
9
10
public T removeFirst() {
if (isEmpty()) { /* because of circular sentinel, removedNode won't be null */
return null; /* just in case size -= 1, return is okay since sentinel.item is null */
}
Node removedNode = sentinel.next; /* even without if, these two lines won't crash */
sentinel.next = removedNode.next;
removedNode.next.prev = sentinel; /* ok for all size >= 1 */
size -= 1; /** But "if" decides if this line should be run */
return removedNode.item;
}

removeLast

1
2
3
4
5
6
7
8
9
10
11
public T removeLast() {
if (isEmpty()) {
return null;
}
/** Usually, when using a circular sentinel and the list is empty, both sides of the equation are pointing at the sentinel! Just do useless work */
Node removedNode = sentinel.prev; /** Use some local variables */
removedNode.prev.next = sentinel;
sentinel.prev = removedNode.prev;
size -= 1;
return removedNode.item;
}

Array Deque

Constructor (How/where to start?)

One requirement of the project is that the initSize of the array should be 8. We can initially make it 4. Make things easier! Later, we have to deal with many boundary cases and design a way to resize the array.

What fields do we need?

1
2
3
4
5
6
7
publci class ArrayDeque<T> {
private int size;
private int nextFirst;
private int nextLast;
private T[] items;
private int initSize = 4;
}

First, where do we start? Well, I can pick a position, what about the middle position mid = length / 2.

[ ][ ][ ][ ]

nextFirst and nextLast point to the same box or two boxes?

If they point to the same box, for addFirst and addLast, we have to deal with special cases.

What if nextFirst points to the leftmost element (i.e. nextFirst - 1 is the position we about to put a new element in), while nextLast points to the position we about to put a new element in? Think about it.

Finally, I decide to make them point to the future spots because it makes code cleaner without special if. It’s more intuitive too.

1
2
3
4
5
6
7
public ArrayDeque() {
items = (T[]) new Object[initSize];
int mid = items.length / 2;
nextFirst = mid - 1;
nextLast = mid;
size = 0;
}

Hit the Boundary

When there is no enough space in one side, I’ll put elements into the other side. The guide suggests we using the circular approach. There are few things we need to think over while designing the algorithm.

  • When to resize?

    F stands for nextFirst; L stands for nextLast.

    Init state: [ ][ ][ ][ ]

    F points to the 2nd box. L points to the 3rd box.

    Consider 3 cases here:

    • Invoke addFirst only:

      1
      2
      3
      4
       0  1  2  3
      [x][x][ ][x]
      -------F---- F starts from 1 to 2 (move 3 times)
      -------L---- L doesn't change
    • Invoke addLast only:

      1
      2
      3
      4
       0  1  2  3
      [x][ ][x][x]
      ----F------- F doesn't change
      ----L------- L starts from 2 to 1 (move 3 times)
    • Move F 1 time & Move L 2 times:

      1
      2
      3
      4
       0  1  2  3
      [ ][x][x][x]
      -F---------- F starts from 1 to 0
      -L---------- L starts from 2 to 0
    • Move F

      1
      2
      3
      4
       0  1  2  3  4  5
      [x][x][x][x][ ][x]
      -------------F---- F starts from 2 to 4
      -------------L---- L starts from 3 to 4

    My question is do we need to add one more element into the array, in other words, make it fully filled?

    You’ll see it is not a good idea. The 1st reason is that once we do that we don’t know how to detect whether the array is full, although we can use size. That L is before F doesn’t ensure that the array is full.

    However, the most important reason is that if we keep F always equal or less than L we can make things easier or possible for later implementation of get and resize.

    In these functions, we need to know which part of the array belongs to the left or right side.

    Note: You know what. Later, I think it’s okay to fully fill that out. What we need to do in later iteration, the order is either F -> L (not full), F -> END -> START -> L. So the relative order of F and L does not really matters here. F may encounter L, but size could tell that it does not reach the END.

    Also, we need resize when the array is full… not at any other time :)

  • Since we need to implement get(int index) of a constant time later, how can we calculate the real index? (horrible) And how to resize?

My solution

My solution for addFirst, addLast, and resize (all passed the test):

Test: ArrayDequeTest.java

resize & resizeDown
  • resize

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    public void resize(int capacity) {

    T[] newItems = (T[]) new Object[capacity];
    // 0 1 2 3 4 5 6 7
    // [x][x][x][x] items (copy array)
    // [ ][ ][ ][ ][ ][ ][ ][ ] newItems
    // [x][x][x] if initSize is an odd number
    // [ ][ ][ ][ ][ ][ ]
    int startPos = newItems.length / 2 - size / 2; /* draw a picture */
    /** Copy */
    /* // stupid way
    int oldIndex = (nextFirst + 1 > size - 1) ? (0) : (nextFirst + 1);
    // if nextF points at the last position, it means we need to start from 0
    */
    int oldIndex = nextFirst + 1; /* Use MOD operation instead */
    int newIndex = startPos; /* newIndex for newItems */
    int count = 0;
    while (count < size) { /* yes! the original size! */
    newItems[newIndex] = items[oldIndex % items.length]; /* 3 + 1 = 4, 4 % 4 = 0 */
    oldIndex++; newIndex++;
    count++;
    }
    /** Set new fields */
    items = newItems;
    // size = capacity; bug! we don't need to change size!
    nextFirst = startPos - 1;
    nextLast = newIndex; /* or nextFirst + size */
    }
  • resizeDown

    1
    2
    3
    private void resizeDown() {
    resize(size * 2 < initSize ? initSize : size * 2); /* if it is too small, make it 8 */
    }
addFirst/addLast
  • addFirst

    1
    2
    3
    4
    5
    6
    7
    8
    9
    public void addFirst(T item) {
    if (size == items.length) { /** FULL! */
    resize(items.length * 2);
    }
    items[nextFirst] = item;
    nextFirst = ((nextFirst - 1) + items.length) % items.length;
    /* since in java, -5 % 6 == -5, we need to add items.length */
    size++;
    }
  • addLast

    1
    2
    3
    4
    5
    6
    7
    8
    public void addLast(T item) {
    if (size == items.length) {
    resize(items.length * 2);
    }
    items[nextLast] = item;
    nextLast = (nextLast + 1) % items.length; /* nextLast += 1 */
    size++;
    }
removeFirst/removeLast

Now, let’s finish up with removeFirst, removeLast, and get. Based on the code of addFirst and addLast, it is not difficult. But there are few things to be mentioned.

  • Set the deleted item reference to null. It helps the Garbage Collector to clean the unused objects. If you don’t do it, it still stays there.
  • Be careful about the boundary. I just copy the code from addFirst and addLast, then write cases to test them out.
  • Invariants:
    • nextFirst always points to the previous position of the first element.
    • nextLast always points to the next position of the last element.
  • removeFirst

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    public T removeFirst() {
    if (isEmpty()) {
    return null;
    }

    /** Resize down */
    if ((double) size / items.length < 0.25 && items.length > initSize) {
    resizeDown();
    }

    nextFirst = (nextFirst + 1) % items.length;
    T removedItem = items[nextFirst];
    items[nextFirst] = null; /* since it is a reference */
    size--;
    return removedItem;
    }
  • removeLast

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    public T removeLast() {
    // 0 1 2 3
    // [ ][x][x][x]
    // [ ][ ][ ][ ]
    if (isEmpty()) {
    return null;
    }

    /** Resize down */
    if ((double) size / items.length < 0.25 && items.length > initSize) {
    resizeDown();
    }

    nextLast = ((nextLast - 1) + items.length) % items.length;
    T removedItem = items[nextLast];
    items[nextLast] = null;
    size--;
    return removedItem;
    }
get
1
2
3
4
5
6
7
8
9
10
11
12
13
public T get(int index) {
/* Test at the first place. It makes the condition later more succinct */
if (index < 0 || index >= size) {
return null;
}

int oldIndex = nextFirst + 1; /* will be MODed */
while (index > 0) {
oldIndex++;
index--;
}
return items[oldIndex % items.length];
}

Project 1B

Code: link
Guide: link

Done~

0%