Java Singly Ordered Linked List

Introduction

The Ordered or Sorted Singly Linked List is a linear data structure that uses dynamic memory allocation instead of an array using fixed contiguous memory blocks. Each node of the Linked List is connected to the next Node using a reference or pointer to that node. Each node stores its data. Each node has data that is either smaller or equal to the data of its next node to maintain Ascending order. Due to dynamic memory allocation singly linked require O(N) memory where N is the number of elements. It is a linear container where traversal is normally implemented to move forward because it only maintains a reference or pointer to the next node. Backward traversal can be costly with respect to the performance of the Singly Linked List.

Example

Create List: []
Add Front 3: [3]
Add Front 5: [5, 3]
Add Back 7: [5, 3, 7]
Add Back 9: [5, 3, 7, 9]
Remove First: [3, 7, 9]
Remove Last: [3, 7]

Ordered Linked List Time Complexity

  • Search: requires linear search. The best-case scenario happens if the key is found at the head of the node. The best and Worst case complexity of the search is O(N) where N is the number of elements.
  • Insertion: takes O(1) in the best case if inserted at the head of the singly linked list. In the best and worst cases takes O(N) time to insert the node anywhere in the middle of the linked list or at the end of the linked list. The time complexity to insert at the end of the node can be improved to O(n) if we add another node reference within the linked list called “tail” to keep track of the last node.
  • Deletion: takes O(1) in the best case if deleted from the head of the singly linked list. The best and worst cases take O(N) time to remove the node anywhere from the middle of the linked list or at the end of the linked list.

Node.java

/**
 * Node class Represents a Node within a Linked List.
 *
  * @author CodingHelpLine
 * Website: https://codinghelpline.org
 */
public class Node {
   
    private int data;
    private Node next;      // this is reference to next node object
   
    public Node() {
        data = 0;
        next = null;
    }
   
    public Node(int data) {
        this.data = data;
        this.next = null;
    }
   
    public int getData() {
        return this.data;
    }
   
    public void setData(int data) {
        this.data = data;
    }
   
    public void setNext(Node next) {
        this.next = next;
    }
   
    public Node getNext() {
        return this.next;
    }
}

OrderedList.java

/**
 * Singly Ordered Linked List Class
 *
 * @author CodingHelpLine
 * Website: https://codinghelpline.org
 */
public class OrderedList {
   
    // linked list head
    private Node head;
   
    // number of nodes
    private int count;
   
    // constructor to initialize empty list
    public OrderedList() {
        this.head = null;  // ensure empty list at startup
        this.count = 0;
    }
   
    // Add new value in correct order of the List.
    // Function will maintain the Ascending order of the list.
    public void add(int value) {
       
        // check two things
        // 1. Empty List - add to front
        // 2. if Value is smaller than head node value
        // store to front of Sorted List
        if(this.isEmpty() || value < this.head.getData()) {
            addFront(value);
            return;
        }
       
        // Case 3: Need to insert somewhere between the existing nodes
        Node node = new Node(value);
       
        //Find Correct Location
        Node current = head;    // start with head node
       
        // Conditional while to locate the location to insert new node
        while(current.getNext() != null && current.getNext().getData() <= value) {
            current = current.getNext();
        }
       
        // Two case
        // Case 4: if we reached Last Node
        if(current.getNext() == null) { // this is last node
            current.setNext(node);
        } else {
            // Put between two nodes
            node.setNext(current.getNext());  // new node next will be
            // the next node of current node
           
            // now set next node of current node to new node
            current.setNext(node);
        }
       
        count++;
    }
   
    // add at the front of the linked list.
    private void addFront(int value) {
       
        // first create node
        Node node = new Node(value);
       
        // if list is empty
        if(this.isEmpty()) {
            head = node;
        } else {
            node.setNext(head);
            head = node;
        }
       
        count++;
    }
   
    // remove
    public void remove(int value) {
       
        // if the list empty
        // case 1:
        if(this.isEmpty()) {
            System.out.println("The List is Empty");
            return;
        }
       
        // Case 2: We are remove head node
        if(head.getData() == value) {
            head = head.getNext();
            count--;
        } else {
           
            // Find the node
            // Keep track of two nodes, previous and current
            Node current = head, pre = null;
           
            // Iterate to find the node to remove
            while(current != null) {
               
                // if we reached desired node
                if(current.getData() == value) {
                    pre.setNext(current.getNext());
                    count--;
                    break;
                }
               
                // Traversal
                pre = current;
                current = current.getNext();
            }
        }
    }
   
    // print function
    public void print() {
       
        // start with head node
        Node current = head;
       
        // Iterate till end of list
        while(current != null) {
            System.out.printf("%-10d", current.getData());
            current = current.getNext();
        }
       
        System.out.println("");
    }
   
    //check empty list
    public boolean isEmpty() {
        return head == null;
    }
   
    // size
    public int size() {
        return count;
    }
}

OrderedLinkedListTest.java

/**
 * Singly Ordered Linked List Test.
 *
 * @author CodingHelpLine
 * Website: https://codinghelpline.org
 */
public class OrderedLinkedListTest {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        OrderedList list = new OrderedList();
       
        System.out.println("Adding 4 at the back of List");
        list.add(4);
        System.out.println("Size of List: " + list.size());
        System.out.println("List is Now:");
        list.print();
       
        System.out.println("\nAdding 11 at the back of List");
        list.add(11);
        System.out.println("Size of List: " + list.size());
        System.out.println("List is Now:");
        list.print();
       
        System.out.println("\nAdding 10 at the back of List");
        list.add(10);
        System.out.println("Size of List: " + list.size());
        System.out.println("List is Now:");
        list.print();

        System.out.println("\nAdding 7 at the front of List");
        list.add(7);
        System.out.println("Size of List: " + list.size());
        System.out.println("List is Now:");
        list.print();
       
        System.out.println("\nAdding 9 at the front of List");
        list.add(9);
        System.out.println("Size of List: " + list.size());
        System.out.println("List is Now:");
        list.print();
       
        System.out.println("\nAdding 1 at the front of List");
        list.add(1);
        System.out.println("Size of List: " + list.size());
        System.out.println("List is Now:");
        list.print();
       
        // Testing Remove
        System.out.println("\nRemove 1 from the List");
        list.remove(1);
        System.out.println("Size of List: " + list.size());
        System.out.println("List is Now:");
        list.print();
       
        System.out.println("\nRemove 4 from the List");
        list.remove(4);
        System.out.println("Size of List: " + list.size());
        System.out.println("List is Now:");
        list.print();
       
        System.out.println("\nRemove 10 from the List");
        list.remove(10);
        System.out.println("Size of List: " + list.size());
        System.out.println("List is Now:");
        list.print();
       
        System.out.println("\nRemove 11 from the List");
        list.remove(11);
        System.out.println("Size of List: " + list.size());
        System.out.println("List is Now:");
        list.print();
       
        System.out.println("\nRemove 9 from the List");
        list.remove(9);
        System.out.println("Size of List: " + list.size());
        System.out.println("List is Now:");
        list.print();
       
        System.out.println("\nRemove 7 from the List");
        list.remove(7);
        System.out.println("Size of List: " + list.size());
        System.out.println("List is Now:");
        list.print();
    }
}
Views: 13

Leave a Reply

Your email address will not be published. Required fields are marked *