Thursday , 4 June 2020
Home » Class 12 » Some Operations on Linked List using Java

Some Operations on Linked List using Java

Watch this video first :



DOWNLOAD PDF NOTES : Download PDF


This brief article will cover just few of the basics of Linked lists and not go into its details. In ISC Computer Science you will get a maximum of 4 marks and a minimum of 2 marks from this portion of linked lists in Part II, Section C.

A node (list) is defined as a storage space which contains two fields, data and link. Data field stores data item and link field contains the address of the next list.

single node linked list

If you use a list shown above represented by an object ‘ptr‘ of a class ‘Node‘, then to handle its contents the following statements can be applied:

ptr.data // to access the data field of node ptr
ptr.link // to access the link field of node ptr

Single linked lists is a connection of various lists in such a way that each list has the address of the next list. In this system,control can only proceed in the forward direction but not in backward direction. Link of the last node is NULL which indicates end of the linked list structure.

linked list java

Traversing a Single Linked List :

If the class definition of a linked list is:

class Node
{
int data;
Node link;
}

Then the ALGORITHM for traversal will be:

Step 1 : Start
Step 2 : Set temporary pointer to the start node
Step 3 : Repeat Steps 4 and _____ until the pointer reaches null
Step 4 : ****** Do the asked operation Here ******
Step 5 : Move pointer to the next node
Step 6 : End

And the METHOD for traversal will be:

void traversal(Node start)
{
    Node ptr = new Node(start); //creating a temporary object and pointing it to the start node of the linked list
    while(ptr.link != null)
    {
        /* Do the asked operation here */
        ptr = ptr.link;
    }
}

EXAMPLES


1. Display all the data of a Linked List :

A linked list is formed from the objects of the class:

class Node
{
int data;
Node link;
}

Write an Algorithm OR a Method to display all the data in a linked list.
The method declaration is given below: void display(Node start)

Solution:

ALGORITHM:

Step 1 : Start
Step 2 : Set temporary pointer to the start node
Step 3 : Repeat Steps 4 and 5 until the pointer reaches null
Step 4 : Display data
Step 5 : Move pointer to the next node
Step 6 : End

METHOD:

void display( Node start )
{
    Node temp = new Node(start);                                       
    while(temp.link != null)
    {
        System.out.println(temp.data);
        temp = temp.link;
    }
}

2. Search for a value in a Linked List

A linked list is formed from the objects of the class:

class Node
{
int data;
Node link;
}

Write an Algorithm OR a Method to search for a value in a linked list.
The method declaration is given below: void search(Node start, int value)

Solution:

ALGORITHM:

Step 1 : Start
Step 2 : Set temporary pointer to start node
Step 3 : Set message to “Number Not Found”
Step 4 : Repeat Steps 5 and 6 until the pointer reaches null.
Step 5 : If data equals to value
              then set message to “Number found”
              Exit
Step 6 : Move pointer to the next node
Step 7 : Display message
Step 8 : End

METHOD:

void search( Node start, int value )
{
    Node temp = new Node(start); 
    String message = "Number Not Found";
    while(temp.link != null)
    {
        if(temp.data == value)
        {
            message = "Number Found";
            break;
        }
        temp = temp.link;
    }
    System.out.println(message);
}

3. Insert (add) a node in the beginning of a Linked List :

In the below code, ‘start’ denotes the start node and ‘x’ denotes the value to be inserted in the new node:

ALGORITHM:

Step 1 : Start
Step 2 : Create a new node and assign ‘x’ to data
Step 3 : Point new node to first node
Step 4 : Set start node to new node
Step 5 : End

METHOD:

void addBeginning( Node start, int x )
{
    Node ob = new Node(start);                                      
    ob.data = x;
    ob = ob.link;
    start = ob;
}

4. Insert (add) a node after ‘n’ nodes in a Linked List :

In the below code, ‘start’ denotes the start node, ‘x’ denotes the value to be inserted in the new node and ‘n’ denotes the number of nodes after which the new node is to be added:

ALGORITHM:

Step 1 : Start
Step 2 : Set temporary pointer to start node
Step 3 : Repeat Step 4 until the pointer
              reaches nth node
Step 4 : Move pointer to the next node
Step 5 : Create a new node and assign ‘x’ to data
Step 6 : Point new node to the next node
Step 7 : Set temporary pointer to new node
Step 8 : End

