SHARE
TWEET

Untitled

a guest Oct 12th, 2017 38 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. public class DoublyLinkedList<E> implements Iterable<E>, Cloneable {
  2.  
  3. // instance variables of the DoublyLinkedList
  4.     private final Node<E> header;     // header sentinel
  5.     private final Node<E> trailer;    // trailer sentinel
  6.     private int size = 0;       // number of elements in the list
  7.     private int modCount = 0;   // number of modifications to the list (adds or removes)
  8.  
  9.     /**
  10.      * Creates both elements which act as sentinels
  11.      */
  12.     public DoublyLinkedList() {
  13.  
  14.         header = new Node<>(null, null, null);      // create header
  15.         trailer = new Node<>(null, header, null);   // trailer is preceded by header
  16.         header.setNext(trailer);                    // header is followed by trailer
  17.     }
  18.  
  19.     /**
  20.      * Returns the number of elements in the linked list
  21.      *
  22.      * @return the number of elements in the linked list
  23.      */
  24.     public int size() {
  25.         return size;
  26.     }
  27.  
  28.     /**
  29.      * Checks if the list is empty
  30.      *
  31.      * @return true if the list is empty, and false otherwise
  32.      */
  33.     public boolean isEmpty() {
  34.         return size == 0;
  35.     }
  36.  
  37.     /**
  38.      * Returns (but does not remove) the first element in the list
  39.      *
  40.      * @return the first element of the list
  41.      */
  42.     public E first() {
  43.         return header.getNext().getElement();
  44.     }
  45.  
  46.     /**
  47.      * Returns (but does not remove) the last element in the list
  48.      *
  49.      * @return the last element of the list
  50.      */
  51.     public E last() {
  52.         return trailer.getPrev().getElement();
  53.     }
  54.  
  55. // public update methods
  56.     /**
  57.      * Adds an element e to the front of the list
  58.      *
  59.      * @param e element to be added to the front of the list
  60.      */
  61.     public void addFirst(E e) {
  62.         addBetween(e, header, header.getNext());
  63.     }
  64.  
  65.     /**
  66.      * Adds an element e to the end of the list
  67.      *
  68.      * @param e element to be added to the end of the list
  69.      */
  70.     public void addLast(E e) {
  71.         addBetween(e, trailer.getPrev(), trailer);
  72.     }
  73.  
  74.     /**
  75.      * Removes and returns the first element of the list
  76.      *
  77.      * @return the first element of the list
  78.      */
  79.     public E removeFirst() {
  80.         if (header.getNext() == trailer) {
  81.             return null;
  82.         }
  83.         return remove(header.getNext());
  84.     }
  85.  
  86.     /**
  87.      * Removes and returns the last element of the list
  88.      *
  89.      * @return the last element of the list
  90.      */
  91.     public E removeLast() {
  92.         if (trailer.getPrev() == header) {
  93.             return null;
  94.         }
  95.         return remove(trailer.getPrev());
  96.     }
  97.  
  98. // private update methods
  99.     /**
  100.      * Adds an element e to the linked list between the two given nodes.
  101.      */
  102.     private void addBetween(E e, Node<E> predecessor, Node<E> successor) {
  103.         Node<E> nova = new Node<>(e, predecessor, successor);
  104.         predecessor.setNext(nova);
  105.         successor.setPrev(nova);
  106.         size++;
  107.         modCount++;
  108.     }
  109.  
  110.     /**
  111.      * Removes a given node from the list and returns its content.
  112.      */
  113.     private E remove(Node<E> node) {
  114.         Node<E> previous = node.getPrev();
  115.         Node<E> successor = node.getNext();
  116.         previous.setNext(successor);
  117.         successor.setPrev(previous);
  118.         size--;
  119.         modCount++;
  120.         return node.getElement();
  121.     }
  122.  
  123. // Overriden methods        
  124.     @Override
  125.     public boolean equals(Object obj) {
  126.         if (getClass() != obj.getClass()) {
  127.             return false;
  128.         }
  129.         DoublyLinkedList dllist = (DoublyLinkedList) obj;
  130.  
  131.         if (this.size() != dllist.size()) {
  132.             return false;
  133.         }
  134.  
  135.         DoublyLinkedListIterator t = (DoublyLinkedListIterator) listIterator();
  136.         DoublyLinkedListIterator n = (DoublyLinkedListIterator) dllist.listIterator();
  137.  
  138.         while (t.hasNext() && n.hasNext()) {
  139.             if (!t.next().equals(n.next())) {
  140.                 return false;
  141.             }
  142.         }
  143.  
  144.         return true;
  145.     }
  146.  
  147.     @Override
  148.     public Object clone() throws CloneNotSupportedException {
  149.         DoublyLinkedList clone = new DoublyLinkedList();
  150.  
  151.         DoublyLinkedListIterator it1 = (DoublyLinkedListIterator) this.listIterator();
  152.         DoublyLinkedListIterator it2 = (DoublyLinkedListIterator) clone.listIterator();
  153.  
  154.         while (it1.hasNext()) {
  155.             it2.add(it1.next());
  156.         }
  157.  
  158.         return clone;
  159.     }
  160.  
  161. //---------------- nested DoublyLinkedListIterator class ----------------        
  162.     private class DoublyLinkedListIterator implements ListIterator<E> {
  163.  
  164.         private DoublyLinkedList.Node<E> nextNode, prevNode, lastReturnedNode; // node that will be returned using next and prev respectively
  165.         private int nextIndex;  // Index of the next element
  166.         private int expectedModCount;  // Expected number of modifications = modCount;
  167.  
  168.         public DoublyLinkedListIterator() {
  169.             this.prevNode = header;
  170.             this.nextNode = header.getNext();
  171.             lastReturnedNode = null;
  172.             nextIndex = 0;
  173.             expectedModCount = modCount;
  174.         }
  175.  
  176.         final void checkForComodification() {  // invalidate iterator on list modification outside the iterator
  177.             if (modCount != expectedModCount) {
  178.                 throw new ConcurrentModificationException();
  179.             }
  180.         }
  181.  
  182.         @Override
  183.         public boolean hasNext() {
  184.             checkForComodification();
  185.             return nextNode != trailer;
  186.         }
  187.  
  188.         @Override
  189.         public E next() throws NoSuchElementException {
  190.             checkForComodification();
  191.  
  192.             if (hasNext()) {
  193.                 this.prevNode = prevNode.getNext();
  194.                 this.nextNode = nextNode.getNext();
  195.                 nextIndex++;
  196.  
  197.                 lastReturnedNode = prevNode;
  198.                 return prevNode.getElement();
  199.             }
  200.             throw new NoSuchElementException("End of list reached.");
  201.         }
  202.  
  203.         @Override
  204.         public boolean hasPrevious() {
  205.             checkForComodification();
  206.             return prevNode != header;
  207.         }
  208.  
  209.         @Override
  210.         public E previous() throws NoSuchElementException {
  211.             checkForComodification();
  212.  
  213.             if (hasPrevious()) {
  214.                 this.prevNode = prevNode.getPrev();
  215.                 this.nextNode = nextNode.getPrev();
  216.                 nextIndex--;
  217.  
  218.                 lastReturnedNode = nextNode;
  219.                 return nextNode.getElement();
  220.             }
  221.             throw new NoSuchElementException("End of list reached.");
  222.         }
  223.  
  224.         @Override
  225.         public int nextIndex() {
  226.             checkForComodification();
  227.             return nextIndex;
  228.         }
  229.  
  230.         @Override
  231.         public int previousIndex() {
  232.             checkForComodification();
  233.             return nextIndex - 1;
  234.         }
  235.  
  236.         @Override
  237.         public void remove() throws NoSuchElementException {
  238.             checkForComodification();
  239.             if (lastReturnedNode != null) {
  240.                 expectedModCount++;
  241.                 DoublyLinkedList.this.remove(lastReturnedNode);
  242.                 lastReturnedNode = null;
  243.                 return;
  244.             }
  245.             throw new NoSuchElementException();
  246.         }
  247.  
  248.         @Override
  249.         public void set(E e) throws NoSuchElementException {
  250.             checkForComodification();
  251.             if (lastReturnedNode == null) {
  252.                 throw new NoSuchElementException();
  253.             }
  254.  
  255.             lastReturnedNode.setElement(e);
  256.         }
  257.  
  258.         @Override
  259.         public void add(E e) {
  260.             checkForComodification();
  261.  
  262.             DoublyLinkedList.this.addBetween(e, prevNode, nextNode);
  263.             nextNode = prevNode.getNext();
  264.             expectedModCount++;
  265.             next();
  266.         }
  267.  
  268.     }    //----------- end of inner DoublyLinkedListIterator class ----------
  269.  
  270. //---------------- Iterable implementation ----------------
  271.     @Override
  272.     public Iterator<E> iterator() {
  273.         return new DoublyLinkedListIterator();
  274.     }
  275.  
  276.     public ListIterator<E> listIterator() {
  277.         return new DoublyLinkedListIterator();
  278.     }
  279.  
  280. //---------------- nested Node class ----------------
  281.     private static class Node<E> {
  282.  
  283.         private E element;      // reference to the element stored at this node
  284.         private Node<E> prev;   // reference to the previous node in the list
  285.         private Node<E> next;   // reference to the subsequent node in the list
  286.  
  287.         public Node(E element, Node<E> prev, Node<E> next) {
  288.             this.element = element;
  289.             this.prev = prev;
  290.             this.next = next;
  291.         }
  292.  
  293.         public E getElement() {
  294.             return element;
  295.         }
  296.  
  297.         public Node<E> getPrev() {
  298.             return prev;
  299.         }
  300.  
  301.         public Node<E> getNext() {
  302.             return next;
  303.         }
  304.  
  305.         public void setElement(E element) { // Not on the original interface. Added due to list iterator implementation
  306.             this.element = element;
  307.         }
  308.  
  309.         public void setPrev(Node<E> prev) {
  310.             this.prev = prev;
  311.         }
  312.  
  313.         public void setNext(Node<E> next) {
  314.             this.next = next;
  315.         }
  316.     }
RAW Paste Data
Top