Understanding Linked List Concepts Using Pseudo Codes And Examples In Java



Singly Linked List  is another Data Structure that store and organize the data into memory. 

In this chapter we will discuss about linked list features, use, different operations and java implementation. If you are not aware about data structure basics, please go through with the link given below.
Click here to know more about basics of data structure


1.
Linked List comes in non-primitive category and it is Linear Lists type data structure. Linear list means data stores in sequential order.

2.

Linked List comes in dynamic data structure category i.e. there is no list size limitation. 

Queue and Stack can be also implemented by linked list to make them dynamic.


3.

In Linked List every element known as node, and every node is separate with each other. 

Initially each node contains value and null as address. Usually where the value stores in node known as data and where the address stores known as next.



Linked List Node definition
Linked List Node Definition. ByTechAchievers.com

4.

Linked List can be defined in three different types, Singly Linked List, Doubly Linked List and Circular Linked List.

Here we will learn about singly linked list, I will discuss other in next chapters.

Operations Of LinkedList -  


Let’s discuss about the operations that we perform with List


insertion()  


This operation is to insert node into LinkedList from start, end or from any index.

deletion ()


This operation is to remove node from LinkedList from the start,end or from any index.
     
traverse()

This operation is to display all node elements of LinkedList.



How LinkedList Works – Implementation

Singly LinkedList -


As the name suggests it is initial type of List, each node contains address of next node. 


Singly List takes less memory per node. While traversing or reading lists, it traverse in single direction.



 Insertion Process


Every first element would be known as start node and last element would be known as end node. Initially start and end both are set as null.


On every insertion new node will created. Every node contains data value and address of the next node. Initially the address of next node will set as null. 


Let’s understand with pseudo code …


startNode = null;

endNode = null;

//create new node
Node newNode = createNode;


//Set data value and node address
newNode -> value = dataValue

newNode -> next = null.
note :Above code is the common for every insertion process.


Insertion from beginning

If it is first node i.e. it is the only one node of the list.


if (start = null ) {

start = newNode

end = newNode

}
If it is not first node, every new node will be added from start.

Current start node of list will contain new node address. 

New node would become new start. End node would remain same.

Linked List -Insertion from beginning

Singly Linked List: Insertion from start. ByTechAchievers.com

Insertion from end

If it is first node i.e. it is the only one node of the list.

if (start = null ) {

start = newNode

end = newNode

}
If it is not first node, every new node will be added from end

Current end of the list will contain new node address. 

New node would become new end.

Start node would remain same.

else {

end -> next = newNode;

end = newNode;

}          
Linked List -Insertion from end

Singly Linked List: Insertion from end. ByTechAchievers.com



Insertion at any index


Assume we have to put node into Nth position.
Assuming that we have list of nodes and we have to add new node at Nth position. Traverse the list and track the Nth position node and  previous node as well. 

Previous node's next will contain address of new node and new node's next will contain Nth node's address.

count = 1

if (start != null ) {

    traverseList() // please find its implementation below

    if ( count == N ) {

      previousNode ->next = newNode;

      newNode ->next = NNode; 

    }
}

Linked List - Insertion at any index
Singly Linked List: Insertion at any index. ByTechAchievers.com

Traversing The List -

First check start should not be null i.e. list is not null. We have to read list from start to end so that we will take new temp node that will work as a point to each node.

if ( start != null ) {

    tempNode = start;

    while ( tempNode ->next != null ) {

       print tempNode ->data;

       tempNode = tempNode -> next ;
    }

}
While loop will read list until tempNode is null.

tempNode starts with start node , it prints first node's data then tempNode will point to tempNode -> next which is the next node address of the list. 


Deletion Process -

First check start should not be null i.e. list is not null.

If start is null that is list is empty and message will be printed.

if ( start == null ) {

print "List is empty, can not remove element."

}


Deletion from beginning

As we know every node contains the address of next node.

When deletion happens from start then next address would become new start of the list.

else {

start = start -> next;

}

Deletion from end

When deletion happens from end then previous node would become as new end of the list.

To get the previous node we have to traverse the list, as we know that we can't get previous node address from end node. 

Make sure new end will have null value in next block. Put start node into temp, while traversing start should not be impacted.

else {

tempNode = start;

   while ( tempNode != null ) {

     if (tempNode->next == end) {  

       previousNode = temp; 

      }

  } //end of loop

end = previousNode;

end -> next = null;  

}

Deletion from any index

When deletion happens from any index then first we will reach to the specific index.

Assume we want to remove Nth node.

Put Nth node's next address to the previous node's next.

Put start node into temp, while traversing start should not be impacted.

Start counting node till N.

else {

count = 1; 

tempNode = start;

   while ( tempNode ->next != null ) {

      if ( count == N - 1 ) {      

         previousNode = temp;
    
     }

      if ( count == N ) { // removing Nth node

         previous -> next = temp -> next;

         break; // break the loop 
     }

  } //end of loop

} // end of else
Linked List - Deletion from beginning, end and from any index
Singly Linked List: Deletion from start, end and at any index. 
ByTechAchievers.com



Singly Linked-List Example In Java

