SHARE
TWEET

Untitled

a guest Jan 21st, 2019 69 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
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top