DLL LIST CLASS package ods; import java.util.AbstractSequentialList; import java
ID: 3821818 • Letter: D
Question
DLL LIST CLASS
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 <T>
* the type of elements stored in the list
*/
public class DLList<T> extends AbstractSequentialList<T> {
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<T> 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<T> {
/**
* The list we are iterating over
*/
DLList<T> 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<T> 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);
}
}
}
SLL LIST CLASS
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 <T> the class of objects stored in the queue
*/
public class SLList<T> extends AbstractQueue<T> {
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<T> iterator() {
class SLIterator implements Iterator<T> {
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<Integer> q = new SLList<Integer>();
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);
}
}
Explanation / Answer
package ods;
import java.util.AbstractSequentialList;
import java.util.ListIterator;
public class DLList<T> extends AbstractSequentialList<T> {
class Node {
T x;
Node prev, next;
}
int n;
protected Node dummy;
public DLList() {
dummy = new Node();
dummy.next = dummy;
dummy.prev = dummy;
n = 0;
}
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;
}
protected void remove(Node w) {
w.prev.next = w.next;
w.next.prev = w.prev;
n--;
}
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<T> 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<T> {
DLList<T> l;
Node p;
int i;
Iterator(DLList<T> 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);
}
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.