Assignment8

package assignment8;


public abstract class LinkedListClass
{
    //definition of the node
    protected class LinkedListNode
    {
        DataElement info;
        LinkedListNode link;
    }

    protected LinkedListNode first; //variable to point to the first node
    protected LinkedListNode last;  //variable to point to the last node
    protected int count;            //variable to store the number of nodes
                                    //in the list

    //default constructor
    //initializes the list to an empty state
    public LinkedListClass()
    {
        first = null;
        last = null;
        count = 0;
    }

    //copy constructor
    //method to initialize the list to an empty state
    public LinkedListClass(LinkedListClass otherList)
    {
        copy(otherList);
    }

    //method to initialize the list to an empty state
    public void initializeList()
    {
        first = null;
        last = null;
        count = 0;
    }

    //method to determine whether the list is empty
    public boolean isEmptyList()
    {
        return (first == null);
    }

    //method to output the data contained in each node
    public void print()
    {
        LinkedListNode current; //variable to traverse the list

        current = first;        //set current so that it points to
                                //the first node
        while(current != null)  //while more data to print
        {
            System.out.println(current.info + " ");
            current = current.link;
        }
    }

    //method to return the number of nodes in the list
    public int length()
    {
        return count;
    }

    //method to return the reference of the object containing the data of the
    //first node in the list
    public DataElement front()
    {
        DataElement temp = first.info.getCopy();
        return temp;
    }

    //method to return the reference of the object containing the data of the
    //last node in the list
    public DataElement back()
    {
        DataElement temp = last.info.getCopy();
        return temp;
    }

    //method to determine whether searchItem is in the list
    public abstract boolean search(DataElement searchItem);

    //method to insert newItem in the list
    public void insertFirst(DataElement newItem)
    {
        LinkedListNode newNode;             //variable to create the new node

        newNode = new LinkedListNode();     //create the new node
        newNode.info = newItem.getCopy();   //assign a copy of the newItem
                                            //to the node
        newNode.link = first;               //insert newNode before first
        first = newNode;                    //make first point to the
                                            //actual first node
        if(last == null)                    //if the list was empty, newNode is
                                            //also the last node in the list
            last = newNode;

        count++;
    }

    //method to insert newItem at the end of the list
    public void insertLast(DataElement newItem)
    {
        LinkedListNode newNode;             //variable to create the new node

        newNode = new LinkedListNode();     //create the new node
        newNode.info = newItem.getCopy();   //assign a copy of the newItem
                                            //to the node
        newNode.link = first;               //insert newNode before first
        first = newNode;                    //make first point to the
                                            //actual first node
        if(last == null)                    //if the list was empty, newNode is
                                            //also the last node in the list
        {
            first = newNode;
            last = newNode;
        }
        else            //if the list is not empty, insert newNode after last
        {
            last.link = newNode;    //insert newNode after last
            last = newNode;         //set last to point to the actual last node
        }

        count++;
    }

    //method to delete deleteItem from the list
    public abstract void deleteNode(DataElement deleteItem);

    //method to return the reference of the copy of otherList
    private void copy(LinkedListClass otherList)
    {
        LinkedListNode newNode; //variable to create a node
        LinkedListNode current; //variable to traverse the list

        first = null;   //make this list empty

        if(otherList.first == null) //otherList is empty
        {
            first = null;
            last = null;
            count = 0;
        }
        else
        {
            count = otherList.count;
            current = otherList.first;  //current points to the list
                                        //to be copied

            //copy the first element
            first = new LinkedListNode();           //create the node
            first.info = current.info.getCopy();    //copy the info
            first.link = null;  //set the link field of the node to null
            current = current.link; //make current point to the next node of
                                    //the list being copied

            //copy the remaining list
            while(current != null)
            {
                newNode = new LinkedListNode();
                newNode.info = current.info.getCopy();
                newNode.link = null;
                last.link = newNode;
                last = newNode;
                current = current.link;
            }
        }
    }

    //method to return the reference of the copy of otherList
    public void copyList(LinkedListClass otherList)
    {
        if(this != otherList)       //avoid self-copy
            copy(otherList);
    }

    public void splitMid(LinkedListClass otherList)
    {
        otherList = new UnorderedLinkedList();
        LinkedListNode current;
        LinkedListNode current2;
        if (count == 0)
            System.out.println("The list is null.");
        else
        {
            int newLength = count / 2;
            current2 = first;
            if (count % 2 == 0)
                for(int i = 0; i<newLength; i++)
                {
                    current2 = current2.link;
                }
            else
                for(int i = 0; i<newLength+1; i++)
                {
                    current2 = current2.link;
                }

            current = first;
            if (count % 2 == 0)
                while(current != current2)

                {
                    this.deleteNode(first.info);
                    this.deleteNode(first.info);
                    this.insertLast(current.info);
                    current = current.link;
                }
            else
            {
                while(current != current2)
                {
                    this.deleteNode(first.info);
                    this.insertLast(current.info);
                    current = current.link;

                }
                int nC = count / 2 - 1;

                for(int i = 0; i <= nC; i++)
                {
                    this.deleteNode(first.info);
                }

            }

            while(current2 != null)
            {
                otherList.insertLast(current2.info);
                current2 = current2.link;
            }
        }
    }

}


