Thread: Linked List Help

I happen to have written a DoublyLinkedLIst(same as Linked List) class earlier and you can look at it if you want. These can hold any parameter type.



However, you can later make a main method that has one of these that holds type Double if you want.

package ProjectOfDoom;
 
public interface MyCollection<T>
{
 
public void add(int index, T data);
public void remove(int index);
public void addFirst(T data);
public void addLast(T data);
public void removeFirst();
public void removeLast();
 
public void removeRange(int from, int to);
public void removeAll();
public int Size();
public T get(int value);
 
 
}

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: 12/31/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. It is a generic class than can hold date types.  
 */
 
 
public class DoublyLinkedList<T> implements MyCollection<T>
{
 
	/* This is the generic class Node, a private innner class of DoublyLnkedList.  
	 */
	private class Node<T>
	{
		/*
		 * variables
		 * T data - a variable of generic type
		 * a Node next, which refers to the Node after the current Node
		 * a Node previous, which refers to the Node before the current Node
		 */
		private T data;
		private Node<T> next;
		private Node<T> previous;
 
		/*
		 * Constructor Node(T data, Node<T> next, Node<T> previous)
		 * parameters T data
		 * a Node next
		 * a Node previous
		 */
		public Node(T data,Node<T> next, Node<T> previous)
		{
			this.data = data;
			this.next = next;
			this.previous=previous;
		}
 
		/*
		 * returns the data of that Node
		 */
		public T getData()
		{
			return data;
		}
 
		/*
		 * returns the Node after the current Node
		 */
		public Node<T> getNext()
		{
			return next;
		}
 
		/*
		 * returns the Node before the current Node
		 */
		public Node<T> getPrevious()
		{
			return previous;
		}
 
		/*
		 * sets the Node after the current Node to next
		 */
		public void setNext(Node<T> next)
		{
			this.next = next;
		}      
 
		/*
		 * sets the Node before the current Node to previous
		 */
		public void setPrevious(Node<T> previous)
		{
			this.previous = previous;
		}
 
		/*
		 * creates a copy of the Node and returns that copy
		 * @see java.lang.Object#clone()
		 */
		public Node<T> clone()
		{
			Node<T> copy = new Node<T>(this.getData(), this.getNext(), this.getPrevious());
			return copy;
		}
	}
 
	/*
	 * data for class DoublyLinkedList
	 * Node head - beginning of DoublyLinkedList
	 * Node tail - end of DoublyLinkedList
	 * int side - size of DoublyLinkedList
	 * 
	 */
	private Node<T> head;//head of the linked list
	private Node<T> tail; // tail of linked list
	private int size;
                    private DoublyLinkedList<T> subDLL;
private DoublyLinkedList<T> anotherOne, anotherOne2;
	private ImageIcon icon;
                    private DoublyLinkedList<T> copiedDLL;
	private Icon icon2;
	/*
	 * constructor DoublyLinkedList()
	 * no parameters
	 */
	public DoublyLinkedList()
	{
		/*
		 * sets head and tail to null
		 * sets size to 0
		 */
		head = null;
		tail = null;
		size = 0;
		icon = new ImageIcon("doh3.jpg");
	}
 
 
 
	/*
	 * returns a String of all the elements in the DoublyLinkedList
	 * @see java.lang.Object#toString()
	 */
	public String toString()
	{
		String str = "[";
 
		Node<T> curr;
 
		for (curr=head;curr!=null;curr = curr.getNext())
		{
			str = str + curr.getData().toString();
			if (curr.getNext()!=null)
				str = str + " ";
		}
		str = str + "]";
		return str;
 
 
	}
 
public T middle()
{
 
int middle = (int) (Size() -1 ) /2;
return (get(middle));
 
}
 
	/*
	 * removeRange(int from, int to)
	 * from - the starting index to remove
	 * to - the last index to remove
	 * removes all values between from and to
	 */
	public void removeRange(int from, int to)
	{
		if (from < 0 || from >= Size() || to < 0 || to >=Size())
		{
			return;
		}
 
if (from >=to)
{
for (int j = from; j >= to; j--)
{
remove(j);
}
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.  
	/*
	 * addFirst(T data)
	 * data - the type of data
	 * adds the data to the beginning of the DoublyLinkedList
	 */
	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++;
	}
 
	/*
	 * removes the data the begining of the DoublyLinkedList
	 */
// an alternate way of doing this would just be to call remove(0)
	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--;
	}
 
	/*
	 * addLast(T data)
	 * parameters data
	 * data- the data to be added
	 * adds data to end of DoublyLinkedList
	 */
	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<T>(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++;
	}
 
	/*
	 * returns the size of the DoublyLinkedList
	 */
	public int Size()
	{
		return(size);
	}
 
	/*
	 * add(int index, T data)
	 * parameters index, data
	 * index - the index to add the data
	 * data- the data to add
	 * adds the data at the specified index
	 */
	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++;
	}  
 
	/*
	 * remove(int index)
	 * parameters index
	 * index- the index of the data to remove
	 * removes the data at the specified index
	 */
	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 the value before the Node we want to remove is null, it probably means that the Node to be removed is the head. (Either that or some goof set it to null and added it anyway to the list.)
		if (previous3 == null)
		{
// if the next one is also null, it means that this Node is you're only Node so it clears the whole list
			if (next2 == null)
			{
				head = null;
				tail = null;
			}
// otherwise it sets the head to the value after the removed Node
			else
			{
				head = next2;
			}
		}
