CS 61B | Lecture 1 ~ 2 | IntList, SLList, DLLists, Array, AList


LectureList.first

Phase 1: Java (w1-4)
Phase 2: Advanced Programming (w5-7)
Phase 3: Data Structures and Algorithms (w8-14)

Focus: there is a problem; there is a way (it is a problem-solution tutorial).

IntList (naked recursive)

Code: IntListEx.java

IntList is a naked recursive data structure.

When you create a public member (i.e. method or variable), be careful, because you’re effectively committing to supporting that member’s behavior exactly as it is now, forever.

Lab 2 (IntList) Code:

sqaureList & catenate & decatenate (iterative + recursive)

IntList.java

存储物理结构/形式

  • List 列表/线性表(Sequence)
    • Array 数组/顺序存储 (ArrayList or AList)
    • Linked List 链表/链式存储 (LList, SLList, DLList)

逻辑结构(操作):(可通过上者实现)

  • Queue 队列
  • Stack 栈

SLList

Add Bureaucracy to IntList

Basic Operations

Code: SLList.java

Nested class and nested class

Code: Government.java (code is below)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Government {
private int treasury = 5;

/* Thief and Explorer both know Government but not the instance object of Government */

public static class Thief {
public void doStuff() {
Government tmp = null; // ok
tmp.treasury = 0; // ok
treasury = 0; // error - cannot access instance member
}
}

public static class Explorer { // ok
public void doStuff(Government a, Government b) {
Government favorite = Government.greaterTreasury(a, b);
System.out.println("The best government has treasury " + favorite.treasury);
}
}
}

IntNode: nested class & static class.

static nested class: This saves a bit of memory, because each IntNode no longer needs to keep track of how to access its enclosing SLList (the specific instance, class & other instances are accessible still).

Sentinel Nodes

Code: SLList_Sentinel.java

1
2
3
4
5
6
7
8
9
10
11
12
13
/* Original - Without Sentinel */
public void addLast(int x) {
size += 1;
if (first == null) {
first = new IntNode(x, null);
return;
}
IntNode p = first;
while (p.next != null) {
p = p.next;
}
p.next = new IntNode(x, null);
}

With an SLList, we can now represent an empty list. We simply set first to null and size to 0. However, we have introduced some bugs; namely, because first is now null, any method that tries to access a property of first (like first.item) will return a NullPointerException.

AddLast’s fundamental problem: The empty list has a null first. Can’t access first.next!

  • Renamed first to be sentinel
  • sentinel is never null, it next always points to sentinel node if the list is empty
  • Its item needs to be some integer (whatever)

The second meaning refers to a technique to deal with the following issue: If you represent a linked list as just the nodes with data, then when the list is empty, all references (and/or pointers, depending on the language) to the list have to be null, because there is nothing to point at. This creates lots of bookkeeping problems for code that uses the list.
A list head solves this problem. It is a list node that contains no actual data. A reference or pointer to the list is always a pointer to the head node. The first element of the list is always head.next. Usually the existence of the head is hidden in the class that implements a “linked list with head.” (link)

哨兵顾名思义有巡逻、检查的功能,在我们程序中通过增加哨兵结点往往能够简化边界条件,从而防止对特殊条件的判断,使代码更为简便优雅,在链表中应用最为典型。

单链表中的哨兵结点:首先讨论哨兵结点在单链表中的运用,如果不加哨兵结点在进行头尾删除和插入时需要进行特殊判断。

关于链表中哨兵结点问题的深入剖析

  • addFirst (no effect)
  • getFirst (no effect)

    1
    2
    3
    4
    public int getFirst() {
    if (sentinel.next == null) return -1;
    return sentinel.next.item; /* sentinel.next COULD BE null */
    }
  • deleteFirst (no effect)

    1
    2
    3
    4
    public deleteFirst() {
    if (sentinel.next == null) return -1;
    // ...
    }
  • addLast (has effect)

    1
    2
    3
    4
    IntNode p = sentinel; /* if p.next is null, while-loop won't be executed */
    while (p.next != null) { p = p.next; } /* p is not null */
    p.next = new IntNode(x, null);
    size += 1;

Invariant

An invariant is a fact about a data structure that is guaranteed to be true (assuming there are no bugs in your code).

A SLList with a sentinel node has at least the following invariants / guarantees:

  • The sentinel reference always points to a sentinel node.
    • which means we can use this node (access its item and next)
  • The first item (if it exists), is always at sentinel.next.item.
  • The size variable is always the total number of items that have been added.

Invariants make it easier to reason about code, and also give you specific goals to strive for in making sure your code works.

Slow addLast?

Cache the last pointer!

1
2
3
4
5
6
private IntNode last;
public void addLast(int x) {
last.next = new IntNode(x, null);
last = last.next;
size += 1;
}

Compare addLast, getLast, and removeLast, which one is the slowest?

Answer: removeLast. Because last has no access to the previous node’s next.

DLList

What if we add a last node (just like the first node)? Not good enough.

Why last pointer is not enough?

We only know the last node, but we need information to do:

  • set last 2nd node’s next to null
  • set last point

Solution: Add .last and .prev

DLList (doubly linked list)

Sentinel Upgrade

Back pointers allow a list to support adding, getting, and removing the front and back of a list in constant time.

There is a subtle issue with this design where the last pointer sometimes points at the sentinel node (empty list), and sometimes at a real node. (special case again)

Note: write the code first, then consider the special case.

Not Circular!

  • addFirst

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    /* L.addFirst(x) */
    public void addFirst(int x) {
    IntNode newNode = new IntNode(x, sentinel.next);
    /* Set the prev of new node */
    newNode.prev = sentinel;
    /* Set the prev of the previous first node - newNode.next may be null */
    if (newNode.next != null) {
    newNode.next.prev = newNode;
    }
    /* Update Last */
    last = sentinel.prev;
    if (size == 0) {
    last = newNode;
    } /* Otherwise, last stays the same */
    size += 1;
    }
  • getFirst

    1
    2
    3
    4
    5
    6
    7
    8
    9
    /* L.getFirst() */
    public int getFirst() {
    /* if size == 0, just return -1 */
    if (size == 0) { /* or sentinel == last */
    return -1;
    }
    /* if size >= 1 */
    return sentinel.next.item;
    }
  • removeFirst

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    /* L.removeFirst() */
    public int removeFirst {
    /* if size == 0, just return -1 */
    if (size == 0) {
    return -1;
    }
    IntNode removedNode = sentinel.next;
    sentinel.next = removedNode.next; /* it's maybe null */
    /* if size == 1, last is still pointing to removedNode */
    if (size == 1) {
    last = sentinel;
    } /* Otherwise if size > 2, last stays the same */
    size -= 1;
    return removedNode.item;
    }
  • addLast

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    /* L.addLast(x) */
    public void addLast(int x) {
    IntNode newLast = new IntNode(x, null);
    if (size == 0) {
    sentinel.next = newLast;
    } else {
    last.prev.next = newLast; /* not okay if size == 0 */
    }
    newLast.prev = last;
    last = newLast;
    size += 1;
    }
  • getLast

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    /* L.getLast() */
    public int getLast(int x) {
    if (size == 0) {
    return -1;
    /* You may think what if we set sentinel.item to -1, so we don't need the "if" anymore (just return last.item) */
    /* However, it's just okay with getLast. What about other methods? It's not consistent! */
    /* last may point to sentinel and a real node both, while */
    /* sentinel.next always points to the first real node or null */
    }
    return last.item;
    }
  • removeLast

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    /* L.removeLast() */
    public int removeLast() {
    if (size == 0) { /* last.prev == null */
    return -1;
    }
    /* okay with size >= 1 */
    int retItem = last.item; /* the2ndLastNode may be sentinel */
    IntNode the2ndLastNode = last.prev; /* the2ndLastNode */
    the2ndLastNode.next = null;
    last = the2ndLastNode;
    size -= 1;
    return retItem;
    }

Solution:

  • Add a 2nd sentinel node to the back of the list.

  • Use circular sentinel approach


    (Be careful of what the pointers are pointing at!)

Both the two-sentinel and circular sentinel approaches work and result in code that is free of ugly special cases, though I personally find the circular approach to be cleaner and more aesthetically beautiful. We will not discuss the details of these implementations, as you’ll have a chance to explore one or both in project 1.

