Single link list
A singly linked
list is a special type of linked list in which each node has only one
link that points to the next node in the linked list.
Characteristics:
·
Each
node holds a single value and a reference to the next node in the list.
·
The
list has a head, which is a reference to the first node in the list, and a
tail, which is a reference to the last node in the list.
·
The
nodes are not stored in a contiguous block of memory, but instead, each node
holds the address of the next node in the list.
·
Accessing
elements in a singly linked list requires traversing the list from the head to
the desired node, as there is no direct access to a specific node in memory.
Application of
Singly Linked Lists:
Memory management: Singly
linked lists can be used to implement memory pools, in which memory is
allocated and deallocated as needed.
Database indexing: Singly linked
lists can be used to implement linked lists in databases, allowing for fast
insertion and deletion operations.
Representing
polynomials and sparse matrices: Singly linked lists can be used to
efficiently represent polynomials and sparse matrices, where most elements are
zero.
Operating systems: Singly-linked lists are used in operating systems for tasks such as scheduling
processes and managing system resources.
Advantages of
Singly Linked Lists:
Dynamic memory
allocation:
Singly linked lists allow for dynamic memory allocation, meaning that the size
of the list can change at runtime as elements are added or removed.
Cache
friendliness: Singly
linked lists can be cache-friendly as nodes can be stored in separate cache
lines, reducing cache misses and improving performance.
Space-efficient: Singly-linked lists are space-efficient, as they only need to store a reference to the
next node in each element, rather than a large block of contiguous memory.
Disadvantages of
Singly Linked Lists:
Poor random-access
performance:
Accessing an element in a singly linked list requires traversing the list from
the head to the desired node, making it slow for random access operations
compared to arrays.
Increased memory
overhead: Singly
linked lists require additional memory for storing the pointers to the next
node in each element, resulting in increased memory overhead compared to
arrays.
Vulnerability to
data loss: Singly-linked lists are vulnerable to data loss if a node’s next pointer is lost or
corrupted, as there is no way to traverse the list and access other elements.
Not suitable for
parallel processing: Singly-linked lists are not suitable for parallel processing, as updating a node
requires exclusive access to its next pointer, which cannot be easily done in a
parallel environment.
Backward
traversing not possible: In singly linked list does not support backward
traversing.
Representation of a Single linked list:
A Node Creation:
Creating a node in
a linked list involves allocating memory for the new node and setting its data
and next pointer. Below is a simple algorithm in a language-agnostic pseudocode
to create a node in a singly linked list:
Algorithm: Create
Node
Input: data (value to
be stored in the node)
Output: newNode (a
newly created node)
1. Allocate
memory for a new node (let's call it newNode).
2. Set the data of
newNode to the input data.
3. Set the next
pointer of the newNode to NULL (as it is the last node in the beginning).
Return newNode.
Example:- Node creation in a linked list using C++ and
Python.
C++ Example:
#include
<iostream>
// Define the
structure for a node
struct Node {
int data;
Node* next;
};
// Function to
create a new node
Node*
createNode(int data) {
// Allocate memory for a new node
Node* newNode = new Node;
// Set the data of the new node
newNode->data = data;
// Set the next pointer to NULL
newNode->next = nullptr;
// Return the newly created node
return newNode;
}
int main() {
// Example usage
Node* myNode = createNode(42);
std::cout << "Node created with
data: " << myNode->data << std::endl;
// Don't forget to delete the allocated
memory when you're done using the node
delete myNode;
return 0;
}
Python Example:
class Node:
def __init__(self, data):
self.data = data
self.next = None
# Function to
create a new node
def
create_node(data):
# Instantiate a new Node
new_node = Node(data)
# Return the newly created node
return new_node
# Example usage
my_node =
create_node(42)
print(f"Node
created with data: {my_node.data}")
# In Python,
memory management is handled by the garbage collector, so there's no need to
explicitly free memory
Operations of
single link list
The following
operations are performed on a Single Linked List
Insertion: The
insertion operation can be performed in three ways.
They are as
follows…
Inserting At
the Beginning of the list
Inserting at the end of the list
Inserting a specific location in the list
Deletion: The
deletion operation can be performed in three ways.
They are as
follows…
Deleting from
the Beginning of the list
Deleting from
the End of the list
Deleting a
Specific Node
Search: It
is a process of determining and retrieving a specific node either from the
front, the end or anywhere in the list.
Display: This
process displays the elements of a Single-linked list.
Updating:-
In details: -
Insertion: Inserting
At the Beginning of the list
Algorithm: Insert
a Node at the beginning of a Singly Linked List
Input: Linked list
head pointer, value to be inserted (assumes that you have a linked list node
structure with a `data` field and a `next` pointer.)
1. Create a new
node with the given value.
2. Set the next
pointer of the new node to point to the current head of the linked list.
3. Update the head
pointer of the linked list to point to the new node.
4. End.
C++ Example: cpp
#include
<iostream>
// Node structure
struct Node {
int data;
Node* next;
Node(int value) : data(value),
next(nullptr) {}
};
// Function to
insert a node at the beginning
void
insertAtBeginning(Node*& head, int value) {
Node* newNode = new Node(value);
newNode->next = head;
head = newNode;
}
// Function to
display the linked list
void
displayList(Node* head) {
Node* current = head;
while (current) {
std::cout << current->data
<< " -> ";
current = current->next;
}
std::cout << "nullptr"
<< std::endl;
}
int main() {
Node* head = nullptr;
// Insert at the beginning
insertAtBeginning(head, 30);
insertAtBeginning(head, 20);
insertAtBeginning(head, 10);
// Display the linked list
displayList(head);
return 0;
}
Output:
10 -> 20 ->
30 -> nullptr
----------------------------
Python Example:
class Node:
def __init__(self, data):
self.data = data
self.next = None
# Function to
insert a node at the beginning
def
insert_at_beginning(head, value):
new_node = Node(value)
new_node.next = head
head = new_node
return head
# Function to
display the linked list
def
display_list(head):
current = head
while current:
print(current.data, end=" ->
")
current = current.next
print("None")
# Main program
head = None
# Insert at the
beginning
head =
insert_at_beginning(head, 30)
head =
insert_at_beginning(head, 20)
head =
insert_at_beginning(head, 10)
# Display the
linked list
display_list(head)
Output:
10 -> 20 ->
30 -> None
In both examples,
the `insertAtBeginning` (C++) and `insert_at_beginning` (Python) functions are
used to insert a new node at the beginning of the linked list, and the
`displayList` and `display_list` functions are used to print the elements of
the linked list for verification.
--------------------------------------------
Insertion:- Inserting at the end of the list
Algorithm: Insert
a Node at the End of a Singly Linked List
Input: Linked list
head pointer, value to be inserted
1. Create a new
node with the given value.
2. If the linked
list is empty (head is null), set the head pointer to the new node and end.
3. Otherwise,
traverse the linked list until the last node is reached (i.e., node->next is
null).
4. Set the next
pointer of the last node to point to the new node.
5. End.
C++ Example: cpp
#include
<iostream>
// Node structure
struct Node {
int data;
Node* next;
Node(int value) : data(value),
next(nullptr) {}
};
// Function to
insert a node at the end
void
insertAtEnd(Node*& head, int value) {
Node* newNode = new Node(value);
if (head == nullptr) {
// If the list is empty, set the head
to the new node
head = newNode;
return;
}
Node* current = head;
// Traverse the list to find the last node
while (current->next != nullptr) {
current = current->next;
}
// Set the next pointer of the last node to
the new node
current->next = newNode;
}
// Function to
display the linked list
void
displayList(Node* head) {
Node* current = head;
while (current) {
std::cout << current->data
<< " -> ";
current = current->next;
}
std::cout << "nullptr"
<< std::endl;
}
int main() {
Node* head = nullptr;
// Insert at the end
insertAtEnd(head, 10);
insertAtEnd(head, 20);
insertAtEnd(head, 30);
// Display the linked list
displayList(head);
return 0;
}
Output:
10 -> 20 ->
30 -> nullptr
-----------------------------
Python Example:
class Node:
def __init__(self, data):
self.data = data
self.next = None
# Function to
insert a node at the end
def
insert_at_end(head, value):
new_node = Node(value)
if head is None:
# If the list is empty, set the head to
the new node
head = new_node
return head
current = head
# Traverse the list to find the last node
while current.next is not None:
current = current.next
# Set the next pointer of the last node to
the new node
current.next = new_node
return head
# Function to
display the linked list
def
display_list(head):
current = head
while current:
print(current.data, end=" ->
")
current = current.next
print("None")
# Main program
head = None
# Insert at the end
head =
insert_at_end(head, 10)
head =
insert_at_end(head, 20)
head =
insert_at_end(head, 30)
# Display the
linked list
display_list(head)
Output:
10 -> 20 ->
30 -> None
In both examples,
the `insertAtEnd` (C++) and `insert_at_end` (Python) functions are used to
insert a new node at the end of the linked list, and the `displayList` and
`display_list` functions are used to print the elements of the linked list for
verification.
------------------------------------------------
Insertion:-Inserting
At a Specific location in the list.
Algorithm: Insert
a Node at a Specific Location in a Singly Linked List
Input: Linked list
head pointer, value to be inserted, position (0-indexed)
1. Create a new
node with the given value.
2. If the position
is 0:
a. Set the next pointer of the new node to
point to the current head of the linked list.
b. Update the head pointer of the linked
list to point to the new node.
3. Otherwise:
a. Traverse the linked list until the node
at the (position - 1) is reached.
b. Set the next pointer of the new node to
point to the next node of the current node.
c. Set the next pointer of the current node
to point to the new node.
4. End.
C++ Example: cpp
#include
<iostream>
// Node structure
struct Node {
int data;
Node* next;
Node(int value) : data(value),
next(nullptr) {}
};
// Function to
insert a node at a specific location
void
insertAtPosition(Node*& head, int value, int position) {
Node* newNode = new Node(value);
if (position == 0) {
// Insert at the beginning
newNode->next = head;
head = newNode;
} else {
// Traverse to the node at (position -
1)
Node* current = head;
for (int i = 0; i < position - 1
&& current != nullptr; ++i) {
current = current->next;
}
if (current == nullptr) {
std::cout << "Position
out of bounds" << std::endl;
return;
}
// Insert at the specific position
newNode->next = current->next;
current->next = newNode;
}
}
// Function to
display the linked list
void
displayList(Node* head) {
Node* current = head;
while (current) {
std::cout << current->data
<< " -> ";
current = current->next;
}
std::cout << "nullptr"
<< std::endl;
}
int main() {
Node* head = nullptr;
// Insert at specific positions
insertAtPosition(head, 10, 0); // Insert at the beginning
insertAtPosition(head, 30, 1); // Insert at position 1
insertAtPosition(head, 20, 1); // Insert at position 1
// Display the linked list
displayList(head);
return 0;
}
Output:
10 -> 20 ->
30 -> nullptr
----------------------------------
Python Example: python
class Node:
def __init__(self, data):
self.data = data
self.next = None
# Function to
insert a node at a specific location
def
insert_at_position(head, value, position):
new_node = Node(value)
if position == 0:
# Insert at the beginning
new_node.next = head
head = new_node
else:
# Traverse to the node at (position -
1)
current = head
for i in range(position - 1):
if current is None:
print("Position out of
bounds")
return
current = current.next
# Insert at the specific position
new_node.next = current.next
current.next = new_node
return head
# Function to
display the linked list
def
display_list(head):
current = head
while current:
print(current.data, end=" ->
")
current = current.next
print("None")
# Main program
head = None
# Insert at specific
positions
head =
insert_at_position(head, 10, 0) # Insert
at the beginning
head =
insert_at_position(head, 30, 1) # Insert
at position 1
head =
insert_at_position(head, 20, 1) # Insert
at position 1
# Display the
linked list
display_list(head)
Output:
10 -> 20 ->
30 -> None
In both examples,
the `insertAtPosition` (C++) and `insert_at_position` (Python) functions are
used to insert a new node at a specific location in the linked list, and the
`displayList` and `display_list` functions are used to print the elements of
the linked list for verification.
-----------------------------------------------------------------------------
Deletion:
Deletion: The
deletion operation can be performed in three ways.
Deleting from the
Beginning of the list
Algorithm: Delete
a Node from the Beginning of a Singly Linked List
Input: Linked list
head pointer
1. If the linked
list is empty (head is null), print an error message and end.
2. Otherwise,
create a temporary pointer to the head node.
3. Update the head
pointer to point to the next node of the current head.
4. Free the memory
of the node pointed to by the temporary pointer.
5. End.
C++ Example: cpp
#include
<iostream>
// Node structure
struct Node {
int data;
Node* next;
Node(int value) : data(value),
next(nullptr) {}
};
// Function to
delete a node from the beginning
void
deleteFromBeginning(Node*& head) {
if (head == nullptr) {
// If the list is empty, print an error
message
std::cout << "List is empty.
Cannot delete from the beginning." << std::endl;
return;
}
// Save the current head
Node* temp = head;
// Update the head pointer to the next node
head = head->next;
// Free the memory of the original head
delete temp;
}
// Function to
display the linked list
void
displayList(Node* head) {
Node* current = head;
while (current) {
std::cout << current->data
<< " -> ";
current = current->next;
}
std::cout << "nullptr"
<< std::endl;
}
int main() {
Node* head = nullptr;
// Insert some nodes
for (int i = 5; i > 0; --i) {
Node* newNode = new Node(i);
newNode->next = head;
head = newNode;
}
// Display the original linked list
std::cout << "Original Linked
List: ";
displayList(head);
// Delete from the beginning
deleteFromBeginning(head);
// Display the linked list after deletion
std::cout << "Linked List after
Deletion: ";
displayList(head);
return 0;
}
Output:
Original Linked
List: 1 -> 2 -> 3 -> 4 -> 5 -> nullptr
Linked List after
Deletion: 2 -> 3 -> 4 -> 5 -> nullptr
-------------------------------
Python Example:
class Node:
def __init__(self, data):
self.data = data
self.next = None
# Function to
delete a node from the beginning
def
delete_from_beginning(head):
if head is None:
# If the list is empty, print an error
message
print("List is empty. Cannot
delete from the beginning.")
return None
# Save the current head
temp = head
# Update the head pointer to the next node
head = head.next
# Free the memory of the original head
del temp
return head
# Function to
display the linked list
def
display_list(head):
current = head
while current:
print(current.data, end=" ->
")
current = current.next
print("None")
# Main program
head = None
# Insert some
nodes
for i in range(5,
0, -1):
new_node = Node(i)
new_node.next = head
head = new_node
# Display the
original linked list
print("Original
Linked List: ", end="")
display_list(head)
# Delete from the
beginning
head =
delete_from_beginning(head)
# Display the
linked list after deletion
print("Linked
List after Deletion: ", end="")
display_list(head)
Output:
Original Linked
List: 1 -> 2 -> 3 -> 4 -> 5 -> None
Linked List after
Deletion: 2 -> 3 -> 4 -> 5 -> None
In both examples,
the `deleteFromBeginning` (C++) and `delete_from_beginning` (Python) functions
are used to delete a node from the beginning of the linked list, and the
`displayList` and `display_list` functions are used to print the elements of
the linked list for verification.
-----------------------------------------------
Deleting from the
End of the list
Algorithm: Delete
a Node from the End of a Singly Linked List
Input: Linked list
head pointer
1. If the linked
list is empty (head is null), print an error message and end.
2. If the linked
list has only one node (head->next is null):
a. Free the memory of the head node.
b. Set the head pointer to null.
c. End.
3. Otherwise,
traverse the linked list until the second-to-last node is reached (i.e.,
node->next->next is null).
4. Save the last
node in a temporary pointer.
5. Set the next
pointer of the second-to-last node to null.
6. Free the memory
of the last node.
7. End.
C++ Example: cpp
#include
<iostream>
// Node structure
struct Node {
int data;
Node* next;
Node(int value) : data(value),
next(nullptr) {}
};
// Function to
delete a node from the end
void
deleteFromEnd(Node*& head) {
if (head == nullptr) {
// If the list is empty, print an error
message
std::cout << "List is empty.
Cannot delete from the end." << std::endl;
return;
}
if (head->next == nullptr) {
// If the list has only one node
delete head;
head = nullptr;
} else {
// Traverse to the second-to-last node
Node* current = head;
while (current->next->next !=
nullptr) {
current = current->next;
}
// Save the last node in a temporary
pointer
Node* temp = current->next;
// Set the next pointer of the
second-to-last node to null
current->next = nullptr;
// Free the memory of the last node
delete temp;
}
}
// Function to
display the linked list
void
displayList(Node* head) {
Node* current = head;
while (current) {
std::cout << current->data
<< " -> ";
current = current->next;
}
std::cout << "nullptr"
<< std::endl;
}
int main() {
Node* head = nullptr;
// Insert some nodes
for (int i = 1; i <= 5; ++i) {
Node* newNode = new Node(i);
newNode->next = head;
head = newNode;
}
// Display the original linked list
std::cout << "Original Linked
List: ";
displayList(head);
// Delete from the end
deleteFromEnd(head);
// Display the linked list after deletion
std::cout << "Linked List after
Deletion: ";
displayList(head);
return 0;
}
Output:
Original Linked
List: 5 -> 4 -> 3 -> 2 -> 1 -> nullptr
Linked List after
Deletion: 5 -> 4 -> 3 -> 2 -> nullptr
-----------------------------
Python Example:
class Node:
def __init__(self, data):
self.data = data
self.next = None
# Function to
delete a node from the end
def
delete_from_end(head):
if head is None:
# If the list is empty, print an error
message
print("List is empty. Cannot
delete from the end.")
return None
if head.next is None:
# If the list has only one node
del head
return None
# Traverse to the second-to-last node
current = head
while current.next.next is not None:
current = current.next
# Save the last node in a temporary pointer
temp = current.next
# Set the next pointer of the
second-to-last node to null
current.next = None
# Free the memory of the last node
del temp
return head
# Function to display
the linked list
def
display_list(head):
current = head
while current:
print(current.data, end=" ->
")
current = current.next
print("None")
# Main program
head = None
# Insert some
nodes
for i in range(5,
0, -1):
new_node = Node(i)
new_node.next = head
head = new_node
# Display the
original linked list
print("Original
Linked List: ", end="")
display_list(head)
# Delete from the
end
head =
delete_from_end(head)
# Display the
linked list after deletion
print("Linked
List after Deletion: ", end="")
display_list(head)
Output:
Original Linked
List: 5 -> 4 -> 3 -> 2 -> 1 -> None
Linked List after
Deletion: 5 -> 4 -> 3 -> 2 -> None
In both examples,
the `deleteFromEnd` (C++) and `delete_from_end` (Python) functions are used to
delete a node from the end of the linked list, and the `displayList` and
`display_list` functions are used to print the elements of the linked list for
verification.
---------------------------------------------------
Deleting a
Specific Node
Deleting a
specific node from a singly linked list involves finding the node with the
given value and removing it from the list. Below is a generic algorithm for
deleting a specific node in a singly linked list:
Algorithm: Delete
a Specific Node from a Singly Linked List
Input: Linked list
head pointer, value to be deleted
1. If the linked
list is empty (head is null), print an error message and end.
2. If the node to
be deleted is the head node (head->data equals the value):
a. Save the current head in a temporary
pointer.
b. Update the head pointer to point to the
next node.
c. Free the memory of the node pointed to by
the temporary pointer.
d. End.
3. Otherwise,
traverse the linked list until the node to be deleted is found.
4. If the node is
not found, print an error message and end.
5. Save the
previous node in a temporary pointer.
6. Set the next
pointer of the previous node to point to the next node of the node to be
deleted.
7. Free the memory
of the node to be deleted.
8. End.
C++ Example: cpp
#include
<iostream>
// Node structure
struct Node {
int data;
Node* next;
Node(int value) : data(value),
next(nullptr) {}
};
// Function to
delete a specific node
void
deleteNode(Node*& head, int value) {
if (head == nullptr) {
// If the list is empty, print an error
message
std::cout << "List is empty.
Cannot delete." << std::endl;
return;
}
if (head->data == value) {
// If the node to be deleted is the
head node
Node* temp = head;
head = head->next;
delete temp;
return;
}
// Traverse the list to find the node to be
deleted
Node* current = head;
Node* prev = nullptr;
while (current != nullptr &&
current->data != value) {
prev = current;
current = current->next;
}
if (current == nullptr) {
// If the node is not found, print an
error message
std::cout << "Node with
value " << value << " not found." <<
std::endl;
return;
}
// Delete the node
prev->next = current->next;
delete current;
}
// Function to
display the linked list
void
displayList(Node* head) {
Node* current = head;
while (current) {
std::cout << current->data
<< " -> ";
current = current->next;
}
std::cout << "nullptr"
<< std::endl;
}
int main() {
Node* head = nullptr;
// Insert some nodes
for (int i = 1; i <= 5; ++i) {
Node* newNode = new Node(i);
newNode->next = head;
head = newNode;
}
// Display the original linked list
std::cout << "Original Linked
List: ";
displayList(head);
// Delete a specific node
deleteNode(head, 3);
// Display the linked list after deletion
std::cout << "Linked List after
Deletion: ";
displayList(head);
return 0;
}
Output:
Original Linked
List: 5 -> 4 -> 3 -> 2 -> 1 -> nullptr
Linked List after
Deletion: 5 -> 4 -> 2 -> 1 -> nullptr
-----------------------------
Python Example: python
class Node:
def __init__(self, data):
self.data = data
self.next = None
# Function to
delete a specific node
def
delete_node(head, value):
if head is None:
# If the list is empty, print an error
message
print("List is empty. Cannot
delete.")
return None
if head.data == value:
# If the node to be deleted is the head
node
temp = head
head = head.next
del temp
return head
# Traverse the list to find the node to be
deleted
current = head
prev = None
while current is not None and current.data
!= value:
prev = current
current = current.next
if current is None:
# If the node is not found, print an
error message
print(f"Node with value {value}
not found.")
return head
# Delete the node
if prev is not None:
prev.next = current.next
else:
head = current.next
del current
return head
# Function to
display the linked list
def
display_list(head):
current = head
while current:
print(current.data, end=" ->
")
current = current.next
print("None")
# Main program
head = None
# Insert some
nodes
for i in range(5,
0, -1):
new_node = Node(i)
new_node.next = head
head = new_node
# Display the
original linked list
print("Original
Linked List: ", end="")
display_list(head)
# Delete a
specific node
head =
delete_node(head, 3)
# Display the
linked list after deletion
print("Linked
List after Deletion: ", end="")
display_list(head)
Output:
Original Linked
List: 5 -> 4 -> 3 -> 2 -> 1 -> None
Linked List after
Deletion: 5 -> 4 -> 2 -> 1 -> None
In both examples,
the `deleteNode` (C++) and `delete_node` (Python) functions are used to delete
a specific node from the linked list, and the `displayList` and `display_list`
functions are used to print the elements of the linked list for verification.
---------------------------------------
Algorithm of
traversing in the single link list
Traversing a
singly linked list involves visiting each node in the list and performing an
operation (such as printing or processing the data) on each node. Below is a
generic algorithm for traversing a singly linked list:
Algorithm:
Traverse a Singly Linked List
Input: Linked list
head pointer
1. Set a pointer
(current) to the head of the linked list.
2. While the
current pointer is not null:
a. Perform the desired operation on the data
of the current node.
b. Move the current pointer to the next node
in the list (current = current->next in C++, current = current.next in
Python).
3. End.
C++ Example: cpp
#include
<iostream>
// Node structure
struct Node {
int data;
Node* next;
Node(int value) : data(value),
next(nullptr) {}
};
// Function to
traverse the linked list
void
traverseList(Node* head) {
Node* current = head;
while (current != nullptr) {
// Perform the desired operation (e.g.,
print data)
std::cout << current->data
<< " -> ";
// Move to the next node
current = current->next;
}
std::cout << "nullptr"
<< std::endl;
}
int main() {
Node* head = nullptr;
// Insert some nodes
for (int i = 1; i <= 5; ++i) {
Node* newNode = new Node(i);
newNode->next = head;
head = newNode;
}
// Display the linked list by traversing it
std::cout << "Linked List:
";
traverseList(head);
return 0;
}
Output:
Linked List: 5
-> 4 -> 3 -> 2 -> 1 -> nullptr
-----------------------
Python Example:
class Node:
def __init__(self, data):
self.data = data
self.next = None
# Function to traverse
the linked list
def
traverse_list(head):
current = head
while current is not None:
# Perform the desired operation (e.g.,
print data)
print(current.data, end=" ->
")
# Move to the next node
current = current.next
print("None")
# Main program
head = None
# Insert some
nodes
for i in range(5,
0, -1):
new_node = Node(i)
new_node.next = head
head = new_node
# Display the
linked list by traversing it
print("Linked
List: ", end="")
traverse_list(head)
Output:
Linked List: 5
-> 4 -> 3 -> 2 -> 1 -> None
In both examples,
the `traverseList` (C++) and `traverse_list` (Python) functions are used to
traverse the linked list, and the elements of the list are printed as they are
visited. You can customize the operation inside the loop based on your specific
requirements.
---------------------------------------------
Search/displaying:
Search /
display: It is a process of determining and retrieving a specific node
either from the front, the end, or anywhere in the list.
Searching in a
singly linked list involves traversing the list to find a node with a specific
value. Below is a generic algorithm for searching in a singly linked list:
Algorithm: Search
in a Singly Linked List
Input: Linked list
head pointer, value to be searched
1. Set a pointer
(current) to the head of the linked list.
2. While the
current pointer is not null:
a. If the data of the current node is equal
to the value being searched, return true (node found).
b. Move the current pointer to the next node
in the list (current = current->next in C++, current = current. next in
Python).
3. If the loop
completes without finding the value, return false (node not found).
4. End.
C++ Example:
#include <iostream>
// Node structure
struct Node {
int data;
Node* next;
Node(int value) : data(value),
next(nullptr) {}
};
// Function to
search for a value in the linked list
bool
searchInList(Node* head, int value) {
Node* current = head;
while (current != nullptr) {
if (current->data == value) {
// Node found
return true;
}
// Move to the next node
current = current->next;
}
// Node not found
return false;
}
int main() {
Node* head = nullptr;
// Insert some nodes
for (int i = 1; i <= 5; ++i) {
Node* newNode = new Node(i);
newNode->next = head;
head = newNode;
}
// Search for values in the linked list
std::cout << "Search for 3:
" << (searchInList(head, 3) ? "Found" : "Not
Found") << std::endl;
std::cout << "Search for 7:
" << (searchInList(head, 7) ? "Found" : "Not
Found") << std::endl;
return 0;
}
Output:
Search for 3:
Found
Search for 7: Not
Found
-----------------------------------
Python Example: python
class Node:
def __init__(self, data):
self.data = data
self.next = None
# Function to
search for a value in the linked list
def
search_in_list(head, value):
current = head
while current is not None:
if current.data == value:
# Node found
return True
# Move to the next node
current = current.next
# Node not found
return False
# Main program
head = None
# Insert some
nodes
for i in range(5,
0, -1):
new_node = Node(i)
new_node.next = head
head = new_node
# Search for
values in the linked list
print("Search
for 3:", "Found" if search_in_list(head, 3) else "Not
Found")
print("Search
for 7:", "Found" if search_in_list(head, 7) else "Not
Found")
Output:
Search for 3:
Found
Search for 7: Not
Found
In both examples,
the `searchInList` (C++) and `search_in_list` (Python) functions are used to
search for a value in the linked list. The result is printed to indicate
whether the value was found or not.
--------------------------------------------------------------------------
Updating:-
Updating a node in
a singly linked list typically involves searching for a node with a specific
value and then modifying its data. Below is a generic algorithm for updating a
node in a singly linked list:
Algorithm: Update
a Node in a Singly Linked List
Input: Linked list
head pointer, old value (value to be updated), new value (updated value)
1. Set a pointer
(current) to the head of the linked list.
2. While the
current pointer is not null:
a. If the data of the current node is equal
to the old value:
i. Update the data of the current node
with the new value.
ii. Return true to indicate successful
update.
b. Move the current pointer to the next node
in the list (current = current->next in C++, current = current. next in
Python).
3. If the loop
completes without finding the old value, return false to indicate that the node
was not found.
4. End.
C++ Example: cpp
#include
<iostream>
// Node structure
struct Node {
int data;
Node* next;
Node(int value) : data(value),
next(nullptr) {}
};
// Function to
update a node in the linked list
bool updateNode(Node*
head, int oldValue, int newValue) {
Node* current = head;
while (current != nullptr) {
if (current->data == oldValue) {
// Node found, update the data
current->data = newValue;
return true;
}
// Move to the next node
current = current->next;
}
// Node not found
return false;
}
// Function to
display the linked list
void
displayList(Node* head) {
Node* current = head;
while (current) {
std::cout << current->data
<< " -> ";
current = current->next;
}
std::cout << "nullptr"
<< std::endl;
}
int main() {
Node* head = nullptr;
// Insert some nodes
for (int i = 1; i <= 5; ++i) {
Node* newNode = new Node(i);
newNode->next = head;
head = newNode;
}
// Display the original linked list
std::cout << "Original Linked
List: ";
displayList(head);
// Update a node in the linked list
bool result = updateNode(head, 3, 8);
// Display the linked list after updating
std::cout << "Linked List after
Update: ";
displayList(head);
// Print the result of the update operation
std::cout << "Update Result:
" << (result ? "Success" : "Node not found")
<< std::endl;
return 0;
}
Output:
Original Linked
List: 5 -> 4 -> 3 -> 2 -> 1 -> nullptr
Linked List after
Update: 5 -> 4 -> 8 -> 2 -> 1 -> nullptr
Update Result:
Success
----------------------------
Python Example: python
class Node:
def __init__(self, data):
self.data = data
self.next = None
# Function to
update a node in the linked list
def
update_node(head, old_value, new_value):
current = head
while current is not None:
if current.data == old_value:
# Node found, update the data
current.data = new_value
return True
# Move to the next node
current = current.next
# Node not found
return False
# Function to
display the linked list
def
display_list(head):
current = head
while current:
print(current.data, end=" ->
")
current = current.next
print("None")
# Main program
head = None
# Insert some
nodes
for i in range(5,
0, -1):
new_node = Node(i)
new_node.next = head
head = new_node
# Display the
original linked list
print("Original
Linked List: ", end="")
display_list(head)
# Update a node in
the linked list
result =
update_node(head, 3, 8)
# Display the
linked list after updating
print("Linked
List after Update: ", end="")
display_list(head)
# Print the result
of the update operation
print("Update
Result:", "Success" if result else "Node not found")
Output:
Original Linked
List: 5 -> 4 -> 3 -> 2 -> 1 -> None
Linked List after
Update: 5 -> 4 -> 8 -> 2 -> 1 -> None
Update Result:
Success
In both examples,
the `updateNode` (C++) and `update_node` (Python) functions are used to update
a node in the linked list, and the `displayList` and `display_list` functions
are used to print the elements of the linked list for verification. The result of
the update operation is also printed to indicate whether the update was
successful or if the node was not found.
Note:- :- IMAGES from the web resource .
=======================================================================
0 Comments