Tuesday , 24 January 2017
Home » Class 12 » Some Operations on Linked List using Java

Some Operations on Linked List using Java

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

Method to Traverse a Single Linked List :

If the class definition of a linked list is:

class Node
{
int data;
Node link;
}

Then the method for traversal will be:

void traversal(Node start)
{
Node ptr = new Node(); //creating a temporary object
ptr = start; //referring it to the first list (start node) of the linked list
while(ptr.link != null)
{

/* process ptr.data here */

ptr = ptr.link;
}
}

Examples:

Example 1:

[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:

int count(Node ptr_start)
{
int c=0;
Node ptr = new Node();
ptr = ptr_start;
while(ptr.link != null)
{
c++;
ptr = ptr.next;
}
return c;
}

Example 2:

[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:

void search(node start, String b)
{
int f=0;
node ptr = new node();
ptr = start;
while(ptr.link != null)
{
if(b.equalsIgnoreCase(ptr.n))
{
f=1;
System.out.println("Content of the node  = " + ptr.p);
}
ptr = ptr.next;
}
if(f==0)
System.out.println("Name not found");
}

Example 3:

[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.next != null)
{
sum = sum + ptr.item;
ptr = ptr.next;
}
return sum;
}

Example 4:

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:

void search(Node start, int value)
{
int f=0;
Node ptr = new Node();
ptr = start;
while(ptr.link != null)
{
if(ptr.data == value)
{
f=1;
}
ptr = ptr.link;
}
if(f == 1)
System.out.println("Search is Successful");
else
System.out.println("Search is Unsuccessful");
}

Example 5:

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:

void display(Node start)
{
Node ptr = new Node();
ptr = start;
System.out.println("Data in the linked list are: ");
while(ptr.link != null)
{
System.out.println(ptr.data);
ptr = ptr.link;
}
}

Method to 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:

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

Method to 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:

void insertMiddle(Node start, int x, int n)
{
    Node temp = new Node();
    temp.data = x;
    Node ptr = new Node();
    ptr = start; 
    
    int c = 1;
    while(c <= n) //'ptr' will access all nodes up to the nth node
    {
        ptr = ptr.link;
        c++;
    }
    
    temp.link = ptr.link;
    ptr.link = temp;
}

Method to 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:

void insertEnd(Node start, int x)
{
    Node temp = new Node();
    temp.data = x;
    Node ptr = new Node();
    ptr = start;
    
    while(ptr.link != null) //'ptr' will access all nodes up to the last node
    {
        ptr = ptr.link;
    }
    
    temp.link = null;
    ptr.link = temp;
}

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 added:

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

ISC 2016 Computer Science Solution + Examiner’s Comments – From the Council

Solution of ISC 2016 Computer science Paper as provided by the Council for the Indian School Certificate Examinations.

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 to gfs_fan Cancel reply

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