CSC171: Intro to Computer Science - Linked Lists, Sets, and Maps

Recursion

  • Recursion involves methods calling themselves directly or indirectly.
  • Examples include factorial, Fibonacci sequence, and fractals.
  • Additional examples are determinants, matrix multiplication, minimax search, binary search, depth-first search, dynamic programming, trees, and lists.

Linked Lists

  • Linked lists illustrate structural recursion, where a class is defined in terms of itself.
  • Implementation includes a wrapper class, a recursive node class, and various methods.
  • Focus is on building a linked list of Strings.

Desiderata

  • Desired behaviors for a linked list:
    • Adding elements (at the front, back, or by position).
    • Retrieving elements by position.
    • Searching for an element by value.
    • Printing the list as a string.

ListNode and List Classes

  • ListNode:
    • Contains a String data field.
    • Contains a next field, which is a reference to the next ListNode.
  • List:
    • Contains a head field, which points to the first ListNode in the list.

Adding to a Linked List

  • Adding elements can be done anywhere in the list but is easiest at the front or back.
  • Adding to the front involves updating the head.
  • Adding to the back can be done by traversing the list to find the last node or by maintaining a tail pointer for faster access.

Linked List Structures

  • List Class:
    • head: Points to the first element.
    • tail: Points to the last element.
  • ListNode Class:
    • data: Holds the data.
    • next: A reference to the next node (recursion).

Generics

  • Using generics, the List and ListNode classes can be generalized to hold any type T:
    • class List<T> { ListNode<T> head; ListNode<T> tail; ... }
    • class ListNode<T> { T data; ListNode<T> next; ... }

Adding Elements

  • Adding to the Front:

    • For the first element, create a node and point both head and tail to it.
    • For subsequent elements, update the head to point to the new element.
    public void addFront(String data) {
    head = new Node(data, head);
    if (size == 0)
        tail = head;
    size++;
}

Note: After the first element is added, the tail never changes.

  • Adding to the Back:

    public void addBack(String data) {
    Node node = new Node(data);
    if (size == 0) {
        head = node;
    } else {
        tail.next = node;
    }
    tail = node;
    size++;
}

Note: After the first element is added, the head never changes.

List Traversal

  • Traversing a linked list involves visiting each element, useful for printing, searching, and accessing elements by index.

    public boolean contains(String data) {
    Node current = head;
    while (current != null) {
        if (current.data.equals(data))
            return true;
        current = current.next;
    }
    return false;
}

Time Complexity

  • Adding at the front or back takes constant time, denoted as O(1), as it involves no loops or recursion.
  • Traversing the list requires visiting each element, resulting in linear time complexity, denoted as O(n).

Big-O Complexity Chart

  • Common time complexities:
    • O(n!)
    • O(2^n)
    • O(n^2)
    • O(n \log n)
    • O(n)
    • O(\log n), O(1)

Mystery Method

  • Time complexity analysis:
    • fun(i, j) has a time complexity of O(1).
    • mystery(n) has a time complexity of O(n^2).

String Builders

  • String Builders are used for efficient string manipulation.

    public String toString() {
    StringBuilder answer = new StringBuilder();
    answer.append("<");
    Node<T> current = head;
    while (current != null) {
        answer.append(current.data);
        if (current.next != null)
            answer.append(", ");
        current = current.next;
    }
    answer.append(">");
    return answer.toString();
}

  • Without String Builder:

    public String toString() {
    String answer = “”;
    answer = answer + ”<“;
    Node<T> current = head;
    while (current != null) {
        answer = answer + current.data;
        if (current.next != null)
            answer = answer + ", ";
        current = current.next;
    }
    answer = answer + ">";
    return answer;
}
    • The time complexity without StringBuilder is O(n^2), due to repeated string concatenation.
    • 1 + 2 + … + n = \frac{n(n+1)}{2}

Checkpoint: Linked Lists

  • Linked lists are versatile and fundamental data structures for sequential data.
  • They are structurally recursive with self-referential links/nodes.
  • Insert/remove cost depends on implementation.
  • Searching for a value is expensive.

ArrayLists

  • ArrayLists use an array of Objects for data storage.
  • They provide a method to "grow" the array when space runs out.
  • Include methods for adding, removing, searching, and sorting data.

ArrayList Implementation

  • Due to type erasure, generic arrays cannot be created directly.

  • Instead, an Object array is created, relying on polymorphism and typecasting.

    public class DIYArrayList <T extends Comparable<T>> implements DIYList<T> {
    private Object[] values;
    private int size;
    public DIYArrayList() {
        values = new Object[INIT_SIZE];
    }
}

