Imagine you are taking part in a treasure hunt game. The first thing you’d have to do is to find the first clue which would lead you to the second clue and that would lead you to the third clue and so on. To get something in the middle, or at the end, the only way to get to it is to follow this list from the beginning (or to cheat 😉 ).
In technical language- A Linked List is a linear collection of data elements, whose order is not given by their physical placement in memory. Instead, each element points to the next. It is a data structure consisting of a collection of nodes which together represent a sequence.
Where arrays are stored in contiguous memory locations, in linked lists each “node” is at a random location in the memory. Each element in a linked list is stored in the form of a node.
So a node is like a box having two compartments. One side of the box contains the Data while the other side contains the address(in other words, a link) of the next node.
Note: The following coding exercises have been uploaded in JAVA.
Coding exercise 1: Representation of a Linked List
public class Program001Linked_List_Intro{
static class Linked_List{
Node head;
class Node{
int data;
Node next;
// Constructor to create a new node
// Next is by default initialized
// as null
Node (int d) { data= d;}
}
}Coding exercise 2: Creation of three nodes
//create three nodes in a linked list
public class Program002Create_Linked_List {
Node head;
static class Node{
int data;
Node next;
Node (int d){
data=d;
next=null;
}
}
public static void main ( String [] args){
Program002Create_Linked_List llist= new Program002Create_Linked_List();
llist.head = new Node (1);
Node second= new Node(2);
Node third = new Node(3);
llist.head.next= second;
second.next=third;
}
}Coding exercise 3: Traverse of a Linked List
//Traverse a Linked List
public class Program003Traverse_Linked_list {
Node head;
static class Node{
int data;
Node next;
Node (int d) {
data= d;
next= null;
}
}
public void printlist (){
Node n= head;
while(n!=null)
{
System.out.print(n.data + " ");
n=n.next;
}
}
public static void main (String [] args){
Program003Traverse_Linked_list llist= new Program003Traverse_Linked_list();
llist.head= new Node(1);
Node second= new Node (2);
Node third= new Node (3);
llist.head.next= second;
second.next=third;
llist.printlist();
}
}Coding exercise 4: Insert Node in beginning
//adding new node at beginning of linked list
public class Program004insert_node_in_beginning {
Node head;
static class Node{
int data;
Node next;
Node(int d)
{
data=d;
next= null;
}
}
public void printlist (){
Node n= head;
while (n!=null){
System.out.print(n.data + " ");
n=n.next;
}
System.out.println();
}
public void insertinbeginning (int new_data){
Node new_node= new Node(new_data);
new_node.next=head;
head= new_node;
}
public static void main(String [] args){
Program004insert_node_in_beginning llist= new Program004insert_node_in_beginning ();
llist.head= new Node(1);
Node second= new Node(2);
Node third= new Node(3);
llist.head.next=second;
second.next=third;
llist.printlist();
llist.insertinbeginning(0);
llist.printlist();
}
}Coding exercise 5: Insert Node in Middle
//inserting a node in the middle of linked list
public class Program005insert_node_in_middle {
Node head;
static class Node
{
int data;
Node next;
Node (int d)
{
data=d;
next= null;
}
}
public void printlist ()
{
Node n= head;
while(n!=null)
{
System.out.print(n.data+ " ");
n=n.next;
}
System.out.println();
}
public void insertinmiddle (Node prev_node, int new_data)
{
Node new_node= new Node(new_data);
new_node.next=prev_node.next;
prev_node.next=new_node;
}
public static void main (String [] args)
{
Program005insert_node_in_middle llist = new Program005insert_node_in_middle ();
llist.head= new Node (1);
Node second = new Node (2);
Node third= new Node(4);
llist.head.next=second;
second.next=third;
llist.printlist();
llist.insertinmiddle(second,3 );
llist.printlist();
}
}
Coding exercise 6: Insert Node at end
//inserting node at the end
public class Program006insert_node_at_end {
Node head;
static class Node
{
int data;
Node next;
Node(int d)
{
data= d;
next=null;
}
}
public void printlist()
{
Node n= head;
while(n!=null)
{
System.out.print(n.data+ " ");
n=n.next;
}
System.out.println();
}
public void insertatend (int new_data)
{
Node new_node= new Node(new_data);
Node n= head;
while(n.next!=null)
{
n=n.next;
}
n.next=new_node;
}
public static void main( String [] args)
{
Program006insert_node_at_end llist= new Program006insert_node_at_end();
llist.head= new Node(1);
Node second= new Node(2);
Node third= new Node(3);
llist.head.next= second;
second.next=third;
llist.printlist();
llist.insertatend(4);
llist.printlist();
}
}
Coding exercise 7: Delete node containing the number 1 (or anything else) as it’s data
//delete node
public class Program007delete_node {
Node head;
static class Node{
int data;
Node next;
Node (int d)
{
data=d;
next=null;
}
}
public void delete (int key)
{
Node temp= head, prev=null;
if(temp!=null && temp.data==key)
{
head=temp.next;
return;
}
while(temp!=null && temp.data!=key)
{
prev=temp;
temp=temp.next;
}
if(temp==null)return;
prev.next=temp.next;
}
public void printlist()
{
Node n= head;
while(n!=null)
{
System.out.print(n.data +" ");
n=n.next;
}
System.out.println();
}
public static void main(String [] args)
{
Program007delete_node llist= new Program007delete_node();
llist.head= new Node(2);
Node second = new Node(3);
Node third= new Node(1);
Node fourth= new Node(7);
llist.head.next= second;
second.next=third;
third.next=fourth;
llist.printlist();
llist.delete(1);
llist.printlist();
}
}
Coding exercise 8: Delete nth node
//delete nth node
public class Program008delete_nth_node {
Node head;
static class Node{
int data;
Node next;
Node (int d)
{
data=d;
next=null;
}
}
public void delete(int key)
{
Node temp= head, prev=null;
int k=0;
while(temp!=null && k!=key)
{
prev=temp;
temp=temp.next;
k++;
}
if(temp==null)return;
prev.next=temp.next;
}
public void printlist()
{
Node n=head;
while(n!=null)
{
System.out.print(n.data+ " ");
n=n.next;
}
System.out.println();
}
public static void main (String [] args)
{
Program008delete_nth_node llist= new Program008delete_nth_node();
llist.head= new Node (1);
Node second= new Node(2);
Node third= new Node(3);
Node fourth= new Node(4);
llist.head.next= second;
second.next=third;
third.next=fourth;
llist.printlist();
llist.delete(2);
llist.printlist();
}Coding exercise 9: Delete Linked List
//delete a linked list
public class Program009delete_Linked_list {
Node head;
static class Node{
int data;
Node next;
Node (int d)
{
data=d;
next=null;
}
}
public void delete()
{
head=null;
}
public void printlist()
{
Node temp=head;
while(temp!=null)
{
System.out.print(temp.data+ " ");
temp=temp.next;
}
}
public static void main(String [] args)
{
Program009delete_Linked_list llist= new Program009delete_Linked_list();
llist.head = new Node(1);
Node second= new Node(2);
Node third= new Node(3);
llist.head.next=second;
second.next= third;
System.out.print("Linked List ");
llist.printlist();
System.out.println(" will be deleted");
System.out.println("Linked List deleted");
}
}
Coding exercise 10: Finding Length of a linked list (Iterative Method)
//find the length of a linked list (iterative method)
public class Program010length_of_Linked_List_Iterative {
Node head;
static class Node{
int data;
Node next;
Node(int d)
{
data=d;
next=null;
}
}
public int get_length()
{
Node n=head;
int length=0;
while(n!=null)
{
length++;
n=n.next;
}
return length;
}
public void printlist()
{
Node n=head;
while(n!=null)
{
System.out.print(n.data +" ");
n=n.next;
}
System.out.println();
}
public static void main ( String [] args)
{
Program010length_of_Linked_List_Iterative llist= new Program010length_of_Linked_List_Iterative();
llist.head= new Node(1);
Node second= new Node(2);
Node third= new Node(3);
llist.head.next= second;
second.next=third;
llist.printlist();
System.out.println("Length of linked list "+ llist.get_length());
}
}
Coding Exercise 11: Finding length of a linked list (Recursive Method)
//length of linked list (recursive)
public class Program011length_of_linked_list_Recursive {
Node head;
static class Node{
int data;
Node next;
Node(int d)
{
data=d;
next=null;
}
}
public int find_length(Node node)
{
if(node==null)
return 0;
else
return 1+find_length(node.next);
}
public void printlist()
{
Node n=head;
while(n!=null)
{
System.out.print(n.data+ " ");
n=n.next;
}
System.out.println();
}
public static void main (String [] args)
{
Program011length_of_linked_list_Recursive llist= new Program011length_of_linked_list_Recursive();
llist.head= new Node(1);
Node second= new Node(2);
Node third= new Node(3);
llist.head.next=second;
second.next=third;
llist.printlist();
System.out.println("Length of linked list: "+ llist.find_length(llist.head));
}
}
Github Link: https://github.com/aarushi-nema/data-structure/tree/master/src/linkedlist
References:
- https://www.geeksforgeeks.org/
- Data Structures and Algorithms (by Narasimha Karumanchi)