teaching machines

CS 245 Lecture 15 – Linked String

October 22, 2013 by Chris Johnson. Filed under cs245, fall 2013, lectures.

Agenda

• what ?s
• define this
• the need for a node class
• pitting linked structures against arrays

Define This

Code

LinkedString.java

package lecture15;

public class LinkedString {
  private Node head;

  public LinkedString() {
    head = null;
  }

  public LinkedString(char c,
                      LinkedString rest) {
    head = new Node(c, rest.head);
  }

  public void print() {
    for (Node node = head; node != null; node = node.next) {
      System.out.print(node.c);
    }
  }

  public int length() {
    int length = 0;
    for (Node node = head; node != null; node = node.next) {
      ++length;
    }
    return length;
  }

  public char charAt(int i) {
    int nodeIndex = 0;
    for (Node node = head; node != null; node = node.next, ++nodeIndex) {
      if (i == nodeIndex) {
        return node.c;
      }
    }

    throw new StringIndexOutOfBoundsException();
  }

  public char charAtRecursively(int i) {
    if (head != null) {
      return head.charAt(i);
    } else {
      throw new StringIndexOutOfBoundsException();
    }
  }

  // public LinkedString substring(int startIndex) {
  //
  // }

  private static class Node {
    private char c;
    private Node next;

    public Node(char c,
                Node next) {
      this.c = c;
      this.next = next;
    }

    public char charAt(int i) {
      // Base case. No reaching into subproblem here!
      if (i == 0) {
        return c;
      }
      
      else if (next == null) {
        throw new StringIndexOutOfBoundsException();
      }

      // General case. Aww. Not as easy.
      else {
        return next.charAt(i - 1);
      }
    }
  }

  // private char c;
  // private LinkedString rest;
  //
  // public LinkedString(char c,
  // LinkedString rest) {
  // this.c = c;
  // this.rest = rest;
  // }
  //
  // public void print() {
  // System.out.print(c);
  // if (rest != null) {
  // rest.print();
  // }
  // }
  //
  // public int length() {
  // int length = 1;
  // for (LinkedString s = rest; s != null; s = s.rest) {
  // ++length;
  // }
  //
  // return length;
  // }

  public static void main(String[] args) {
    LinkedString name = new LinkedString('a',
                                         new LinkedString('l',
                                                          new LinkedString('a',
                                                                           new LinkedString('n',
                                                                                            new LinkedString()))));
    name.print();
    System.out.println(name.length());

    System.out.println(name.charAt(0));
    System.out.println(name.charAt(1));
    System.out.println(name.charAt(2));
    System.out.println(name.charAt(3));
    
    System.out.println(name.charAtRecursively(0));
    System.out.println(name.charAtRecursively(1));
    System.out.println(name.charAtRecursively(2));
    System.out.println(name.charAtRecursively(3));
    // System.out.println(name.charAt(4));
  }
}

Haiku