426 lines
8.8 KiB
Java
426 lines
8.8 KiB
Java
/**
|
|
* <PRE>
|
|
* LinkedList.java
|
|
*
|
|
* Revisions: 1.0 Sep. 21, 2002
|
|
* Created the LinkedList class
|
|
* 1.1 Sep. 26, 2002
|
|
* Compiled, Finished, Commented
|
|
*
|
|
* </PRE>
|
|
*
|
|
* Collaboration Statement:
|
|
* I worked on the homework assignment alone, using only
|
|
* course materials.
|
|
*
|
|
* Created with JCreatorLE, some indents are off when viewed through notepad
|
|
* or EMACS
|
|
*
|
|
* @author <A HREF="mailto:gtg184g@mail.gatech.edu">Jose Manuel Caban</A>
|
|
* @version Version 1.1, Sep. 26, 2002
|
|
*/
|
|
|
|
public class LinkedList {
|
|
|
|
/**
|
|
*Front of the list
|
|
*/
|
|
private LLNode head;
|
|
|
|
/**
|
|
*Back of the List
|
|
*/
|
|
private LLNode tail;
|
|
|
|
//there's actually something to debug this time!
|
|
private static final boolean bDebug = false;
|
|
|
|
////////////////
|
|
//Constructors//
|
|
////////////////
|
|
|
|
/**
|
|
*Default constructor for LinkedList
|
|
*sets head and tail to null
|
|
*/
|
|
public LinkedList(){
|
|
head = null;
|
|
tail = null;
|
|
}
|
|
|
|
///////////
|
|
//Methods//
|
|
///////////
|
|
|
|
/**
|
|
*Add node to front of list
|
|
*@param o, the data to be stored in the node
|
|
*/
|
|
public void addToFront(Object o){
|
|
LLNode node = new LLNode(o,head);
|
|
|
|
if(bDebug){System.out.print("Adding to Front:");}
|
|
|
|
head = node;
|
|
if(tail == null){
|
|
this.tail = node;
|
|
}
|
|
|
|
if(bDebug){System.out.println("Done.");}
|
|
}
|
|
|
|
/**
|
|
*Add node to back of list
|
|
*@param o, the data to be stored in the node
|
|
*/
|
|
public void addToBack(Object o){
|
|
LLNode node = new LLNode(o);
|
|
|
|
if(bDebug){System.out.print("Adding to Back:");}
|
|
|
|
if(tail != null){
|
|
tail.setNext(node);
|
|
}
|
|
|
|
tail = node;
|
|
if(head == null){
|
|
head = node;
|
|
}
|
|
|
|
if(bDebug){System.out.println("Done.");}
|
|
}
|
|
|
|
/**
|
|
*@return the data stored by the first node
|
|
*/
|
|
public Object getFirst(){
|
|
if(head != null){
|
|
return head.getData();
|
|
}
|
|
|
|
else {
|
|
return null;
|
|
}
|
|
}
|
|
|
|
/**
|
|
*@return the data stored by the last node
|
|
*/
|
|
public Object getLast(){
|
|
if(tail != null){
|
|
return tail.getData();
|
|
}
|
|
else {
|
|
return null;
|
|
}
|
|
}
|
|
|
|
/**
|
|
*@return the data stored by the first node, destroy first node
|
|
*/
|
|
public Object removeFromFront(){
|
|
if(head == null){
|
|
return null;
|
|
}
|
|
|
|
if(bDebug){System.out.print("Removing from Front:");}
|
|
|
|
Object temp = head.getData();
|
|
|
|
head = head.getNext();
|
|
|
|
if(head == null){
|
|
tail = null;
|
|
}
|
|
|
|
if(bDebug){System.out.println("Done.");}
|
|
|
|
return temp;
|
|
}
|
|
|
|
/**
|
|
*@return the data stored by the last node, destroy the last node
|
|
*/
|
|
public Object removeFromBack(){
|
|
if(tail == null){
|
|
return null;
|
|
}
|
|
|
|
if(bDebug){System.out.print("Removing from Back:");}
|
|
|
|
Object temp = tail.getData();
|
|
LLNode current = head;
|
|
|
|
if(current != tail){
|
|
//find second to last node
|
|
while(current.getNext() != tail){
|
|
current = current.getNext();
|
|
}
|
|
tail = current;
|
|
tail.setNext(null);
|
|
}
|
|
|
|
else {
|
|
tail = null;
|
|
}
|
|
|
|
if(tail == null){
|
|
head = null;
|
|
}
|
|
|
|
if(bDebug){System.out.println("Done.");}
|
|
|
|
return temp;
|
|
}
|
|
|
|
/**
|
|
*@return the number of nodes in the LinkedList
|
|
*/
|
|
public int size(){
|
|
|
|
if(head == null){
|
|
return 0;
|
|
}
|
|
|
|
if(head == tail){
|
|
return 1;
|
|
}
|
|
|
|
int count=0;
|
|
LLNode current = head;
|
|
|
|
while(current!= null){
|
|
current = current.getNext();
|
|
count++;
|
|
}
|
|
|
|
return (count);
|
|
}
|
|
|
|
/**
|
|
*Turn the LinkedList into an Array
|
|
*@return array containing all the data held by the LinkedList
|
|
*/
|
|
public Object[] asArray(){
|
|
|
|
Object[] array = new Object[this.size()];
|
|
|
|
if(head == null){
|
|
return array;
|
|
}
|
|
|
|
LLNode current = head;
|
|
int i=0;
|
|
while(current != null){
|
|
array[i] = current.getData();
|
|
i++;
|
|
current = current.getNext();
|
|
}
|
|
|
|
return array;
|
|
}
|
|
|
|
/**
|
|
*temp method to output list on screen
|
|
*meant for debugging to circumvent the array method
|
|
*/
|
|
public void listOut(){
|
|
LLNode current = head;
|
|
|
|
while(current != null){
|
|
System.out.println(current.getData());
|
|
current = current.getNext();
|
|
}
|
|
}
|
|
|
|
/**
|
|
*Find the equality of the LinkedList
|
|
*@param LL, the list to be compared to
|
|
*@return the equality value
|
|
*/
|
|
public boolean equals(Object obj){
|
|
if(!(obj instanceof LinkedList)){
|
|
return false;
|
|
}
|
|
|
|
LinkedList LL = (LinkedList)obj;
|
|
|
|
LLNode thisCurrent = this.head;
|
|
LLNode temp = LL.head;
|
|
|
|
if(this.size() != LL.size()){
|
|
return false;
|
|
}
|
|
while(thisCurrent != null){
|
|
if(!(thisCurrent.getData().equals(temp.getData()))){
|
|
return false;
|
|
}
|
|
thisCurrent = thisCurrent.getNext();
|
|
temp = temp.getNext();
|
|
}
|
|
|
|
return true;
|
|
}
|
|
|
|
/**
|
|
* Change standard string to output to be used for this specific program
|
|
* @return phrase as string
|
|
*/
|
|
public String toString(){
|
|
String ReallyLong;
|
|
ReallyLong = "[ ";
|
|
LLNode current = head;
|
|
while(current != null){
|
|
ReallyLong += current.getData().toString();
|
|
if(current.getNext() != null){
|
|
ReallyLong += ", ";
|
|
}
|
|
current = current.getNext();
|
|
}
|
|
ReallyLong += "]";
|
|
|
|
return ReallyLong;
|
|
}
|
|
|
|
/**
|
|
*Check if there is an object in the list matching o
|
|
*@return true if such an object exists
|
|
*/
|
|
public boolean contains(Object o){
|
|
LLNode current = head;
|
|
while(current != null){
|
|
if(current.getData().equals(o)){
|
|
return true;
|
|
}
|
|
current = current.getNext();
|
|
}
|
|
return false;
|
|
}
|
|
|
|
/**
|
|
*Method meant for debugging
|
|
*clears the list
|
|
*/
|
|
public void clear(){
|
|
head = null;
|
|
tail = null;
|
|
}
|
|
|
|
/*********************************************************/
|
|
|
|
/**
|
|
* Debugging main for class LinkedList.
|
|
* This method will rigorously test my code.
|
|
*
|
|
* <br><br>
|
|
* @param args a String array of command line arguments.
|
|
*/
|
|
public static void main(String[] args) {
|
|
LinkedList LL = new LinkedList();
|
|
Object[] array;
|
|
LinkedList LL2 = new LinkedList();
|
|
|
|
System.out.println("test 1");
|
|
LL.addToFront("2");
|
|
LL.addToFront("1");
|
|
LL.addToBack("3");
|
|
LL.addToBack("4");
|
|
LL.listOut();
|
|
array = LL.asArray();
|
|
|
|
for(int i=0; i<array.length; i++){
|
|
System.out.println(array[i]);
|
|
}
|
|
|
|
System.out.println("test 2");
|
|
LL.removeFromFront();
|
|
LL.removeFromBack();
|
|
LL.removeFromBack();
|
|
|
|
array = LL.asArray();
|
|
|
|
for(int i=0; i<array.length; i++){
|
|
System.out.println(array[i]);
|
|
}
|
|
|
|
System.out.println(LL.equals(LL2));
|
|
|
|
LL.clear();
|
|
LL.addToFront("1");
|
|
LL.addToFront("2");
|
|
LL.addToBack("3");
|
|
LL2.addToFront("1");
|
|
LL2.addToFront("2");
|
|
LL2.addToBack("3");
|
|
|
|
System.out.println(LL2.equals(LL));
|
|
|
|
LL.clear();
|
|
LL2.clear();
|
|
|
|
LL.addToBack("2");
|
|
|
|
LL.addToFront(new Integer(1));
|
|
LL2.addToBack("2");
|
|
|
|
System.out.println(LL.equals(LL2));
|
|
|
|
LL2.addToFront(new Integer(1));
|
|
|
|
System.out.println(LL2.equals(LL));
|
|
|
|
LL2.removeFromBack();
|
|
|
|
System.out.println(LL2.equals(LL));
|
|
System.out.println(LL.equals(LL));
|
|
LL.clear();
|
|
System.out.println(LL.equals(LL2));
|
|
|
|
//test what autograder finds as wrong
|
|
//431, 653, 95, 201, 331, 326, 627, 38, 284, 350, 960, 36
|
|
LL.clear();
|
|
LL2.clear();
|
|
|
|
LL.addToBack(new Integer(36));
|
|
LL.addToFront(new Integer(960));
|
|
LL.addToFront(new Integer(350));
|
|
LL.addToFront(new Integer(284));
|
|
LL.addToFront(new Integer(38));
|
|
LL.addToFront(new Integer(627));
|
|
LL.addToFront(new Integer(326));
|
|
LL.addToFront(new Integer(331));
|
|
LL.addToFront(new Integer(201));
|
|
LL.addToFront(new Integer(95));
|
|
LL.addToFront(new Integer(653));
|
|
LL.addToFront(new Integer(431));
|
|
|
|
System.out.println(LL.equals(LL));
|
|
System.out.println(LL.equals(LL2));
|
|
LL2 = LL;
|
|
System.out.println(LL.equals(LL2));
|
|
|
|
//Holy crap this is a long debug main!
|
|
LL2.clear();
|
|
|
|
LL2.addToFront(new Integer(960));
|
|
LL2.addToFront(new Integer(350));
|
|
LL2.addToFront(new Integer(284));
|
|
LL2.addToFront(new Integer(38));
|
|
LL2.addToFront(new Integer(627));
|
|
LL2.addToFront(new Integer(326));
|
|
LL2.addToFront(new Integer(331));
|
|
LL2.addToFront(new Integer(201));
|
|
LL2.addToFront(new Integer(95));
|
|
LL2.addToFront(new Integer(653));
|
|
LL2.addToFront(new Integer(431));
|
|
|
|
System.out.println(LL.equals(LL2));
|
|
|
|
|
|
|
|
|
|
|
|
}// end of main(String[] args)
|
|
|
|
}// end of class LinkedList
|