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')); } }