Sorted Single Linked List in java


I am very new to Java and have been assigned to implement a few methods:

1. add (T newValue) ---> add an entry to a sorted list requires that you find the right position the new entry belongs (ascending order).

ex:

SortedListClass mylist = new SortedListClass();

mylist.add(7);

mylist.add(2);

mylist.add(5);

The list should by in this order:

2 5 7

2. remove( T target) ---> To be able to remove a particular entry you need to find it first.

3. Print the items in the reverse order. 

So far my code looks like this:

public class SortedListClass <T> implements ListClassInterface<T>{
    private ListNode head;
    private int size;
    
    public void ListClass(){
        head = null;
        size = 0;
    }  
}

public class ListNode <T>{
    private T item;
    private ListNode<T> next;
    
    ListNode(T item, ListNode next ){
        this.item = item;
        this.next = next;
    }
    ListNode(T item){
        this(item, null);
    }
	
	public void setItem(T item){
		this.item = item;
	}
	public T getItem(){
		return item;
	}
	public void setNext(ListNode n){
		next = n;
	}
	public ListNode getNext(){
		return next;
	}
    
}

Asked by:- IIShriyaII
0
: 346 At:- 4/8/2018 1:40:33 PM
Java SingleLinkedList

Please upvote and mark the answer as correct which helped you for all the question you ask, so other users you have landed on the same page can get Idea, that it worked for you or if not , feel free to comment on the answer, thanks 0
By : vikas_jk - at :- 4/18/2018 1:26:38 PM





1 Answers
profileImage Answered by:- jaiprakash

You can create the Sorted Linked list by following these steps

  1. Create a class SortedLinkedList.java and use the code below, which has code for print, enter data in a sorted linked list, reverse a linked list, & delete a data from the specified position
    package linkedList;
    
    /*  Class Node  */
    class Node {
     protected int data;
     protected Node link;
    
     /*  Constructor  */
     public Node() {
       link = null;
       data = 0;
      }
      /*  Constructor  */
     public Node(int d, Node n) {
       data = d;
       link = n;
      }
      /*  Function to set link to next Node  */
     public void setLink(Node n) {
       link = n;
      }
      /*  Function to set data to current Node  */
     public void setData(int d) {
       data = d;
      }
      /*  Function to get link to next node  */
     public Node getLink() {
       return link;
      }
      /*  Function to get data from current Node  */
     public int getData() {
      return data;
     }
    }
    class linkedList {
     protected Node start;
     public int size;
     public linkedList() {
       start = null;
       size = 0;
      }
      /*  Function to check if list is empty  */
     public boolean isEmpty() {
       return start == null;
      }
      /*  Function to check size of list  */
     public int getSize() {
       return size;
      }
      /*  Function to insert an element  */
     public void insert(int val) {
       Node nptr, ptr, tmp = null;
       nptr = new Node(val, null);
       boolean ins = false;
       if (start == null)
        start = nptr;
       else if (val <= start.getData()) {
        nptr.setLink(start);
        start = nptr;
       } else {
        tmp = start;
        ptr = start.getLink();
        while (ptr != null) {
         if (val >= tmp.getData() && val <= ptr.getData()) {
          tmp.setLink(nptr);
          nptr.setLink(ptr);
          ins = true;
          break;
         } else {
          tmp = ptr;
          ptr = ptr.getLink();
         }
        }
        if (ins == false) {
         tmp.setLink(nptr);
        }
       }
       size++;
      }
      /*  Function to delete an element at position  */
     public void deleteAtPos(int pos) {
       if (pos == 1) {
        start = start.getLink();
        size--;
        return;
       }
       if (pos == size) {
        Node ptr = start;
    
        for (int i = 1; i < size - 1; i++)
         ptr = ptr.getLink();
        ptr.setLink(null);
        size--;
        return;
       }
       Node ptr = start;
       pos = pos - 1;
       for (int i = 1; i < size - 1; i++) {
        if (i == pos) {
         Node tmp = ptr.getLink();
         tmp = tmp.getLink();
         ptr.setLink(tmp);
         break;
        }
        ptr = ptr.getLink();
       }
       size--;
      }
      /*  Function to display elements  */
     public void display() {
      System.out.println("Sorted Singly Linked List = ");
      if (size == 0) {
       System.out.print("empty\n");
       return;
      }
      if (start.getLink() == null) {
       System.out.println(start.getData());
       return;
      }
      Node ptr = start;
      System.out.print(start.getData() + "->");
      ptr = start.getLink();
      while (ptr.getLink() != null) {
       System.out.print(ptr.getData() + "->");
       ptr = ptr.getLink();
      }
      System.out.print(ptr.getData() + "\n");
     }
     
     
     public void printReverse() {
    	    if (start == null) {
    	        System.out.println("null");
    	    } else {
    	        printReverseRecursive(start);
    	    }
    	}
    
    	private void printReverseRecursive(Node node) {
    	    if (node == null) {
    	        return;
    	    }
    	    printReverseRecursive(node.link);
    	    System.out.print(node.getData() + " ");
    	}
    }
    ?
  2. Now create a separate Main.Java class to call the above data
    package linkedList;
    
    import java.util.Scanner;
    
    public class Main {
    	 public static void main(String[] args) {
    	  Scanner scan = new Scanner(System.in);
    	  /* Creating object of linkedList */
    	  linkedList list = new linkedList();
    	  System.out.println("Sorted Singly Linked List Test\n");
    	  char ch;
    	  /*  Perform list operations  */
    	  do {
    	   System.out.println("\nSorted Singly Linked List Operations\n");
    	   System.out.println("1. insert");
    	   System.out.println("2. delete at position");
    	   System.out.println("3. check empty");
    	   System.out.println("4. get size");
    	   System.out.println("5: Print in reverse");
    	   int choice = scan.nextInt();
    	   switch (choice) {
    	    case 1:
    		     System.out.println("Enter integer element to insert");
    		     list.insert(scan.nextInt());
    		     break;
    	    case 2:
    	         System.out.println("Enter position");
    		     int p = scan.nextInt();
    		     if (p < 1 || p > list.getSize())
    		       System.out.println("Invalid position\n");
    		     else
    		       list.deleteAtPos(p);
    	          break;
    	    case 3:
    		     System.out.println("Empty status = " + list.isEmpty() + "\n");
    		     break;
    	    case 4:
    		     System.out.println("Size = " + list.getSize() + " \n");
    		     break;
    	    case 5:
    		     list.printReverse();
    		     break;
    	    default:
    	        System.out.println("Wrong Entry \n ");
    	     break;
    	   }
    	   /*  Display List  */
    	   list.display();
    	   System.out.println("\nDo you want to continue (Type y or n) \n");
    	   ch = scan.next().charAt(0);
    	  } while (ch == 'Y' || ch == 'y');
    	 }
    	}?

When I executed the above Program in my Java IDE(Eclipse) and got the following series of output, pasting images in order

output-sorted-single-linked-list-in-java-min.png

sorted-linked-list-java-2-min.png

reverse-single-linked-list-java-min.png

That's it, You are done, please upvote and mark it as the answer, if it helps, thanks

4
At:- 4/8/2018 7:43:12 PM
excellent answer with proper details. 0
By : Vinnu - at :- 4/9/2018 7:38:05 AM





Login/Register to answer
Or
Register directly by posting answer/details

Full Name *

Email *




By posting your answer you agree on privacy policy & terms of use