Guest User

Untitled

a guest
Jan 21st, 2019
72
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /**
  2. * Your implementation of a circular singly linked list.
  3. *
  4. * @author Bhanu grg
  5. * @userid bgarg6
  6. * @GTID 903444695
  7. * @version 1.0
  8. */
  9. public class SinglyLinkedList<T> {
  10. // Do not add new instance variables or modify existing ones.
  11. private LinkedListNode<T> head;
  12. private int size;
  13.  
  14. /**
  15. * Adds the element to the index specified.
  16. *
  17. * Adding to indices 0 and {@code size} should be O(1), all other cases are
  18. * O(n).
  19. *
  20. * @param index the requested index for the new element
  21. * @param data the data for the new element
  22. * @throws java.lang.IndexOutOfBoundsException if index is negative or
  23. * index > size
  24. * @throws java.lang.IllegalArgumentException if data is null
  25. */
  26. public void addAtIndex(int index, T data) {
  27. if (index < 0 || index > this.size) {
  28. throw new IndexOutOfBoundsException("the index provided is "
  29. + "outside the bounds of the list");
  30. }
  31.  
  32. if (data == null) {
  33. throw new IllegalArgumentException("the data "
  34. + "provided does not exist, is null");
  35. }
  36.  
  37. if (size == 0) {
  38. LinkedListNode<T> replaceHead = new LinkedListNode<>(data, head);
  39. head = replaceHead;
  40.  
  41. }
  42. if (size > 0) {
  43. LinkedListNode<T> temp = head;
  44. for (int i = 0; i < index; i++) {
  45. if (i > 0) {
  46. temp = temp.getNext();
  47. }
  48.  
  49. }
  50.  
  51. LinkedListNode<T> input = new LinkedListNode<>(data, temp.getNext());
  52. temp.setNext(input);
  53.  
  54. }
  55. this.size++;
  56.  
  57.  
  58.  
  59.  
  60. }
  61.  
  62. /**
  63. * Adds the element to the front of the list.
  64. *
  65. * Must be O(1) for all cases.
  66. *
  67. * @param data the data for the new element
  68. * @throws java.lang.IllegalArgumentException if data is null
  69. */
  70. public void addToFront(T data) {
  71. if (data == null) {
  72. throw new IllegalArgumentException("the data provided"
  73. + "does not exist, is null");
  74. }
  75. if (size == 0) {
  76. LinkedListNode<T> replaceHead = new LinkedListNode<>(data, head);
  77. head = replaceHead;
  78. this.size++;
  79.  
  80. } else {
  81. LinkedListNode<T> input = new LinkedListNode<>(data, head.getNext());
  82. head.setNext(input);
  83. input.setData(head.getData());
  84. head.setData(data);
  85. this.size++;
  86. }
  87.  
  88.  
  89.  
  90. }
  91.  
  92. /**
  93. * Adds the element to the back of the list.
  94. *
  95. * Must be O(1) for all cases.
  96. *
  97. * @param data the data for the new element
  98. * @throws java.lang.IllegalArgumentException if data is null
  99. */
  100. public void addToBack(T data) {
  101. if (data == null) {
  102. throw new IllegalArgumentException("the data provided"
  103. + "does not exist, is null");
  104. }
  105. if (size == 0) {
  106. LinkedListNode<T> replaceHead = new LinkedListNode<>(data, head);
  107. head = replaceHead;
  108. this.size++;
  109.  
  110. } else {
  111. LinkedListNode<T> temp = head;
  112. for (int i = 0; i < size - 1; i++) {
  113. temp = temp.getNext();
  114. }
  115. // while (temp.getNext() != head) {
  116. // temp = temp.getNext();
  117. // }
  118. LinkedListNode<T> input = new LinkedListNode<>(data, head);
  119. temp.setNext(input);
  120. this.size++;
  121. }
  122.  
  123.  
  124.  
  125. //could also try add at index
  126.  
  127. }
  128.  
  129. /**
  130. * Removes and returns the element from the index specified.
  131. *
  132. * Removing from index 0 should be O(1), all other cases are O(n).
  133. *
  134. * @param index the requested index to be removed
  135. * @return the data formerly located at index
  136. * @throws java.lang.IndexOutOfBoundsException if index is negative or
  137. * index >= size
  138. */
  139. public T removeAtIndex(int index) {
  140. if (index < 0 || index >= this.size) {
  141. throw new IndexOutOfBoundsException("the index provided"
  142. + "is outside the bounds of the list");
  143. }
  144. LinkedListNode<T> temp = head;
  145. for (int i = 0; i < index - 1; i++) {
  146. temp = temp.getNext();
  147. }
  148. LinkedListNode<T> retData = temp.getNext();
  149. temp.setNext(temp.getNext().getNext());
  150. this.size--;
  151.  
  152. return retData.getData();
  153. }
  154.  
  155. /**
  156. * Removes and returns the element at the front of the list. If the list is
  157. * empty, return {@code null}.
  158. *
  159. * Must be O(1) for all cases.
  160. *
  161. * @return the data formerly located at the front, null if empty list
  162. */
  163. public T removeFromFront() {
  164. LinkedListNode<T> retData = head;
  165.  
  166. head.setData(head.getNext().getData());
  167. head.setNext(head.getNext().getNext());
  168. this.size--;
  169.  
  170. return retData.getData();
  171.  
  172. }
  173.  
  174. /**
  175. * Removes and returns the element at the back of the list. If the list is
  176. * empty, return {@code null}.
  177. *
  178. * Must be O(n) for all cases.
  179. *
  180. * @return the data formerly located at the back, null if empty list
  181. */
  182. public T removeFromBack() {
  183. LinkedListNode<T> temp = head;
  184. for (int i = 0; i < size - 2; i++) {
  185. temp = temp.getNext();
  186. }
  187. LinkedListNode<T> retData = temp.getNext();
  188.  
  189. temp.setNext(head);
  190. this.size--;
  191. return retData.getData();
  192.  
  193. }
  194.  
  195. /**
  196. * Removes the last copy of the given data from the list.
  197. *
  198. * Must be O(n) for all cases.
  199. *
  200. * @param data the data to be removed from the list
  201. * @return the removed data occurrence from the list itself (not the data
  202. * passed in), null if no occurrence
  203. * @throws java.lang.IllegalArgumentException if data is null
  204. */
  205. public T removeLastOccurrence(T data) {
  206. if (data == null) {
  207. throw new IllegalArgumentException("the data provided"
  208. + "does not exist, is null");
  209. }
  210. LinkedListNode<T> temp = head.getNext();
  211. if (head.getData() == data) {
  212. return removeFromFront();
  213. }
  214. int counter = 1;
  215. while (temp.getData() != data) {
  216. if (temp == head) {
  217. return null;
  218. }
  219. if (temp.getData() == data) {
  220. return removeAtIndex(counter);
  221. }
  222. temp = temp.getNext();
  223. counter++;
  224.  
  225. }
  226. return null;
  227.  
  228. }
  229.  
  230. /**
  231. * Returns the element at the specified index.
  232. *
  233. * Getting index 0 should be O(1), all other cases are O(n).
  234. *
  235. * @param index the index of the requested element
  236. * @return the object stored at index
  237. * @throws java.lang.IndexOutOfBoundsException if index < 0 or
  238. * index >= size
  239. */
  240. public T get(int index) {
  241. if (index < 0 || index >= this.size) {
  242. throw new IndexOutOfBoundsException("the index provided"
  243. + "is outside the bounds of the list");
  244. }
  245. LinkedListNode<T> temp = head;
  246.  
  247. if (index == 0) {
  248. return temp.getData();
  249. }
  250. for (int i = 0; i < index; i++) {
  251. temp.getNext();
  252. }
  253. return temp.getData();
  254.  
  255. }
  256.  
  257. /**
  258. * Returns an array representation of the linked list.
  259. *
  260. * Must be O(n) for all cases.
  261. *
  262. * @return an array of length {@code size} holding all of the objects in
  263. * this list in the same order
  264. */
  265. public Object[] toArray() {
  266. T[] arr = (T[]) new Object[this.size];
  267. LinkedListNode<T> temp = head;
  268. arr[0] = head.getData();
  269. int counter = 0;
  270. while (temp.getNext() != head) {
  271. temp = temp.getNext();
  272. ++counter;
  273. arr[counter] = temp.getData();
  274.  
  275. }
  276.  
  277. return arr;
  278.  
  279. }
  280.  
  281. /**
  282. * Returns a boolean value indicating if the list is empty.
  283. *
  284. * Must be O(1) for all cases.
  285. *
  286. * @return true if empty; false otherwise
  287. */
  288. public boolean isEmpty() {
  289. if (head == null) {
  290. return true;
  291. }
  292. return false;
  293.  
  294. }
  295.  
  296. /**
  297. * Clears the list of all data.
  298. *
  299. * Must be O(1) for all cases.
  300. */
  301. public void clear() {
  302. head = null;
  303. this.size = 0;
  304.  
  305. }
  306.  
  307. /**
  308. * Returns the number of elements in the list.
  309. *
  310. * For grading purposes only. You shouldn't need to use this method since
  311. * you have direct access to the variable.
  312. *
  313. * @return the size of the list
  314. */
  315. public int size() {
  316. // DO NOT MODIFY!
  317. return size;
  318. }
  319.  
  320. /**
  321. * Returns the head node of the linked list.
  322. *
  323. * For grading purposes only. You shouldn't need to use this method since
  324. * you have direct access to the variable.
  325. *
  326. * @return node at the head of the linked list
  327. */
  328. public LinkedListNode<T> getHead() {
  329. // DO NOT MODIFY!
  330. return head;
  331. }
  332. }
RAW Paste Data