Linked List Operations Program in Java and Python
Linked list operations for ISC Computer Science, including traversal, count, sum, search, display, insert at beginning, insert after n nodes, insert at end and delete after n nodes.
Question:
A linked list is formed from nodes. Each node contains a data field and a link field. The data field stores the value, and the link field stores the address of the next node. In a singly linked list, movement is possible only in the forward direction. The last node contains null in its link field.
Write methods to perform the following basic operations on a singly linked list:
- Traverse a linked list.
- Count the number of nodes.
- Search for a name and display the contents of that node.
- Find the sum of all integer items stored in the linked list.
- Search for an integer value.
- Display all the data values in the linked list.
- Insert a node at the beginning.
- Insert a node after
nnodes. - Insert a node at the end.
- Delete a node after
nnodes.
Example
Algorithm:
Step 1: Start.
Step 2: Define a node class with fields data, name and link.
Step 3: To display or traverse the list, assign ptr = start and move forward while ptr != null.
Step 4: To count nodes, increase a counter once for every visited node.
Step 5: To find the sum, add ptr.data to sum for every node.
Step 6: To search a value, compare ptr.data with the required value while traversing the list.
Step 7: To search a name, compare ptr.name with the required name using case-insensitive comparison.
Step 8: To insert at the beginning, create a new node, point its link to start and make it the new start.
Step 9: To insert at the end, move to the last node and point its link to the new node.
Step 10: To insert after n nodes, move a pointer to the nth node, connect the new node to the next node and then connect the nth node to the new node.
Step 11: To delete after n nodes, move to the nth node and bypass the next node by changing links.
Step 12: Use a menu in main() to accept values and call the required linked-list methods.
Step 13: Stop.
Explanation:
A linked list is made of nodes connected through links. Unlike an array, the nodes are not stored in continuous memory locations. Each node knows where the next node is because it stores a reference to that next node. The first node is usually called start. If start is null, the list is empty. If a node's link is null, that node is the last node.
Most linked-list operations begin with traversal. A temporary pointer is assigned to start. The pointer is then moved from one node to the next using ptr = ptr.link. The loop must continue while ptr != null if every node is to be processed. During this traversal, the program can count nodes, display data, calculate the sum of integer values or search for a required value.
Insertion changes links carefully. To insert at the beginning, the new node points to the old start node and then becomes the new start. To insert at the end, the program first reaches the last node and then attaches the new node after it. To insert in the middle, the program reaches the required position, points the new node to the next node and then points the current node to the new node. The order of these assignments is important because otherwise part of the list may become disconnected.
Deletion also works by changing links. To delete a node after a given position, the program reaches the node before the one to be deleted. It then changes the link so that this node points to the node after the deleted node. The deleted node is no longer reachable from the list. This is the central idea behind linked-list manipulation: data is not shifted as in arrays; only links are changed.
Java Program:
/**
* The class LinkedListOperations demonstrates basic operations
* on a singly linked list.
* @author : www.guideforschool.com
* @Program Type : BlueJ Program - Java
*/
import java.util.Scanner;
class Node
{
int data;
String name;
Node link;
}
class LinkedListOperations
{
Node start;
Node createNode(int value, String name)
{
Node temp = new Node();
temp.data = value;
temp.name = name;
temp.link = null;
return temp;
}
void display()
{
Node ptr = start;
System.out.println("Data in the linked list are:");
while(ptr != null)
{
System.out.println(ptr.data + " " + ptr.name);
ptr = ptr.link;
}
}
int count()
{
int c = 0;
Node ptr = start;
while(ptr != null)
{
c++;
ptr = ptr.link;
}
return c;
}
int listsum()
{
int sum = 0;
Node ptr = start;
while(ptr != null)
{
sum = sum + ptr.data;
ptr = ptr.link;
}
return sum;
}
void searchValue(int value)
{
int f = 0;
Node ptr = start;
while(ptr != null)
{
if(ptr.data == value)
{
f = 1;
break;
}
ptr = ptr.link;
}
if(f == 1)
System.out.println("Search is Successful");
else
System.out.println("Search is Unsuccessful");
}
void searchName(String b)
{
int f = 0;
Node ptr = start;
while(ptr != null)
{
if(b.equalsIgnoreCase(ptr.name))
{
f = 1;
System.out.println("Content of the node = " + ptr.data);
break;
}
ptr = ptr.link;
}
if(f == 0)
System.out.println("Name not found");
}
void insertBeginning(int x, String name)
{
Node temp = createNode(x, name);
temp.link = start;
start = temp;
}
void insertEnd(int x, String name)
{
Node temp = createNode(x, name);
if(start == null)
{
start = temp;
return;
}
Node ptr = start;
while(ptr.link != null)
{
ptr = ptr.link;
}
ptr.link = temp;
}
void insertAfter(int n, int x, String name)
{
Node temp = createNode(x, name);
Node ptr = start;
int c = 1;
while(ptr != null && c < n)
{
ptr = ptr.link;
c++;
}
if(ptr != null)
{
temp.link = ptr.link;
ptr.link = temp;
}
}
void deleteAfter(int n)
{
Node ptr = start;
int c = 1;
while(ptr != null && c < n)
{
ptr = ptr.link;
c++;
}
if(ptr != null && ptr.link != null)
{
Node del = ptr.link;
ptr.link = del.link;
del.link = null;
}
}
public static void main(String args[])
{
Scanner sc = new Scanner(System.in);
LinkedListOperations ob = new LinkedListOperations();
System.out.print("Enter number of nodes: ");
int n = sc.nextInt();
sc.nextLine();
for(int i = 1; i <= n; i++)
{
System.out.print("Enter data: ");
int value = sc.nextInt();
sc.nextLine();
System.out.print("Enter name: ");
String name = sc.nextLine();
ob.insertEnd(value, name);
}
ob.display();
System.out.println("Number of nodes = " + ob.count());
System.out.println("Sum of data = " + ob.listsum());
System.out.print("Enter value to search: ");
int value = sc.nextInt();
sc.nextLine();
ob.searchValue(value);
System.out.print("Enter name to search: ");
String name = sc.nextLine();
ob.searchName(name);
}
}Equivalent Python Program:
# Program to demonstrate basic operations on a singly linked list.
class Node:
def __init__(self, data, name):
self.data = data
self.name = name
self.link = None
class LinkedListOperations:
def __init__(self):
self.start = None
def display(self):
ptr = self.start
print("Data in the linked list are:")
while ptr is not None:
print(ptr.data, ptr.name)
ptr = ptr.link
def count(self):
c = 0
ptr = self.start
while ptr is not None:
c += 1
ptr = ptr.link
return c
def listsum(self):
total = 0
ptr = self.start
while ptr is not None:
total += ptr.data
ptr = ptr.link
return total
def search_value(self, value):
ptr = self.start
while ptr is not None:
if ptr.data == value:
print("Search is Successful")
return
ptr = ptr.link
print("Search is Unsuccessful")
def search_name(self, name):
ptr = self.start
while ptr is not None:
if ptr.name.lower() == name.lower():
print("Content of the node =", ptr.data)
return
ptr = ptr.link
print("Name not found")
def insert_beginning(self, data, name):
temp = Node(data, name)
temp.link = self.start
self.start = temp
def insert_end(self, data, name):
temp = Node(data, name)
if self.start is None:
self.start = temp
return
ptr = self.start
while ptr.link is not None:
ptr = ptr.link
ptr.link = temp
def insert_after(self, n, data, name):
temp = Node(data, name)
ptr = self.start
c = 1
while ptr is not None and c < n:
ptr = ptr.link
c += 1
if ptr is not None:
temp.link = ptr.link
ptr.link = temp
def delete_after(self, n):
ptr = self.start
c = 1
while ptr is not None and c < n:
ptr = ptr.link
c += 1
if ptr is not None and ptr.link is not None:
ptr.link = ptr.link.link
ob = LinkedListOperations()
n = int(input("Enter number of nodes: "))
for i in range(n):
value = int(input("Enter data: "))
name = input("Enter name: ")
ob.insert_end(value, name)
ob.display()
print("Number of nodes =", ob.count())
print("Sum of data =", ob.listsum())
value = int(input("Enter value to search: "))
ob.search_value(value)
name = input("Enter name to search: ")
ob.search_name(name)Output:
Leave a Reply
Your email address will not be published. Comments are reviewed before appearing publicly.