Java

Modify the class as appropriate so that add(E e) method operates in constant time

Add an add(E e, int i) method to the DoublyLinkedList class. What is the run time of this method? Throw an exception if i is an invalid index. (i must be >= 0 and < size. After this operation, the parameter e will be stored in a node at the given index i).

Add a remove (E e, int i) method to the DoublyLinkedList class What is the run time of this method? Throw an exception if i is an invalid index.

Add a get(int i) to the DoublyLinkedList class to retrieve the i^th element in the list. Throw an exception if i is an invalid index.

Add a addSecond(E e) method - If list is empty, throw exception.

1. Modify Tester1 class that demonstrates that all methods shown above operate correctly.
2. Write a Tester2 class that demonstrates that add(E e) operates in constant time. Also demonstrate that add(E e, int i) runs in linear time.

public 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 }

public int size() { return size; }

public boolean isEmpty() { return size == 0; }

public E first() { if (isEmpty()) return null; return header.getNext().getElement(); // first element is beyond header }

public E last() { if (isEmpty()) return null; return trailer.getPrev().getElement(); // last element is before trailer }

public void addFirst(E e) { addBetween(e, header, header.getNext()); // place just after the header }

public void addLast(E e) { addBetween(e, trailer.getPrev(), trailer); // place just before the trailer }

public E removeFirst() { if (isEmpty()) return null; // nothing to remove return remove(header.getNext()); // first element is beyond header }

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(); } } //----------- end of DoublyLinkedList class -----------

TESTER CLASS

import java.util.Iterator; public class Tester1 { public static void main(String[] args) { DoublyLinkedList dll = new DoublyLinkedList<>(); dll.addFirst("a"); dll.addLast("b"); dll.addLast("c"); for(String s : dll) { System.out.println(s); } } }