1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 |
import java.util.Iterator; public class LinkedListIterable<E> implements Iterable<E> { @SuppressWarnings("ClassCanBeStatic") private class Node<T> { T data; Node<T> next; public Node(T data){ this.data = data; } public Node(T data, Node<T> next){ this.data = data; this.next = next; } } @SuppressWarnings("ClassCanBeStatic") public class LLIterator<U> implements Iterator<U> { private LinkedListIterable<U> ll; private LinkedListIterable<U>.Node<U> curr; public LLIterator(LinkedListIterable<U> ll){ this.ll = ll; curr = null; } @Override public boolean hasNext(){ if (curr == ll.tail && ll.tail != null) return false; return true; } @Override public U next(){ if (curr == null) curr = ll.head; else curr = curr.next; return curr.data; } } private Node<E> head, tail; private int count = 0; public int size(){ return count; } @Override public Iterator<E> iterator(){ return new LLIterator<E>(this); } // If the LL is empty, create a new node, // that new node is head and tail. // If LL is not empty, prepend as before. public void prepend(E d){ if (head == null) tail = head = new Node<>(d); else head = new Node<>(d, head); count++; } public void append(E d){ if (head == null) tail = head = new Node<>(d); else tail = tail.next = new Node<>(d); count++; } public boolean contains(E d){ Node<E> curr = head; while (curr != null && curr.data != d) curr = curr.next; return curr != null; } public E get(int idx){ if (idx >= count || idx < 0) throw new IndexOutOfBoundsException(); Node<E> curr = head; for (int i = 0; i < idx; i++){ curr = curr.next; } return curr.data; } // Insert d into the linked list at index idx // Find the node *before* where the new node is // to be inserted. Create the new node and update // references as necessary. public void insert(int idx, E d){ if (idx > count || idx < 0) throw new IndexOutOfBoundsException(); if (idx == 0) prepend(d); else { Node<E> curr = head; for (int i = 0; i < idx-1; i++){ curr = curr.next; } Node<E> newNode = new Node<E>(d, curr.next); curr.next = newNode; } count++; } @Override public String toString(){ String retVal = "Linked list of size: " + count + '\n'; for (Node<E> temp = head; temp != null; temp = temp.next) retVal += temp.data + " "; /*Node curr = head; while(curr != null){ retVal += curr.data + " "; curr = curr.next; }*/ return retVal; } // Testing our LL: public static void main(String[] args){ LinkedListIterable<Integer> ll = new LinkedListIterable<Integer>(); ll.prepend(10); ll.prepend(45); ll.prepend(23); System.out.println("Contains 45? " + ll.contains(45)); System.out.println("Contains 37? " + ll.contains(37)); System.out.println(ll); ll.append(19); System.out.println(ll); System.out.println("First element: " + ll.get(0)); System.out.println("Last element: " + ll.get(3)); // System.out.println("Last element: " + ll.get(4)); ll.insert(4, 15); System.out.println(ll); for (Integer i : ll) System.out.println(i); } } |