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.

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

• 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 nodepublic:		node* link=NULL;	int data=0;};class singly_link_list {  //This class stores the nodes of the listpublic:	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 codeint 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 codeint 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 codeint 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 