Implementing Dynamic Circular Doubly Linked List with a dummy header node In ord
ID: 3815895 • Letter: I
Question
Implementing Dynamic Circular Doubly Linked List with a dummy header node In order to make traversing, inserting and removing modes from a linked list more efficient the list is often created with each node containing links to both its predecessor and its successor, this is called a doubly linked list. This list is often made circular so that from any point within the list you can travel completely around the list. To avoid the special case of inserting and removing from the empty list a circular doubly linked list usually uses a dummy header node. This node is created when the list is created and is NOT part of the list. An empty list is one which only contains the dummy header node. Your assignment is to implement the accompanying specification for a circular doubly linked list with a dummy header node. This list should be an ordered list. The implementation you are to create must match the supplied specification (it can not be changed)Explanation / Answer
import java.util.ArrayList;
import java.util.Random;
public class DoublyLinkedListTester {
public static void main(String[] args) throws ListEmptyException {
Random random = new Random();
ArrayList<Integer> randomNumbers = new ArrayList<Integer>();
final int NR_ELEMENTS = 10;
DoublyLinkedList<Integer> list = new DoublyLinkedList<Integer>();
if (list.isEmpty()) {
System.out.println("isEmpty works correct");
} else {
System.out.println("isEmpty should return true");
}
if (list.size() == 0) {
System.out.println("Size works correct");
} else {
System.out.println("Size should return 0");
}
// Testing insert
for (int i = 0; i < NR_ELEMENTS; i++) {
int temp = random.nextInt(100);
list.insert(temp);
// make a copy of the random numbers to use later when removing elements
randomNumbers.add(temp);
}
// For this to work you need to have a toString method
System.out.println("The list should be printed in sorted order");
System.out.println(list);
// Test the forward iterator
// Should print the whole list just like the toString method above
// If you get an error here the problem might be in the insert method
list.begin();
while (!list.end()) {
try {
System.out.print(list.current() + " ");
} catch (ListEmptyException e) {
System.out.println("This should not happen here");
}
list.advance();
}
System.out.println();
// Test the backward iterator
// Should print the whole list just in reverse order
// If you get an error here the problem might be in the insert method.
// For example incorrectly updating the prev pointer or forgetting to update it,
// First retreat one step back from the end
list.retreat();
do {
try {
System.out.print(list.current() + " ");
} catch (ListEmptyException e) {
System.out.println("This should not happen here");
}
list.retreat();
} while (!list.end());
System.out.println();
// Test the remove method by removing three values that are in the list.
for (int i = 0; i < 3; i++) {
try {
list.remove(randomNumbers.remove(random.nextInt(randomNumbers.size())));
} catch (ListEmptyException e) {
System.out.println("This should not happen");
} catch (NotInListException e) {
System.out.println("This should not happen");
}
}
if (list.size() != 7) {
System.out.println("The list has " + list.size() + " elements now and should have 7");
System.out.println("Check that you are decrement size in the remove method");
}
// Print the list
System.out.println(list);
}
}
public class DoublyLinkedList<T extends Comparable> {
private class Node
{
private T data;
private Node next;
private Node prev;
private Node(T d){
this.data=d;
this.next=this.prev=null;
}
private Node(T d, Node pref, Node nref)
{
this.data=d;
this.prev=pref;
this.next=nref;
}
}
private Node head;
private Node current;
private int size;
public DoublyLinkedList()
{
head=new Node(null);
head.next=head;
head.prev=head;
current=head;
size=0;
}
public DoublyLinkedList(DoublyLinkedList<T> l)
{
head=new Node(null);
head.next=head.prev=null;
l.begin();
for(int i=0;i<l.size();i++)
{
this.insert(l.current());
l.advance();
}
current=head.next;
size=0;
}
public void insert(T d)
{
this.begin();
while(current!=head && current.data.compareTo(d)<0)
current=current.next;
Node temp=new Node(d,current,current.prev);
current.prev.next=temp;
current.prev=temp;
}
public void remove(T d) throws ListEmptyException , NotInListException
{
if(size==0)
throw new ListEmptyException("List is emply");
this.begin();
while(current!=head && !current.data.equals(d))
this.advance();
if(current==head)
throw new NotInListException("not in this list");
current.prev.next=current.next;
current.next.prev=current.prev;
current.next=current.prev=null;
}
public void begin()
{
current=head.next;
}
public void advance()
{
current=current.next;
}
public void retreat()
{
current=current.prev;
}
public T current() {
return current.data;
}
public boolean end()
{
if(current.next==head)
return true;
else
return false;
}
public int size()
{
return size;
}
public boolean isEmpty()
{
return (size==0);
}
public String toString()
{
return " ";
}
}
public class NotInListException extends Exception{
public NotInListException( String message)
{
super(message);
}
}
public class ListEmptyException extends Exception{
public ListEmptyException( String message)
{
super(message);
}
}