CS61B(6): DLLists, Arrays

Posted on | In , |

This is the lecture note of CS61B - Lecture 6.

Two lectures ago, we built a naked recursive linked data structure —— IntList. It works, but is hard to use.

So, in the previous lecture, we add an extra layer on the naked data structure and built a better linked list —— SLLit. However, SLList has some limitations, one of them is inserting at the back of an SLList is much slower than adding at the front. This is because under the hood, to add an item at the end of the SLList, it needs to iterate through all of the items.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public void addFirst(int x) {
    size += 1;
    sentinel.next = new IntNode(x, sentinel.next);
}

public void addLast(int x) {
    size += 1;

    IntNode p = sentinel;
    while (p.next != null) {
        p = p.next;
    }

    p.next = new IntNode(x, null);
}

How could we modify our list data structure so that addLast is also fast?

DLList: Doubly Linked List

However, adding .last and .prev introduces a special case:

To avoid these, either:

  • Add an additional sentBack sentinel at the end of the list.
  • Make your linked list circular (highly recommened for project 1), with a single sentinel in the middle.

You will implement your version of DLList in Project 1.

Generic Lists

Until now, our SLList and DLList only support Integers. To make our list more practical, one important task it to make it generic.

Java allows us to defer type selection until declaration.

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/** Generic SLList */
  public class SLList<Type> {	
	private class StuffNode {
		private Type item;
		private StuffNode next;

		public StuffNode(Type i, StuffNode n) {
			item = i;
			next = n;
		}
	} 

	private StuffNode first;
	private int size;

	public SLList(Type x) {
		first = new StuffNode(x, null);
		size = 1;
	}

 	/** Adds x to the front of the list. */
 	public void addFirst(Type x) {
 		first = new StuffNode(x, first);
 		size += 1;
 	}

 	/** Returns the first item in the list. */
 	public Type getFirst() {
 		return first.item; 		
 	}

 	/** Adds an item to the end of the list. */
 	public void addLast(Type x) {
 		size += 1;

 		StuffNode p = first;

 		/* Move p until it reaches the end of the list. */
 		while (p.next != null) {
 			p = p.next;
 		}

 		p.next = new StuffNode(x, null);
 	}

 	public int size() {
 		return size;
 	}
}
1
2
3
4
5
6
7
8
9
public class SLListLauncher {
    public static void main(String[] args) {
        SLList<String> L = new SLList<>("A");
        L.addFirst("B");

        SLList<Integer> L2 = new SLList<>(1);
        L.addFirst(2);
    }
}

Arrays

Try to understand the following code. I think it is easy for you to except the last line.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int[] z = null;

int[] x, y;
 
x = new int[]{1, 2, 3, 4, 5};
y = x;
x = new int[]{-1, 2, 5, 4, 99};
y = new int[3];
z = new int[0];
int xL = x.length;
 
String[] s = new String[6];
s[4] = "ketchup";
s[x[3] - x[1]] = "muffins";
 
int[] b = {9, 10, 11};  // can omit the new if you are also declaring a variable
System.arraycopy(b, 0, x, 3, 2);

To understand array deeper, let’s take a look at 2-dimensional arrays in Java. Try to understand the following code.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int[][] pascalsTriangle;
pascalsTriangle = new int[4][];
int[] rowZero = pascalsTriangle[0];
 
pascalsTriangle[0] = new int[]{1};
pascalsTriangle[1] = new int[]{1, 1};
pascalsTriangle[2] = new int[]{1, 2, 1};
pascalsTriangle[3] = new int[]{1, 3, 3, 1};
int[] rowTwo = pascalsTriangle[2];
rowTwo[1] = -5;
 
int[][] matrix;
matrix = new int[4][];
matrix = new int[4][4];
 
int[][] pascalAgain = new int[][]{{1}, {1, 1},
                              	{1, 2, 1}, {1, 3, 3, 1}};

This is the result:

Exercise: 2D Arrays

What will be the value of x[0][0] and w[0][0] when the code shown completes?

1
2
3
4
5
6
7
8
9
int[][] x = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
 
int[][] z = new int[3][];
z[0] = x[0];
z[0][0] = -z[0][0];
 
int[][] w = new int[3][3];
System.arraycopy(x[0], 0, w[0], 0, 3);
w[0][0] = -w[0][0];

🐹 Solution:

1
2
x[0][0]: -1
w[0][0]: 1

Until now, we've seen how to harness a recursive class definition to build an expandable list, ie. the IntList, the SLList and the DLList. In the next two lectures, we will transfer from linked data structure to arrays, and see how to harness arrays to build such a list, namely AList.

See you next time. 🦄