Java DOUBLYLINKEDLIST

Add a nested ReverseIterator class (dont add a remove method here, only use hasNext() and next() methods).

Add a reverseIterator() accessor method to the DoublyLinkedList class to return an instance of a ReverseIterator.

Add a remove method to the ForwardIterator class.

Create a Tester2 class and show that add(E e) operates in constant time. Also show that add(E e, int i) runs in linear time.

Code:

import java.util.Iterator; class DoublyLinkedList { private static class Node { private E element; private Node prev; private Node next; public Node(E e, Node p, Node n) { element = e; prev = p; next = n; } public E getElement() { return element; } public Node getPrev() { return prev; } public Node getNext() { return next; } public void setPrev(Node p) { prev = p; } public void setNext(Node n) { next = n; } } // ----------- end of nested Node class ----------- private Node header; private Node trailer; // trailer sentinel private int size = 0; // number of elements in the list public DoublyLinkedList() { header = new Node<>(null, null, null); // create header trailer = new Node<>(null, header, null); // trailer is preceded by header header.setNext(trailer); // header is followed by trailer } // Complexity O(1) public int size() { return size; } // Complexity O(1) public boolean isEmpty() { return size == 0; } // Complexity O(1) public E first() { if (isEmpty()) return null; return header.getNext().getElement(); // first element is beyond header } // Complexity O(1) public E last() { if (isEmpty()) return null; return trailer.getPrev().getElement(); // last element is before trailer } // Complexity O(1) public void addFirst(E e) { addBetween(e, header, header.getNext()); // place just after the header } // Complexity O(1) public void addLast(E e) { addBetween(e, trailer.getPrev(), trailer); // place just before the trailer } // Complexity O(1) public void add(E e) { addLast(e); } // Complexity O(N) public void add(E e, int i) { if(i < 0 || i >= size) { throw new IllegalArgumentException(); } Node start = header; while(i > 0) { start = start.getNext(); i--; } addBetween(e, start, start.getNext()); } // Complexity O(1) public E removeFirst() { if (isEmpty()) return null; // nothing to remove return remove(header.getNext()); // first element is beyond header } // Complexity O(N) public void remove(int i) { if(i < 0 || i >= size) { throw new IllegalArgumentException(); } Node start = header.getNext(); while(i > 0) { start = start.getNext(); i--; } remove(start); } // Complexity O(N) public E get(int i) { if(i < 0 || i >= size) { throw new IllegalArgumentException(); } Node start = header.getNext(); while(i > 0) { start = start.getNext(); i--; } return start.getElement(); } // Complexity O(1) public void addSecond(E e) { if(isEmpty()) { throw new IllegalArgumentException("List is Empty"); } Node start = header.getNext(); addBetween(e, start, start.getNext()); } // Complexity O(1) public E removeLast() { if (isEmpty()) return null; // nothing to remove return remove(trailer.getPrev()); // last element is before trailer } private void addBetween(E e, Node predecessor, Node successor) { // create and link a new node Node newest = new Node<>(e, predecessor, successor); predecessor.setNext(newest); successor.setPrev(newest); size++; } private E remove(Node node) { Node predecessor = node.getPrev(); Node successor = node.getNext(); predecessor.setNext(successor); successor.setPrev(predecessor); size--; return node.getElement(); } public String toString() { StringBuilder sb = new StringBuilder("("); Node walk = header.getNext(); while (walk != trailer) { sb.append(walk.getElement()); walk = walk.getNext(); if (walk != trailer) sb.append(", "); } sb.append(")"); return sb.toString(); } } public class Tester1 { public static void main(String[] args) { DoublyLinkedList dll = new DoublyLinkedList<>(); dll.addFirst("a"); dll.addLast("c"); dll.addLast("e"); System.out.println(dll); dll.addSecond("b"); System.out.println(dll); dll.add("d", 3); System.out.println(dll); System.out.println(dll.get(2)); dll.remove(2); System.out.println(dll); } }