Values are numbers, booleans, and pointers. They cannot change without being replaced entirely. Kinds of values:
int, double, bool,
char, short, long, float,
byte
Simple containers are named and contain values, which may be pointers to structured containers.
Structured containers are anonymous and contain zero or more simple containers.
Java variables and fields are simple containers! We don't work directly with structured containers, but instead through pointers.
public class Cat {
int id;
int age;
public Cat(int id, int age) {
this.id = id;
this.age = age;
}
public static void main(String[] args) {
Cat marty = new Cat(2, 5);
}
}
A linked list is a data structure that is a structured container containing two simple containers:
head holds a valuetail holds a pointer to the next Linked List, which holds two
simple containers:
head holds a valuetail holds a pointer to the next Linked List, which holds two simple
containers:
head holds a valuetail holds a pointer to the next Linked List, which holds two
simple containers...
head holds a valuetail holds a pointer to the next Linked List, which holds two
simple containers...
A linked list is a recursive data structure!
Our linked list type is IntList.
IntList L = new IntList(1, new IntList(2, new IntList(3, null)));
You don't need to draw the red boxes, though - it's clear that
head and tail are part of the same structured container.
An array is a data structure that is a structured container that contains a fixed number of simple containers of the same type of value.
Access the simple container at index i with arr[i].
An array stores its length in the field length, but we don't usually draw
it in diagrams.
int[] intArr = new int[]{4, 1, 8};
IntList[] intListArr = new IntList[]{new IntList(3, null), new IntList(5, null)};
What if I run
intListArr[0].tail = intListArr[1]?
In Java, assignment and function calls copy the values inside simple containers. The original simple containers are left alone!
Destructive functions alter the structured container pointed to by the argument. The changes remain even after we leave the function.
Non-Destructive functions do not alter the structured container(s) pointed to by the argument.
void f(int[] x) {
x[1] = 5; // destructive
x = new int[]{5}; // non-destructive
}
// main
int[] A = new int[]{4, 1, 8};
f(A);
IntList L = IntList.list(1, 2, 3, 4);
IntList M = L.tail.tail;
IntList N = IntList.list(5, 6, 7);
N.tail.tail.tail = N;
L.tail.tail = N.tail.tail.tail.tail;
M.tail.tail = L;
How does the box and pointer diagram change after each statement?
IntList L1 = IntList.list(1, 2, 3);
IntList L2 = new IntList(4, L1.tail);
L2.tail.head = 13;
L1.tail.tail.tail = L2;
IntList L3 = IntList.list(50);
L2.tail.tail = L3;
/** Returns the head of IntList L. Assumes that L is not null. */
public static int getHead(IntList L) {
int listHead = L.head;
L = new IntList(5, null);
return listHead;
}
Is getHead destructive or non-destructive?
/** Nondestructively reverses IntList L. */
public static IntList reverseNondestructive(IntList L) {
}
/** Destructively reverses IntList L using recursion */
public static IntList reverseDestructive(IntList L) {
}
/** Inserts item at the given position in IntList L and returns the resulting
* IntList. If the value of position is past the end of the list, inserts the
* item at the end of the list. Uses recursion. */
public static IntList insertRecursive(IntList L, int item, int position) {
}
/** Inserts item at the given position in IntList L and returns the resulting
* IntList. If the value of position is past the end of the list, inserts the
* item at the end of the list. Uses iteration. */
public static IntList insertIterative(IntList L, int item, int position) {
}
/** Destructively shifts the elements of the given IntList L to the
* left by one position. Returns the first node in the shifted list. */
public static IntList shiftListDestructive(IntList L) {
}