singly linked list in sorted order

[raamay]

i have been given an assignment to create a singly linked list which maintains order. but i am not sure whether to use a sorting method or to take care of the sorting while adding the values in the list. i guess i am correct to decide the second option because if we insert values according to the order, then the list is automatically a sorted one.

my code for now is as below:
Link.java

package LinkedList;
 
public class Link {    
        public String data;        
        public Link next; 
 
        public Link(){            
            this.next = null;
        }
 
        public Link(String data){            
            this.data = data;            
        }
 
        public void display(){            
            System.out.println(data);            
        }
 
        public String toString(){            
            return data;            
        }
 
        public static void main(String[] args) {            
            LinkList theLinkedList = new LinkList();            
 
            int size = theLinkedList.size();
 
            System.out.println("Size of the Linked List: "+size);
 
            System.out.println("The value stored in Linked List initially is: "+theLinkedList.firstLink);
 
            theLinkedList.insertFirstLink("X");
 
            System.out.println("Value of head node in Linked List after adding: " + theLinkedList.firstLink);
 
            theLinkedList.removeFirst();
 
            System.out.println("The value stored in Linked List after deletion: "+theLinkedList.firstLink);
 
        }
 
}
 

LinkList.java

package ucsc;
 
class LinkList{
 
    public Link firstLink; 
 
    LinkList(){        
        firstLink = null;        
    }
 
    public int size(){
        Link temp = new Link();
        int counter = 0;
 
        while(temp!=null){
            temp = temp.next;
            counter++;
        }
        return counter;
    }
 
    public boolean isEmpty(){        
        return(firstLink == null);        
    }
 
    public void insertFirstLink(String data){        
        Link newLink = new Link(data);        
        newLink.next = firstLink;
 
        firstLink = newLink;        
    }
 
    public Link removeFirst(){
 
        if(!isEmpty()){        
            firstLink = firstLink.next;        
        } else {            
            System.out.println("Empty LinkedList");            
        }        
        return firstLink;        
    }
 
    public void display(){        
        Link theLink = firstLink;
 
        while(theLink != null){            
            System.out.println(theLink);
 
            theLink = theLink.next;            
 
            System.out.println();            
        }
 
    }    
}
 

Kindly, advice me what is the best thing for me to do. If i am rite with my move then i need to know how to do the insert operation. how do we loop through each node of a linked list and what is the algorithm for me to follow.

i can think about iterating through each node and comparing the value in the node with the value i am about to add, if(currentnode.next.element > value && currentnode.element < value) then i can create a node in between those nodes and insert the new element. but i am not sure how to implement my idea in code.

any suggestions would be appreciated.

[Oralloy]

raamay,

The point of a storage object, like your LinkedList, is to guard the client from having to deal with the implementation details.

In your case, having an exposed method like insertFirstLink makes the user of your class have to deal with the details of its implementation.

Perhaps you want to have a simple interface, instead, and keep the first/last/other details of list management hidden?

The basic, exposed (public) interface should probably look something like this:

class LinkedList
{
  public LinkedList()
  {
    // stuff here
  }
 
  public void insertString(String value)
  {
    // stuff here
  }
 
  public void removeString(String value)
  {
    // stuff here
  }
 
  public int size()
  {
    // stuff here
  }
};

With the insertString and removeString methods having responsibility for all list manipulation and maintenence. They should work correctly regardless of where in the list a value is inserted, whether the list is empty, or the insert/remove position. This way, client code never sees the details of the implementation, it just uses your class in a very simple and logical fashion.

What I have not included are methods for accessing the data in the list. Since this is pretty obviously a school assignment, you can do one of two things:

1. Expose the list structure to the client, and allow the client class to walk the list directly.
2. Embed any list processing functions into the LinkedList class, which keeps the details private.

What you do, of course, depends on the project requirements. This is a learning task, so learn to deal with list manipulation, but also learn a bit about abstraction and encapsulation while you are at it.

Again, to reiterate - the value of having a LinkedList class is to protect the client classes from having to know (and deal with) the details of the list's implementation. By encapsulating the implementation, you can provide correct behaviour without having to worry about your client classes inadvertently breaking the implementation.

Good Luck,
Oralloy

[Nepomuk]

Hi raamay!

A general rule to follow is: optimize for commonly used features. In your case this means that if you insert new objects into the list often but only output the list rarely, you should sort the list on output. But if you enter the items only very rarely and read the list often, sort them when putting them into the list.

Concerning what Oralloy said about the public interface, you could have a look at the List interface from the Java Collections Framework. While it may not be necessary for your LinkedList to implement the List interface, it may be a good idea to look at it so as to decide which publicly available functions you need and what kind of signature they should have.