CS 245 Lecture 15 – Linked String
Agenda
- what ?s
- define this
- the need for a node class
- pitting linked structures against arrays
Define This
What is a string? Say it in 10 words or less.
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
Arrays are to loops
As linked structures are to what?
As linked structures are to what?
Loops and recursion!