CS 61B Part 2 Linked List

prev: [[61B_Part_1_Java]]
next: [[61B_Part_3_OOP]]

public class IntList {
   public int first;
   public IntList rest;
   public IntList(int f, IntList r) {
      first = f;
      rest = r;
   }
}

SLList

While functional, “naked” linked lists like the one above are hard to use.
Users of this class are probably going to need to know references very well, and be able to think recursively. Let’s make our users’ lives easier.

public class IntNode {
    public int item;
    public IntNode next;

    public IntNode(int i, IntNode n) {
        item = i;
        next = n;
    }
} //a simple copy of IntList.
public class SLList {
    private IntNode first; //avoid infinite loop like 1

    public SLList(int x) {
        first = new IntNode(x, null);
    }

    /** Adds an item to the front of the list. */
    public void addFirst(int x) {
        first = new IntNode(x, first);
    }
    /** Retrieves the front item from the list. */
    public int getFirst() {
    return first.item;
    }
}

1:

SLList L = new SLList(15);
L.addFirst(10);
L.first.next.next = L.first.next;

in large software engineering projects, the private keyword is the signal of the programs that needn’t to be understand by users.

also, we can nest the classes:

public class SLList {
    public class IntNode {
    public int item;
    public IntNode next;

    public IntNode(int i, IntNode n) {
        item = i;
        next = n;
        }
    } //a simple copy of IntList.
    private IntNode first; //avoid infinite loop like 1

    public SLList(int x) {
        first = new IntNode(x, null);
    }

    /** Adds an item to the front of the list. */
    public void addFirst(int x) {
        first = new IntNode(x, first);
    }
    /** Retrieves the front item from the list. */
    public int getFirst() {
    return first.item;
    }
    /** Adds an item to the end of the list. */
    public void addLast(int x) {
        IntNode p = first;

        /* Advance p to the end of the list. */
        while (p.next != null) {
            p = p.next;
        }
        p.next = new IntNode(x, null);
    } // using pointers
    private static int size(IntNode p) {
    if (p.next == null) {
        return 1;
    }

    return 1 + size(p.next);
    } //using recursions
    /* more easily: **/
    public int size() {
    return size(first);
    } // overload of size()
}

However, the recursion are really slow, as each time call size would recurse millions of times. So, we should create a varible called size directly.

public class SLList {
    ... /* IntNode declaration omitted. */
    private IntNode first;
    private int size;

    public SLList(int x) {
        first = new IntNode(x, null);
        size = 1;
    }

    public void addFirst(int x) {
        first = new IntNode(x, first);
        size += 1;
    }

    public int size() {
        return size;
    }
    ...
}

sentinal node

to address the problem of empty list

create the node for the first of the linked list

sentinal.next is the first element of the SLList

public class SLList {
    ... /* IntNode declaration omitted. */
    private IntNode sentinal;
    private int size;

    public SLList() {
        sentinal = new IntNode(63, null); //63 is randomly chosen
        size = 1;
    }

    public void addFirst(int x) {
        sentinal.next = new IntNode(x, sentinal.next);
        size += 1;
    }

    public int size() {
        return size;
    }
    ...
}

Lect6 Part 1: DLList

AddLast

the formal addLast method is a little bit slow:

