import javax.swing.Icon;
import javax.swing.ImageIcon;
import javax.swing.JOptionPane;
import java.util.*;
import java.io.*;
//Paul Adcock
// Assignment 4
// Lasted Worked On: 10/12/2010
// this class is the Doubly Linked list class. It has a Node that holds a reference to some date of type T and has a reference
// to the next Node and to the previous Node.
public class DoublyLinkedList<T>
{
private class Node<T>
{
private T data;
private Node<T> next;
private Node<T> previous;
public Node(T data,Node<T> next, Node<T> previous)
{
this.data = data;
this.next = next;
this.previous=previous;
}
public T getData()
{
return data;
}
public Node<T> getNext()
{
return next;
}
public Node<T> getPrevious()
{
return previous;
}
public void setNext(Node<T> next)
{
this.next = next;
}
public void setPrevious(Node<T> previous)
{
this.previous = previous;
}
}
private Node<T> head;//head of the linked list
private Node<T> tail; // tail of linked list
private int size;
private ImageIcon icon;
private Icon icon2;
public DoublyLinkedList()
{
head = null;
tail = null;
size = 0;
icon = new ImageIcon("doh3.jpg");
}
// returns a String of all the items in the linked list.
public String toString()
{
String str = "[";
Node<T> curr;
for (curr=head;curr!=null;curr = curr.getNext())
{
str = str + curr.getData();
if (curr.getNext()!=null)
str = str + " ";
}
str = str + "]";
return str;
}
public void removeRange(int from, int to)
{
if (from < 0 || from > = Size() || to < 0 || to >=Size())
{
return;
}
for (int i = from; i <=to; i++)
{
remove(i);
}
}
// adds the data as the first element. If the list size is 0, makes first element tail. If head is not null, it puts the old
// tail as the second element and the new element as the new head.
public void addFirst(T data)
{
/* Since this is the first Object, previous should be null
*/
Node<T> newNode = new Node<T>(data,head,null);
//We know that if head is null, the list is empty
if (head==null)
{
//If the list is empty, tail will be newNode
tail = newNode;
}
if(head!=null)
head.setPrevious(newNode);
//We want to set head to be newNode
// if the list was empty before, both head and tail will be set to newNode;
head = newNode;
//Increment Size
size++;
}
public void removeFirst()
{
if (size == 0)
{
JOptionPane pane = new JOptionPane();
pane.setIcon(icon);
pane.showMessageDialog(null, "Cannot remove from an empty list!", "Invalid removal", JOptionPane.ERROR_MESSAGE);
pane.setMessageType(JOptionPane.ERROR_MESSAGE);
return;
}
Node<T> current = head; // creates a Node called current and sets it to head.
head = head.getNext(); //move head to the next element
current.setNext(null);
size--;
}
public void addLast(T data)
{
//If there are no elements, use the addFirst method
if (tail == null)
{
addFirst(data);
return;
}
/* Create the new Node from the data. Set next to null
* because this will be the last element and will not
* have a next. Set previous to tail because tail has
* not been changed yet and is currently referencing
* that element that will be directly before this element
*/
Node<T> newNode = new Node(data,null,tail);
/* Since the tail variable still references the element
* directly before the new element, we can set that node's
* next to our new element.
*/
tail.setNext(newNode);
//Set tail to our new Node
tail = newNode;
//Increment size
size++;
}
public int Size()
{
return(size);
}
public void add(int index,T data)
{
int i;
if (index == 0)
{
addFirst(data);
return;
}
if (index>size)
{
JOptionPane.showMessageDialog(null, "Cannot add out of bounds!", "Invalid command", JOptionPane.ERROR_MESSAGE);
return;
}
if (index < 0)
{
JOptionPane.showMessageDialog(null, "Cannot add out of bounds!", "Invalid command", JOptionPane.ERROR_MESSAGE);
return;
}
if (head==null)
{
addFirst(data);
return;
}
if (index == size)
{
addLast(data);
return;
}
//step 1
Node<T> current;
current = head;
for (i=0;i<index-1;i++)
{
current = current.getNext();
}
//current now refers to object immediately before new node
//step 2
Node<T> newnode = new Node<T>(data,current.getNext(), current.getPrevious());
//step 3
current.setNext(newnode);
size++;
}
public void remove(int index)
{
if ((index<0) || (index>=size))
{
JOptionPane.showMessageDialog(null, "You cannot remove an out-of-bounds value!", "Invalid removal", JOptionPane.ERROR_MESSAGE);
return;
}
Node <T> next2, previous3;
Node<T> NodeToRemove = head; // sets Node to remove originally to head
for (int v = 0; v < index; v++)
{
NodeToRemove = NodeToRemove.getNext(); // traverse to Node we want to remove
}
previous3 = NodeToRemove.getPrevious(); // sets previous3 to value before Node to remove
next2 = NodeToRemove.getNext(); // sets next2 to value after Node to remove
if (previous3 == null)
{
if (next2 == null)
{
head = null;
tail = null;
}
else
{
head = next2;
}
}
else
{
previous3.setNext(next2);
}
if (next2 == null)
{
if (previous3 == null)
{
head = null;
tail = null;
}
else
{
tail = previous3;
}
}
else
{
next2.setPrevious(previous3);
}
size--;
}
public T get(int i)
{
if (i < 0 || i >= size)
return null;
if (i ==0)
{
Node<T> thisNode = head;
return(head.getData());
}
if (i == size - 1)
{
Node<T> thisNode = tail;
return(tail.getData());
}
Node<T> specialNode = head;
for (int x = 1; x < i + 1; x++)
{
specialNode = specialNode.getNext();
}
return(specialNode.getData());
// How do I get it to return the data at i?
}
// calls get method of first index
public T front()
{
if (head == null)
return null;
return(get(0));
}
// calls get Method of last index
public T back()
{
if (tail == null)
return null;
return(get(size - 1));
}
public void removeLast()
{
if (head == null)
{
JOptionPane.showMessageDialog(null, "Cannot remove from an empty list!", "Invalid removal", JOptionPane.ERROR_MESSAGE);
return;
}
remove(Size() -1 );
}
// gets a String for the first bracket. Then stores each set of first and last, 2nd and 2nd to last, etc, in a String array;
// it then sets the third string to the concatination of all of the Strings in the array. It thens puts these together and adds
// the last set of brackets and returns the final string.
public String printAlternate()
{
/*
This method returns a string that has
the data in the following fashion (assume for this example that the list stores String objects)
If the list is currently [amit is now here], it will return a string �[amit here is now]�
If the list is currently [amit is now currently here], it will return a string �[amit here is currently now]�
*/
String str = "[";
String [] str2 = new String[size];
for (int v = 0; v < size; v++)
{
str2[v] = this.get(v) + " " + this.get(size - (v+1) );
}
String str3 = "";
for (int x = 0; x < size - 2; x++)
{
str3 = str2[x].concat(str2[x+1]);
}
String str4 = str + " " + str3 + " " + "]";
return(str4);
}
// removes all data
public void removeAll()
{
int x = 0;
int y = this.Size() - 1;
removeRange(x,y);
}
public DoublyLinkedList<T> getCopy()
{
DoublyLinkedList<T> dLL = new DoublyLinkedList<T>();
T[] array = new T[this.Size()];
for (int x =0; x < this.Size; x++)
{
array[x] = this.get(x);
dLL.add(array[x], x);
}
return dLL;
}
}