====== LAB 8 - Implement a doubly linked list ====== Fill in the unimplemented parts of the following ''DoublyLinkedList'' class. Comment each method using javadoc syntax (see ''insertNode'' method as an example). Generate javadoc from the code. It should look like the [[http://www.cs.bilkent.edu.tr/~bgedik/courses/cs102/2012-fall/DoublyLinkedList.html|following]]. Test your class by running the ''main'' method. **Important note**: You have to turn on assertions by passing an argument of -ea to the JVM. Configure this in your IDE. Otherwise all assertions will be ignored by the JVM. Try to see if every single line of code in the class is exercised by one of the test lines in the main method. <code> package com.fun.tips; import java.util.Iterator; public class DoublyLinkedList<T> implements Cloneable, Iterable<T> { private static class Node<T> { T data; Node<T> next; Node<T> prev; Node(T data) { this.data = data; } } private Node<T> first; private Node<T> last; private int size; public int getSize() { return size; } public boolean isEmpty() { return (first==null); } public T getLastElement() { if (isEmpty()) return null; 
 return last.data; } public T getFirstElement() { if (isEmpty()) return null; return first.data; } public void appendElement(T e) { Node<T> n = new Node<T>(e); if (isEmpty()) { first = last = n; } else { last.next = n; n.prev = last; last = n; } size++; } public void prependElement(T e) { // TODO } public boolean removeFirstElement() { if (isEmpty()) return false; first = first.next; if (first!=null) first.prev = null; else last = null; size--; return true; } public boolean removeLastElement() { // TODO } public T getElementAt(int index) { Node<T> node = getNodeAt(index); if (node==null) return null; return node.data; } private Node<T> getNodeAt(int index) { if (index<0) return null; Node<T> curr = first; for (int i=0; i<index && curr!=null; ++i) curr = curr.next; return curr; } public boolean insertElementAt(T e, int index) { if (index==size) { appendElement(e); } else { Node<T> n = getNodeAt(index); if (n==null) return false; Node<T> c = new Node<T>(e); insertNode(c, n); } return true; } /** * Insert a new node at the position of another node * @param c The new node to be inserted * @param n The node at the insertion position */ private void insertNode(Node<T> c, Node<T> n) { Node<T> nP = n.prev; c.prev = nP; if (nP!=null) nP.next = c; else first = c; c.next = n; n.prev = c; size++; } public boolean removeElementAt(int index) { Node<T> n = getNodeAt(index); if (n==null) return false; removeNode(n); return true; } private void removeNode(Node<T> n) { // TODO } @Override public DoublyLinkedList<T> clone() { DoublyLinkedList<T> other = new DoublyLinkedList<T>(); for (T data : this) other.appendElement(data); return other; } @Override public Iterator<T> iterator() { return new DoublyLinkedListIterator<T>(this); } @Override public String toString() { StringBuilder sb = new StringBuilder(); sb.append("["); Iterator<T> it = iterator(); if (it.hasNext()) { T data = it.next(); sb.append(data); while (it.hasNext()) { sb.append(","); sb.append(it.next()); } } sb.append("]"); return sb.toString(); } private static class DoublyLinkedListIterator<T> implements Iterator<T> { Node<T> curr; DoublyLinkedList<T> list; public DoublyLinkedListIterator(DoublyLinkedList<T> list) { this.list = list; curr = list.first; } @Override public boolean hasNext() { return (curr != null); } @Override public T next() { // TODO } @Override public void remove() { // TODO } } public static void main(String[] args) { DoublyLinkedList<String> list = new DoublyLinkedList<String>(); assert(list.isEmpty()); list.prependElement("a"); assert(list.getSize()==1); assert(!list.isEmpty()); assert(list.getElementAt(0).equals("a")); assert(list.getFirstElement().equals("a")); assert(list.getLastElement().equals("a")); list.removeLastElement(); assert(list.getSize()==0); assert(list.isEmpty()); list.appendElement("b"); assert(list.getSize()==1); assert(!list.isEmpty()); assert(list.getElementAt(0).equals("b")); assert(list.getFirstElement().equals("b")); assert(list.getLastElement().equals("b")); list.removeFirstElement(); assert(list.getSize()==0); assert(list.isEmpty()); list.appendElement("c"); list.prependElement("b"); list.prependElement("a"); list.appendElement("d"); assert(list.getSize()==4); assert(!list.isEmpty()); assert(list.getElementAt(0).equals("a")); assert(list.getElementAt(1).equals("b")); assert(list.getElementAt(2).equals("c")); assert(list.getElementAt(3).equals("d")); DoublyLinkedList<String> other = (DoublyLinkedList<String>) list.clone(); Iterator<String> it = list.iterator(); while (it.hasNext()) { it.next(); it.remove(); } assert(list.isEmpty()); assert(list.getSize()==0); list = other; String all = ""; for (String s : list) all += s; assert(all.equals("abcd")); assert(list.getElementAt(-1)==null); assert(list.getElementAt(4)==null); list.removeLastElement(); assert(list.getSize()==3); assert(!list.isEmpty()); list.removeFirstElement(); assert(list.getSize()==2); assert(!list.isEmpty()); list.removeLastElement(); assert(list.getSize()==1); assert(!list.isEmpty()); list.removeFirstElement(); assert(list.getSize()==0); assert(list.isEmpty()); boolean b = list.insertElementAt("x", -1); assert(b==false); b = list.insertElementAt("x", 1); assert(b==false); b = list.insertElementAt("c", 0); assert(b==true); b = list.insertElementAt("a", 0); assert(b==true); b = list.insertElementAt("d", 2); assert(b==true); b = list.insertElementAt("b", 1); assert(b==true); assert(list.toString().equals("[a,b,c,d]")); b = list.removeElementAt(-1); assert(b==false); b = list.removeElementAt(4); assert(b==false); assert(list.getSize()==4); assert(!list.isEmpty()); b = list.removeElementAt(3); assert(b==true); assert(list.getSize()==3); assert(!list.isEmpty()); b = list.removeElementAt(1); assert(b==true); assert(list.getSize()==2); assert(!list.isEmpty()); b = list.removeElementAt(0); assert(b==true); assert(list.getSize()==1); assert(!list.isEmpty()); b = list.removeElementAt(0); assert(b==true); assert(list.getSize()==0); assert(list.isEmpty()); ssert(b==true); } } </code>