// otherwise it just sets the next2 to be the Node right after previous3
		else
		{
			previous3.setNext(next2);
		}
 
		if (next2 == null)
		{
			if (previous3 == null)
			{
				head = null;
				tail = null;
			}
 
			else
			{
				tail = previous3;
			}
		}
		else
		{
			next2.setPrevious(previous3);
		}
 
 
		size--;
	}
 
	/*
	 * get(int i)
	 * parametsrs i
	 * i - the index
	 * returns the data at index i
	 */
	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?
 
 
	}
 
	public Node<T> getNodeAt(int index)
	{
		Node<T> temp5 = head;
		for (int i =0; i < index; i++)
		{
			temp5 = temp5.getNext();
		}
		return temp5;
	}
	/*
	 * getSubList(int from, int to)
	 * parameters from, to
	 * from - the starting index
	 * to - the ending index
	 * gets the data from index from to index to and copies it into another DoublyLinkedList
	 * and returns that DoublyLinkedList
	 */
	public DoublyLinkedList<T> getSubList(int from, int to)
	{
		DoublyLinkedList<T> sub = new DoublyLinkedList<T>();
		int count = 0;
		for (int value = from; value <=to; value++)
		{
			sub.add(count, this.get(value));
			count++;
		}
		return sub;
	}
 
	/*
	 * swap(int first, int second)
	 * parameters first, second
	 * first - the index of the first value to be swapped
	 * second - the index of the second value to be swapped
	 * swaps the data at index first and index second
	 * Not yet written
	 */
	public void swap(int first, int second)
	{
if (first < 0 || first >=Size() || second < 0 || second >=Size())
return;
 
// no use bothering to swap an index with itself
if (first == second)
return;
		Node<T> prevTemp;
		Node<T> prevTemp2;
		Node<T> nextTemp;
		Node<T> nextTemp2;
 
 
                      prevTemp = getNodeAt(first).getPrevious();
                     prevTemp2 = getNodeAt(second).getPrevious();
                    nextTemp = getNodeAt(first).getNext();
                  nextTemp2 = getNodeAt(second).getNext();
getNodeAt(first).setPrevious(prevTemp2);
getNodeAt(first).setNext(nextTemp2);
getNodeAt(second).setPrevious(prevTemp);
getNodeAt(second).setNext(nextTemp);
 
	}
 
	/*
	 * getIndex(T data)
	 * parameters data
	 * data - the data to look for
	 * if it finds the data, it returns the index where it finds it
	 * otherwise it returns -1 if it cannot find it
	 */
	public int getIndex(T data)
	{
		for (int x =0; x < Size(); x++)
		{
			if (this.get(x).equals(data))
				return x;
		}
		return -1;
	}
	// calls get method of first index
 
	/*
	 * returns the data at the beginning of the DoublyLinkedList
	 */
	public T front()
	{
		if (head == null)
			return null;
 
		return(get(0));
	}
 
	// calls get Method of last index
	/*
	 * returns the data at the end of the DoublyLinkedList
	 */
	public T back()
	{
		if (tail == null)
			return null;
 
		return(get(size - 1));
	}
 
	/*
	 * removes the data at the end of the DoublyLinkedList
	 */
	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
	/*
	 * removes all data in the DoublyLinkedList
	 */
	public void removeAll()
	{
		int x = 0;
		int y = this.Size() - 1;
 
		removeRange(x,y);
	}
	/*
	 * copies the data from this DoublyLinkedList into another one and returns that
	 * DoublyLinkedList
	 * @see java.lang.Object#clone()
	 */
public DoublyLinkedList<T> clone()
{
	DoublyLinkedList<T> copy = new DoublyLinkedList<T>();
	for (int x = 0; x < this.Size(); x++)
	{
		copy.add(x, this.get(x));
	}
	return copy;
}
 
public void addMyCollection(MyCollection<T> aCollection)
{
for (int i =0; i < aCollection.Size(); i++)
{
addLast(aCollection.get(i));
}
 
}
 
public DoublyLinkedList<T> getSubList2(MyCollection<T> collection, int from, int to)
	{
 
		DoublyLinkedList<T> sub = new DoublyLinkedList<T>();
		int count = 0;
		for (int value = from; value <=to; value++)
		{
			sub.add(count, collection.get(value));
			count++;
		}
		return sub;
	}
 
 
 
 
 
 
public DoublyLinkedList<T> getSubList4(Vector<T> aVector, int from, int to)
{
DoublyLinkedList<T> sub = new DoublyLinkedList<T>();
int count = 0;
 
for (int i = from; i <= to; i++)
{
sub.add(count, aVector.get(i));
count++;
}
return sub;
}
public DoublyLinkedList ( DoublyLinkedList<T>original)
{
copiedDLL = original.clone();
this.copiedDLL = copiedDLL;
 
}
 
 
 
 
public DoublyLinkedList ( MyCollection<T> collection, int from, int to)
{
anotherOne = getSubList2(collection, from, to);
this.anotherOne = anotherOne;
}
 
 
 
public Object[] toArray()
{
Object[] obj = new Object[this.Size()];
for (int i =0 ; i < this.Size(); i++)
{
obj[i]  = this.get(i);
}
return obj;
}
 
public void addCloneAt(int index, int indexToClone)
{
if (index < 0 || index >Size())
return;
if (indexToClone <0 || indexToClone >=Size())
return;
add(get(indexToClone), index);
 
}
}