METHOD:

void addMiddle( Node start, int x, int n )
{
    Node temp = new Node(start);
    int count = 1;
    while(count <= n)
    {
        temp = temp.link; 
        count ++;
    }
    Node ob = new Node(start);
    ob.data = x;                                               
    ob = temp.link;
    temp = ob;
}

5. Insert (add) a node at the end of a Linked List :

In the below code, ‘start’ denotes the start node and ‘x’ denotes the value to be inserted in the new node:

ALGORITHM:

Step 1 : Start
Step 2 : Set temporary pointer to start node
Step 3 : Repeat Step 4 until the pointer
              reaches null
Step 4 : Move pointer to the next node
Step 5 : Create a new node and assign ‘x’ to data
Step 6 : Set new node to null
Step 7 : Set temporary pointer to new node
Step 8 : End

METHOD:

void addEnd( Node start, int x )
{
    Node temp = new Node(start);
    while(temp.link != null)
    {
        temp = temp.link;
    }
    Node ob = new Node(start);  
    ob.data = x;                                               
    ob.link = null;
    temp = ob;
}

6. Insert (add) a node to a Linked List (Combining above 3):

In the below code, ‘start’ denotes the start node and ‘x’ denotes the value to be inserted in the new node:

ALGORITHM:

Step 1 : Start
Step 2 : Accept info for the node to be added
Step 3 : Create a new node and assign ‘x’ to data
Step 4 : if node is to be added in front then
              Point new node to the first node
              Set start node to new node
              Stop
              else go to step 5
Step 5 : Set temporary pointer to start node
Step 6 : Repeat Steps 6 to 8 until the pointer
              reaches null
Step 7 : Move pointer to next node.
Step 8 : if the desired node is found then
              Point new node to the next node
              Set temporary pointer to new node
              Exit
Step 9 : if desired node is not found then
              we add new node at the end
              Set new node to null
              Set temporary pointer to new node
Step 10: End

METHOD:

void addNode( Node start, int x )
{
    System.out.print("Enter info of the node to be deleted : ");
    int n = sc.nextInt();
    Node ob = new Node(start);                                    
    ob.data = x;
    if( n == 0)
    {
        ob = ob.link;                                                
        start = ob;                                                       
     }
     else
     {
        Node temp = new Node(start);
        int count = 1;
        while(temp.link != null)
        {
            temp = temp.link;
            count ++;
            if(n == count)
            {
                ob = temp.link;                                  
                temp = ob;
                break;
            }
        }
        if(temp.link == null)
        {
            ob.link = null; 
            temp = ob;
        }
     }
}

LINKED LIST : ISC BOARD QUESTIONS SOLVED


[ISC 2020]

A linked list is formed from the objects of the class Node. The class structure of the Node is given below

class Node
{
int n;
Node next; 

}

Write an Algorithm OR a Method to find the product of the integer numbers from an existing linked list.
The method declaration is as follows: void Product _ Node( Node str )

Solution:

ALGORITHM:

Step 1 : Start
Step 2 : Set temporary pointer to the start node
Step 3 : Set product to 1
Step 4 : Repeat Steps 5 and 6 until the pointer reaches null
Step 5 : Multiply ‘n’ to product
Step 6 : Move pointer to the next node
Step 7 : Display product
Step 8 : End

METHOD:

void Product _ Node( Node str )
{
    Node temp = new Node(str);
    int product = 1;
    while(temp.next != null)
    {
        product = product * temp.n;
        temp = temp.next;
    }
    System.out.println(product);
}

[ISC 2019]

A linked list is formed from the objects of the class Node. The class structure of the Node is given below:

class Node
{
int num;
Node next;
}

Write an Algorithm OR a Method to find and display the sum of even integers from an existing linked list.
The method declaration is as follows: void SumEvenNode( Node str )

Solution:

ALGORITHM:

Step 1 : Start
Step 2 : Set temporary pointer to the start node
Step 3 : Set sum to 0
Step 4 : Repeat Steps 5 and 6 until the pointer reaches null
Step 5 : If num is even then add it to sum
Step 6 : Move pointer to the next node
Step 7 : Display sum
Step 8 : End

METHOD:

void SumEvenNode ( Node str )
{
    Node temp = new Node(str);          
    int sum = 0;
    while(temp.next != null)
    {
        if(temp.num % 2 == 0)
        {
            sum = sum + temp.num;
        }
        temp = temp.next;
    }
    System.out.println(sum);
}

