A singly linked list is the simplest form of a Linked List. The nodes are represented in non-contiguous memory and each maintains the link to the next node. The following are the properties of the linked list.
- Linked List is dynamic in size and suitable for growing data needs.
- Ease of insertion and deletion at random positions. Hence the insertion and deletion work faster in Linked List compared to Array.
- Random access is not possible. Instead, a sequential traversal is required.
- Unlike arrays, additional memory is required to store the pointers.
- No cache-friendly for the CPU due to its non-contiguous memory.
1. Singly Linked List Representation
- Head: The starting point of the linked list
- Node: A node consists of the data element and the pointer to the Next node
- Element: The actual data (provided as 10, 20, and 30)
- Next: Pointer to the next node
2. Implementation of Singly Linked List in C++
/**
* C++ example to demonstrate the Singly Linked List
*/
#include <iostream>
using namespace std;
// Linked list node representation
struct Node
{
int element;
Node* next;
};
/**
* Linked list implementation
*/
class List
{
// Head of the list
Node* head;
public:
// Constructor
List() : head(NULL) {}
// Insert an element in front of the list
// Returns the new node inserted
Node* insert_front(int element);
// Insert an element after the given node
// Returns the new node inserted
Node* insert_after(Node* prev, int element);
// Delete the front element
// Returns the next node if available, NULL otherwise.
Node* delete_front();
// Delete the element after the given node
// Returns the next node if available, NULL otherwise.
Node* delete_after(Node* prev);
// Search and delete the given element
void remove(int element);
// Search an element from the list
// Returns the matching node if found, NULL otherwise.
Node* search(int element);
// Traverse the elements
void traverse(const std::string& msg);
};
Node* List::insert_front(int element)
{
// Step 1. Create the new node
Node* new_node = new Node();
new_node->element = element;
// Step 2. Link before the head node
new_node->next = head;
// Step 3. Change the head to point the new node
head = new_node;
return new_node;
}
Node* List::insert_after(Node* prev, int element)
{
// Step 1. Create the new node
Node *new_node = new Node();
new_node->element = element;
// Step 2. Link the new node after the given node
new_node->next = prev->next;
prev->next = new_node;
return new_node;
}
Node* List::delete_front()
{
// Step 1. Check if the list is empty and return if true.
if (head == NULL) {
return NULL;
}
// Step 2. Store the reference to front node as target node and
// move the head to next node if available or NULL.
Node* target = head;
head = head->next;
// Step 3. Delete the target node
delete target;
return head;
}
Node* List::delete_after(Node* prev)
{
// Step 1. Store the reference to target node
Node* target = prev->next;
// Step 2. Check if the target node is NULL and return if true
if (target == NULL) {
return NULL;
}
// Step 3. Disconnect the target node by linking its previous and next
// node directly
prev->next = target->next;
// Step 4. Delete the target node
delete target;
return prev->next;
}
void List::remove(int element)
{
// Step 1. Check if the list is empty and return if true.
if (head == NULL) {
return;
}
// Step 2. Check if the front node matches the element. If true,
// invoke the delete_front() operation and return.
if (head->element == element) {
delete_front();
return;
}
// Step 3. Otherwise, iterate the linked list from start to end,
// and search the element.
for (Node* node = head ; node->next != NULL ; node = node->next) {
if (node->next->element == element) {
// Step 4. If found, set the node as target node and disconnect
// it by directly linking the previous and next node.
Node* target = node->next;
node->next = node->next->next;
// Step 5. Delete the target node
delete target;
return;
}
}
return;
}
Node* List::search(int element)
{
// Step 1. Iterate the linked list from start to end
for (Node* node = head ; node != NULL ; node = node->next) {
// Step 2. Check if the element matches, and return the node if found.
if (node->element == element) {
return node; // Found element
}
}
// Step 3. Return NULL if none matches.
return NULL; // Not found
}
void List::traverse(const std::string& msg)
{
cout << msg << endl;
cout << "HEAD ==> ";
// Iterate the linked list from start to end
for (Node* node = head ; node != NULL ; node = node->next) {
cout << node->element << " ==> ";
}
cout << "NULL" << endl << endl;
}
int main()
{
// Create a linked list
List list;
list.traverse("initial list");
// Insert elements
list.insert_front(20);
list.traverse("insert_front(20)");
Node *node_10 = list.insert_front(10);
list.traverse("insert_front(10)");
list.insert_after(node_10, 15);
list.traverse("insert_after(node_10, 15)");
// Search an element
Node *node_15 = list.search(15);
cout << "search(15) matches node " << node_15->element << endl << endl;
// Delete elements
list.delete_front();
list.traverse("delete_front()");
list.delete_after(node_15);
list.traverse("delete_after(node_15)");
list.remove(15);
list.traverse("remove(15)");
}
Output
initial list
HEAD ==> NULL
insert_front(20)
HEAD ==> 20 ==> NULL
insert_front(10)
HEAD ==> 10 ==> 20 ==> NULL
insert_after(node_10, 15)
HEAD ==> 10 ==> 15 ==> 20 ==> NULL
search(15) matches node 15
delete_front()
HEAD ==> 15 ==> 20 ==> NULL
delete_after(node_15)
HEAD ==> 15 ==> NULL
remove(15)
HEAD ==> NULL3. Operations of Singly Linked List
3.1. Insert Front
Connect the new Node before the front Node and update the Head to point to the new Node.
Algorithm
- Create the new node.
- Link before the Head node.
- Finally, change the Head to point to the new node.
Examples
Let’s see a few examples of inserting the element at the Front in the following empty list.
1. Insertion at Front (20)
- The insertion is straightforward here since the linked list is empty.
2. Insertion at Front (10)
- Insert element (10) before the first node (20).
- The Head points to the new node after insertion.
3.2. Insert After
Connect the new Node after the given Node, and link the rest of the list after the new Node.
Algorithm
- Create the new node.
- Link the new node after the given node.
Examples
1. Insertion of new Node (15) after the Node (10)
- Here, we create a new node and link it between node (10) and node (20)
3.3. Delete Front
Change the Head pointer to point to the second node, and delete the Front node.
Algorithm
- Check if the list is empty and return if true.
- Store the reference to the front node as the target node. Subsequently, move the head to the next node if available or NULL.
- Finally, delete the target node.
Examples
Let’s consider the following linked list and perform deletions.
1. Delete the Front Node (10)
- Deleting the front node is straightforward. So, we need to move the Head to the next node.
3.4. Delete After
A node can be removed from the linked list by directly connecting its previous and next node.
Algorithm
- Store the reference to the target node.
- Check if the target node is NULL and return if true.
- Disconnect the target node by linking its previous and next node directly.
- Finally, delete the target node.
Examples
Let’s take the following linked list and perform deletion after the node (15)
1. Delete the Node (20) located after Node (15)
- Node (20) is located after the given node (15).
- We need to unlink only the node (20) in the middle and make sure that rest of the list exists.
3.5. Remove the given Element
Check if the element matches with the Front node and invoke delete_front() if true. Otherwise, search for the given Element by iterating the linked list and deleting the particular node if found.
Algorithm
- Check if the list is empty and return if true.
- Check if the front node matches the element. If true, invoke the delete_front() operation and return.
- Otherwise, iterate the linked list from start to end, and search the element.
- If found, set the node as the target node and disconnect it by directly linking the previous and next nodes.
- Finally, delete the target node
3.6. Search an Element
The list is traversed from start to end to search for an element in the Linked List.
Algorithm
- Iterate the linked list from start to end
- Check if the element matches, and return the node if found.
- Return NULL if none matches.
4. References
- std::forward_list – C++ standard library for the singly-linked lists.