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