# CS 61B | Part 1 | List (Linked List & Array List)

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

## IntList

IntList - Naked Recursive Structure

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

Basic Operations: SLList.java

### Nested Class

Note: There is a `static` modifier.

Code: Government.java (code is below)

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

Code: SLList_Sentinel.java

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 or variants`; namely, because `first` is now `null`, any method that tries to access a property of `first` (like `first.item`) will return a `NullPointerException`.

Solution:

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

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)

• getFirst (no effect) Note: Could be addressed by adding the second sentinel or make the first sentinel point to itself.
• deleteFirst (no effect)

### 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.
• Sentinel is `null` if the list is empty.

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

### Slow removeLast

Cache the last pointer! But it’ll make code more complicated.

• For example: `addFirst` should update `last` for the first item in the list, but not in other cases.
• It’d better to use `circular sentinel` or `two sentinels`.

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 pointer (just like the first node)? Not good enough.

### Doubly (Go Back)

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

• Set last 2nd node’s next to null
• Set last pointer

`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).

Because the list is not `circular`! Here are some code for taking care of the last node.

• getFirst
• removeFirst
• getLast
• removeLast

Solution:

Note: There is no `last` node here, since it breaks invariants.

• 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.

## AList

### Array In Java

Java Array: Arrays are a special kind of object which consists of a `numbered sequence` of memory boxes with `fixed` integer length.

Unlike other classes, arrays do not have methods.

Note: Bound checking only happens in runtime.

2D Array:

Notice the difference:

### 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`.
• Remember to do `size += 1`.
• `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.

• `size` should be decreased
• `items` should not be changed
• `items[i]` should not be changed (no need to “destroy” it)

### Resizing

#### Issue #1

Raw implementation:

Better encapsulation:

Geometric Resizing

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

Great performance (multiplicative amount):

#### Issue #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 Array

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

### 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.

### 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

### 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)

### DLList

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)
• 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)

### AList

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`.

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 (D2 + Guide)

Problem: Osmosis

Iterative:

Recursive (interesting!):

### 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.

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

### Ex 3 (Arrrrghrays)

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. The output is:

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

### Ex 4 (HighOrderFunctionsAndArrays)

Code: HigherOrderFunctionsAndArrays.java

### Ex 5 (Squaring a List)

Mutative / Non-mutative + Recursive / Iterative

## Ex (Discussion 3)

### Ex 1 (insert)

Data Structure (Note that no size field):

#### My Way

Recursive:

Later, I wrote a `recursive` version. More succinct!

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.

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`.

#### Count code patterns:

`count > 0`:

Equivalent to `count >= 1`:

### 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.

`p != null`:

`p.next != null`:

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

### 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 of using recursion.

Same as above (Just do it again when I am reviewing):

vs. (similar)

## Midterm 1 - Notes

Array:

IntList:

IntList (Destructive):

Good code (using `x.next = ...` to connect)

## Integer Cache (Lab 3)

Problem:

Explanation:

Therefore, we can manage our integers within the range of \$[-128, 127)\$ to achieve better performance, or by setting the system property to change the behavior:

Comment
Junhao Wang
a software engineering cat