package cse1030;
public class LinkedList {
private static class Node {
private char data;
private Node next;
public Node(char c) {
this.data = c;
this.next = null;
}
}
private int size;
private Node head;
/**
* Create a linked list of size 0.
*/
public LinkedList() {
this.size = 0;
this.head = null;
}
/**
* Adds the given character to the end of the list.
*
* @param c The character to add
*/
public void add(char c) {
if (this.size == 0) {
this.head = new Node(c);
} else {
LinkedList.add(c, this.head);
}
this.size++;
}
/**
* Adds the given character to the end of the list.
*
* @param c The character to add
* @param node The node at the head of the current sublist
*/
private static void add(char c, Node node) {
if (node.next == null) {
node.next = new Node(c);
} else {
LinkedList.add(c, node.next);
}
}
/**
* Returns the element at the specified position in the list.
*
* @param index
* Index of the element to return
* @return the element at the specified position
* @throws IndexOutOfBoundsException
* if the index is out of the range
* {@code (index < 0 || index >= list size)}
*/
public char get(int index) {
if (index < 0 || index >= this.size) {
throw new IndexOutOfBoundsException("Index: " + index + ", Size: "
+ this.size);
}
return LinkedList.get(index, this.head);
}
/**
* Returns the item at the specified position in the list.
*
* @param index
* index of the element to return
* @param node
* The node at the head of the current sublist
* @return the element at the specified position
*/
private static char get(int index, Node node) {
if (index == 0) {
return node.data;
}
return LinkedList.get(index - 1, node.next);
}
/**
* Sets the element at the specified position in the list.
*
* @param index
* index of the element to set
* @param c
* new value of element
* @throws IndexOutOfBoundsException
* if the index is out of the range
* {@code (index < 0 || index >= list size)}
*/
public void set(int index, char c) {
if (index < 0 || index >= this.size) {
throw new IndexOutOfBoundsException("Index: " + index + ", Size: "
+ this.size);
}
LinkedList.set(index, c, this.head);
}
/**
* Sets the element at the specified position in the list.
*
* @param index
* index of the element to set
* @param c
* new value of element
* @param node
* The node at the head of the current sublist
*/
private static void set(int index, char c, Node node) {
if (index == 0) {
node.data = c;
return;
}
LinkedList.set(index - 1, c, node.next);
}
public String toString() {
if (this.size == 0) {
return "[]";
}
return "[" + LinkedList.toString(this.head);
}
private static String toString(Node n) {
if (n.next == null) {
return n.data + "]";
}
String s = n.data + ", ";
return s + LinkedList.toString(n.next);
}
/**
* Returns true
if this list contains the specified element.
*
* @param c
* element to search for
* @return true
if this list contains the specified element
*/
public boolean contains(char c) {
if (this.size == 0) {
return false;
}
return LinkedList.contains(c, this.head);
}
/**
* Returns true
if this list contains the specified element.
*
* @param c
* element to search for
* @param node
* the node at the head of the current sublist
* @return true
if this list contains the specified element
*/
private static boolean contains(char c, Node node) {
if (node.data == c) {
return true;
}
if (node.next == null) {
return false;
}
return LinkedList.contains(c, node.next);
}
/**
* Returns the index of the first occurrence of the specified element in this
* list, or -1 if this list does not contain the element.
*
* @param c
* element to search for
* @return the index of the first occurrence of the specified element in this
* list, or -1 if this list does not contain the element
*/
public int indexOf(char c) {
if (this.size == 0) {
return -1;
}
return LinkedList.indexOf(c, this.head);
}
/**
* Returns the index of the first occurrence of the specified element in this
* list, or -1 if this list does not contain the element.
*
* @param c
* element to search for
* @param node
* the node at the head of the current sublist
* @return the index of the first occurrence of the specified element in this
* list, or -1 if this list does not contain the element
*/
private static int indexOf(char c, Node n) {
if (n.data == c) {
return 0;
}
if (n.next == null) {
return -1;
}
int i = LinkedList.indexOf(c, n.next);
if (i == -1) {
return -1;
}
return 1 + i;
}
public static void main(String[] args) {
LinkedList t = new LinkedList();
System.out.println(t.indexOf('a'));
System.out.println(t.contains('a'));
System.out.println(t);
t.add('a');
t.add('x');
t.add('r');
t.add('a');
t.add('s');
System.out.println(t);
for (int i = 0; i < 5; i++) {
t.set(i, (char) ('a' + i));
}
System.out.println(t);
System.out.println(t.indexOf('z'));
System.out.println(t.indexOf('a'));
System.out.println(t.contains('a'));
System.out.println(t.indexOf('c'));
System.out.println(t.contains('c'));
System.out.println(t.indexOf('e'));
System.out.println(t.contains('e'));
}
}