Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 2 of 2

Thread: What is the difference between ordered and unordered linked list and how to implement unordered linked list to get ordered set?

  1. #1
    Member
    Join Date
    Jun 2012
    Posts
    59
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default What is the difference between ordered and unordered linked list and how to implement unordered linked list to get ordered set?

    Last week we had an assignment to create an Unordered Link List using an abstract class. However, now the teacher wants us to implement an Ordered Link List using an interface but I'm not quite sure what I'm supposed to be doing or the difference.

    This is my code from last week.

    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();
     
     
    }

    public class IntElement extends DataElement
    {
     
        protected int number;
     
        public IntElement()
        {
            number = 0;
        }
     
        public IntElement(int num)
        {
            number = num;
        }
     
        public IntElement(IntElement obj)
        {
            this.number = obj.getNum();
     
        }
     
        public void setNum(int num)
        {
     
            number = num;
        }
     
        public int getNum()
        {
     
            return number;
        }
     
        public boolean equals(DataElement obj)
        {
     
    		if (obj == null) return false;
    		if (getClass() != obj.getClass()) return false;
    		IntElement temp = (IntElement)obj;
    		return (number == temp.number); 
        }
     
        public int compareTo(DataElement obj)
    	{
    		IntElement temp = (IntElement)obj;
    		if (number < temp.number) return -1;
    		else if (number > temp.number) return 1;
    		else return 0;
    	}
     
    public void makeCopy(DataElement obj)
    	{
    		IntElement temp = (IntElement)obj;
    		number = temp.number;
    	}
     
    	public DataElement getCopy()
    	{
    		DataElement temp = new IntElement(number);
    		return temp;
    	}
     
    }

    public abstract class LinkedList{
     
     
    	protected class LinkedListNode{   // inner class node definition
    		protected DataElement info;
    		protected LinkedListNode link;
    	}
     
    	protected LinkedListNode first; //variable to store the address of the first node of the list
    	protected LinkedListNode last;  // variable to store the address of the last node of the list
     
    	protected int count; //variable to store the number of nodes in the list
     
    	//default constructor
    	//initializes the list to an empty state.
    	//postcondition: first = null, last = null, count = 0
     
    	public LinkedList(){
    		first = null;  //
    		last = null;  //empty list
    		count = 0;   //
    	}
     
     
     
    	//method to determine whether the list is empty
    	//postcondition: returns true if the list is empty; false otherwise
     
     
    	public boolean isEmptyList(){
    		return (count == 0);
    	}
     
     
     
    	//method to initialize the list to an empty state
    	//postcondition: first = null, last = null, count = 0
     
    	public void initializeList(){
    		first = null;
    		last = null;
    		count = 0;
    	}
     
     
    	//method to output the data contained in each node
     
    	public void print(){
     
    	if(count == 0){
    		System.out.println("Cannot print an empty list.");
    	}
    	else{
     
    			LinkedListNode pointer = new LinkedListNode();
    		pointer = first;
    		while(pointer != null)
     
    		System.out.println(pointer.info.toString() + " ");
    		pointer=pointer.link;
     
    	}
    	System.out.println();
    	}
     
     
    	//method to return the number of nodes in the list.
    	//postcondition: the value of count is returned
     
    	public int length(){
    		return count;
    	}
     
    	//method to return a reference of the object 
    	//containing the data of the first node of the list
    	//precondition: the list must exist and must not be empty.
    	//postcondition: the reference of the object that contains
    	//the info of the first node is returned
     
    	public DataElement front(){
     
     
    				return first.info.getCopy();
    		}
     
     
    	//Method to return a reference of object containing
            //the data of the last node of the list.
            //Precondition: The list must exist and must not be empty.
            //Postcondition: The reference of the object that
            //contains the info of the last node
            //is returned.
        public DataElement back(){
        	return last.info.getCopy();
        }
     
        //Method to insert newItem in the list.
            //Postcondition: first points to the new list
            //               and newItem is inserted at the
            //               beginning of the list. Also,
            //               last points to the last node and
            //               count is incremented by 1.
        public void insertFirst(DataElement newItem){
        	LinkedListNode newNode = new LinkedListNode();
        newNode.info = newItem.getCopy();
        newNode.link = first;
        first = newNode;
     
        if(last == null){
     
        last = newNode;
        count++;
        }
     
     
        }
     
        //Method to insert newItem at the end of the list.
            //Postcondition: first points to the new list and
            //newItem is inserted at the end
            //of the list. Also, last points to
            //the last node and
            //count is incremented by 1.
        public void insertLast(DataElement newItem){
     
     LinkedListNode newNode = new LinkedListNode();   
        	newNode.info = newItem.getCopy();
        	newNode.link = null;
        	if(first == null){
        		first = newNode;
        		last = newNode;
        	}
        	else{
     
        	last.link = newNode;
        	last = newNode;
        	count++;
        	}
        }
     
        //Method to determine whether searchItem is in the list.
        //Postcondition: Returns true if searchItem is found
        //in the list; false otherwise.
        public abstract boolean search(DataElement searchItem);	
     
    		//Method to delete deleteItem from the list.
            //Postcondition: If found, the node containing
            //deleteItem is deleted from the
            //list. Also first points to the first
            //node, last points to the last
            //node of the updated list, and count
            //is decremented by 1.
        public abstract void deleteNode(DataElement deleteItem);
     
     
    	}

    public abstract class LinkedList{
     
     
    	protected class LinkedListNode{   // inner class node definition
    		protected DataElement info;
    		protected LinkedListNode link;
    	}
     
    	protected LinkedListNode first; //variable to store the address of the first node of the list
    	protected LinkedListNode last;  // variable to store the address of the last node of the list
     
    	protected int count; //variable to store the number of nodes in the list
     
    	//default constructor
    	//initializes the list to an empty state.
    	//postcondition: first = null, last = null, count = 0
     
    	public LinkedList(){
    		first = null;  //
    		last = null;  //empty list
    		count = 0;   //
    	}
     
    	public LinkedList(LinkedList list)
        {
             copy(list);
        }
     
        private void copy(LinkedList list)
        {
            LinkedListNode pointer;
            LinkedListNode newNode;
     
            if(list.first == null)
            {
                first = null;
                last = null;
                count = 0;
            }
            else
            {
                count = list.count;
                pointer = list.first;
                first = new LinkedListNode();
                first.info = pointer.info.getCopy();
                first.link = null;
                last = first;
                pointer = pointer.link;
     
                while(pointer != null)
                {
                    newNode = new LinkedListNode();
                    newNode.info = pointer.info.getCopy();
                    newNode.link = null;
                    last.link = newNode;
                    last = newNode;
                    pointer = pointer.link;
                }
            }
        }
     
     
     
    	//method to determine whether the list is empty
    	//postcondition: returns true if the list is empty; false otherwise
     
     
    	public boolean isEmptyList(){
    		return (count == 0);
    	}
     
     
     
    	//method to initialize the list to an empty state
    	//postcondition: first = null, last = null, count = 0
     
    	public void initializeList(){
    		first = null;
    		last = null;
    		count = 0;
    	}
     
     
    	//method to output the data contained in each node
     
    	public void print(){
     
    	if(count == 0){
    		System.out.println("Cannot print an empty list.");
    	}
    	else{
     
    			LinkedListNode pointer = new LinkedListNode();
    		pointer = first;
    		while(pointer != null){
     
     
    		System.out.println(pointer.info.toString());
    		pointer=pointer.link;
    		}
     
    	}
     
    	}
     
     
    	//method to return the number of nodes in the list.
    	//postcondition: the value of count is returned
     
    	public int length(){
    		return count;
    	}
     
    	//method to return a reference of the object 
    	//containing the data of the first node of the list
    	//precondition: the list must exist and must not be empty.
    	//postcondition: the reference of the object that contains
    	//the info of the first node is returned
     
    	public DataElement front(){
     
     
    				return first.info.getCopy();
    		}
     
     
    	//Method to return a reference of object containing
            //the data of the last node of the list.
            //Precondition: The list must exist and must not be empty.
            //Postcondition: The reference of the object that
            //contains the info of the last node
            //is returned.
        public DataElement back(){
        	return last.info.getCopy();
        }
     
        //Method to insert newItem in the list.
            //Postcondition: first points to the new list
            //               and newItem is inserted at the
            //               beginning of the list. Also,
            //               last points to the last node and
            //               count is incremented by 1.
        public void insertFirst(DataElement newItem){
        	LinkedListNode newNode = new LinkedListNode();
        newNode.info = newItem.getCopy();
        newNode.link = first;
        first = newNode;
     
        if(last == null){
     
        last = newNode;
        count++;
        }
     
     
        }
     
        //Method to insert newItem at the end of the list.
            //Postcondition: first points to the new list and
            //newItem is inserted at the end
            //of the list. Also, last points to
            //the last node and
            //count is incremented by 1.
        public void insertLast(DataElement newItem){
     
     LinkedListNode newNode = new LinkedListNode();   
        	newNode.info = newItem.getCopy();
        	newNode.link = null;
        	if(first == null){
        		first = newNode;
        		last = newNode;
        	}
        	else{
     
        	last.link = newNode;
        	last = newNode;
        	count++;
        	}
        }
     
        		public void deleteFront()
        {
            if(first.link != null) 
            {
                first = first.link;
                count--;
            }
            else
            {
                first = null;
                last = null;
                count = 0;
            }
        }
     
        public void deleteLast()
        {
            LinkedListNode pointer = first;
            if(pointer.link == null)
            {
                first = null;
                last = null;
                count = 0;
            }
            else 
            {
                while(pointer.link.link != null) pointer = pointer.link;
                pointer.link = null;
                last = pointer;
                count--;
            }
        }
     
         public void splitMid(LinkedList list)
        {
            int stopPoint = list.count / 2;
            LinkedListNode pointer = null;
            pointer = list.first.link;
            for(int i = 0; i < stopPoint; i++)
            {
                pointer = pointer.link;
            }
            LinkedListNode secondFirst = pointer.link;
     
            pointer.link.link = null;
     
        }
     
     
            public double average(){
     
     
        			double sum=0;
        			LinkedListNode pointer = new LinkedListNode();
     
     
        			pointer = first;
     
        			while(first != null){
     
        		pointer = first;
        			IntElement temp = (IntElement)pointer.info.getCopy();
     
        			sum = sum + temp.getNum();
        			first = pointer.link; 
     
     
        			}
     
        		double average = (sum/59.0);
        		return average;
     
        		}
     
        		public double stdDev(double avg){
        			double stdAvg = avg;
        			double variance = 0;
        			LinkedListNode pointer = new LinkedListNode();
     
        			while(first!= null){
     
        				pointer = first;
        				IntElement temp = (IntElement)pointer.info.getCopy();
        				variance = (variance + ((temp.getNum() - stdAvg)*(temp.getNum() - stdAvg)));
        				first = pointer.link;
     
     
        				}
     
        			return (Math.sqrt(variance/59));
        		}
     
     
        //Method to determine whether searchItem is in the list.
        //Postcondition: Returns true if searchItem is found
        //in the list; false otherwise.
        public abstract boolean search(DataElement searchItem);	
     
    		//Method to delete deleteItem from the list.
            //Postcondition: If found, the node containing
            //deleteItem is deleted from the
            //list. Also first points to the first
            //node, last points to the last
            //node of the updated list, and count
            //is decremented by 1.
        public abstract void deleteNode(DataElement deleteItem);
     
     
     
     
      	}

     
    public class UnorderedLinkedList extends LinkedList{
     
     
    	public UnorderedLinkedList(){
    		super();
    	}
     
    	public UnorderedLinkedList(UnorderedLinkedList list){
    		super(list);
    	}
     
    	//Method to determine whether searchItem is in the list.
            //Postcondition: Returns true if searchItem is found
            //in the list; false otherwise.
        public boolean search(DataElement searchItem){
     
        LinkedListNode pointer = new LinkedListNode();
        pointer = first;
        boolean foundData = false;
     
        while(pointer != null && !foundData){
        	if(pointer.info.equals(searchItem) == true){
        		foundData = true;
        	}
        	else{
        		pointer = pointer.link;
        	}
     
        }
        return foundData;	
     
        }
     
     
        //Method to delete deleteItem from the list.
            //Postcondition: If found, the node containing
            //deleteItem is deleted from the
            //list. Also first points to the first
            //node, last points to the last
            //node of the updated list, and count
            //is decremented by 1.
        public void deleteNode(DataElement deleteItem){
     
        	if(count == 0)
        		System.out.println("The list is empty.");
        		else{
        			if(first.info.equals(deleteItem) == true)
        			{
        				if(first.link == null){
        					first = null;
        					last = null;
        					count = 0;
        				}
        				else{
        					first = first.link;
        					count--;
        					if(count == 1){
        						first.link = null;
        						last = first;
        					}
        				}
        			}
     
        			else{
        			LinkedListNode pointer = new LinkedListNode();
        			pointer = first;
     
        			while(pointer.info.equals(deleteItem) != true){
        				pointer = pointer.link;
        				pointer.link = pointer.link.link; //inception
     
        				if(pointer.link == null){
        					last = pointer;
        					count--;
        				}
     
        			}	
     
     
        			}
        			}
     
     
     
     
        }
     
    }

    This is the main to test every method.

     
    import java.util.Random;
     
    public class TestLinkedList{
     
     
    	public static void main(String[] args){
    		double sum = 0;
    		UnorderedLinkedList list = new UnorderedLinkedList();
    		Random rand = new Random();
    		for(int i = 0; i<=59; i++){
    			int randomNum = rand.nextInt(100)+1;
    			 sum += randomNum;
    			list.insertLast(new IntElement(randomNum));
     
    		}
     
     
     
    		UnorderedLinkedList copyList = new UnorderedLinkedList(list); //a copy of the linked list to use for avg and std. deviation
    		UnorderedLinkedList copyList2 = new UnorderedLinkedList(list);
    		UnorderedLinkedList copyList3 = new UnorderedLinkedList(list);
     
    	System.out.println("Printing the list.");
    		list.print();
     
    		System.out.println("Deleting the first node.");
    		list.deleteFront();
    		list.print();
     
    		System.out.println("Deleting the last node.");
    		list.deleteLast();
    		list.print();
     
    		System.out.println("Inserting node into the front with a number of 68.");
    		list.insertFirst(new IntElement(68));
    		list.print();
     
    		System.out.println("Inserting node into the back with a number of 75.");
    		list.insertLast(new IntElement(75));
    		list.print();
     
    		System.out.println("Now splitting the list into to two equal lists.");
    		list.splitMid(list);
    		list.print();
    		System.out.println("The average of the list is: " + copyList.average());
    		double avg = copyList2.average();
    			System.out.println("The standard deviation is: " + copyList3.stdDev(avg));	
     
     
    	}
    }



    So this leads me to my question.... the teacher gave us these files.

    public interface ListInterface
    {
      public int size();
      // Returns the number of elements on this list.
     
      public void add(DataElement element);
      // Adds element to this list.
     
      public boolean remove (DataElement element);
      // Removes an element e from this list such that e.equals(element)
      // and returns true; if no such element exists, returns false. 
     
      public boolean contains (DataElement element);
      // Returns true if this list contains an element e such that 
      // e.equals(element); otherwise, returns false.
     
      public DataElement get(DataElement element);
      // Returns an element e from this list such that e.equals(element);
      // if no such element exists, returns null.
     
      public String toString();
      // Returns a nicely formatted string that represents this list.
     
     
      //----------------------------------------------------------------------------
      // The list has a special property called the current position - the position 
      // of the next element to be accessed by getNext during an iteration through 
      // the list. Only reset and getNext affect the current position.
      //----------------------------------------------------------------------------
     
      public void reset();
      // Initializes current position for an iteration through this list,
      // to the first element on this list.
     
      public DataElement getNext();
      // Preconditions: The list is not empty
      //                The list has been reset
      //                The list has not been modified since the most recent reset
      //
      // Returns the element at the current position on this list.
      // If the current position is the last element, then it advances the value 
      // of the current position to the first element; otherwise, it advances
      // the value of the current position to the next element.
    }

    public class LLNode
    {
      private LLNode link;
      private DataElement info;
     
      public LLNode(DataElement info)
      {
        this.info = info;
        link = null;
      }
     
      public void setInfo(DataElement info)
      {
        this.info = info;
      }
     
      public DataElement getInfo()
      {
        return info;
      }
     
      public void setLink(LLNode link)
      {
        this.link = link;
      }
     
      public LLNode getLink()
      {
        return link;
      }
    }

    public class RefUnsortedList implements ListInterface  
    {
     
      protected int numElements;      // number of elements in this list
      protected LLNode currentPos;    // current position for iteration
     
      // set by find method
      protected boolean found;        // true if element found, else false
      protected LLNode location;      // node containing element, if found
      protected LLNode previous;      // node preceeding location
     
      protected LLNode list;          // first node on the list
     
      public RefUnsortedList()
      {
        numElements = 0;
        list = null;
        currentPos = null;
      }
     
      public void add(DataElement element)
      // Adds element to this list at the front.
      {
        LLNode newNode = new LLNode(element);
        newNode.setLink(list);
        list = newNode;
        numElements++;
      }
     
      protected void find(DataElement target)
      // Searches list for an occurence of an element e such that
      // e.equals(target). If successful, sets instance variables
      // found to true, location to node containing e, and previous
      // to the node that links to location. If not successful, sets 
      // found to false.
      {
        location = list;
        found = false;
     
        while (location != null) 
        {
          if (location.getInfo().equals(target))  // if they match
          {
           found = true;
           return;
          }
          else
          {
            previous = location;                 // move to next node 
            location = location.getLink();
          }
        }
      }
     
      public int size()
      // Returns the number of elements on this list. 
      {
        return numElements;
      }
     
      public boolean contains (DataElement element)
      // Returns true if this list contains an element e such that 
      // e.equals(element); otherwise, returns false.
      {
        find(element);
        return found;
      }
     
      public boolean remove (DataElement element)
      // Removes an element e from this list such that e.equals(element)
      // and returns true; if no such element exists, returns false.
      {
        find(element);
        if (found)
        {
          if (list == location)     
            list = list.getLink();    // remove first node
          else
            previous.setLink(location.getLink());  // remove node at location
     
          numElements--;
        }
        return found;
      }
     
      public DataElement get(DataElement element)
      // Returns an element e from this list such that e.equals(element);
      // if no such element exists, returns null.
      {
        find(element);    
        if (found)
          return location.getInfo().getCopy() ;  //we changed this
        else
          return null;
      }
     
      public String toString()
      // Returns a nicely formatted string that represents this list.
      {
        LLNode currNode = list;
        String listString = "List:\n";
        while (currNode != null)
        {
          listString = listString + "  " + currNode.getInfo() + "\n";
          currNode = currNode.getLink();
        }
        return listString;
      }  
     
      public void reset()
      // Initializes current position for an iteration through this list,
      // to the first element on this list.
      {
        currentPos  = list;
      }
     
      public DataElement getNext()
      // Preconditions: The list is not empty
      //                The list has been reset
      //                The list has not been modified since most recent reset
      //
      // Returns the element at the current position on this list.
      // If the current position is the last element, then it advances the value 
      // of the current position to the first element; otherwise, it advances
      // the value of the current position to the next element.
      {
    	  DataElement next = currentPos.getInfo().getCopy();
     
        if (currentPos.getLink() == null)
          currentPos = list;
        else
          currentPos = currentPos.getLink();
        return next;
      }
     
      public void clear()
      {
         LLNode cur  = list.getLink();      //point to second node
         LLNode prev = list;                //point to first node 
     
         while( cur != null )
         {
            prev.setLink(null);
            prev = cur;
            cur = cur.getLink();
         }
         list = null;
         numElements = 0;
         currentPos = null;
      }
     
     
    }//class RefUnsortedList

    This is essentially the same thing I wrote, except...probably less sloppy. I still don't understand how we are supposed to implement or what is a ordered list? Would I have to make the RefUnsortedList an interface too, and then implement it into my ordered class? Need opinions, thank you!

    edit: Should i even use the example from the teacher, or just keep continuing on mine? Couldn't I just keep using my abstract LinkedList class and just go deeper?
    Last edited by Deep_4; November 7th, 2012 at 10:56 PM.


  2. #2
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,895
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

    Default Re: What is the difference between a unordered and ordered Link List??

    Usually an unordered linked list means the items can be put into the list in any order you want.

    For example:

    bob->james->mike->adam->dave

    An ordered linked list just means the linked list must have some kind of "sorted" order. Different possible orders are lexicographical order (alphabetical), shortest to longest, etc.

    lexicographical order:

    adam->bob->dave->james->mike

Similar Threads

  1. Ordered Linked List
    By LemmyWinks in forum Java Theory & Questions
    Replies: 1
    Last Post: July 21st, 2012, 03:49 PM
  2. Ordered Binary Decision Tree
    By nilay in forum Member Introductions
    Replies: 1
    Last Post: October 7th, 2011, 06:12 AM
  3. link
    By Joy123 in forum What's Wrong With My Code?
    Replies: 5
    Last Post: July 8th, 2011, 08:47 PM
  4. Data Structure for ordered binay tree
    By wash in forum Algorithms & Recursion
    Replies: 0
    Last Post: April 23rd, 2010, 05:31 PM
  5. How to Hyper-link pages together in Java?
    By don.java1 in forum Java Applets
    Replies: 5
    Last Post: July 21st, 2008, 05:09 AM