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.
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]
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.
CreateOddList()
This function will Create a new Linked List with odd elements from the current linked list. The original List will remain unchanged. New Linked List will only contain odd elements of the original linked list.
Example:
List: 1, 2, 3, 4, 5, 6, 7, 8
New List: 1, 3, 5, 7
CreateEvenList()
This function will Create a new Linked List with even elements from the current linked list. The original List will remain unchanged. New Linked List will only contain even elements of the original linked list.
Example:
List: 1, 2, 3, 4, 5, 6, 7, 8
New List: 2, 4, 6, 8
MergeLists()
This function will Create a new Linked List by merging two linked lists. The current list elements added to the new list first and then second linked list elements inserted at the end of the new list.
Example:
List1: 1, 3, 5, 7
List2: 2, 4, 5, 8
Merged List: 1, 3, 5, 7, 2, 4, 6, 8
SplitList():
This function will split the current list into two lists at a threshold value. The two new lists and the threshold value passed to the function as parameter. The existing list will remain unchanged.
Example:
Threshold Value: 7
List: 1, 3, 9, 2, 7, 12, 13, 15
List-Left: 1, 3, 2, 7
Light-Right: 9, 12, 13, 15
ZipLists():
This function will operate on two linked lists and zip them. It takes one element from the first list and insert to the new list. Then takes one element from the second linked list and insert in it at the end of new list. It repeats until all the elements from both the lists are inserted into the new list. The original List will remain unchanged.
Example:
list1: 1, 3, 5
list2: 2, 4, 6
ZipList: 1, 2, 3, 4, 5, 6
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;
}
}
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();
System.out.println("Adding 4 at the back of List");
list.addBack(4);
System.out.println("Size of List: " + list.size());
System.out.println("List is Now:");
list.print();
System.out.println("\nAdding 5 at the back of List");
list.addBack(5);
System.out.println("Size of List: " + list.size());
System.out.println("List is Now:");
list.print();
System.out.println("\nAdding 6 at the back of List");
list.addBack(6);
System.out.println("Size of List: " + list.size());
System.out.println("List is Now:");
list.print();
System.out.println("\nAdding 3 at the front of List");
list.addFront(3);
System.out.println("Size of List: " + list.size());
System.out.println("List is Now:");
list.print();
System.out.println("\nAdding 2 at the front of List");
list.addFront(2);
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.addFront(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 6 from the List");
list.remove(6);
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 3 from the List");
list.remove(3);
System.out.println("Size of List: " + list.size());
System.out.println("List is Now:");
list.print();
System.out.println("\nRemove 5 from the List");
list.remove(5);
System.out.println("Size of List: " + list.size());
System.out.println("List is Now:");
list.print();
System.out.println("\nRemove 2 from the List");
list.remove(2);
System.out.println("Size of List: " + list.size());
System.out.println("List is Now:");
list.print();
}
}