class Node {

   
    Integer data;


    Node next;
   

    private static Node start = null;
   

    private static Node end = null;
   

    private static  Node temp = null;
   

    private static Node previousNode = null;


    Node (Integer aData, Node aNext) {
       

        this.data = aData;
       

        this.next = aNext; 

    }


    public static void insertionFromBeginning(Node aNode){
       

        if ( start == null ){
           

            System.out.println("First Node Creation ...\n");

           
            start = aNode;

            end   = aNode;  

        }


        else{       

            aNode.next = start;


            start = aNode;

        }

    }


    public static void insertionFromEnd(Node aNode){

          
            end.next = aNode;
           

            end = aNode;  

    }

   
    public static void insertionAtAnyIndex(Node aNode, int index){

       
        int count = 1;
       

        temp = start;

  

        if (start != null ) {


        while (temp!=null){

           
             if ( index == 1 ) {


                insertionFromBeginning(aNode);
   

            }
           

             if ( count == index-1 ) {

              
                 previousNode = temp;
                

            }


            else if ( count == index ) {

 
                 previousNode.next = aNode;
   

                 aNode.next = temp;
                

            }
           

            count ++;
           

            temp = temp.next;               

        }

    }       

}   

    public static void deletionFromBeginning(){

       
        if(start == null || end == null){
           

            System.out.println(" List is empty");           

        }

        else{

             start = start.next;              

        }       

    }

   
    public static void DeletionFromEnd(){

       
        temp = start;
       

        while (temp!=null){

           
            if(temp.next == end){
               

                previousNode = temp;

            }           

            temp = temp.next;           

        }
       
        end = previousNode;
      
        end.next = null;

    }

  
    public static void deletionAtAnyIndex(int index){

      
        int count = 1;

        temp = start;


        if (start != null ) {


        while (temp!=null){
        

             if ( index == 1 ) {


                deletionFromBeginning();
              

            }
          
             if ( count == index-1 ) {
              

                 previousNode = temp;
                

            }
      

            else if ( count == index ) {


                 previousNode.next = temp.next;                

            }           

            count ++;
           
            temp = temp.next;
               
        }
   

      }

    }


    public static void traverseList(){

       
        if ( start == null ){  

            System.out.println(" List is empty ...");

        }
      
        else{
           

            temp = start;
  

            while (temp!=null) {
      

                System.out.println( "Node Value - "+temp.data);

               
                temp = temp.next;

            }   

        }   

    }

}

public class SinglyLinkedListExample{


     public static void main(String []args){
        

        System.out.println(" \nInsertion from beginning\n ");
    

        Node.insertionFromBeginning ( new Node (1,null));
       

        Node.insertionFromBeginning ( new Node (2,null));
       

        System.out.println(" \nTraverse List - process\n ");
       

        Node.traverseList();

       
        System.out.println(" \nInsertion from end\n ");
       

        Node.insertionFromEnd( new Node (3,null));
       

        Node.insertionFromEnd( new Node (4,null));

       
        System.out.println(" \nTraverse List - process\n ");
       

        Node.traverseList();

       
        System.out.println(" \nInsertion at N index\n ");

        
        Node.insertionAtAnyIndex ( new Node (5,null),2);
       

        System.out.println("\nTraverse List - process\n ");
       

        Node.traverseList();
       

        System.out.println("\nDeletion - process from beginning\n ");
       

        Node.deletionFromBeginning();
       

        System.out.println("\nTraverse List - process\n ");

       
        Node.traverseList();

       
        System.out.println("\n Deletion from end \n");

        Node.DeletionFromEnd();

       
        System.out.println("\nTraverse List- process\n ");
       

        Node.traverseList();

       
        System.out.println("\n Deletion from N Index\n");
       

        Node.deletionAtAnyIndex(2);
       

        System.out.println("\n Traverse List process\n ");
       

        Node.traverseList();

       
     }

} 

OUTPUT - 

Insertion from beginning

First Node Creation ...

Traverse List - process

Node Value - 2

Node Value - 1

Insertion from end

Traverse List - process

Node Value - 2

Node Value - 1

Node Value - 3

Node Value - 4

Insertion at N index

Traverse List - process

Node Value - 2

Node Value - 5

Node Value - 1

Node Value - 3

Node Value - 4

Deletion - process from beginning

Traverse List - process

Node Value - 5

Node Value - 1

Node Value - 3

Node Value - 4

Deletion from end

Traverse List- process

Node Value - 5

Node Value - 1

Node Value - 3

Deletion from N Index

Traverse List process

Node Value - 5

Node Value - 3
Doubly LinkedList -

It is another type of List, each new node contains address of next node and previous node will have address of new node. 

It gives tight coupling, while traversing linked list we can traverse it in both directions.

Click here for "Doubly Linked List Implementation"

Circular LinkedList -

Circular linked list is a form of connecting nodes in circular form. 

We can make singlyList or Doubly LinkedList as circular list.Each first node has the address of last node and last node will have address of first node. 

Circular linked list are generally used with time sharing problems, scheduling management, operating system operations etc.

Click here for Circular Linked List Implementation



No comments

Powered by Blogger.