CS210 - Lists, Arrays & Iterators Study Guide

📊 Arrays

Definition

An array is a sequenced collection of variables all of the same type. Each variable, or cell, in an array has an index, which uniquely refers to the value stored in that cell.

The cells of an array A are numbered 0, 1, 2, and so on.

Array Structure

...

Key Concepts

🔑 Array Length and Capacity

Length/Capacity: The maximum number of elements that can be stored in the array
In Java: accessed using a.length
Cells are numbered from 0 to a.length - 1
Access cell with index k: a[k]

Declaring Arrays

Method 1: Literal Form

elementType[] arrayName = {initialValue₀, initialValue₁, ..., initialValueₙ₋₁};

// Example:
int[] a = {5, 7, 9, 10};
                

Method 2: Using 'new' Operator

new elementType[length]

// Example:
int[] numbers = new int[10];
String[] names = new String[3];
                

Array Operations

✏️ Adding an Entry at Index i

Process: To add entry e at index i, shift forward the n - i entries from board[i] to board[n-1]

Time Complexity: O(n) in worst case (when i = 0)

// Pseudocode for adding at index i
for (j = n-1; j >= i; j--)
    board[j+1] = board[j];
board[i] = e;
size++;
                    

🗑️ Removing an Entry at Index i

Process: To remove entry at index i, shift backward the n - i - 1 entries from board[i+1] to board[n-1]

Time Complexity: O(n) in worst case (when i = 0)

// Pseudocode for removing at index i
for (j = i; j < size-1; j++)
    board[j] = board[j+1];
board[size-1] = null;
size--;
                    

Performance Summary

Operation	Time Complexity	Notes
Access element at index i	O(1)	Direct access via a[i]
Insert at index i	O(n)	Need to shift elements
Remove at index i	O(n)	Need to shift elements
Search for element	O(n)	Must check each element

🔗 Singly Linked Lists

Definition

A singly linked list is a concrete data structure consisting of a sequence of nodes, starting from a head pointer. Each node stores:

An element (the data)
A link to the next node

The last node's link points to null.

⚠️ Key Characteristics

Can only move forward through the list
Each node has a reference to the next node only
The last node points to null
Requires a head pointer to access the list
Often includes a tail pointer for efficient insertion at end

Node Class Implementation

private static class Node<E> {
    private E element;           // reference to element
    private Node<E> next;       // reference to next node
    
    public Node(E e, Node<E> n) {
        element = e;
        next = n;
    }
    
    public E getElement() { return element; }
    public Node<E> getNext() { return next; }
    public void setNext(Node<E> n) { next = n; }
}
                

Basic Operations

➕ Inserting at the Head

Steps:

Allocate a new node
Insert new element
Have new node point to old head
Update head to point to new node

Time Complexity: O(1)

public void addFirst(E element) {
    head = new Node<>(element, head);
    size++;
    if (size == 1)
        tail = head;  // special case: new node becomes tail
}
                    

➕ Inserting at the Tail

Steps:

Allocate a new node
Insert new element
Have new node point to null
Have old last node point to new node
Update tail to point to new node

Time Complexity: O(1)

public void addLast(E element) {
    Node<E> newest = new Node<>(element, null);
    if (isEmpty())
        head = newest;
    else
        tail.setNext(newest);
    tail = newest;
    size++;
}
                    

➖ Removing at the Head

Steps:

Update head to point to next node
Allow garbage collector to reclaim the former first node

Time Complexity: O(1)

public E removeFirst() {
    if (isEmpty()) return null;
    E answer = head.getElement();
    head = head.getNext();
    size--;
    if (size == 0)
        tail = null;  // list is now empty
    return answer;
}
                    

⚠️ Removing at the Tail - NOT EFFICIENT!

Removing at the tail of a singly linked list is not efficient because:

There is no constant-time way to update the tail to point to the previous node
We would need to traverse the entire list to find the second-to-last node
Time Complexity: O(n)

Performance Summary

Operation	Time Complexity	Notes
Insert at head	O(1)	Just update head pointer
Insert at tail	O(1)	With tail pointer
Remove at head	O(1)	Just update head pointer
Remove at tail	O(n)	Must traverse to find previous node
Access element at index i	O(n)	Must traverse from head

🔗🔗 Doubly Linked Lists

Definition

A doubly linked list provides a more versatile data structure that can be traversed forward and backward. Each node stores:

An element (the data)
A link to the previous node
A link to the next node

Uses special header and trailer sentinel nodes (with no data).

⚠️ Key Advantages over Singly Linked Lists

Can traverse both forward and backward
Can efficiently remove at the tail - O(1)
Can efficiently insert before a given node
Easier to implement certain operations

Node Class Implementation

private static class Node<E> {
    private E element;           // reference to element
    private Node<E> prev;       // reference to previous node
    private Node<E> next;       // reference to next node
    
    public Node(E e, Node<E> p, Node<E> n) {
        element = e;
        prev = p;
        next = n;
    }
    
    public E getElement() { return element; }
    public Node<E> getPrev() { return prev; }
    public Node<E> getNext() { return next; }
    public void setPrev(Node<E> p) { prev = p; }
    public void setNext(Node<E> n) { next = n; }
}
                

Sentinel Nodes

🏁 Header and Trailer Nodes

Header: Dummy node at the beginning (stores no data)
Trailer: Dummy node at the end (stores no data)
Purpose: Simplify implementation by eliminating special cases for empty lists
An empty list has header.next = trailer and trailer.prev = header

// Constructor for empty list
public DoublyLinkedList() {
    header = new Node<>(null, null, null);
    trailer = new Node<>(null, header, null);
    header.setNext(trailer);
}
                    

Basic Operations

➕ Inserting Between Two Nodes

Steps:

Create new node
Link new node to predecessor and successor
Link predecessor to new node
Link successor to new node

Time Complexity: O(1)

private void addBetween(E element, Node<E> predecessor, Node<E> successor) {
    Node<E> newest = new Node<>(element, predecessor, successor);
    predecessor.setNext(newest);
    successor.setPrev(newest);
    size++;
}

// Insert at front (after header)
public void addFirst(E element) {
    addBetween(element, header, header.getNext());
}

// Insert at end (before trailer)
public void addLast(E element) {
    addBetween(element, trailer.getPrev(), trailer);
}
                    

➖ Removing a Node

Steps:

Get predecessor and successor of node to remove
Link predecessor to successor
Link successor to predecessor
Allow garbage collection of removed node

Time Complexity: O(1)

private E remove(Node<E> node) {
    Node<E> predecessor = node.getPrev();
    Node<E> successor = node.getNext();
    predecessor.setNext(successor);
    successor.setPrev(predecessor);
    size--;
    return node.getElement();
}

// Remove first element
public E removeFirst() {
    if (isEmpty()) return null;
    return remove(header.getNext());
}

// Remove last element - NOW EFFICIENT!
public E removeLast() {
    if (isEmpty()) return null;
    return remove(trailer.getPrev());
}
                    

Performance Summary

Operation	Time Complexity	Notes
Insert at head	O(1)	After header node
Insert at tail	O(1)	Before trailer node
Remove at head	O(1)	After header node
Remove at tail	O(1)	✅ NOW EFFICIENT! Can access previous node
Insert/Remove at given node	O(1)	If we have reference to the node

⚖️ Arrays vs. Linked Lists Comparison

📊 Arrays

Advantages:

✅ Fast random access - O(1)
✅ Memory efficient (no extra pointers)
✅ Better cache locality
✅ Simple implementation

Disadvantages:

❌ Slow insertion/deletion - O(n)
❌ Fixed size (or expensive resizing)
❌ Wasted space if not full

🔗 Linked Lists

Advantages:

✅ Fast insertion/deletion at known positions - O(1)
✅ Dynamic size
✅ No wasted space
✅ Easy to split/merge lists

Disadvantages:

❌ Slow random access - O(n)
❌ Extra memory for pointers
❌ Poor cache locality

When to Use Each

Use Arrays when:

You need fast random access by index
The size is known and relatively fixed
Memory is limited (no extra pointers)
You're doing lots of reading, little insertion/deletion

Use Linked Lists when:

You need frequent insertions/deletions
The size changes dynamically
You don't need random access
You're implementing queues, stacks, or other sequential structures

📈 Dynamic Array Lists (Growable Arrays)

The Problem with Fixed Arrays

Standard arrays have a fixed capacity. What if we don't know the size in advance? What if we need to grow the array?

Solution: Dynamic Arrays

When the array becomes full, we can:

Create a new, larger array
Copy all elements from the old array to the new array
Replace the reference to point to the new array

Growth Strategies

Incremental Strategy

Increase size by a constant c

New size = old size + c

Analysis:

Replace array k = n/c times
Total time: n + c + 2c + 3c + ... + kc
T(n) = O(n + k²) = O(n²)
Amortized time per push: O(n)

❌ Not efficient!

Doubling Strategy

Double the size each time

New size = 2 × old size

Analysis:

Replace array k = log₂ n times
Total time: n + 1 + 2 + 4 + 8 + ... + 2^k
T(n) = n + 2^(k+1) - 1 = O(n)
Amortized time per push: O(1)

✅ Much better!

Implementation

public void add(int index, E element) {
    // Check if array is full
    if (size == data.length) {
        // Double the capacity!
        E[] newData = (E[]) new Object[2 * data.length];
        for (int i = 0; i < size; i++)
            newData[i] = data[i];
        data = newData;
    }
    
    // Shift elements to make room
    for (int i = size; i > index; i--)
        data[i] = data[i-1];
    
    data[index] = element;
    size++;
}
                

🎯 Key Takeaway: Amortized Analysis

Amortized time is the average time per operation over a sequence of operations.

With the doubling strategy:

Most insertions are cheap (O(1))
Occasionally we have an expensive operation (O(n)) when we resize
But resizing happens so infrequently that the average is still O(1)!

Java's ArrayList

Java's java.util.ArrayList implements this dynamic array concept:

Automatically grows as needed
Provides O(1) amortized insertion at end
Provides O(1) access by index
Still O(n) for insertion/deletion in the middle

📍 Positional Lists

What is a Positional List?

A positional list is an ADT that provides a general abstraction of a sequence with the ability to identify the location of an element.

A position acts as a marker or token within the list, independent of the element's index.

🎯 Key Concepts

A position is unaffected by changes elsewhere in the list
Only becomes invalid if explicitly deleted
Supports efficient insertion/deletion at any position
Natural implementation: doubly linked list

Position Interface

public interface Position<E> {
    // Returns the element stored at this position
    E getElement() throws IllegalStateException;
}
                

Positional List ADT Methods

Accessor Methods

Method	Description	Complexity
`first()`	Returns position of first element (or null if empty)	O(1)
`last()`	Returns position of last element (or null if empty)	O(1)
`before(p)`	Returns position immediately before p (or null)	O(1)
`after(p)`	Returns position immediately after p (or null)	O(1)
`isEmpty()`	Returns true if list contains no elements	O(1)
`size()`	Returns number of elements in the list	O(1)

Update Methods

Method	Description	Complexity
`addFirst(e)`	Insert element at front, return its position	O(1)
`addLast(e)`	Insert element at back, return its position	O(1)
`addBefore(p, e)`	Insert element just before position p	O(1)
`addAfter(p, e)`	Insert element just after position p	O(1)
`set(p, e)`	Replace element at position p, return old element	O(1)
`remove(p)`	Remove and return element at position p	O(1)

Example Usage

PositionalList<String> list = new LinkedPositionalList<>();

// Build list: (A, B, C)
Position<String> p1 = list.addLast("A");
Position<String> p2 = list.addLast("B");
Position<String> p3 = list.addLast("C");

// Insert before B: (A, X, B, C)
Position<String> p4 = list.addBefore(p2, "X");

// Access neighbors
list.after(p1);    // returns position of X
list.before(p2);   // returns position of X

// Remove X: (A, B, C)
list.remove(p4);
                    

🔄 Iterators

What is an Iterator?

An iterator is a software design pattern that abstracts the process of scanning through a sequence of elements, one element at a time.

Iterator Interface

public interface Iterator<E> {
    // Returns true if there is at least one more element
    boolean hasNext();
    
    // Returns the next element in the sequence
    E next();
    
    // Optional: removes the last returned element
    default void remove() {
        throw new UnsupportedOperationException("remove");
    }
}
                

Iterable Interface

Collections implement the Iterable interface, which provides a method to obtain an iterator:

public interface Iterable<E> {
    // Returns an iterator over elements of type E
    Iterator<E> iterator();
}
                    

Using Iterators

Traditional Way