[ISC 2018]

A linked list is formed from the objects of the class Node. The class structure of the Node is given

class Node
{
int n;
Node link;
}

Write an Algorithm OR a Method to search for a number from an existing linked list.
The method declaration is as follows: void FindNode( Node str, int b )

Solution:

ALGORITHM:

Step 1 : Start
Step 2 : Set temporary pointer to start node
Step 3 : Set message to “Number Not Found”
Step 4 : Repeat Steps 5 and 6 until the pointer reaches null.
Step 5 : If n equals to b
              then set message to “Number found”
              Exit
Step 6 : Move pointer to the next node
Step 7 : Display message
Step 8 : End

METHOD:

void FindNode( Node str, int b )
{
    Node temp = new Node(str); 
    String message = "Number Not Found";
    while(temp.link != null)
    {
        if(temp.n == b)
        {
            message = "Number Found";
            break;
        }
        temp = temp.link;
    }
    System.out.println(message);
}


[ISC 2017]

A linked list is formed from the objects of the class Node. The class structure of the Node is given below:
class Node
{
int num;
 Node next;
 }

Write an Algorithm OR a Method to count the nodes that contain only odd integers from an existing linked list and returns the count.
The method declaration is as follows: int CountOdd( Node startPtr )

Solution:

ALGORITHM:

Step 1 : Start
Step 2 : Set temporary pointer to the start node
Step 3 : Set count to 0
Step 4 : Repeat Steps 5 and 6 until the pointer
              reaches null
Step 5 : If num is odd then
              increment counter
Step 6 : Move pointer to the next node
Step 7 : Return count
Step 8 : End

METHOD:

int CountOdd( Node startPtr )
{
    Node temp = new Node(startPtr);              
    int count = 0;
    while(temp.next != null)
    {
        if(temp.num % 2 != 0)
        {
            count++;
        }
        temp = temp.next;
    }
    return count;
}

[ISC 2016]

A linked list is formed from the objects of the class Node. The class structure Of the Node is given below:

class Node
{
String name;
Node next;
}

Write an Algorithm OR a Method to search for a given name in the linked list.
The method declaration is as follows: boolean searchName(Node start, String v)

Solution:

ALGORITHM:

Step 1 : Start
Step 2 : Set temporary pointer to start node
Step 3 : Set result to false
Step 4 : Repeat Steps 5 and 6 until the pointer reaches null.
Step 5 : If v equals to name
              then set result to true
              Exit
Step 6 : Move pointer to the next node
Step 7 : Return result
Step 8 : End

METHOD:

boolean searchName(Node start, String v)
{
    Node temp = new Node(start);
    boolean result = false;
    while(temp.next != null)
    {
        if(v.equals(temp.name))
        {
            result = true;
            break;
        }
        temp = temp.link;
    }
    return result;
}

[ISC 2015]

A linked list is formed from the objects of the class:

 class Nodes
{

int num;
Nodes next;
}

Write an Algorithm OR a Method to print the sum of nodes that contains only odd integers of an existing linked list.
The method declaration is as follows: void NodesCount( Nodes starPtr )

Solution:

ALGORITHM:

Step 1 : Start
Step 2 : Set temporary pointer to the start node
Step 3 : Set sum to 0
Step 4 : Repeat Steps 5 and 6 until the pointer reaches null
Step 5 : If num is odd then add it to sum
Step 6 : Move pointer to the next node
Step 7 : Display sum
Step 8 : End

METHOD:

void NodesCount( Nodes starPtr )
{
    Nodes temp = new Nodes(starPtr);
    int sum = 0;
    while(temp.next != null)
    {
        if(temp.num % 2 != 0)
        {
            sum = sum + temp.num;
        }
        temp = temp.next;
    }
    System.out.println(sum);
}

[ISC 2014]

A linked list is formed from the objects of the class:
class Node
{

int number;
Node nextNode;
}

Write an Algorithm OR a Method to add a node at the end of an existing linked list.
The method declaration is as follows: void addnode( Node start, int num )

Solution:

ALGORITHM:

Step 1 : Start
Step 2 : Set temporary pointer to the start node
Step 3 : Repeat Steps 4 until the pointer reaches null
Step 4 : Move pointer to the next node
Step 5 : Create a new node, assign num to number and nextNode to null
Step 6 : Set temporary pointer to the new node
Step 7 : End

