Give the definition of a generic class that uses a doubly linked list of data items. Include a copy constructor, an equals method, a clone method, a toString method, a method to produce an iterator, and any other methods that would normally be expected. Write a suitable test program.
Program:
// DoublyLinkedList.java
public class DoublyLinkedList<T> implements Cloneable
{
private class DoublyNode<T>
{
private T item;
private DoublyNode<T> previous;
private DoublyNode<T> next;
public DoublyNode()
{
item = null;
previous = null;
next = null;
}
public DoublyNode(T newItem, DoublyNode<T> newPrevious, DoublyNode<T> newNext)
{
item = newItem;
previous = newPrevious;
next = newNext;
}
}
private DoublyNode<T> head;
public DoublyLinkedList()
{
head = null;
}
public DoublyLinkedList(DoublyLinkedList<T> newList)
{
DoublyLinkedList<T> copy = new DoublyLinkedList<T>();
if(newList.head == null)
{
this.head = null;
}
else
{
copy.head = new DoublyNode<T>(newList.head.item, null, newList.head.next);
DoublyNode<T> currNode = copy.head.next;
DoublyNode<T> prevNode = copy.head;
while(currNode != null)
{
DoublyNode<T> newNode =
new DoublyNode<T>(currNode.item, prevNode, currNode.next);
prevNode.next = newNode;
prevNode = newNode;
currNode = currNode.next;
}
this.head = copy.head;
}
}
public void addFirst(T newItem)
{
DoublyNode<T> newNode = new DoublyNode<T>(newItem, null, head);
if(head != null)
{
head.previous = newNode;
}
head = newNode;
}
public void addLast(T newItem)
{
if(head == null)
{
head = new DoublyNode<T>(newItem, null, null);
}
else
{
DoublyNode<T> current = head;
while(current.next != null)
{
current = current.next;
}
current.next = new DoublyNode<T>(newItem, current, null);
}
}
public T removeFirst()
{
if(head == null)
return null;
T firstItem = head.item;
head = head.next;
if(head != null)
head.previous = null;
return firstItem;
}
public T removeLast()
{
if(head == null)
return null;
DoublyNode<T> current = head;
DoublyNode<T> prev = null;
while(current != null && current.next != null)
{
prev = current;
current = current.next;
}
T lastItem = null;
if(prev == null)
{
lastItem = head.item;
head = head.next;
if(head != null)
head.previous = null;
}
else
{
lastItem = current.item;
prev.next = null;
}
return lastItem;
}
public T remove(T item)
{
if(item == null || head == null)
return null;
DoublyNode<T> current = head;
DoublyNode<T> prev = null;
while(current != null && !current.item.equals(item))
{
prev = current;
current = current.next;
}
T removedItem = null;
if(prev == null)
{
removedItem = head.item;
head = head.next;
if(head != null)
head.previous = null;
}
else
{
removedItem = current.item;
prev.next = current.next;
if(prev.next != null)
prev.next.previous = prev;
}
return removedItem;
}
public boolean isEmpty()
{
return head == null;
}
public void clear()
{
head = null;
}
public int size()
{
int count = 0;
DoublyNode<T> current = head;
while(current != null)
{
count++;
current = current.next;
}
return count;
}
public void printForward()
{
DoublyNode<T> current = head;
while(current != null)
{
System.out.print(current.item + " ");
current = current.next;
}
}
public void printBackward()
{
DoublyNode<T> current = head;
while(current != null && current.next != null)
{
current = current.next;
}
while(current != null)
{
System.out.print(current.item + " ");
current = current.previous;
}
}
public String toString()
{
String result = "";
DoublyNode<T> current = head;
while(current != null)
{
result = result + current.item + "\n";
current = current.next;
}
return result;
}
public boolean equals(Object obj)
{
if(obj == null)
{
return false;
}
else if(getClass() != obj.getClass())
{
return false;
}
else
{
DoublyLinkedList<T> otherList = (DoublyLinkedList<T>)obj;
if(size() != otherList.size())
{
return false;
}
DoublyNode<T> current = head;
DoublyNode<T> otherCurrent = otherList.head;
while(current != null)
{
if(!(current.item.equals(otherCurrent.item)))
{
return false;
}
current = current.next;
otherCurrent = otherCurrent.next;
}
return true;
}
}
public DoublyLinkedList<T> clone()
{
try
{
DoublyLinkedList<T> copy = (DoublyLinkedList<T>)super.clone();
if(this.head == null)
{
copy.head = null;
}
else
{
copy.head = new DoublyNode<T>(this.head.item, null, this.head.next);
DoublyNode<T> currNode = copy.head.next;
DoublyNode<T> prevNode = copy.head;
while(currNode != null)
{
DoublyNode<T> newNode =
new DoublyNode<T>(currNode.item, prevNode, currNode.next);
prevNode.next = newNode;
prevNode = newNode;
currNode = currNode.next;
}
}
return copy;
}
catch(CloneNotSupportedException e)
{
return null;
}
}
public DoublyLinkedListIterator iterator()
{
return new DoublyLinkedListIterator();
}
public class DoublyLinkedListIterator
{
private DoublyNode<T> current = null;
public DoublyLinkedListIterator()
{
current = head;
}
public void restart()
{
current = head;
}
public T next()
{
if(!hasNext())
{
throw new IllegalStateException();
}
T itemToBeReturn = current.item;
current = current.next;
return itemToBeReturn;
}
public boolean hasNext()
{
return (current != null);
}
public T peek()
{
if(!hasNext())
{
throw new IllegalStateException();
}
return current.item;
}
public void insertHere(T newItem)
{
if(current == null && head != null)
{
DoublyNode<T> tempNode = head;
while(tempNode.next != null)
{
tempNode = tempNode.next;
}
tempNode.next = new DoublyNode<T>(newItem, tempNode, null);
}
else if(head == null || current.previous == null)
{
DoublyLinkedList.this.addFirst(newItem);
}
else
{
DoublyNode<T> tempNode =
new DoublyNode<T>(newItem, current.previous, current);
current.previous.next = tempNode;
current.previous = tempNode;
}
}
public void delete()
{
if(current == null)
{
throw new IllegalStateException();
}
else if(current.previous == null)
{
head = head.next;
current = head;
}
else if(current.next == null)
{
current.previous.next = null;
current = null;
}
else
{
current.previous.next = current.next;
current.next.previous = current.previous;
current = current.next;
}
}
}
}
// DoublyLinkedListDemo.java
public class DoublyLinkedListDemo
{
public static void main(String[] args)
{
DoublyLinkedList<String> list = new DoublyLinkedList<String>();
list.addLast("Chars");
list.addLast("James");
list.addLast("Mary");
list.addFirst("Mike");
list.addFirst("John");
list.addFirst("Steve");
System.out.println("List of elements:");
System.out.println(list);
System.out.println("Element removed from the list (Last element in the list): "
+ list.removeLast());
System.out.println("Element removed from the list (First element in the list): "
+ list.removeFirst());
System.out.println("\nList of elements:");
DoublyLinkedList.DoublyLinkedListIterator itr = list.iterator();
while(itr.hasNext())
{
System.out.println(itr.next());
}
}
}
Output:
List of elements:
Steve
John
Mike
Chars
James
Mary
Element removed from the list (Last element in the list): Mary
Element removed from the list (First element in the list): Steve
List of elements:
John
Mike
Chars
James