Generic DLLists

1
2
3
4
5
6
7
8
9
10
public class DLList<BleepBlorp> {
private IntNode sentinel;
private int size;

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

In other .java files, which use your data structure, specify the specific desired type during declaration, and use the empty diamond operator during instantiation.

1
DLList<Integer> d1 = new DLList<>(5);

Arrays

Java array:

Arrays are a special kind of object which consists of a numbered sequence of memory boxes.

A fixed integer length (cannot change! 0 ~ length - 1)

Unlike classes, arrays do not have methods.

1
2
/* Can omit the new if you are also declaring a variable */
int[] w = {9, 10, 11, 12, 13}

1
System.arraycopy(b, 0, x, 3, 2); /* copy from b to x start from 0 to the position of x at 3rd with 2 elements (9, 10 in the graph) */

java.lang.ArrayIndexOutOfBoundsException: shows in runtime.

1
2
3
4
5
6
7
int[] x = {9, 10, 11, 12, 13};
int[] y = new int[2];
int i = 0;
while (i < x.length) {
y[i] = x[i];
i += 1;
}

2D Array

1
2
3
4
5
6
7
8
9
10
11
12
13
int[][] pascalsTriangle;
/* 1 array */
pascalsTriangle = new int[4][]; /* 4 null values */
int[] rowZero = pascalsTriangle[0];

pascalsTriangle[0] = new int[]{1};
pascalsTriangle[1] = new int[]{1, 1};
pascalsTriangle[2] = new int[]{1, 1, 1};
pascalsTriangle[3] = new int[]{1, 1, 1, 1};
int[][] pascalAgain = new int[][]{{1}, {1, 1}, {1, 1, 1}, {1, 1, 1, 1}}; /* 1 array */

/* 5 arrays */
int[][] matrix = new int[4][4]; /* 4 references to 4 zero arrays */

Ex (D2 + Study Guide)

Ex 1 (Osmosis - addAdjacent)

Problem: Osmosis

Iterative:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/** addAdjacent(L) */
public void addAdjacent(IntList p) {
/* if p == null, p.rest will no longer execute */
if (p.rest == null) {
/* size <= 1 */
return;
}
/**
* p.rest != null
* p ends at the last node finally
* loop through 1st ~ last 2nd node
*/
while (p.rest != null) { /* p ends at the last node */
if (p.first == p.rest.first) {
/* merge */
p.first *= 2;
p.rest = p.rest.rest; /* it's okay if it is null */
/* Notice: no ++ here */
} else {
p = p.rest;
}
}
}

Recursive (interesting!):

1
2
3
4
5
6
7
8
9
10
11
12
13
public void addAdjacent(IntList p) {
if (p == null) return;
adj(p.rest, p);
}

// helper function - pass previous node recursively
private void adj(IntList current, IntList prev) {
if (current == null) return prev.first;
if (prev.first == current.first) { /* same as prev */
prev.first *= 2;
prev.rest = current.rest; /* maybe null */
}
}

Ex 2 (Square Insertion)

Modify the IntList class so that every time you add a value you “square” the IntList. For example, upon the insertion of 5, the below IntList would transform from:

1 => 2 to 1 => 1 => 2 => 4 => 5

and if 7 was added to the latter IntList, it would become

1 => 1 => 1 => 1 => 2 => 4 => 4 => 16 => 5 => 25 => 7

Additionally, you are provided the constraint that you can only access the size() function one time during the entire process of adding a node.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/** Square Insertion */
public void addLastAndSquare(int x) {
IntList p = this;
while (p.rest != null) { /* p won't be null */
IntList squareNode = new IntList(p.first * p.first, p.rest);
p.rest = squareNode;
p = p.rest.rest;
} /* p stops at the last node */
/* add node of x */
IntList newNode = new IntList(x, null);
/* square the last node */
IntList squareNode = new IntList(p.first * p.first, newNode); /* p.rest is null */
p.rest = squareNode;
/* if use while (p != null), need an extra pointer to the previous node (to remember) */
size += 1;
}

But I don’t access the size() function.

1
2
3
4
5
6
7
8
9
10
11
12
/** Recursively */
public void addLastAndSquare(int x) {
helper(this, x);
}
private IntList helper(IntList L, int x) {
if (L == null) {
return new IntList(x, null);
}
L.rest = new IntList(x * x, L.rest);
L.rest.rest = helper(L.rest.rest, x);
return L
}

Ex 3 (Arrrrghrays)

Problem: link
Code: Arrrrghrays.java

第一列不会发生重复,因为加入的时候已经杜绝这种情况了。

Note: for every p[i], j will start over!

The 1st half of the problem took me half a day to think about… ‘cause I thought I was required to implement sorting in this function :(

The 2nd half of the problem took me another half a day to think about… ‘cause I was not sure about:

  • groupByLat, sortByLat, sortHalfLong should be in what kind of orders?
    • Since the parameter of sortByLat is Piece[][], it should follow groupByLat.
  • The most confusing one is sortHalfLong, because there could be 2 situations (the length is even or odd). I spent a lot of time on the implementation of the function, but I kind of misinterpreted its purpose.
  • In the solution, each row has the same latitude, so we need to halfsoft it by longitude… okay… I see… It provides halfsoft on purpose… so we have a chance to practice System.arraycopy
  • System.arraycopy(src, srcPos, dest, destPos, length)
    • upper, lower, mid (learn this pattern)
      • length = 3 (odd)
        • upper = (3.0 / 2 = 1.5) = 2
        • lower = (3.0 / 2 = 1.5) = 1
        • (0 ~ lower is the 1st half, upper could be the length of it)
      • length = 4 (even)
        • upper = (4.0 / 2 = 2.0) = 2
        • lower = (4.0 / 2 = 2.0) = 2
        • For even numbers, upper and lower are the same
    • System.arraycopy(halfsort, 0, tmp, lower, upper);
    • System.arraycopy(halfsort, upper, tmp, 0, lower);
  • You know what. I am confused again, so I’d better test it out.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    public static void main(String[] args) {
    int[] a = {1, 2, 3};
    int[] b = {0, 0, 0};
    int upper = (int) Math.ceil((double) a.length / 2);
    int lower = (int) Math.floor((double) b.length / 2);
    System.arraycopy(a, 0, b, lower, upper);
    System.arraycopy(a, upper, b, 0, lower);

    System.out.println("a: " + Arrays.toString(a));
    System.out.println("b: " + Arrays.toString(b));
    }

    The output is:

    1
    2
    3
    4
    [1, 2, 3] // the provided "even number" version: [0, 2, 4, 9]
    [3, 1, 2] // the provided "even number" version: [4, 9, 0, 2]
    // I thought it should be [3, 2, 1] dead~
    // So I am totally wrong about it.

By now, I am clear about the intention of the problem.

Ex 4 (HighOrderFunctionsAndArrays)

Problem: link
Code: HigherOrderFunctionsAndArrays.java

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
public int compare(String s1, String s2) {
if ((s1 == null) && (s2 == null)) return 0;
if (s1 == null) return -1;
if (s2 == null) return 1;
return s1.length() - s2.length();
}

public static String[][] step(String[][] arr) {
/* Recall: All String references in stepped are null by
default, so the edges are correct on initialization */
String[][] stepped = new String[arr.length][arr[0].length];
for (int i = 1; i < arr.length - 1; i += 1) {
for (int j = 1; j < arr[0].length - 1; j += 1) {
String[] temp = new String[9];
// LengthComparator lc = new LengthComparator();
int count = 0;
for (int k = -1; k <= 1; k += 1) { /* horizontally */
for (int m = -1; m <= 1; m += 1) { /* vertically */
// int index = (k + 1) * 3 + (m + 1);
// temp[index] = arr[i + k][j + m];
temp[count] = arr[i + k][j + m];
count += 1; /** nice! (mapping) */
}
}
// stepped[i][j] = max(temp, lc);
stepped[i][j] = max(temp, new LengthComparator());
}
}
return stepped;
}

Ex 5 (Squaring a List)

Mutative / Non-mutative + Recursive / Iterative

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
/** Non-mutative (new) - Recursive */
public static IntList square_re(IntList L) {
if (L == null) {
return null;
}
return new IntList(L.first * L.first, square_re(L.rest));
}

/** Non-mutative - Iterative */
public static IntList square(IntList L) {
if (L == null) {
return null;
}
IntList p = new IntList(L.first * L.first, null);
IntList ret = p;
L = L.rest;
while (L != null) {
p.rest = new IntList(L.first * L.first, null);
p = p.rest;
L = L.rest;
}
return ret;
}

/** Mutative - Recursive */
public static IntList squareMutative_re(IntList L) {
if (L == null) { return null; }
L.first = L.first * L.first;
L.rest = squareMutative_re(L.rest);
return L;
}

/** Mutative - Iterative */
public static IntList squareMutative(IntList L) {
IntList p = L;
while (p != null) {
p.first = p.first * p.first;
p = p.rest;
}
return L;
}

ALists

Linked List Performance Puzzle

It turns out that no matter how clever you are, the get method will usually be slower than getBack if we’re using the doubly linked list structure.

This is because, since we only have references to the first and last items of the list, we’ll always need to walk through the list from the front or back to get to the item that we’re trying to retrieve.

In other words, our worst case execution time for get is linear in the size of the entire list. This in contrast to the runtime for getBack, which is constant, no matter the size of the list.

The Way in which you should think

  • Work out a small example
  • Abstract the pattern
    • Come up with invariants
      • addLast: The next item we want to add, will go into position size
      • getLast: The item we want to return is in position size - 1
      • size: The number of items in the list should be size

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. So, …

  • size should be decreased
  • items should not be changed
  • items[i] should not be changed (no need to “destroy” it)
1
2
3
4
5
public int removeLast() {
int x = getLast();
size -= 1;
return x;
}

Array “Resizing”

1
2
3
4
5
6
7
8
9
public void addLast(int x) {
if (size >= items.length) {
int[] a = new int[size + 100];
System.arraycopy(items, 0, a, 0, size); /* or items.length */
items = a;
}
items[size] = x;
size += 1;
}

Better encapsulation:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public void addLast(int x) {
if (size >= items.length) {
resize(size + 1);
}
items[size] = x;
size += 1;
}

/** Resize the underlying array to the target capacity. */
private void resize(int capacity) {
int[] a = new int[capacity];
System.arraycopy(items, 0, a, 0, size); /* or items.length */
items = a;
}
  1. (Assume increment is 1) Suppose we have an array of size 100. If we call insertBack two times, how many total boxes will we need to create and fill throughout this entire process? How many total boxes will we have at any one time, assuming that garbage collection happens as soon as the last reference to an array is lost?

    1st time: 101, 2nd time: 102, total: 203 (the first array above will be thrown away)

  2. Starting from an array of size 100, approximately how many memory boxes get created and filled if we call addLast 1,000 times?

    101 + 102 + 103 + … + 1000 ~ 500,000

Geometric Resizing

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

Unusably bad:

1
2
3
4
5
6
7
public void insertBack(int x) {
if (size == items.length) {
resize(size + RFACTOR);
}
items[size] = x;
size += 1;
}

Great performance:

1
2
3
4
5
6
7
public void insertBack(int x) {
if (size == items.length) {
resize(size * RFACTOR); // RFACTOR = 2 will bring about great improvement
}
items[size] = x;
size += 1;
}

Another Performance Problem #2

Suppose we have a very rare situation occur which causes us to:

  • Insert 1,000,000,000 items
  • Then remove 990,000,000 items

Our data structure will handle this spike of events as well as it could, but afterwards there is a problem.

An AList should not only be efficient in time, but also efficient in space.

  • Define the usage ratio as R = size / items.length
  • Typical solution: Half array size when R < 0.25

Later we will consider tradeoffs between time and space efficiency for a variety of algorithms and data structures.

Generic ALists

In Java, generic array is not supported. We need to do the casting

1
2
3
4
public AList() {
items = (T[]) new Object[100];
size = 0;
}

Nulling Out Deleted Items

Unlike integer based ALists, we actually want to null out deleted items. Since Java only destroys unwanted objects when the last reference has been lost. Save memory. Don’t loiter.

1
2
3
4
5
6
7
8
9
public T removeLast() {
if (size > 0) {
size -= 1;
T removedItem = items[size];
items[size] = null;
return removedItem;
}
return null;
}

Obscurantism

We talk of layers of abstraction often in computer science. We also rely on obscurantism. The user of a class does not and should not know how it works.

In Java, we may use private to hide details.

Discussion 3

About Linked Lists, Arrays.

SLList

The SLList allows us to hide away the inner workings of the linked list and also allows us to store meta-information about the list as a whole such as the size.

Sentinel Nodes

How do we represent an empty linked list? Set first to null?

Goal of sentinel: Make code as simple as generic as possible so we don’t have to have any special cases. (avoid pesky null checks)

DLLists

One thing that a list should support is remove(int i) which removes the node whose item is i. With SLList with sentinel, what would we have to do to remove a link?

  • Save a reference to this node
  • Remove its “next” pointer (i)
  • Jump to the node before
  • Reassign next to the node after

We had to traverse the list TWICE in order to do the job. So we add a previous link as well. (don’t quite understand… what if I traverse a node ahead)

ALists

Even with the super sophisticated doubly linked list, it’ll take a long time to traverse through the list. So we go back to arrays.

But the bad thing about arrays is that you can’t efficiently add or remove items.

Let’s write a list class that takes advantage of both an array's constant access time and a linked lists adding and removing feature.

AList is a list whose underlying structure is an array.

Ex (Discussion 3)

Ex 1 (insert)

Data Structure (Note that no size field):

1
2
3
4
5
6
7
8
public class SLList {
class IntNode {
int item;
IntNode next;
}

IntNode first;
}

My Way

Recursive:

Later, I wrote a recursive version. More succinct!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// size == 3
// if pos == 0, first
// if pos == 3, last
// if pos > 3, last
public void insert(int item, int pos) {
// better check size first; but in this case, no size field
first = insert(first, item, pos);
}

private IntNode insert(IntNode x, int item, int pos) {
if (pos <= 0 || x == null) { // consider invalid pos
return new IntNode(item, x); // return connects to prev
}
x.next = insert(x.next, item, pos - 1);
return x;
}

Iterative:

It is too complicated. Remember the insert pattern I summarize.

This is the code using another count variable. Don’t look at it. Go for the version in the Solution section.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public void insert(int item, int position) {
if (position == 0 || first == null) {
addFirst(item); return;
} /** position >= 1 && first != null */

IntNode p1 = null; /* prev node */
IntNode p2 = first; /* p1 p2 (ahead) */
int count = 0;
while (count < position) {
p1 = p2;
p2 = p2.next;
count += 1;
if (p2 == null) { /* hit the end */
break;
}
}
p1.next = new IntNode(item, p1.next);
}

Answer

You don’t need extra pointer to remember the previous node. In insert cases, you just need to look ahead, which means currentNode (also the one ptr finally stops at) is the one at pos - 1.

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
// 0 1 2 (index)  always use 2~3 nodes to test
// 3 6 2
/**
* Case 1: pos == 1, <currentNode> stops at pos 0
* Case 2: pos == 2, <currentNode> stops at pos 1
* Case 3: pos >= 3, <currentNode> stops at pos 2 (ending)
* ----------------------------------------------
* If pos is valid: <while> stops when pos hits 1
* If pos is invalid (>3): <while> stops when <currentNode.next> is null
*/
public void insert(int item, int pos) {
/**
* Guarantee [first] is not null, and we are not gonna insert node at (pos 0) since there is no (pos - 1) here.
* Unless a <sentinel> is used
*/
if (first == null || pos == 0) {
addFirst(item);
return;
}

IntNode currentNode = first; /* won't be null */
while (pos > 1 && currentNode.next != null) { // why pos > 1? If pos == 1, currentNode should not move.
pos--;
currentNode = currentNode.next;
}
IntNode newNode = new IntNode(item, currentNode.next);
currentNode.next = newNode; /* lastNode.next = newNode */
}

Count code patterns:

count > 0:

1
2
3
4
5
int count = 3;
while (count > 0) {
// 3 => 2 => 1 (3 times)
count--;
}

Equivalent to count >= 1:

1
2
3
4
5
int count = 3;
while (count >= 1) {
// 3 => 2 => 1 (3 times)
count--;
}

Ex 2 (reverse)

Iterative version

Use the same data structures above. Reverse elements using the existing IntNode objects (you should not use new).

My Way

Note: Similar to the solution. Just use one extra variable but make it clearer.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public void reverse() {
if (first == null || first.next == null) { // size = 0 or 1
return;
}
IntNode prev = null;
IntNode p = first; // first and first.next are not null
while (p.next != null) { // since p should stop at the last node
IntNode temp = p.next; // record the next
p.next = prev; // reverse
prev = p; // update prev
p = temp; // go to next
} /* p finally stops at the last node */
first = p;
}

Answer

The answer just uses the first as my prev, but it turns out to be a bit confusing.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// first -1-> ptr -2-> ptr.next (temp) -3-> ptr.next.next
public void reverse() {
if (first == null || first.next == null) {
return;
}
IntNode ptr = first.next; /* if no ".next", there will be a bug */
first.next = null; /* -1-> */
/* How to determine the condition?
* If ptr is pointing at the last node, we still need to work on it.
* Although ptr.next is null, we need to change it to the last 2nd node.
* The nice thing is: first is set at the same time.
* Next round, ptr is null. So we can go with ptr != null
*/
while (ptr != null) {
IntNode temp = ptr.next;
ptr.next = first; /* -2-> */
first = ptr; /* changing -3-> needs first */
ptr = temp;
}
}

Ex 2.5 (reverse extra - Challenging)

Write a second version that uses recursion.

Combine my way and the answer:

It is a very interesting way.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public void reverse() {
if (first == null) return null; // size = 0
first = reverseHelper(first); // helper must return the last node
}

private IntNode reverseHelper(IntNode x) {
// ok with size = 1
if (x.next == null) { // x finally stops at the last node
return x; // return the last node to first in the reverse()
}
// FOCUS (In the graph)
IntNode newHead = reverseHelper(x.next); // dig into
IntNode nextOfX = x.next;
nextOfX.next = x; // reverse (nextOfX.next.next = x)
x.next = null; // it would be set correctly in next round
// or you can write: if (x == first) x.next = null; NOT NECESSARY
return newHead;
}
}

Ex 3 (insert extra)

My solution (answer)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static int[] insert(int[] arr, int item, int position) {
int[] newArr = new int[arr.length + 1];
/** copy items before */
int i = 0;
for (i = 0; i < position; i++) {
newArr[i] = arr[i];
}
/** insert */
newArr[i] = item;
i++;
/** copy the items after */
for (; i < newArr.length; i++) {
newArr[i] = arr[i - 1];
}
return newArr;
}

Ex 4 (Array reverse)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static void reverse(int[] arr) {
// 0 1 2 3
// 1 2 3 4
// 1 2 3
// 1
// i < mid
// even: 1st half; odd: 1st half, but the middle element not included)
int mid = arr.length / 2; /* think over it */
for (int i = 0; i < mid; i++) {
int j = arr.length - i - 1;
int temp = a[i];
a[i] = arr[j];
a[j] = temp;
}
}

Ex 5 (Replicate extra)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static int[] replicate(int[] arr) {
int total = 0;
for (int num : arr) {
total += num;
}
int[] newArr = new int[total];
int i = 0;
for (int num : arr) {
int count = num;
while (count > 0) {
newArr[i] = num;
i++;
count--;
}
}
return newArr;
}

Exam Prep 3

Skippify

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public void skippify() {
IntList p = this;
int n = 1;
while (p != null) {
IntList next = p.rest;
for (int = 0; i < n; i += 1) {
if (next == null) {
break;
}
next = next.rest;
}
p.rest = next;
p = next;
n += 1;
}
}

Remove Duplicates

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static void removeDuplicate(IntList p) {
if (p == null) {
return;
}
IntList current = p.rest;
IntList previous = p;
while (current != null) {
if (previous.first == current.first) {
previous.rest = current.rest;
} else {
previous = current;
}
current = current.rest; /* previous stay the same */
}
}

Midterm 1 - Notes

Lab 3

Why is 128==128 false but 127==127 is true when comparing Integer wrappers in Java?

0%