Guest User

Untitled

a guest
Jan 24th, 2020
177
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. package edu.ncsu.csc316.dsa.list;
  2.  
  3. import java.util.Iterator;
  4. import java.util.NoSuchElementException;
  5.  
  6. /**
  7. * Class for a singly linked list
  8. * This list can only be traversed in a single direction
  9. * @author Andrew Sonnier
  10. *
  11. * @param <E> Generic Type
  12. */
  13. public class SinglyLinkedList<E> extends AbstractList<E> {
  14.  
  15. private LinkedListNode<E> front;
  16. private LinkedListNode<E> tail;
  17.  
  18. private int size;
  19.  
  20. /**
  21. * Constructs a Linked List with a initial front node and size 0
  22. */
  23. public SinglyLinkedList() {
  24. // Let front be a dummy (sentinel) node
  25. front = new LinkedListNode<E>(null);
  26. tail = null;
  27. size = 0;
  28. }
  29.  
  30.  
  31. @Override
  32. public void add(int index, E value) {
  33. super.checkIndexForAdd(index);
  34. LinkedListNode<E> current = front;
  35. if(size == 0) {
  36. tail = new LinkedListNode<E>(value);
  37. front.setNext(tail);
  38. }
  39. else {
  40. while(index > 0) {
  41. current = current.getNext();
  42. index--;
  43. }
  44. current.setNext(new LinkedListNode<E>(value, current.getNext()));
  45. current = new LinkedListNode<E>(value, current);
  46. }
  47. size++;
  48. }
  49.  
  50. @Override
  51. public E get(int index) {
  52. super.checkIndex(index);
  53. LinkedListNode<E> current = front;
  54. while(index >= 0) {
  55. current = current.getNext();
  56. index--;
  57. }
  58. return current.getElement();
  59. }
  60.  
  61. @Override
  62. public E remove(int index) {
  63. super.checkIndex(index);
  64. LinkedListNode<E> current = front;
  65. while(index > 0) {
  66. current = current.getNext();
  67. index--;
  68. }
  69. E temp = current.getNext().getElement();
  70. current.setNext(current.getNext().getNext());
  71. size--;
  72. return temp;
  73. }
  74.  
  75. @Override
  76. public E set(int index, E value) {
  77. super.checkIndex(index);
  78. LinkedListNode<E> current = front;
  79. while(index >= 0) {
  80. current = current.getNext();
  81. index--;
  82. }
  83. E temp = current.getElement();
  84. current.setElement(value);
  85. return temp;
  86. }
  87.  
  88. @Override
  89. public int size() {
  90. return size;
  91. }
  92.  
  93. @Override
  94. public Iterator<E> iterator() {
  95. // We need to tell the iterator to skip the dummy/sentinel node
  96. return new ElementIterator(front.getNext());
  97. }
  98.  
  99. @Override
  100. public E last() {
  101. if(tail != null)
  102. return tail.getElement();
  103. else
  104. throw new NoSuchElementException();
  105. }
  106.  
  107. @Override
  108. public void addLast(E value) {
  109. if(tail == null) {
  110. tail = new LinkedListNode<E>(value);
  111. front.setNext(tail);
  112. }
  113. else {
  114. tail.setNext(new LinkedListNode<E>(value));
  115. tail = tail.getNext();
  116. }
  117. size++;
  118. }
  119.  
  120. /**
  121. * Linked List Node class for a singly linked list
  122. * A Node is aware of its own value and a
  123. * @author Andrew Sonnier
  124. *
  125. * @param <E> generic type of the node
  126. */
  127. private static class LinkedListNode<E> {
  128.  
  129. private E data;
  130. private LinkedListNode<E> next;
  131.  
  132. public LinkedListNode(E data) {
  133. this.data = data;
  134. this.next = null;
  135. }
  136.  
  137. public LinkedListNode(E data, LinkedListNode<E> node) {
  138. this.data = data;
  139. this.next = node;
  140. }
  141.  
  142. public LinkedListNode<E> getNext() {
  143. return next;
  144. }
  145.  
  146. public E getElement() {
  147. return data;
  148. }
  149.  
  150. public void setNext(LinkedListNode<E> node) {
  151. this.next = node;
  152. }
  153.  
  154. public void setElement(E data) {
  155. this.data = data;
  156. }
  157. }
  158.  
  159. /**
  160. * Class for the element iterator
  161. * This iterator is used to traverse the list
  162. * @author Andrew Sonnier
  163. */
  164. private class ElementIterator implements Iterator<E> {
  165. // Keep track of the next node that will be processed
  166. private LinkedListNode<E> current;
  167. // Keep track of the node that was processed on the last call to 'next'
  168. private LinkedListNode<E> previous;
  169. // Keep track of the previous-previous node that was processed
  170. // so that we can update 'next' links when removing
  171. private LinkedListNode<E> previousPrevious;
  172. private boolean removeOK;
  173.  
  174. public ElementIterator(LinkedListNode<E> start) {
  175. previousPrevious = null;
  176. previous = null;
  177. current = start;
  178. removeOK = false;
  179. }
  180.  
  181. public boolean hasNext() {
  182. return (current != null);
  183. }
  184.  
  185. public E next() {
  186. if(hasNext()) {
  187. previousPrevious = previous;
  188. previous = current;
  189. current = current.getNext();
  190. removeOK = true;
  191. return previous.getElement();
  192. }
  193. else
  194. throw new NoSuchElementException("No Elements Remaining");
  195. }
  196.  
  197. public void remove() {
  198. if(!removeOK)
  199. throw new IllegalStateException("Call next() before removing");
  200. if(previousPrevious != null)
  201. previousPrevious.setNext(current);
  202. else
  203. front.setNext(current);
  204. previous = null;
  205. size--;
  206. removeOK = false;
  207. }
  208. }
  209.  
  210. }
RAW Paste Data