SHARE
TWEET

Untitled

a guest Jan 24th, 2020 69 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
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