A singly Linked List is the simplest linked list in which you can traverse the list only in one direction from head to the last node.
A Linked List is a linear data structure in which each element is stored in the form of a node and each node contains two parts, one part is to store the data and another part contains a pointer pointing to the next node (the pointer holds the address of the next node).
Unlike an array, in linked list nodes are not stored at a contiguous memory location. All nodes are linked using pointers and form a linear structure. We use a head pointer that always points to the first node of the list and it is used to traverse the linked list. The last node of the list points to null that indicates the end of the list.
List of Operations on Singly Linked List.
1. Creating a new List.
Create a class Node with two attributes one is data and the other one is a node. The data is used to store elements and the node is a pointer pointing to the next node.
class Node{ public: int data; Node *next; //constructor Node(int data){ this->data = data; this->next = NULL; } };
As we are creating a completely new list it means there should be no address to store inside the head pointer so in that case, the head pointer points to null. Create a new node and the head node will store the address of the newly created node.
2. Adding a new node to the List.
- Adding a node at the front takes O(1) time complexity.
- Adding a node at the end takes O(n) time complexity.
- Adding a node anywhere in between takes O(n) time complexity.
3. Search for a node in the list.
bool search(Node *head, int value){ Node *current = head; //traverse list while(current != NULL){ if(current->data == value) return true; current = current->next; } return false; }
4. Remove a node from the list.
We can remove a node from the front, end, or middle of the linked list and worst case it can take O(n) time complexity. Always remember to free the memory of the deleted node.
C++ Code Implementation of Singly Linked List.
//C++ Example of Singly Linked List #include<iostream> using namespace std; class Node{ public: int data; Node *next; //constructor Node(int data){ this->data = data; this->next = NULL; } }; //Add a node to the list Node *addNode(Node *head, int data){ Node *new_node = new Node(data); //add a new node when list is empty if(head == NULL) head = new_node; //adding new node at the front of the list else{ new_node->next = head; head = new_node; } return head; } //Search a node in the list bool search(Node *head, int value){ Node *current = head; //traverse list while(current != NULL){ if(current->data == value) return true; current = current->next; } return false; } //Remove a node from the list void deleteNode(Node* head, int position) { Node* temp; Node* prev; temp = head; prev = head; for (int i = 0; i < position; i++) { if (i == 0 && position == 1) { head = head->next; free(temp); } else { if (i == position - 1 && temp) { prev->next = temp->next; free(temp); } else { prev = temp; // Position was greater than // number of nodes in the list if (prev == NULL) break; temp = temp->next; } } } } //Traversing Linked List void display(Node *head){ Node *temp = head; while(temp != NULL){ cout<<temp->data<<" "; temp = temp->next; } } int main(){ Node *head = new Node(32); head = addNode(head, 20); head = addNode(head, 40); head = addNode(head, 12); cout<<"Singly Linked List: "; display(head); if(search(head, 20)) cout<<"\nValue is present in the List"; else cout<<"\nValue is not present in the List"; deleteNode(head, 2); cout<<"\nSingly Linked List after deletion: "; display(head); return 0; }
Singly Linked List: 12 40 20 32
Value is present in the List
Singly Linked List after deletion: 12 20 32
