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.
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. 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.
Node.java
* Implementation of Generic Node Class.
*
* @author CodingHelpLine
* Website: https://codinghelpline.org
*/
public class Node<T> {
// data to store
private T data;
// reference to the next
private Node<T> next;
// constructor to setup the Object
public Node() {
data = null;
next = null;
}
/**
* Instantiate object of Node class.
*
* @param data to store within this node object.
*/
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;
}
}
List.java
* Implementation of the Generic Singly Linked List.
*
* @author CodingHelpLine
* Website: https://codinghelpline.org
*/
public class List<T> {
// head of List class
private Node<T> head;
// count variable
private int count;
/**
* Create an empty List
*/
public List() {
this.head = null;
this.count = 0;
}
/**
* Function to insert a new node with data to the front
* of the linked list.
*
* @param data to store
*/
public void addFront(T data) {
// Create new node
Node<T> node = new Node<>(data);
// if empty, store at head
if(this.isEmpty()) {
head = node;
} else { // if the list is not empty
node.setNext(head); // Set the head to the next pointer of
// new node.
head = node; // make it first node
}
count++;
}
/**
* Function to add the new node with data at the end of the List.
*
* @param data to store
*/
public void addBack(T data) {
// check if empty
if(this.isEmpty()) {
this.addFront(data);
} else {
// create new node
Node<T> node = new Node<>(data);
// means list is not empty
// add to the end of the
Node<T> current = head;
// navigate to last node
while(current.getNext() != null) {
current = current.getNext();
}
// here we set the new node to next reference of last node
current.setNext(node);
count++;
}
}
/**
* Remove an element from the Linked List.
*
* @param data to remove - first occurrence
* @return indicate operation is successful or failed
*/
public boolean remove(T data) {
// Case 1: check if list is empty
if(this.isEmpty()) {
return false;
}
// Case 2: Data exist at the front of the list.
if(head.getData().equals(data)) {
// using equals: This will compare actual object with data inside it
// using ==: this will only compare references not the actual object
// == is good for instrinsic types: int, float, double, char etc
// equals needed to be used for objects like Float, Integer, String,
head = head.getNext();
count--;
return true;
} else {
// node may exist between other nodes, or last node
// navigate to find the node to remove
Node<T> current = head;
Node<T> pre = null;
while(current != null) {
// check node data here
if(current.getData().equals(data)) {
pre.setNext(current.getNext()); // skip the current node
count--;
return true;
}
// update navigation pointers
pre = current;
current = current.getNext();
}
}
return false; // node not found with data
}
/**
* Count the number of elements in list.
*
* @return number of nodes
*/
public int size() {
return count;
}
/**
* Display the List to screen.
*/
public void print() {
if(this.isEmpty()) {
System.out.println("List is Empty");
return;
}
// print something like [1, 2, 3, 4, 5]
System.out.print("[");
if(!this.isEmpty()) {
System.out.printf("%s", head.getData());
}
Node<T> current = head.getNext();
while(current != null) {
System.out.printf(", %s", current.getData());
current = current.getNext();
}
System.out.println("]");
}
/**
* Get the first element
*
* @return first element
*/
public T getFront() {
return head.getData();
}
/**
* Check that List is empty.
*
* @return indicate if the list is empty
*/
public boolean isEmpty() {
return head == null;
}
}
GenericSinglyLinkedListTest
* Client code to test the Generic Singly Linked List.
*
* @author CodingHelpLine
* Website: https://codinghelpline.org
*/
public class GenericSinglyLinkedListTest {
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
// Test with Integers
List<Integer> intList = new List<>();
// lets print state of list
System.out.printf("Size of List: %d%n", intList.size());
System.out.printf("Is List empty: %s%n", intList.isEmpty());
// insert data
System.out.println("Insert to front 4 to the list");
intList.addFront(4);
System.out.printf("Size of List: %d%n", intList.size());
System.out.println("List is Now:");
intList.print();
System.out.println("");
System.out.println("Insert to front 7 to the list");
intList.addFront(7);
System.out.printf("Size of List: %d%n", intList.size());
System.out.println("List is Now:");
intList.print();
System.out.println("");
System.out.println("Insert to Back 8 to the list");
intList.addBack(8);
System.out.printf("Size of List: %d%n", intList.size());
System.out.println("List is Now:");
intList.print();
System.out.println("");
System.out.println("Insert to Back 10 to the list");
intList.addBack(10);
System.out.printf("Size of List: %d%n", intList.size());
System.out.println("List is Now:");
intList.print();
System.out.println("");
// Test remove
while(!intList.isEmpty()) {
Integer x = intList.getFront();
System.out.printf("Front Element: %d%n", x.intValue());
intList.remove(x);
System.out.printf("Size of List: %d%n", intList.size());
System.out.println("List is Now:");
intList.print();
System.out.println("");
}
List<String> strList = new List<>();
strList.addFront("John");
strList.addBack("Marry");
strList.addFront("Peter");
strList.addBack("Smith");
strList.print();
// remove
while(!strList.isEmpty()) {
String str = strList.getFront();
System.out.printf("Element at front: %s%n", str);
strList.remove(str);
}
}
}