Java Single Linked List Implementation - Welcome to Java Data structure and Algrothm Part One
Hello everyone
It has been long since I have never posted new updates in my blog, missing all of you.
It is difficult maintain posting regularly, as I am student and focused on learning, I share what I have learned properly, that's why all of my post possess high-quality, error-free, well-explained every topic.
Okay I am assuming that, you come here to learn implementation of Linked List which is quite easy but if you beginner like me, it is hard to understand what is going on screen, code and so on!
As I have told you I am beginner, so I will make this lesson beginner friendly so that you can easily understand everything, but make sure you have 100% attention of what is going on screen, codes, and so on.
What is Linked List? Why should we use this??
Okay good question. Linked List is reffered to a Data Structure where every data Stay in Linear, or parallel.
The main idea behind a Linked List is to Class that has a child class like Node, which is used to store data like Array, but it follow to store data in Linear methodology, also for fetch and update or delete data by Key or index follows same.
Why to use Linked List?
There are some cases where Linked List is perfect then any other Data Structure, For instance Stack, Queue, or any other Abstract Data types, beacuse of efficient insert and deletion operation.
Okay, how can I make a Linked List class? can you show example in Java??
That's why I am here! now, I am going to show how to create Linked List class, by step by step tutorial.
This LinkedList Class will store integer data, and LinkedList is represented by it's head pointer, If need to insert something in it, we need to travers the list till last node, then create a new node. Okay let's start!
First Step: Create a Class Named LinkedList and inside parent class create a new Child static Class named Node
If you can't do this so, look at this code, and write code like this!
Note: Do not copy and paste, just write in your IDE.
Code From here:
// Java program to implement
// a Singly Linked List
public class LinkedList {
Node head; // head of list
// Linked list Node.
// This inner class is made static
// so that other class can access it
static class Node {
int data;
Node next;
// Constructor
Node(int d){
data = d;
next = null;
}
}
So, we have created LinkedList class with subclass Node, Let's how to write a method that perform insertation operation?
carefully look at this static method, this method can do your job.
Code from here:
// Method to insert a new node
public static LinkedList insert(LinkedList list, int data)
{
// Create a new node with given data
Node new_node = new Node(data);
new_node.next = null;
// If the Linked List is empty,
// then make the new node as head
if (list.head == null) {
list.head = new_node;
}
else {
// Else traverse till the last node
// and insert the new_node there
Node last = list.head;
while (last.next != null) {
last = last.next;
}
// Insert the new_node at last node
last.next = new_node;
}
// Return the list by head
return list;
}
Interesting, umm easy to implement! so how to perform deletion operation by key?
Hmm, now I am going to write a method that can perform deletion operation by key.
Code from here:
// Method to delete a node in the LinkedList by KEY
public static LinkedList deleteByKey(LinkedList list, int key)
{
// Store head node
Node currNode = list.head, prev = null;
// If the key at the head of Node
if (currNode != null && currNode.data == key) {
list.head = currNode.next; // Changed head
// Display the message
System.out.println(key + " found and deleted");
// Return the updated List
return list;
}
// If the key is somewhere other than at head
// Search for the key to be deleted,
// keep track of the previous node
// as it is needed to change currNode.next
while (currNode != null && currNode.data != key) {
// If currNode does not match with key
// continue to next node
prev = currNode;
currNode = currNode.next;
}
// If the key was present, it should be at currNode
// Therefore the currNode shall not be null
if (currNode != null) {
// Since the key is at currNode
// Unlink currNode from linked list
prev.next = currNode.next;
// Display the message
System.out.println(key + " found and deleted");
}
// If key was not present in linked list
// currNode should be null
if (currNode == null) {
// Display the message
System.out.println(key + " not found");
}
// return the List
return list;
}
How to perform deletion operation by index in LinkedList? can you implement this??
Hmm, this is very easy, believe me! Now going to write a method that can do this job.
Code from here:
// Method to delete a node in the LinkedList by POSITION
public static LinkedList deleteAtPosition(LinkedList list, int index)
{
// Store head node
Node currNode = list.head, prev = null;
// If index is 0, then head node itself is to be deleted
if (index == 0 && currNode != null) {
list.head = currNode.next; // Changed head
// Display the message
System.out.println(index + " position element deleted");
// Return the updated List
return list;
}
// If the index is greater than 0 but less than the size of LinkedList
// The counter
int counter = 0;
// Count for the index to be deleted,
// keep track of the previous node
// as it is needed to change currNode.next
while (currNode != null) {
if (counter == index) {
// Since the currNode is the required position
// Unlink currNode from linked list
prev.next = currNode.next;
// Display the message
System.out.println(index + " position element deleted");
break;
}
else {
// If current position is not the index
// continue to next node
prev = currNode;
currNode = currNode.next;
counter++;
}
}
// If the position element was found, it should be at currNode
// Therefore the currNode shall not be null
// CASE 3: The index is greater than the size of the LinkedList
// In this case, the currNode should be null
if (currNode == null) {
// Display the message
System.out.println(index + " position element not found");
}
// return the List
return list;
}
Hmm sounds interesting, Okay, How can make them back to String when I have finished the work? can you do this??
Why not? I can do this. Okay let's create a method that can take LinkedList as Input, and get them return in String format.
Code from here:
// Method to return the String of LinkedList
public static String linkedListToString(LinkedList list)
{
//store current node head
Node currNode = list.head;
StringBuilder sb = new StringBuilder();
while(currNode != null){
sb.append(currNode.data+" ");
currNode = currNode.next;
}
return sb.toString();
}
Hmm, sometime we might be need to calculate current Linked List Size, is your Linked List class have implementation for this?
Yeah, it offers same facility that you mentioned. Okay, let's look this method that can calculate Linked List Length, and return size in Integer.
Code from here:
//method to get linked list size
public static int getLinkedListSize(LinkedList list){
//store current node head
Node currNode = list.head;
int count = 0; //Intitial count
//the currentNode is not null so we increase the count
while(currNode != null){
count++;
currNode = currNode.next;
}
//return total size of LinkedList
return count;
}
Wow, Linked List is very easy! Very easy! Okay, suppose I am looking for a value that located at a index, for example, the following Linked List is: 1,5,3,4,2 and I am Looking for value of index number 5 this index holds value of 2, how to achieve that?
Hmm good question indeed. For your help, I have written a method that can do this job!
Code from here:
//Get value of LinkedList at a requested index
public static int getAtIndex(LinkedList list, int index){
//store current node head
Node currNode = list.head;
int count = 0;
while(currNode != null){
count++;
if(count == index){
return currNode.data;
}
else{
currNode = currNode.next;
}
}
//If requested index is larger then Linked List length
if(count < index){
System.out.println(index+" This requested index is not exists!!");
return new Integer(0);
}
return 0;
}
Sounds interesting! can I code of the Full Linked List Class??
Hmm, the full code of Linked List Class is here:
Code from here:
import java.io.*;
// Java program to implement
// a Single Linked List
public class LinkedList {
Node head; // head of list
// Linked list Node.
// This inner class is made static
// so that other class can access it
static class Node {
int data;
Node next;
// Constructor
Node(int d){
data = d;
next = null;
}
}
// Method to insert a new node
public static LinkedList insert(LinkedList list, int data)
{
// Create a new node with given data
Node new_node = new Node(data);
new_node.next = null;
// If the Linked List is empty,
// then make the new node as head
if (list.head == null) {
list.head = new_node;
}
else {
// Else traverse till the last node
// and insert the new_node there
Node last = list.head;
while (last.next != null) {
last = last.next;
}
// Insert the new_node at last node
last.next = new_node;
}
// Return the list by head
return list;
}
// Method to return the String of LinkedList
public static String linkedListToString(LinkedList list)
{
//store current node head
Node currNode = list.head;
StringBuilder sb = new StringBuilder();
while(currNode != null){
sb.append(currNode.data+" ");
currNode = currNode.next;
}
return sb.toString();
}
// Method to delete a node in the LinkedList by KEY
public static LinkedList deleteByKey(LinkedList list, int key)
{
// Store head node
Node currNode = list.head, prev = null;
// If the key at the head of Node
if (currNode != null && currNode.data == key) {
list.head = currNode.next; // Changed head
// Display the message
System.out.println(key + " found and deleted");
// Return the updated List
return list;
}
// If the key is somewhere other than at head
// Search for the key to be deleted,
// keep track of the previous node
// as it is needed to change currNode.next
while (currNode != null && currNode.data != key) {
// If currNode does not match with key
// continue to next node
prev = currNode;
currNode = currNode.next;
}
// If the key was present, it should be at currNode
// Therefore the currNode shall not be null
if (currNode != null) {
// Since the key is at currNode
// Unlink currNode from linked list
prev.next = currNode.next;
// Display the message
System.out.println(key + " found and deleted");
}
// If key was not present in linked list
// currNode should be null
if (currNode == null) {
// Display the message
System.out.println(key + " not found");
}
// return the List
return list;
}
// Method to delete a node in the LinkedList by POSITION
public static LinkedList deleteAtPosition(LinkedList list, int index)
{
// Store head node
Node currNode = list.head, prev = null;
// If index is 0, then head node itself is to be deleted
if (index == 0 && currNode != null) {
list.head = currNode.next; // Changed head
// Display the message
System.out.println(index + " position element deleted");
// Return the updated List
return list;
}
// If the index is greater than 0 but less than the size of LinkedList
// The counter
int counter = 0;
// Count for the index to be deleted,
// keep track of the previous node
// as it is needed to change currNode.next
while (currNode != null) {
if (counter == index) {
// Since the currNode is the required position
// Unlink currNode from linked list
prev.next = currNode.next;
// Display the message
System.out.println(index + " position element deleted");
break;
}
else {
// If current position is not the index
// continue to next node
prev = currNode;
currNode = currNode.next;
counter++;
}
}
// If the position element was found, it should be at currNode
// Therefore the currNode shall not be null
// CASE 3: The index is greater than the size of the LinkedList
// In this case, the currNode should be null
if (currNode == null) {
// Display the message
System.out.println(index + " position element not found");
}
// return the List
return list;
}
//method to get linked list size
public static int getLinkedListSize(LinkedList list){
//store current node head
Node currNode = list.head;
int count = 0; //Intitial count
//the currentNode is not null so we increase the count
while(currNode != null){
count++;
currNode = currNode.next;
}
//return total size of LinkedList
return count;
}
public static int getAtIndex(LinkedList list, int index){
//store current node head
Node currNode = list.head;
int count = 0;
while(currNode != null){
count++;
if(count == index){
return currNode.data;
}
else{
currNode = currNode.next;
}
}
//If requested index is larger then Linked List length
if(count < index){
System.out.println(index+" This requested index is not exists!!");
return new Integer(0);
}
return 0;
}
}
Okay, I am little confused to use this class, as I am beginner, can't understand use case of this class. can you please.....
Hmm that's why I am here. You need to create a new class name DriverLinkedList and paste following code:
Code from here:
public class DriverLinkedList
{
public static void main(String[] arg){
//Create a instance
LinkedList lst = new LinkedList();
lst = lst.insert(lst, 1);
lst = lst.insert(lst, 2);
lst = lst.insert(lst, 3);
lst = lst.insert(lst, 4);
lst = lst.insert(lst, 5);
lst = lst.insert(lst, 6);
lst = lst.insert(lst, 7);
lst = lst.insert(lst, 8);
lst = lst.insert(lst, 9);
lst = lst.insert(lst, 10);
//Show added linked list in string format
System.out.println(lst.linkedListToString(lst));
//insert linebreak
System.out.println("\n\n");
//Let's remove by key!
lst = lst.deleteByKey(lst, 5);
//insert linebreak
System.out.println("\n\n");
lst = lst.deleteByKey(lst, 6);
//insert linebreak
System.out.println("\n\n");
//Show Linked List again
System.out.println(lst.linkedListToString(lst));
//insert linebreak
System.out.println("\n\n");
//Let's remove by index
lst = lst.deleteAtPosition(lst, 1);
//insert linebreak
System.out.println("\n\n");
lst = lst.deleteAtPosition(lst, 2);
//insert linebreak
System.out.println("\n\n");
//show the Linked list
System.out.println(lst.linkedListToString(lst));
//insert linebreak
System.out.println("\n\n");
//Throwing some exception!
lst = lst.deleteAtPosition(lst, 100);
//insert linebreak
System.out.println("\n\n");
lst = lst.deleteAtPosition(lst, 100);
//insert linebreak
System.out.println("\n\n");
//Show the linked list
System.out.println(lst.linkedListToString(lst));
//insert linebreak
System.out.println("\n\n");
//Show Linked List Length
System.out.println("Linked List Length is: "+lst.getLinkedListSize(lst));
//insert linebreak
System.out.println("\n\n");
//get value from a index
System.out.println("Value of 5 index is: "+lst.getAtIndex(lst, 5));
//insert linebreak
System.out.println("\n\n");
//Throw a error for get a index that is not exists
System.out.println(lst.getAtIndex(lst, 10));
}
}
Comments
Post a Comment
Wow nice post!