Cs61b Experiment Record (2)
project1A
LinkedListDeque
circular sentinel
Incorrect writing:
public LinkedListDeque(a){
sentinel=new Node(sentinel,null,sentinel.next);
size=0;
}
Copy the codeAt the time of instantiation of sentinel, sentinel itself was still null. Using sentinel and sent.next to instantiate sentinel would not work.
We should:
public LinkedListDeque(a){
sentinel=new Node(null.null.null);
sentinel.next=sentinel;
sentinel.prev=sentinel;
size=0;
}
Copy the codeThe next and prev fields are assigned after the sentinel is instantiated.
Complete implementation:
public class LinkedListDeque<T> {
private class Node{
Node prev;
T item;
Node next;
Node(Node prev,T item,Node next){
this.item=item;
this.prev=prev;
this.next=next; }}private int size;
private Node sentinel;
public LinkedListDeque(a){
sentinel=new Node(null.null.null);
sentinel.next=sentinel;
sentinel.prev=sentinel;
size=0;
}
public void addFirst(T item) {
sentinel.next=new Node(sentinel,item,sentinel.next);
sentinel.next.next.prev=sentinel.next;
size++;
}
public void addLast(T item) {
sentinel.prev=new Node(sentinel.prev,item,sentinel);
sentinel.prev.prev.next=sentinel.prev;
size++;
}
public boolean isEmpty(a) {
return size==0;
}
public int size(a) {
return size;
}
public void printDeque(a) {
Node pos=sentinel.next;
for (int i=0; i<size-1; i++){ System.out.print(pos.item+"");
pos=pos.next;
}
System.out.print(pos.item);
}
public T removeFirst(a) {
if (sentinel.next==sentinel)
return null;
Node temp=sentinel.next;
sentinel.next.next.prev=sentinel;
sentinel.next=sentinel.next.next;
size--;
return temp.item;
}
public T removeLast(a) {
if (sentinel.prev==sentinel)
return null;
Node temp=sentinel.prev;
sentinel.prev.prev.next=sentinel;
sentinel.prev=sentinel.prev.prev;
size--;
return temp.item;
}
public T get(int index) {
Node pos=sentinel.next;
if (index>=size)
return null;
for (int i=0; i<index; i++){ pos=pos.next; }return pos.item;
}
public T getRecursive(int index){
if (index>=size)
return null;
return getRecursive(0,index,sentinel.next);
}
private T getRecursive(int pos,int index,Node x){
if (pos==index)
return x.item;
return getRecursive(pos+1,index,x.next); }}Copy the codeArrayDeque
Step by step, the complexity of the data structure implementation should be reduced and its implementation layered.
Resize should not be considered first, and the most basic data structure should be implemented first
public class ArrayDeque<T> {
private int nextFirst;
private int nextLast;
private T[]items;
private int size;
public ArrayDeque(a){
items=(T[])new Object[8];
nextFirst=0;
nextLast=1;
size=0;
}
public void addFirst(T item) {
items[nextFirst]=item;
size++;
nextFirst=nextFirst==0? items.length-1:nextFirst-1;
}
public void addLast(T item) {
items[nextLast]=item;
size++;
nextLast=nextLast==items.length-1?0:nextLast+1;
}
public boolean isEmpty(a) {
return size==0;
}
public int size(a) {
return size;
}
public void printDeque(a) {
for (int i=nextFirst+1; i! =nextLast; i=(i+1)%items.length)
System.out.print(items[i]);
}
public T removeFirst(a) {
if (nextFirst==0)return null;
nextFirst++;
T temp=items[nextFirst];
items[nextFirst]=null;
size--;
return temp;
}
public T removeLast(a) {
if (nextLast==1)return null;
nextLast--;
T temp=items[nextLast];
items[nextLast]=null;
size--;
return temp;
}
public T get(int index) {
if (index>=size)
return null;
return items[(nextFirst+1+index)%items.length]; }}Copy the codeIn fact, we can find that since nextFirst is 0 and nextLast is 1, special judgment should be made when the inflection point of the array is encountered, which causes trouble for the implementation of our method. We can further think, why not set nextFirst to the last element of the array and nextLast to 0? We were surprised to find that there were fewer special judgments.
public class ArrayDeque<T> {
private int nextFirst;
private int nextLast;
private T[]items;
private int size;
public ArrayDeque(a){
items=(T[])new Object[8];
nextFirst=items.length-1;
nextLast=0;
size=0;
}
public void addFirst(T item) {
items[nextFirst]=item;
size++;
nextFirst--;
}
public void addLast(T item) {
items[nextLast]=item;
size++;
nextLast++;
}
public boolean isEmpty(a) {
return size==0;
}
public int size(a) {
return size;
}
public void printDeque(a) {
for (int i=nextFirst+1; i! =nextLast; i=(i+1)%items.length)
System.out.print(items[i]);
}
public T removeFirst(a) {
if (nextFirst==items.length-1)return null;
nextFirst++;
T temp=items[nextFirst];
items[nextFirst]=null;
size--;
return temp;
}
public T removeLast(a) {
if (nextLast==0)return null;
nextLast--;
T temp=items[nextLast];
items[nextLast]=null;
size--;
return temp;
}
public T get(int index) {
if (index>=size)
return null;
return items[(nextFirst+1+index)%items.length]; }}Copy the codeSince nextLast and nextFirst are unlikely to cross the inflection point, we no longer need special judgments in the ADD approach
Resize is also easy to implement by copying the beginning and end of the original array into the new array.
Complete implementation:
public class ArrayDeque<T> {
private int nextFirst;
private int nextLast;
private T[]items;
private int size;
public ArrayDeque(a){
items=(T[])new Object[8];
nextFirst=items.length-1;
nextLast=0;
size=0;
}
private void resize(int capacity){
T[]a=(T[])new Object[capacity];
System.arraycopy(items,0,a,0,nextLast);
int length=items.length-1-nextFirst;
System.arraycopy(items,nextFirst+1,a,capacity-length,length);
nextFirst=capacity-length-1;
items=a;
}
public void addFirst(T item) {
if (nextFirst-1==nextLast)
resize(items.length*2);
items[nextFirst]=item;
size++;
nextFirst--;
}
public void addLast(T item) {
if (nextFirst-1==nextLast)
resize(items.length*2);
items[nextLast]=item;
size++;
nextLast++;
}
public boolean isEmpty(a) {
return size==0;
}
public int size(a) {
return size;
}
public void printDeque(a) {
for (int i=nextFirst+1; i! =nextLast-1; i=(i+1)%items.length)
System.out.print(items[i]+"");
System.out.print(items[nextLast-1]);
}
public T removeFirst(a) {
if (nextFirst==items.length-1)return null;
nextFirst++;
T temp=items[nextFirst];
items[nextFirst]=null;
size--;
if (items.length>=16&&size<items.length/4)
resize(items.length/2);
return temp;
}
public T removeLast(a) {
if (nextLast==0)return null;
nextLast--;
T temp=items[nextLast];
items[nextLast]=null;
size--;
if (items.length>=16&&size<items.length/4)
resize(items.length/2);
return temp;
}
public T get(int index) {
if (index>=size)
return null;
return items[(nextFirst+1+index)%items.length]; }}Copy the codeJust by having two Pointers to the beginning and the end of an array, which is a completely different data structure, you can use arrays to implement a two-way queue, and you can go from linear time to constant time. We went from linear time to constant time.
Updated March 22, 2021:
All of the above ArrayDeque is wrong!
The previous approach ended up getting a 40/50 score on autoGrader and half the score on ArrayDeque. I thought there were only some minor special cases that I didn’t take into account, so I didn’t check and correct them.
I went back and looked at the code and found that it was too naive, and most of ArrayDeque was wrong! The corrections are as follows:
I naively assumed that if I placed nextLast and nextFirst at the beginning and end of the array, respectively, they would never cross the inflection point. Obviously wrong! Because even if add does not cross the inflection point, nextLast and nextFirst can still cross the inflection point when remove is executed!
So, since nextFirst and nextLast are likely to pass the inflection point anyway, it doesn’t matter where they point.
Complete code:
public class ArrayDeque<T> {
private int nextFirst;
private int nextLast;
private int capacity;
private T[]items;
private int size;
public ArrayDeque(a){
items=(T[])new Object[8];
this.capacity=items.length;
nextFirst=capacity-1;
nextLast=0;
size=0;
}
private void resize(int capacity){
T[]a=(T[])new Object[capacity];
// Because the positions of nextFirst and nextLast are uncertain, we can only copy them into the new array one by one
// Start copying from the first point to the right of nextFirst
// Copy ends at the first point to the left of nextLast
for (int i=1; i<=size; i++) a[i]=items[(++nextFirst)%this.capacity];
this.capacity=capacity;
// It doesn't matter where these two Pointers point to
nextFirst=0;
nextLast=size+1;
items=a;
}
public void addFirst(T item) {
// Resize when size equals capacity instead of looking at the relative positions of two Pointers
if (size==capacity)
resize(capacity*2);
items[nextFirst]=item;
size++;
//nextFirst may be out of bounds
nextFirst=nextFirst==0? capacity-1:nextFirst-1;
}
public void addLast(T item) {
if (size==capacity)
resize(capacity*2);
items[nextLast]=item;
size++;
//nextLast may be out of bounds
nextLast=(nextLast+1)%capacity;
}
public boolean isEmpty(a) {
return size==0;
}
public int size(a) {
return size;
}
public void printDeque(a) {
//nextFirst may point to the last position
for (int i=(nextFirst+1)%capacity; i! =nextLast-1; i=(i+1)%capacity)
System.out.print(items[i]+"");
System.out.print(items[nextLast-1]);
}
public T removeFirst(a) {
// Remove cannot be performed when the contents of the array are empty, not depending on the location of nextFirst.
if (size==0)return null;
nextFirst=(nextFirst+1)%capacity;
T temp=items[nextFirst];
items[nextFirst]=null;
size--;
if (capacity>=16&&size<capacity/4)
resize(capacity/2);
return temp;
}
public T removeLast(a) {
if (size==0)return null;
nextLast=nextLast==0? capacity-1:nextLast-1;
T temp=items[nextLast];
items[nextLast]=null;
size--;
if (capacity>=16&&size<capacity/4)
resize(capacity/2);
return temp;
}
public T get(int index) {
if (index>=size)
return null;
return items[(nextFirst+1+index)%capacity]; }}Copy the codeAutograder score:
project1B
Nothing special
See my GitHub for the solution
Github.com/BoL0150/Ber…