------------------------------------------------------------------------------

package assignment8;


public class UnorderedLinkedList extends LinkedListClass
{
    protected LinkedListNode first; //variable to point to the first node
    protected LinkedListNode last;  //variable to point to the last node
    protected int count;            //variable to store the number of nodes
                                    //in the list

    //default constructor
    public UnorderedLinkedList()
    {
        super();
    }

    //copy constructor
    public UnorderedLinkedList(UnorderedLinkedList otherList)
    {
        super(otherList);
    }

    //method to determine whether searchItem is in the list
    public boolean search(DataElement searchItem)
    {
        LinkedListNode current; //variable to traverse the list
        boolean found;

        current = first;    //set current to point to the first node in the list

        found = false;      //set found to false

        while(current != null && !found)    //search the list
            if(current.info.equals(searchItem)) //item is found
                found = true;
            else
                current = current.link;     //make the current point to
                                            //the next node
        return found;
    }

    //method to delete deleteItem from the list
    public void deleteNode(DataElement deleteItem)
    {
        LinkedListNode current;         //variable to traverse the list
        LinkedListNode trailCurrent;    //variable just before current
        boolean found;

        if(first == null)       //Case 1; the list is empty
            System.err.println("Cannot delete from an empty list.");
        else
        {
            if(first.info.equals(deleteItem))   //Case 2
            {
                first = first.link;

                if(first == null)       //the list had only one node
                    last = null;
                count--;
            }
            else    //search the list for the node with the given info
            {
                found = false;
                trailCurrent = first;   //set trailCurrent to point to
                                        //the first node
                current = first.link;   //set current to point to the
                                        //second node

                while(current != null && !found)
                {
                    if(current.info.equals(deleteItem))
                        found = true;
                    else
                    {
                        trailCurrent = current;
                        current = current.link;
                    }
                }

                if(found)   //Case 3; if found, delete the node
                {
                    count--;
                    trailCurrent.link = current.link;

                    if(last == current)         //node to be delete was the
                                                //last node
                        last = trailCurrent;    //update the value of last
                }
                else
                    System.out.println("Item to be delete is not in the list.");
            }
        }
    }



}


------------------------------------------------------------------------------

package assignment8;


import java.io.*;
import java.util.*;

public class Test
{
static BufferedReader keyboard = new
    BufferedReader (new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException
    {
        UnorderedLinkedList myList = new UnorderedLinkedList();
        UnorderedLinkedList otherList = new UnorderedLinkedList();

        IntElement num = new IntElement();
        StringTokenizer tokenizer;

        System.out.print("Enter a list of integers ending with -999: ");

        tokenizer = new StringTokenizer(keyboard.readLine());
        num.setNum(Integer.parseInt(tokenizer.nextToken()));

        while (num.getNum() != -999)
        {
            myList.insertLast(num);
            num.setNum(Integer.parseInt(tokenizer.nextToken()));
        }

        System.out.println("The length of your list is: " + myList.length());
        System.out.println("Your list is: ");
        myList.print();
        myList.splitMid(otherList);
        System.out.println("\n" + "The length of your list is now: " + myList.length());
        System.out.println("Your list after splitting is now: ");
        myList.print();
        System.out.println("\n" + "The length of your new list is: " + otherList.length());
        System.out.println("Your new list after splitting is: ");
        otherList.print();
    }

}



------------------------------------------------------------------------------

package assignment8;


public class IntElement extends DataElement
{
    protected int num;

    //default constructor
    public IntElement()
    {
        num = 0;
    }

    //constructor with parameters
    public IntElement(int x)
    {
        num = x;
    }

    //copy constructor
    public IntElement(IntElement otherElement)
    {
        num = otherElement.num;
    }

    //method to set the value of the instance variable num
    //postcondition: num = x;
    public void setNum(int x)
    {
        num = x;
    }

    //method to return the value of the instance variable num
    //postcondition: the value of num is returned
    public int getNum()
    {
        return num;
    }

    @Override
    public boolean equals(DataElement otherElement)
    {
        IntElement temp = (IntElement) otherElement;
        return(num == temp.num);
    }

    @Override
    public int compareTo(DataElement otheElement)
    {
        IntElement temp = (IntElement) otheElement;
        return(num = temp.num);
    }

    @Override
    public void makeCopy(DataElement otherElement)
    {
        IntElement temp = (IntElement) otherElement;
        num = temp.num;
    }

    @Override
    public DataElement getCopy()
    {
        IntElement temp = new IntElement(num);
        return temp;
    }

    @Override
    public String toString()
    {
        return String.valueOf(num);
    }
}

------------------------------------------------------------------------------


package assignment8;


public abstract class DataElement
{
    public abstract boolean equals(DataElement otherElement);

    public abstract int compareTo(DataElement otherElement);

    public abstract void makeCopy(DataElement otherElement);

    public abstract DataElement getCopy();
}