Introduction
The Singly Linked List is a linear data structures 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. 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 reference or pointer to the next node. Backward traversal can be costly with respect to the performance of the Singly Linked List.
Time Complexity
- Search: requires linear search. Best case scenario happens if the key found at the head of the node. Best and Worst case complexity of search is O(N) where N is the number of elements.
- Insertion: takes O(1) in best case if inserted at the head of the singly linked list. 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 call “tail” to keep track of the last node.
- Deletion: takes O(1) in best case if deleted from the head of the singly linked list. The best and worst cases takes O(N) time to remove the node anywhere from the middle of the linked list or at the end of the linked list.
Example
Create List: Empty 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
Node.java
/**
* Node class
*
* @author CodingHelpLine
*/
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;
}
}
List.java
/**
* Singly Linked List Class
*
* @author CodingHelpLine
*/
public class List {
// linked list head
private Node head;
// number of nodes
private int count;
// constructor to initialize empty list
public List() {
this.head = null;
count = 0;
}
// add first
public void addFront(int value) {
// new create node
Node node = new Node(value);
// if it empty
if(this.isEmpty()) {
head = node;
} else {
node.setNext(head);
head = node; // point first node
}
count++;
}
// add last
public void addBack(int value) {
// create node
Node node = new Node(value);
// if it is empty
if(isEmpty()) {
this.addFront(value);
return;
}
Node current = head;
while(current.getNext() != null) {
current = current.getNext();
}
current.setNext(node); // store at the end of list
count++;
}
// remove
public void remove(int value) {
// Case 1: If empty
if(this.isEmpty()) {
System.out.println("List is Empty");
return;
}
// Case 2: head node
if(head.getData() == value) {
head = head.getNext();
count--;
} else {
// between or end of node
Node current = head, pre = null;
//iterate till the end of list
while(current != null) {
if(current.getData() == value) {
pre.setNext(current.getNext());
count--;
break;
}
// navigate
pre = current; // keep track of previous node
current = current.getNext(); // move to next node
}
}
}
// print function
public void print() {
// if empty
if(this.isEmpty()) {
System.out.println("The List is Empty");
return;
}
Node current = head;
while(current != null) {
System.out.printf("%-7d", current.getData());
current = current.getNext();
}
System.out.println("");
}
//check empty list
public boolean isEmpty() {
return head == null;
}
// size
public int size() {
return count;
}
// Find Max element
public int findMax() {
int max = Integer.MIN_VALUE; // minimum possible value in Java Integer
Node current = head;
while(current != null) {
if(current.getData() > max) {
max = current.getData();
}
current = current.getNext();
}
return max;
}
// Find Minimum Element
public int findMin() {
int min = Integer.MAX_VALUE;
Node current = head;
while(current != null) {
if(current.getData() < min) {
min = current.getData();
}
current = current.getNext();
}
return min;
}
// Calculate Sum of elements
public int calcSum() {
int sum = 0;
Node current = head;
while(current != null) {
sum += current.getData();
current = current.getNext();
}
return sum;
}
// Calculate Average of Elements
public double calcAverage() {
double average = calcSum() / (double)size();
return average;
}
// Calculate Standard Deviation of the Elements
public double calcSD() {
double average = calcAverage();
// summation SQRT((xi - avg)^2 / N)
double numerator = 0;
Node current = head;
while(current != null) {
int x = current.getData();
numerator += (x-average) * ((x-average));
current = current.getNext();
}
double sd = Math.sqrt(numerator / size());
return sd;
}
// Filter odd Elements form the list
public List createOddList() {
List oddList = new List();
Node current = head;
while(current != null) {
int x = current.getData();
if(x % 2 != 0) {
oddList.addBack(x);
}
current = current.getNext();
}
return oddList;
}
// Filter Event Elements form the List
public List createEvenList() {
List evenList = new List();
Node current = head;
while(current != null) {
int x = current.getData();
if(x % 2 == 0) {
evenList.addBack(x);
}
current = current.getNext();
}
return evenList;
}
// Merge Two lists: Current list and the 'list' passed as parameter
public List mergeLists(List list) {
List mergeList = new List();
// Insert all the elements of current list into mergeList
Node current = head;
while(current != null) {
mergeList.addBack(current.getData());
current = current.getNext();
}
// Insert all the elements of "list" into merge list
current = list.head;
while(current != null) {
mergeList.addBack(current.getData());
current = current.getNext();
}
return mergeList;
}
// Split list into two at a threshold value
public void splitList(List left, List right, int threshold) {
// Insert all the elements of current list into mergeList
Node current = head;
while(current != null) {
int x = current.getData();
if(x <= threshold) {
left.addBack(x);
} else {
right.addBack(x);
}
current = current.getNext();
}
}
// Zip the Current List with the List passed as Parameter.
public List zipLists(List list) {
// List 1: 1, 3, 5
// List 2: 2, 4, 6
// Result: 1, 2, 3, 4, 5, 6
List zipList = new List();
Node current1 = head;
Node current2 = list.head;
// this sufficient if both lists have same number
// of elements
while(current1 != null && current2 != null) {
zipList.addBack(current1.getData());
zipList.addBack(current2.getData());
// navigate both
current1 = current1.getNext();
current2 = current2.getNext();
}
// In case length of lists to zip are not same
// have to handle the left overs
while(current1 != null) {
zipList.addBack(current1.getData());
current1 = current1.getNext();
}
// second list left overs
while(current2 != null) {
zipList.addBack(current2.getData());
current2 = current2.getNext();
}
return zipList;
}
}
SinglyLinkedListTest.java
/**
* Test the Linked List Functions.
*
* @author CodingHelpLine
*/
public class SinglyLinkedListTest {
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
List list = new List();
list.addBack(1);
list.addBack(12);
list.addBack(31);
list.addBack(14);
list.addBack(25);
list.addBack(6);
list.addBack(17);
list.addBack(81);
list.addBack(22);
list.addBack(60);
// Statistics
int min = list.findMin();
int max = list.findMax();
int sum = list.calcSum();
double avg = list.calcAverage();
double sd = list.calcSD();
System.out.println("List Statistics");
System.out.println("List is:");
list.print();
System.out.println();
System.out.printf("Minimum element in the List is: %d%n", min);
System.out.printf("Maximum element in the List is: %d%n", max);
System.out.printf("Sum of element in the List is: %d%n", sum);
System.out.printf("Avgerage of element in the List is: %.2f%n", avg);
System.out.printf("Standard Deviation of Elements in the List is: %.2f%n", sd);
System.out.println();
// List Manipulation
// Odd List
List oddList = list.createOddList();
System.out.println("Odd Element List:");
oddList.print();
System.out.println();
// Even List
List evenList = list.createEvenList();
System.out.println("Even Element List:");
evenList.print();
System.out.println();
// Merge Two Lists
List mergeList = oddList.mergeLists(evenList);
System.out.println("Merged Element List:");
mergeList.print();
System.out.println();
// Split List
List left = new List();
List right = new List();
list.splitList(left, right, 23);
System.out.println("Splited Listes:");
System.out.println("Left List:");
left.print();
System.out.println();
System.out.println("Right List:");
right.print();
System.out.println();
// Zip Two Lists
List zipList = oddList.zipLists(evenList);
System.out.println("Zipped List:");
zipList.print();
System.out.println();
}
}
Views: 5