Adding Elements and Growing the Array

  • Growing the array:

    private void growArray() {
    Object[] oldValues = values;
    values = new Object[oldValues.length * 2];
    for (int n = 0; n < oldValues.length; n++)
        values[n] = oldValues[n];
}

public void add(T data) {
    if (size + 1 > values.length) {
        growArray();
    }
    values[size++] = data;
}

public void add(int idx, T data) {
    if (size + 1 > values.length)
        growArray();
    for (int n = size; n > idx; n--)
        values[n] = values[n-1];
    values[idx] = data;
    size++;
}
    • add(T data) has a time complexity of O(1).
    • growArray() has a time complexity of O(n).
    • add(int idx, T data) has a time complexity of O(n).

Selected Time Complexities

OperationArrayListLinkedList (no tail ptr)LinkedList (with tail ptr)
insertFrontO(N)O(1)O(1)
removeFrontO(N)O(1)O(1)
insertBackO(1)*O(N)O(1)
removeBackO(1)O(N)O(1)
getByIndexO(1)O(N)O(N)
searchByValueO(\lg N) or O(N)O(N)O(N)
Fast SortO(N*\lg(N))O(N*\lg(N))O(N*\lg(N))
Slow SortO(N^2)O(N^2)O(N^2)
toString (w/SB)O(N)O(N)O(N)
toString (no SB)O(N^2)O(N^2)O(N^2)

Collections

  • Interfaces/ADTs:
    • List
      • ArrayList
      • LinkedList
    • Queue
      • ArrayStack
      • LinkedStack
    • Set
      • TreeSet
      • HashSet
    • Map
      • TreeMap
      • HashMap
    • Deque

Prelude: Why not use Lists?

  • Sets must support Insert() and Contains().
  • Lists can easily support both, but at what cost?

List Implementations

  • ArrayList: Constant time for insert; Linear time for contains.
  • LinkedList: Constant time for insert; Linear time for contains.

Making Contains() Cheaper

  • Organization (sorting) simplifies contains.
  • For sorted elements, stop searching when a value larger than the target is found.
  • On average, this requires checking N/2 elements instead of N.

Binary Search

  • Binary search can be implemented using array.
  • Implements the contains() operation in O(\lg N) time!

TreeSets and HashSets

  • TreeSets:
    • Support Insert/Contains in O(\lg N);
    • Automatically sorts their inputs.
    • Elements must be comparable.
  • HashSets:
    • Support Insert/Contains in O(1).
    • Elements stored in random order.
    • Elements do not have to be Comparable but must be testable for equality.
    • Requires elements to be hashable.

Trees

  • Trees are non-sequential data structures.
  • They consist of a root and branches (which are also considered trees).

Binary Trees

  • Binary trees consist of a root with a left child and a right child, both of which are binary trees.

Binary Tree Nodes

  • Implementation of a binary tree node:

    class TreeNode<E> {
    TreeNode<E> leftChild;
    TreeNode<E> rightChild;
    E data;
}

Binary Search Tree

  • A Binary Search Tree (BST) has the property that every value less than the root is to the left, and every value greater is to the right.
  • The left and right children must also be binary search trees.

Binary Search Tree Class: TreeNode.java

  • Insert Implementation:

    public void insert(E data) {
    if (data.compareTo(this.data) < 0) {
        if (leftChild == null)
            leftChild = new TreeNode<>(data);
        else
            leftChild.insert(data);
    } else {
        if (rightChild == null)
            rightChild = new TreeNode<>(data);
        else
            rightChild.insert(data);
    }
}

  • Search Implementation:

    public boolean search(E data) {
    if (data.compareTo(this.data) < 0) {
        if (leftChild == null)
            return false;
        else
            return leftChild.search(data);
    } else if (data.compareTo(this.data) > 0) {
        if (rightChild == null)
            return false;
        else
            return rightChild.search(data);
    } else {
        return true;
    }
}

Efficiency

  • Typical binary search trees are efficient for searching (O(\log n)).
  • Insertion is also O(\log n).
  • Worst cases for both are O(n).

Printing Values

  • Inorder: A B C D E F Z

  • Preorder: E B A D C F Z

  • Postorder: A C D B Z F E

    public void inOrder() {
    if (leftChild != null)
        leftChild.inOrder();
    System.out.println(data);
    if (rightChild != null)
        rightChild.inOrder();
}

Summary of Binary Search Trees

  • Data structure for storing sets of comparable values.
  • Efficiency depends on insertion order.
  • Elegant recursive algorithms for processing.