A singly linked list is a type of linked list that is unidirectional, i.e., it can be traversed in only one direction from the head to the last node.
Each element in a linked list is called a node. A single node contains data and a pointer to the ​next node, which helps to maintain​ the structure of the list.
The head is a pointer that points to the first node of the list and, hence, helps us traverse the list. The last node points to nullptr, which helps us in determining when the list ends.
You can determine and retrieve a specific node from the front, end, or anywhere in the list.
The worst-case​ Time Complexity for retrieving a node from anywhere in the list is O(n).
You can add a node at the front, end, or anywhere in the linked list.
The worst-case Time Complexities for performing these operations are:
You can remove a node from the front, end, or anywhere in the list.
The worst-case Time Complexities for performing this operation are:
A singly linked list, along with the functions mentioned above, is implemented in the code snippet below.
#include <iostream>using namespace std;// Making a node struct containing an int data and a pointer// to next nodestruct Node {int data;Node *next;// Parameterised constructor with default argumentNode(int val=0) :data(val),next(nullptr){}// Parameterise constructorNode(int val, Node *tempNext):data(val),next(tempNext){}};class LinkedList{// Head pointerNode* head;public:// default constructor. Initializing head pointerLinkedList():head(nullptr){}// inserting elements (At start of the list)void insert(int val){// make a new nodeNode* new_node = new Node(val);// If list is empty, make the new node, the headif (head == nullptr){head = new_node;}// else, make the new_node the head and its next, the previous// headelse{new_node->next = head;head = new_node;}}// loop over the list. return true if element foundbool search(int val){Node* temp = head;while(temp != nullptr){if (temp->data == val)return true;temp = temp->next;}return false;}void remove(int val){Node* temp = head;// If the head is to be deletedif (temp != nullptr && temp->data == val){head = temp->next;delete temp;return;}// Else loop over the list and search for the node to deleteelse{Node* curr = head;while(temp != nullptr && temp->data != val){// When node is found, delete the node and modify the pointerscurr = temp;temp = temp->next;}// If values is not found in the linked listif(!temp){cout << "Value not found" << endl;return;}curr->next = temp->next;delete temp;}}void display(){Node* temp = head;while(temp != nullptr){cout << temp->data << " ";temp = temp->next;}cout << endl;}};int main() {LinkedList l;// inserting elementsl.insert(6);l.insert(9);l.insert(1);l.insert(3);l.insert(7);cout << "Current Linked List: ";l.display();cout << "Deleting 1: ";l.remove(1);l.display();cout << "Deleting 13: ";l.remove(13);cout << "Searching for 7: ";cout << l.search(7) << endl;cout << "Searching for 13: ";cout << l.search(13) << endl;}
Free Resources