METHOD:

void addnode( Node start, int num )
{
    Node temp = new Node(starPtr);                                      
    while(temp.nextNode != null)
    {
        temp = temp.nextNode;
    }
    Node ob = new Node();
    ob.number = num;
    ob.nextNode = null;
    temp.nextNode = ob;
}

[ISC 2013]

A linked list is formed from the objects of the class:

class Node
{
int item;
Node next;
}

Write an Algorithm OR a Method to count the number of nodes in the linked list.
The method declaration is given below: int count(Node ptr_start)

Solution:

ALGORITHM:

Step 1 : Start
Step 2 : Set temporary pointer to the start node
Step 3 : Set counter to 0
Step 4 : Repeat Steps 5 and 6 until the pointer reaches null
Step 5 : Increment the counter
Step 6 : Move pointer to the next node
Step 7 : Return counter
Step 8 : End

METHOD:

int count( Node ptr_start )
{
    Node temp = new Node(ptr_start);                                     
    int counter = 0;
    while(temp.next != null)
    {
        counter++;
        temp = temp.next;
    }
    return counter;
}

[ISC 2012]

A linked list is formed from the objects of the class:

class node
{
int p;
String n;
node next;
}

Write an Algorithm OR a Method to search for a name and display the contents of that node.
The method declaration is given below: void search(node start, String b)

Solution:

ALGORITHM:

Step 1 : Start
Step 2 : Set temporary pointer to start node
Step 3 : Set message to “Name Not Found”
Step 4 : Repeat Steps 5 and 6 until the pointer reaches null.
Step 5 : If n equals to b
              then
              set message to “Name found. Content is p”
              Exit
Step 6 : Move pointer to the next node
Step 7 : Display message
Step 8 : End

METHOD:

void search( node start, String b )
{
    Node temp = new Node(start); 
    String message = "Name Not Found";    
    while(temp.next != null)
    {
        if(b.equals(temp.n))
        {
            message = "Name Found. Content is : "+temp.p;
            break;
        }
        temp = temp.next;
    }
    System.out.println(message);
}

[ISC 2011]

A linked list is formed from the objects of the class,

class Node
{
int info;
Node link;
}

Write an Algorithm OR a Method for deleting a node from a linked list.
The method declaration is as follows: void deletenode( Node start )

Solution:

ALGORITHM:

Step 1 : Start
Step 2 : Set temporary pointer to start node
Step 3 : Accept info for the node to be deleted
Step 4 : if first node is the desired one then
              Move the pointer of the start node to the
              second node
              Set link of first node to null
              Stop
              else go to step 5
Step 5 : Move temporary pointer to the next node
Step 6 : if the desired node is found then
              (a) if the node to be deleted is last node then
                   Set the pointer of the previous node to null
                   Exit
                   else
              (b) Set the pointer of the previous node to the
                   next node of the node to be deleted
                   Set the temporary pointer node to null
                   Exit
Step 7 : Move temporary pointer to the next node
Step 8 : Repeat step 6 & 7 until the temporary pointer reaches null
Step 9 : End

METHOD:

void deletenode( Node start )
{
    Node temp = new Node(start); 
    System.out.print("Enter info of the node to be deleted : ");
    int n = sc.nextInt();
    if(start.info == n)
    {
        start = temp.link;
        temp.link = null;
     }
     else
     {
        temp = temp.link;
        Node prev = new Node(start);
        while(true)                            
        {
           if(temp.info == n)
           {
              if(temp.link == null)
              {
                 prev.link = null;
                 break;
              }
              else
              {
                 prev.link = temp.link;
                 temp.link = null;
                 break;
              }
           prev = temp;
           temp = temp.link;
        }
     }
}

[ISC 2010]

A linked list is formed from the objects of the class:

class ListNodes
{
int item;
ListNodes next;
}

Write an Algorithm OR a Method to compute and return the sum of all integer items stored in the linked list.
The method declaration is given below: int listsum(ListNodes start)

Solution:

ALGORITHM:

Step 1 : Start
Step 2 : Set temporary pointer to the start node
Step 3 : Set sum to 0
Step 4 : Repeat Steps 5 and 6 until the pointer reaches null
Step 5 : Add item to sum
Step 6 : Move pointer to the next node
Step 7 : Return sum
Step 8 : End

METHOD:

int listsum( ListNodes start )
{
    ListNodes temp = new ListNodes(start);                                       
    int sum = 0;
    while(temp.next != null)
    {
        sum = sum + temp.item;
        temp = temp.next;
    }
    return sum;
}

Method to delete (remove) a node after ‘n’ nodes in a Linked List :

In the below code, ‘start’ denotes the start node and ‘n’ denotes the number of nodes after which the node is to be deleted:

void deleteNode(Node start, int n)
{
    Node ptr = new Node(); //'ptr' is the node which will be deleted
    Node ptr1 = new Node(); //'ptr1' is the node just before the node to be deleted
    ptr = start;
    ptr1 = ptr;

    int c = 0;
    while(c <= n)
    {
        ptr1 = ptr;
        ptr = ptr.link;
        c++;
    }

    ptr1.link = ptr.link;
    ptr.link = null;
}

[Note: Don’t forget to share these resources and links from our website in your social networking sites with your friends and followers.]

Check Also

Infix Postfix Prefix Conversion – Correct Method (ISC Computer Science)

In this video we discuss about the correct way of converting an Infix Expression to Postfix and Prefix.

22 comments

  1. Thankyou so much no words to thank this website.got stromed away by linked list and their application .this website just vanished my fear about linked list

  2. Thank u for all ur programs…they are really helpfull

  3. It has been a great help for me 🙂 Thank You Sir … Keep the good work going 🙂

  4. Thank you so much sir……

  5. sir,
    should I teach programs related to linked list….

    • You can teach programs for clearing the concept, but what comes in ISC is either an algorithm or a method to perform some operation on already created linked list.

      I have listed down all the operations in the above post. Only these will be sufficient.
      .
      .

  6. sir will we get programs related to linked list in practicals…….. what will be the total marks from linked list topic…

  7. It’s really helpful for all the students of ISC…With the develpement of the technology it has become much easier for the coming generation to gather more information by staying at home only…Thnx to u

  8. Sir…how to write an algorithm when the question says just about deleting a node…..nothing more is given…! Should we write the same one which is for deleting a node after ‘n’ nodes

  9. Thanks for the help

  10. Is there any question on writing a method for the sum of the the nodes if there is then please send me..

    • [ISC 2010] : A linked list is formed from the objects of the class:

      class ListNodes
      {
      int item;
      ListNodes next;
      }

      Write an Algorithm OR a Method to compute and return the sum of all integer items stored in the linked list.
      The method declaration is given below:
      int listsum(ListNodes start)

      Solution:

      int listsum(ListNodes start)
      {
      int sum=0;
      ListNodes ptr = new ListNodes();
      ptr = start;
      while(ptr.link != null)
      {
      sum = sum + ptr.item;
      ptr = ptr.next;
      }
      return sum;
      }
  11. Is linked list a linear data structure on non-linear?
    APC says non-linear
    Sumita Arora’s book says Linear
    What is correct ?

  12. Sir,
    This website is really helpful for all computer science students .Thank you for keeping the site always updated.
    I would be grateful if you can provide me with some resources regarding complexity and big O notation, output questions (esp. recursion).

  13. Sir,
    Are questions pertaining to data structures (like stack, queue, and linked lists) asked in the ISC Practical Exam?

  14. Sir,in example 2 i cant understand this part:
    if(b.equalsIgnoreCase(ptr.n))
    {
    f=1;
    System.out.println(“Content of the node = ” + ptr.p);
    }
    ptr = ptr.next;
    }
    PLEASE COULD YOU EXPLAIN LINE BY LINE?
    THANK YOU.

    • Hello Sanchayan,

      Every node in the given linked list consists of 3 parts:
      ‘n’ storing a name
      ‘p’ storing a number
      ‘next’ storing the address of the next node.

      Now,
      ‘b’ is the name to search.
      ‘ptr.n’ is the name part of a node.
      So, ‘if(b.equalsIgnoreCase(ptr.n))’ is checking whether the name to search is matching with the name part of any node or not.
      If yes, then a flag is set to 1 (to indicate that search is successful) and the content (number stored in ‘p’ part) of the node is printed.
      ‘ptr = ptr.next;’ is for changing to the next node.

      I hope it is clear now.

      Regards,
      guideforschool

Leave a Reply

Your email address will not be published. Required fields are marked *