List<String> names = new ArrayList<>();
// ... add elements ...

// Get an iterator
Iterator<String> iter = names.iterator();

// Loop through elements
while (iter.hasNext()) {
    String name = iter.next();
    System.out.println(name);
}
                

For-Each Loop (Syntactic Sugar)

Java's for-each loop is syntactic sugar for iterator usage:

// This elegant syntax...
for (String name : names) {
    System.out.println(name);
}

// ...is equivalent to this:
Iterator<String> iter = names.iterator();
while (iter.hasNext()) {
    String name = iter.next();
    System.out.println(name);
}
                    

🎯 Key Benefits of Iterators

Abstraction: Same interface for different data structures
Flexibility: Can have multiple iterators on same collection
Safety: Can remove elements safely during iteration
Simplicity: For-each loop provides clean syntax

Implementing an Iterator

Example: Iterator for ArrayList

private class ArrayIterator implements Iterator<E> {
    private int current = 0;  // index of next element
    
    public boolean hasNext() {
        return current < size;
    }
    
    public E next() {
        if (!hasNext()) 
            throw new NoSuchElementException();
        return data[current++];
    }
}

// In the ArrayList class
public Iterator<E> iterator() {
    return new ArrayIterator();
}
                    

📝 Complete Summary

Time Complexity Comparison

Operation	Array	Singly Linked	Doubly Linked
Access by index	O(1)	O(n)	O(n)
Insert at head	O(n)	O(1)	O(1)
Insert at tail	O(n)	O(1)	O(1)
Remove at head	O(n)	O(1)	O(1)
Remove at tail	O(n)	O(n)	O(1)
Insert at middle	O(n)	O(n)*	O(n)*

* O(1) if position is already known

🎓 Key Takeaways

1. Arrays

Best for: Random access and fixed-size collections
Weakness: Slow insertion/deletion
Memory: Contiguous, good cache locality

2. Singly Linked Lists

Best for: Sequential access, frequent head operations
Weakness: Can't efficiently remove at tail, no backward traversal
Memory: Scattered, extra space for next pointer

3. Doubly Linked Lists

Best for: Bidirectional traversal, operations at both ends
Weakness: More memory (two pointers per node)
Memory: Scattered, extra space for prev and next pointers

4. Dynamic Arrays (ArrayList)

Combines array access speed with dynamic sizing
Doubling strategy gives O(1) amortized insertion at end
Best general-purpose list in Java

5. Positional Lists

Abstract positions independent of indices
Naturally implemented with doubly linked lists
All operations in O(1) time if position is known

6. Iterators

Provide uniform way to traverse collections
Enable for-each loops
Allow multiple simultaneous traversals

💡 Study Tips & Practice Questions

🎯 What You Must Know

Time complexity of operations for each data structure
When to use arrays vs. linked lists
How to implement basic operations (insert, delete, traverse)
The difference between singly and doubly linked lists
How dynamic arrays work (doubling strategy)
What amortized analysis means
How iterators work and why they're useful

Practice Questions

Question 1: Array Operations

Q: Why is inserting an element in the middle of an array O(n)?

A: Because we need to shift all elements after the insertion point one position to the right. In the worst case (inserting at index 0), we shift n elements.

Question 2: Linked List Advantage

Q: When is a linked list better than an array?

A: When you need frequent insertions/deletions and don't need random access. Linked lists can insert/delete in O(1) time if you have the position, while arrays require O(n) time for shifting elements.

Question 3: Doubly vs. Singly Linked

Q: What's the main advantage of a doubly linked list over a singly linked list?

A: Doubly linked lists can efficiently remove at the tail (O(1)) and traverse backward. Singly linked lists require O(n) time to remove at the tail because they must traverse to find the previous node.

Question 4: Dynamic Arrays

Q: Why is the doubling strategy for dynamic arrays better than incrementing by a constant?

A: Doubling gives O(1) amortized time per insertion (total O(n) for n insertions), while incrementing by a constant gives O(n) amortized time (total O(n²) for n insertions). Doubling reduces the frequency of expensive resize operations.

Question 5: Iterator Usage

Q: What does "iterable" mean in Java?

A: A class is iterable if it implements the Iterable interface, meaning it provides an iterator() method that returns an Iterator object. This allows the class to be used in for-each loops.