package cse1030; import java.util.ArrayList; import java.util.Iterator; import java.util.List; import java.util.NoSuchElementException; public class LinkedList implements Iterable { private static class Node { private char data; private Node next; public Node(char c) { this.data = c; this.next = null; } } private class LinkedListIterator implements Iterator { private Node currNode; private Node prevNode; public LinkedListIterator() { this.currNode = null; this.prevNode = null; } @Override public boolean hasNext() { if (this.currNode == null) { return head != null; } return this.currNode.next != null; } @Override public Character next() { if (!this.hasNext()) { throw new NoSuchElementException(); } this.prevNode = this.currNode; if (this.currNode == null) { this.currNode = head; } else { this.currNode = this.currNode.next; } return this.currNode.data; } @Override public void remove() { if (this.prevNode == this.currNode) { throw new IllegalStateException(); } if (this.currNode == head) { head = this.currNode.next; } else { this.prevNode.next = this.currNode.next; } this.currNode = this.prevNode; size--; } } 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; } /** * Inserts the specified element at the beginning of this list. * * @param c * the character to add to the beginning of this list. */ public void addFirst(char c) { Node newNode = new Node(c); newNode.next = this.head; this.head = newNode; this.size++; } /** * Insert an element at the specified index in the list. * * @param index * the index to insert at * @param c * the character to insert */ public void add(int index, char c) { if (index < 0 || index > this.size) { throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + this.size); } if (index == 0) { this.addFirst(c); } else { LinkedList.add(index - 1, c, this.head); this.size++; } } /** * Insert an element at the specified index after the specified node. * * @param index * the index after prev to insert at * @param c * the character to insert * @param prev * the node to insert after */ private static void add(int index, char c, Node prev) { if (index == 0) { Node newNode = new Node(c); newNode.next = prev.next; prev.next = newNode; return; } LinkedList.add(index - 1, c, prev.next); } /** * Removes and returns the first element from this list. * * @return the first element from this list */ public char removeFirst() { if (this.size == 0) { throw new NoSuchElementException(); } Node curr = this.head; this.head = curr.next; curr.next = null; this.size--; return curr.data; } /** * Removes the element at the specified position in this list. Returns the * element that was removed from the list. * * @param index * the index of the element to be removed * @return the element previously at the specified position */ public char remove(int index) { if (index < 0 || index >= this.size) { throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + this.size); } if (index == 0) { return this.removeFirst(); } else { char result = LinkedList.remove(index - 1, this.head, this.head.next); this.size--; return result; } } /** * Removes the element at the specified position relative to the current node. * * @param index * the index relative to the current node of the element to be * removed * @param prev * the node previous to the current node * @param curr * the current node * @return the element previously at the specified position */ private static char remove(int index, Node prev, Node curr) { if (index == 0) { prev.next = curr.next; curr.next = null; return curr.data; } return LinkedList.remove(index - 1, curr, curr.next); } @Override public Iterator iterator() { return new LinkedListIterator(); } public static void main(String[] args) { LinkedList t = new LinkedList(); System.out.println(t); t.add('a'); t.add('x'); t.add('r'); t.add('a'); t.add('s'); for (Character c : t) { System.out.println(c); } Iterator i = t.iterator(); while (i.hasNext()) { System.out.print("removing " + i.next() + ": "); i.remove(); System.out.println(t); } char[] values = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i'}; for (Character c : values) { t.add(c); } System.out.println(t); i = t.iterator(); while (i.hasNext()) { char c = i.next(); if (String.valueOf(c).matches("[aeiou]")) { System.out.println("removing " + c); i.remove(); } } System.out.println(t); } }