Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

data structures
linear

What is a linked list?

Hafiza Farwa Mahmood

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Linked list

A linked list is a common data structure made of one or more than one nodes. Each node contains a value and a pointer to the previous/next node forming the chain-like structure. These nodes are stored randomly in the system's memory, which improves its space complexity compared to the array.

Types of linked list

  • Singly-linked list
  • Doubly linked list
  • Circular linked list

In this Answer, we'll learn about the singly linked list and its operations.

Hint: Have you ever played Treasure Hunt? It works same as linked list.

Working

We create a linked list by using classes. Here we implement a singly linked list. Let's see how to code a linked list.

class node {
public:
int data;
node* link;
};

We make a node class that has the data attributes and a node pointer link that stores the address of the node.

node* head, *tail =new node();
head = NULL, tail=NULL;

The head pointer points to the first node, and the last element of the list point to the null, which is the tail. When the list is empty, the head and tail the pointer points to NULL.

Operations

We perform the following functions on the linked list:

  • Insertion
  • Search
  • Deletion

Insertion

We can insert a node at the start as head, at the end as tail, or any desired position by entering the position number. Here, we insert the first element at the beginning to create the head and then the upcoming elements at the tail.

#include<iostream>
using namespace std;
class node { //Creating a class of node
public:
node* link=NULL;
int data=0;
};
class singly_link_list { //This class stores the nodes of the list
public:
node* head = NULL,*tail=NULL;
void add_node(int p_data) { //function for adding new nodes into list
node* temp_node=new node(); //temp_node stores the data temporary
temp_node->data = p_data;
temp_node->link = NULL;
if (head == NULL) { //Creating head
head = temp_node;
tail = temp_node;
}
else { //For insertion of all nodes other than head
tail->link = temp_node;
tail = tail->link;
}
}
void display() { //Function to print linked list
node* temp_node = head;
cout << "Link List : ";
while (temp_node != NULL) //Traversing each element and printing them
{
cout << temp_node->data << " ";
temp_node = temp_node->link;
}
}
};
//Driver code
int main()
{
singly_link_list list;
list.add_node(2); //Inserting head
list.add_node(4); //Inserting other nodes
list.add_node(6);
list.display(); //printing list
}

In this code, the add_node function is used to insert nodes into the linked list. First, it checks whether the list exists or not. If yes, a new node is added to the list, and a head is created.

Search

We can search in the linked list by traversing all the elements starting from the head node.

void singly_link_list::search(int p_data) { //Function for searching
node* temp = head; //temporary node
int counter=0;
while (temp != NULL) { //traversing list
counter++;
if (temp->data == p_data) { //Value found
cout << "\nValue has been found at position: " << counter<<endl;
return;
}
else { //Traverse next element
temp = temp->link;
}
}
cout << "\nValue doesn't exist in link list" << endl;
}
//Driver code
int main()
{
singly_link_list list;
list.add_node(2);
list.add_node(4);
list.add_node(6);
list.display();
list.search(4);
}

In this code, the search function is defined to search the given value p_data. We use while loop to traverse the linked list. After finding the value, the loop breaks down. If the loop is not broken, the entered value doesn't exist in the linked list.

Deletion

We can delete the head node, the tail, or at any desired position by first searching it. Here we delete the second node.

#include<iostream>
using namespace std;
void singly_link_list::delete_node(int p_data){ //function for deletion
node* current = new node(),*prev=new node(); //temporary nodes for keeping the track
current = head;
prev = tail;
//Deleting Head
if (p_data == head->data)
{
head = head->link;
delete current;
return;
}
while (current!=NULL)
{
if (current->data == p_data)
break;
prev = current;
current = current->link;
}
//Deleting Tail
if (p_data == tail->data)
{
tail = prev;
prev->link = NULL;
delete current;
return;
}
else if (current==NULL) //Element is not found
{
cout << endl << p_data << " doesn't exist in link list" << endl;
}
else //Traversing next node
{
prev->link = current->link;
delete current;
}
}
//Driver code
int main()
{
singly_link_list list;
list.add_node(2);
list.add_node(4);
list.add_node(6);
cout<<"Before Delete, ";
list.display();
list.delete_node(4);
cout<<"\nAfter Delete, ";
list.display();
}

In this code, delete_node is defined to delete the head, tail, or any node of a linked list. current and prev nodes are keeping track of the linked list.

  • Line 12–26: We delete the head note, and assign the next node as head.
  • Line 30–36: We delete the tail node, and assign the last node as tail.
  • Line 38–48: We set the current to the next node. If current it becomes empty, the given data p_data doesn't exist in the linked list.
Time complexity

Case

Worst

Average

Insertion

O(n)

O(1)

Search

O(n)

O(n)

Deletion

O(n)

O(1)

RELATED TAGS

data structures
linear

CONTRIBUTOR

Hafiza Farwa Mahmood
Copyright ©2022 Educative, Inc. All rights reserved

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Keep Exploring