2021-02-17

cs61b

5 minutes read (About 820 words)

2. Lists

2.1 Mystery of the Walrus

Types in Java

8 primitive types(byte, short, int, long, float, double, boolean, char)
reference types, which is point to specific instance, like array
- instantiation of reference type variable usually use new keyword
- declare reference type variable, allocate 64 bits size of box
  - bits can set to null(all zeros)
  - non-zero bits can address(arrow pointing) of specific instance of that class(address returned by new)

Passing parameters

copy all bits from parameter into function(new scope) <- called ‘pass by value’

IntList

size and iterativeSize methods to get the size of list with recursive and iterative ways
get method to get the ith item of the list

2.2 The SLList

public & private keyword

use private keyword to prevent outside to use members of class, variables, methods
- to hide implementation details from users of your class
public means user can access to class

nested classes

way to keep code organized
declare the nested class static if there no need to use any of instance methods or variables of parent class
- save a bit of memory as no longer need to keep track how to access

SLList vs. IntList

faster size() method than IntList
user of SLList never see IntList class
- simper to use
- addFirst method more efficient
- avoid errors(life cycle)

Sentinel Nodes

handle exception case
- such empty list
sentinel reference always point to sentinel nodes
first node(if exists) is sentinel.next
as global value, easy to access

Handle addFirst and addLast methods

There are two cases for each method

Initialized List is empty list
Initialized List is not empty

In empty list, addFirst method and addLast method are just
1
sentinel.next = new IntNode(x, null)

While list is not empty, addFirst method can be

1	sentinel.next = new IntNode(x, sentinel.next); //breaks

addLast method(2 ways)

O(n)
set pointer and iterate through list until reaching end of list

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

O(1)
set global value last

IntNode p = new IntNode(x, null);
// check empty list
if (sentinel.next == null) {
    sentinel.next = last = p;
}
last.next = p;
last = p;

2.3 The DLList

improvement

two links for every node: Doubly Linked List
extra pointer lead to extra code complexity
constant time to add, get, remove the front and back of a list
subtle issue: last pointer sometimes points at sentinel node, sometimes at a real node
- fix: add a second sentinel node to the back of the list
- fix: front and back pointer share the same sentinel node to make circular

Generic version

when implementing SLList class, we can only create int list. We can use generics as placeholder for type not declared yet, but only work with reference types.

int -> Integer
double -> Double
char -> Character
boolean -> Boolean
long -> Long
string -> String
byte -> Byte
float -> Float

2.4 Arrays

Array Basics

consists of a numbered sequence of memory boxes
a fixed integer length, N
all boxes are of the same type, are numbered 0 through N-1
3 ways to create array
1. x = new int[3]; //create with specific length and filled with default value 0
2. y = new int[]{1,2,3,4}; //create with specific elements
3. int[] z = {7,8,9,10}; // declare and create, no need to write new int[]

copy array (2 ways)

iterate through loop

int[] x = {1,2,3,4};
int[] y = new int[4];
int i = 0;
while (i < x.length) {
    y[i] = x[i];
    i++;
}

System.arraycopy(source, s_start, destination, d_start, n_copy) (faster)

1
2
3

int[] x = {1,2,3,4};
int[] y = new int[4];
System.arraycopy(x, 0, y, 0, 4);

Array vs. Class

both organize in memory boxes, and all fixed
- length of array cannot be changed, class fields cannot be added or removed
while array boxes are numbered and accessed using [] notation, class boxes are named and accessed using dot notation
- [] notation allows to specify which index at runtime, while specifying fields in class we can not do at runtime
array boxes must be same type, class boxes can be different types

2.5 The Alist

use arrays to store data instead of linked list
constant time access array, better performance for get in a linked-list based
remove last element from array, only need to change size
add new element to cause exceed size of array, make a new array which larger original and copy old array
memory performance
- usage ratio R = size of list divided by the length of the items array
- halve the size of the array if R <= 0.25
create generic AList: Term[] items = (Term[]) new Object[8];

references

# java, list

Commentaires

Articles

73

Catégories

11