Data Structures and Algorithms Highly Recommended Java

Generic Sorted Linked List

August 13, 2023
codinghelpline

Introduction

The Singly ordered or sorted Linked List is a linear data structure that uses dynamic memory allocation instead of an array using fixed contiguous memory blocks. Each The node of the Linked List is connected to the next Node using a reference or pointer to that node. Each node stores its data. 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.

Generic Programming

Java included support for writing generic classes in J2SE 5.0 or JDK1.5 version. The generics framework allows us to define a class in terms of a set of parameters that can be used as the type of declared variables, parameters, and return types. Before Java SE 5, generic programming was heavily dependent upon the Java Object class that is the root of the hierarchy in Java Programming Language.

Example:

public class MyClass<T> {

}

This is a generic class that can be instantiated with any Class type such as Integer, String, Double, etc.

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

/**
 * The <code>Node</code> class represents individual node within
 * the linked list. Encapsulates data and reference to the next
 * node in the linked list.
 *
 * @author CodingHelpLine
 * Website: https://codinghelpline.org
 */
public class Node<T extends Comparable<T>> {
    // instance fields
    private T data;
    private Node<T> next;
   
    /**
     * Instantiate node object
     *
     * @param data
     */
    public Node(T data) {
        this.data = data;
        this.next = null;
    }

    public T getData() {
        return data;
    }

    public void setData(T data) {
        this.data = data;
    }

    public Node<T> getNext() {
        return next;
    }

    public void setNext(Node<T> next) {
        this.next = next;
    }
}

OrderedList.java

/**
 * The <code>OrderedList</code> class will implement the Sorted or ordered
 * singly linked list.
 *
 * @author CodingHelpLine
 * Website: https://codinghelpline.org
 */
public class OrderedList<T extends Comparable<T>> {
   
    // Head of the list
    private Node<T> head;
   
    // count of elements
    private int count;
   
    /**
     * Constructor to create empty list
     */
    public OrderedList() {
        this.head = null;
        count = 0;
    }
   
    /**
     * Function to add an element into the List at a correct position
     * to maintain the order of the list.
     *
     * @param data
     */
    public void add(T data) {
       
        // First check if we need to insert before head
        // Case 1 and Case 2
        if(this.isEmpty() || data.compareTo(head.getData()) < 0) {
            this.addFirst(data);
            return;
        }
       
        // create new node
        Node<T> node = new Node<>(data);
       
        // Navigate to the correct position
        Node<T> current = head;
       
        // move to correct position
        while(current.getNext() != null && current.getNext().getData().compareTo(data) <= 0) {
            current = current.getNext();
        }
       
        // There are 2 Cases
        // Case 3: end of linked list reached
        if(current.getNext() == null) {
            current.setNext(node);
        } else {
            // if somewhere between the list
            // put between two nodes
            node.setNext(current.getNext());
           
            // update current's next pointer
            current.setNext(node);
        }
       
        count++;
    }
   
    /**
     * There are two situation that we suppose to insert at the front of the
     * Linked List.
     *
     * 1. If the List is empty.
     * 2. If the head node element or data is larger than the new data
     *
     * To maintain ascending order, insert at front of list.
     *
     * @param data
     */
    public void addFirst(T data) {
       
        // Create new Node
        Node<T> node = new Node<>(data);
       
        // Case 1: If empty
        if(this.isEmpty()) {
            head = node;
           
            // count++;  // Redundancy of code, must keep track of it
           
        } else {
            // Case 2: Insert before Head
            node.setNext(head);
            head = node;
            // count++ //
        }
       
        count++;
    }
   
    /**
     * Remove element from the list.
     *
     * @param data
     */
    public void remove(T data) {
       
        // Case 1 check empty list
        if(this.isEmpty()) {
            System.out.println("This list is empty");
            return;
        }
       
        // Case 2: Remove from the front
        if(head.getData().equals(data)) {
            head = head.getNext();
            count--;
            return;
        }
       
        // declare supporting handles
        Node<T> current = head, pre = null;
       
        while(current != null) {
           
            if(current.getData().equals(data)) {
                pre.setNext( current.getNext());
                count--;
                break;
            }
           
            // update references
            pre = current;
            current = current.getNext();
        }
    }
   
    /**
     * Return the number of elements in the list.
     * @return
     */
    public int size() {
        return count;
    }
   
    /**
     * Function to check if the list is empty.
     *
     * @return indicate empty list
     */
    public boolean isEmpty() {
        return head == null;
    }
   
    /**
     * Print the list
     */
    public void print() {
       
        // check if empty
        if(this.isEmpty()) {
            System.out.println("The list is empty");
            return;
        }
       
        // [1, 2, 3, 4, 5]
       
        Node<T> current = head;
       
        System.out.printf("[%s", current.getData().toString());
       
        current = current.getNext();
       
        while(current != null) {
            System.out.printf(", %s", current.getData());
            current = current.getNext();
        }
       
        System.out.println("]");
    }
}

GenericOrderedLinkedListTest.java

/**
 * Client application to test the Generic Ordered Linked List.
 *
 * @author CodingHelpLine
 * Website: https://codinghelpline.org
 */
public class GenericOrderedLinkedListTest {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
       
        // Integer List
        OrderedList<Integer> intList = new OrderedList<>();
       
        intList.add(5);     // [5]
        intList.print();
        intList.add(2);     // [2, 5]
        intList.print();
        intList.add(9);     // [2, 5, 9]
        intList.print();
        intList.add(11);    // [2, 5, 9, 11]
        intList.print();
        intList.add(4);     // [2, 4, 5, 9, 11
        intList.print();
       
        intList.remove(5);
        intList.print();        // [2, 4, 9, 11]
        intList.remove(11);
        intList.print();        // [2, 4, 9]
        intList.remove(4);
        intList.print();        // [2, 9]
        intList.remove(2);
        intList.print();        // [9]
        intList.remove(9);
        intList.print();        // []
    }    
}
Views: 28

Leave a Reply

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