public void addLast(int x) {
    size += 1;
    IntNode p = sentinel;
    while (p.next != null) {
        p = p.next;
    }

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

as it walks through the whole list to find the best one.

1. add the last varible: when deleting, the second last should be iterated to.

2. add the double-link!

so, a double-linked list(DLList) is in urgent need.(add, get, remove method also get faster!)

Also, it is recommended that the last elements’ next return to the first, and the first elements’ last return to the last.

Therefore, add .last and .prev method to fasten the linked list!

we would build this in project 1A.

SList

how to contain string into the Linked lists?

we can put the parameter as a kind of varible!

public class DLList<BleepBlorp> { // BleepBlorp is a random name
    private IntNode sentinel;
    private int size;

    public class IntNode {
        public IntNode prev;
        public BleepBlorp item;
        public IntNode next;
        ...
    }
    ...
}

usage:

DLList<Integer> d1 = new DLList<>(5);
d1.insertFront(10);

Lecture 4 part 2: the arrays

final objective: build a AList(using arrays instead of the recursive calls to make the Linked List)

x=new int[]{1, 2, 3, 4, 5};
y=x; //y:{1, 2, 3, 4, 5}
x=new int[]{6, 7, 8, 9, 10};//y:{1, 2, 3, 4, 5} x:{6, 7, 8, 9, 10}(a new address!!)
y=new int[3]; //the {1, 2, 3, 4, 5} have been lost! (when arrays lost, the data inside also lost)
System.arraycopy(b, 0, x, 3, 2); //in Python: x[3:5]=b[0:2]
//source array, the start position at source, target array, start position in the target, numbers to copy

### 2D array

```java
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}};

class VS arrays

The differences are: the array can be computed and used at the same time; but class CANNOT!

(reflection API allow class to do so, but it is not recommended)

Lect7 the ALists, resizing

the get(int i) method (Native ALList)

get is really slow in the function! (compared with GetLast)

1. Naive Array Based List

using arrays to build linked list

Accessing the ith element of an array takes constant time on a modern computer.

public class AList {
    private int[] items;
    private int size;

    /** Creates an empty list. */
    public AList() {
        items = new int[100];
        size = 0;
    }

    /** Inserts X into the back of the list. */
    public void addLast(int x) {
        items[size] = x;
        size = size + 1;
    }

    /** Returns the item from the back of the list. */
    public int getLast() {
        return items[size - 1];
    }
    /** Gets the ith item in the list (0 is the front). */
    public int get(int i) {
        return items[i];
    }

    /** Returns the number of items in the list. */
    public int size() {
        return size;
    }

    /** Deletes item from back of the list and
      * returns deleted item. */
    public int removeLast() {
        int x = getLast();
        size = size - 1;
        return x;
    }
} 

2. removeLast

In removeLast, we should see change in our memory box!

E2: Try to write removeLast. Before starting, decide which of size, items, and items[i] needs to change so that our invariants are preserved after the operation, i.e. so that future calls to our methods provide the user of the list class with the behavior they expect.

// lack code here(class required to be viewed)

3. Naive Resizing Arrays

How to add the number of the arrays? In Java, the only way is to add the arrays that is large enough.

int[] a = new int[size + 1];
System.arraycopy(items, 0, a, 0, size);
a[size] = 11;
items = a;
size = size + 1;

the process is called resizing, meaning that the array didn’t change its size, but a new array with more members come.

E4: Try to implement the addLast(int i) method to work with resizing arrays.

Reflection

However, when comparing to our previous SLList, the ALList seemed to be very slow.

Creating all those memory boxes and recopying their contents takes time!

In SLList, each insert take the same time. In ALList, however, each insert take the time that linear increasing!

We can fix our performance problems by growing the size of our array by a multiplicative amount, rather than an additive amount.

for example:

the additive one:

public void insertBack(int x) {
    if (size == items.length) {
           resize(size + RFACTOR);
    }
    items[size] = x;
    size += 1;
}

the multiplicative one:

public void insertBack(int x) {
    if (size == items.length) {
           resize(size * RFACTOR);
    }
    items[size] = x;
    size += 1;
}

which make our program faster. Why?

because that the program is faster as the time of revising the size of the array is much smaller.

to build a AList that the same speed as the DLList, we need to adapt the data structure below:

lists in real java code

java.util.List<Integer> L = new java.util.ArrayList<>();
L.add(5);
L.add(10);
L.add(15);
System.out.println(L);

another example: (more realistic)

import java.util.List;
import java.util.ArrayList;
 
public class SimpleBuiltInListExample {
  public static void main(String[] args) {
    List<Integer> L = new ArrayList<>();
    L.add(5);  L.add(10);   L.add(15);
    System.out.println(L);

    List<Integer> L2 = Utils.readIntsFromFile(“somedata.csv”);
  }
}

you can look up these words in Java official website!