Trusted answers to developer questions

Singly linked list in C++

Free System Design Interview Course

Many candidates are rejected or down-leveled due to poor performance in their System Design Interview. Stand out in System Design Interviews and get hired in 2024 with this popular free course.

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.

svg viewer

Common singly linked​ list operations


1. Search for a node in the ist

svg viewer

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).

2. Add a node to the list

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:

  • Add an item to the front of the list: O(1)
  • Add an item to the end of the list: O(n)
  • Add an item a​nywhere in the list: O(n)

3. Remove a node from the list

svg viewer

You can remove a node from the front, end, or anywhere in the list.

The worst-case Time Complexities for performing this operation are:

  • Remove an item from the front of the list: O(1)
  • Remove an item from the end of the list: O(n)
  • Remove an item from anywhere in the list: O(n)

Implementation

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 node
struct Node {
int data;
Node *next;
// Parameterised constructor with default argument
Node(int val=0) :data(val),next(nullptr){}
// Parameterise constructor
Node(int val, Node *tempNext):data(val),next(tempNext){}
};
class LinkedList
{
// Head pointer
Node* head;
public:
// default constructor. Initializing head pointer
LinkedList():head(nullptr)
{
}
// inserting elements (At start of the list)
void insert(int val)
{
// make a new node
Node* new_node = new Node(val);
// If list is empty, make the new node, the head
if (head == nullptr)
{
head = new_node;
}
// else, make the new_node the head and its next, the previous
// head
else
{
new_node->next = head;
head = new_node;
}
}
// loop over the list. return true if element found
bool 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 deleted
if (temp != nullptr && temp->data == val)
{
head = temp->next;
delete temp;
return;
}
// Else loop over the list and search for the node to delete
else
{
Node* curr = head;
while(temp != nullptr && temp->data != val)
{
// When node is found, delete the node and modify the pointers
curr = temp;
temp = temp->next;
}
// If values is not found in the linked list
if(!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 elements
l.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;
}

RELATED TAGS

singly
linked
list
c++
Copyright ©2024 Educative, Inc. All rights reserved
Did you find this helpful?