Lecture 11:

LinkedLists

CS 136: Spring 2024

Katie Keith

• Lab 3 this week
• Stand up for Science rally today (Friday) at 12pm, Williams Science Quad

📣 Announcements

• Review Recursion and Big-O
• Define and implement LinkedLists

🎯 Today’s Learning Objectives

📚Readings

• Sedgewick & Wayne. CS:IA. Section 2.3.
• Sedgewick & Wayne. CS:IA. Section 4.3.
• Sedgewick & Wayne. Algorithms. Section 1.3.

Review: Big-O: Worst-case order of growth

Runtime or

Memory

Input size, n

Task: Fibonacci Sequence

Add the previous two numbers

Fig credit

1. For the program below, pick the colored line (Big-O) closest to the program’s order of growth for the runtime.
2. Do you think we could write a program for the same task that’s faster (asymptotically)?

public static int fibonacci(int n) {

if (n == 0|| n == 1) {

return n;

} else {

return fibonacci(n - 1) + fibonacci(n - 2);

}

}

💡Think-pair-share

Fibonacci.java

💻

Top-down dynamic programming

In top-down dynamic programming, we cache the result of each subproblem, so that the next time we need to solve the same subproblem, we can use the cached values instead of solving the subproblem from scratch.

private static int[] fibCache = new int[100];

​

public static int topDownFibonacci(int n){

if(n == 0|| n == 1){return n;}

if(fibCache[n] > 0){

return fibCache[n];

}

fibCache[n] = topDownFibonacci(n-1) + topDownFibonacci(n-2);

return fibCache[n];

}

Variable that stores cached values

static variable (declared outside of any method)

Compute and cache value

Big-O?

• Review Recursion and Big-O
• Define and implement LinkedLists

✅

🎯 Today’s Learning Objectives

Review: ADT vs. Data Structures

Review: List Interface

public interface OurListInterface<T>{

public abstract int size();

public abstract void set(int index, T element);

public abstract void remove(T element);

public abstract void add(T element);

public abstract T get(int index);

}

Generics

An abstract method doesn’t include any implementation code.

Review: Generics

public class ArrayList<T>

​

ArrayList<Integer> list1 = new ArrayList<Integer>;

ArrayList<Animal> list2 = new ArrayList<Animal>;

​

In Java, generics allow us to abstract over types while ensuring the compiler checks the type correctness of the program at compile-time.

When a generic declaration is invoked, the actual type arguments are substituted for the formal type parameters.

formal type parameter

actual type argument

Review: ArrayList Data Structure

public class OurArrayList<T> implements OurListInterface<T>{

​

private static final int DEFAULT_INITIAL_CAPACITY = 10;

private static final double GROWTH_FACTOR = 2.0;

​

private Object[] privateArray;

private int currentNumElements;

​

public OurArrayList(int capacity){

privateArray = new Object[capacity];

currentNumElements = 0;

}

...

​

ADT vs. Data Structures

Last week

Next week

Next week

Next week

Lab 4!

Today!

Visualizing LinkedLists

first

A linked list is a recursive data structure that is either empty (null) or a reference to a node.

Each node holds some data (here, a string)

And a reference to the next node

LinkedList.java

Constructor, Inner Node class

💻

LinkedList Inner Node Class

To implement a linked list, we start with an inner class that defines the node abstraction with two instance variables:

// Inner node class

public class Node{

public T data;

public Node next;

​

public Node() {

this.data = null;

this.next = null;

}

}

Each node holds a generic data type T (later, when we create an object, this is replaced with actual type, e.g., String)

Each node also holds a reference to the next node in the Linked List.

Visualizing LinkedLists

first

A linked list is a recursive data structure that is either empty (null) or a reference to a node.

Node x = Node();

x.data = "to";

x.next = y;

Node y = Node();

y.data = "be";

y.next = z;

first = x;

Inserting at the beginning of a LinkedList

LinkedList.java

insertBeginning

add

💻

Compute and compare the big-O runtimes of the same List (ADT) operation, add, for the two different data structures below. Here n is the number of elements currently in the List.

​

Hint: Big-O is the worst case.

// ArrayList

public void add(T element) {

checkExpand(); // Checks if the private array is full,

// if so, expands the array by the GROWTH_FACTOR

privateArray[currentNumElements++] = element;

}

private void checkExpand() {

if (this.currentNumElements == privateArray.length) {

int newSize = (int)(privateArray.length * GROWTH_FACTOR);

Object[] newArray = new Object[newSize];

​

// Copy over the elements

for(int i =0; i<privateArray.length; i++){

newArray[i] = privateArray[i];

}

// Update instance variable� this.privateArray = newArray;

}

}

​

// LinkedList (adds at beginning)

public void add(T element){

Node oldFirst = first;

first = new Node();

first.data = element;

first.next = oldFirst;

}

​

💡Think-pair-share

LinkedLists: Removing the first node.

Suppose the variable x is a Node of a Linked List.

​

What is the result of the following code fragment?

x.next = x.next.next;

​

💡Think-pair-share

Traversing a LinkedList

for(Node x = first; x!=null; x = x.next){

// do something with x here

}

​

Node x = first;

while (x.next != null) {

// do something with x here

x = x.next;

}

​

To traverse a LinkedList, we can use a for or while loop.

LinkedLists: Adding to the end of the list

LinkedList.java

💻

• Review Recursion and Big-O
• Define and implement LinkedLists

✅

✅

🎯 Today’s Learning Objectives

x.next = x.next.next;

​

Answer

x = Node();

x.data = "to";

x.next = y;

y = Node();

y.data = "be";

y.next = z;

z = Node();

z.data = "or";

z.next = a;

💡Think-pair-share