Implement a method that you name swap(x,y) as an additional member of the class SLList and that allows to swap two nodes x and y (and not just their contents) in a SLList instance, given references only to x and y. Repeat this exercise for the case when L is a doubly linked list. Provide your evaluation of these methods running times.

//SLLIST JAVA FILE

package ods;

import java.util.AbstractQueue; import java.util.Iterator; import java.util.Queue;

/** * An implementation of a FIFO Queue as a singly-linked list. * This also includes the stack operations push and pop, which * operate on the head of the queue * @author morin * * @param the class of objects stored in the queue */ public class SLList extends AbstractQueue { class Node { T x; Node next; } /** * Front of the queue */ Node head; /** * Tail of the queue */ Node tail; /** * The number of elements in the queue */ int n; public Iterator iterator() { class SLIterator implements Iterator { protected Node p;

public SLIterator() { p = head; } public boolean hasNext() { return p != null; } public T next() { T x = p.x; p = p.next; return x; } public void remove() { throw new UnsupportedOperationException(); } } return new SLIterator(); }

@Override public int size() { // TODO Auto-generated method stub return n; }

public boolean add(T x) { Node u = new Node(); u.x = x; if (n == 0) { head = u; } else { tail.next = u; } tail = u; n++; return true; } public boolean offer(T x) { return add(x); }

@Override public T peek() { return head.x; }

public T poll() { if (n == 0) return null; T x = head.x; head = head.next; if (--n == 0) tail = null; return x; } /** * Stack push operation - push x onto the head of the list * @param x the element to push onto the stack * @return x */ public T push(T x) { Node u = new Node(); u.x = x; u.next = head; head = u; if (n == 0) tail = u; n++; return x; } protected void deleteNext(Node u) { if (u.next == tail) tail = u; u.next = u.next.next; } protected void addAfter(Node u, Node v) { v = u.next.next; u.next = v; if (u == tail) tail = v; } protected Node getNode(int i) { Node u = head; for (int j = 0; j < i; j++) u = u.next; return u; }

/** * Stack pop operation - pop off the head of the list * @return the element popped off */ public T remove() { if (n == 0) return null; T x = head.x; head = head.next; if (--n == 0) tail = null; return x; } public T pop() { if (n == 0) return null; T x = head.x; head = head.next; if (--n == 0) tail = null; return x; }

public static void main(String[] args) { Queue q = new SLList(); for (int i = 0; i < 100; i++) { q.add(i); } System.out.println(q); for (int i = 0; i < 50; i++) { q.remove(); } System.out.println(q); for (int i = 100; i < 200; i++) { q.add(i); } System.out.println(q); for (int i = 0; i < 50; i++) { q.remove(); } System.out.println(q); while (!q.isEmpty()) { q.remove(); } System.out.println(q);

} }

//DLLIST JAVA FILE

package ods;

import java.util.AbstractSequentialList; import java.util.ListIterator;

/** * An implementation of the List interface as a doubly-linked circular list. A * dummy node is used to simplify the code. * * @author morin * * @param * the type of elements stored in the list */ public class DLList extends AbstractSequentialList { class Node { T x; Node prev, next; } /** * Number of nodes in the list */ int n;

/** * The dummy node. We use the convention that dummy.next = first and * dummy.prev = last */ protected Node dummy;

public DLList() { dummy = new Node(); dummy.next = dummy; dummy.prev = dummy; n = 0; }

/** * Add a new node containing x before the node p * * @param w * the node to insert the new node before * @param x * the value to store in the new node * @return the newly created and inserted node */ protected Node addBefore(Node w, T x) { Node u = new Node(); u.x = x; u.prev = w.prev; u.next = w; u.next.prev = u; u.prev.next = u; n++; return u; }

/** * Remove the node p from the list * * @param w * the node to remove */ protected void remove(Node w) { w.prev.next = w.next; w.next.prev = w.prev; n--; }

/** * Get the i'th node in the list * * @param i * the index of the node to get * @return the node with index i */ protected Node getNode(int i) { Node p = null; if (i < n / 2) { p = dummy.next; for (int j = 0; j < i; j++) p = p.next; } else { p = dummy; for (int j = n; j > i; j--) p = p.prev; } return p; }

public ListIterator listIterator(int i) { if (i < 0 || i > n - 1) throw new IndexOutOfBoundsException(); return new Iterator(this, i); }

public int size() { return n; }

public boolean add(T x) { addBefore(dummy, x); return true; }

public T remove(int i) { if (i < 0 || i > n - 1) throw new IndexOutOfBoundsException(); Node w = getNode(i); remove(w); return w.x; }

public void add(int i, T x) { if (i < 0 || i > n) throw new IndexOutOfBoundsException(); addBefore(getNode(i), x); }

public T get(int i) { if (i < 0 || i > n - 1) throw new IndexOutOfBoundsException(); return getNode(i).x; }

public T set(int i, T x) { if (i < 0 || i > n - 1) throw new IndexOutOfBoundsException(); Node u = getNode(i); T y = u.x; u.x = x; return y; }

public void clear() { dummy.next = dummy; dummy.prev = dummy; n = 0; }

class Iterator implements ListIterator { /** * The list we are iterating over */ DLList l;

/** * The node whose value is returned by next() */ Node p;

/** * The last node whose value was returned by next() or previous() */ Node last;

/** * The index of p */ int i;

Iterator(DLList il, int ii) { l = il; i = ii; p = l.getNode(i); }

public boolean hasNext() { return p != dummy; }

public T next() { T x = p.x; last = p; p = p.next; i++; return x; }

public int nextIndex() { return i; }

public boolean hasPrevious() { return p.prev != dummy; }

public T previous() { p = p.prev; last = p; i--; return p.x; }

public int previousIndex() { return i - 1; }

public void add(T x) { DLList.this.addBefore(p, x); }

public void set(T x) { last.x = x; }

public void remove() { if (p == last) { p = p.next; } DLList.this.remove(last); }

} }