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

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.