Linked List Basics

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;}
    }
}

Download Code

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;
	}

}

Download Code

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();
}
}

Download Code

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();
}
}

Download Code

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();
	}

}

Download Code

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();
	}

}

Download Code

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();
	}

}

Download Code

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();
}

Download Code

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");
		
	}

}

Download Code

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());
	}

}

Download Code

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));
		
	}

}

Download Code

Github Link: https://github.com/aarushi-nema/data-structure/tree/master/src/linkedlist

References:

  1. https://www.geeksforgeeks.org/
  2. Data Structures and Algorithms (by Narasimha Karumanchi)

Leave a Reply

PHP JS HTML CSS BASH PYTHON CODE

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: