Link List

A linked list is a collection of “nodes” connected together via links.

These nodes consist of the data to be stored and a pointer to the
address of the next node within the linked list. In the case of arrays,
the size is limited to the definition, but in linked lists, there is no
defined size. Any amount of data can be stored in it and can be
deleted from it.

There are three types of linked lists −

 Singly Linked List − The nodes only point to the address of the
next node in the list.
 Doubly Linked List − The nodes point to the addresses of both
previous and next nodes.
 Circular Linked List − The last node in the list will point to the
first node in the list. It can either be singly linked or doubly
linked.

Linked List Representation

Linked list can be visualized as a chain of nodes, where every node
points to the next node.
As per the above illustration, following are the important points to
be considered.

 Linked List contains a link element called first (head).

 Each link carries a data field(s) and a link field called next.
 Each link is linked with its next link using its next link.
 Last link carries a link as null to mark the end of the list.

Types of Linked List

Following are the various types of linked list.

Singly Linked Lists

Singly linked lists contain two “buckets” in one node; one bucket
holds the data and the other bucket holds the address of the next
node of the list. Traversals can be done in one direction only as
there is only a single link between two nodes of the same list.
Basic Operations in the Linked Lists
The basic operations in the linked lists are insertion, deletion,
searching, display, and deleting an element at a given key. These
operations are performed on Singly Linked Lists as given below −

 Insertion − Adds an element at the beginning of the list.

 Deletion − Deletes an element at the beginning of the list.
 Display − Displays the complete list.
 Search − Searches an element using the given key.
 Delete − Deletes an element using the given key.

Insertion Operation
Adding a new node in linked list is a more than one step activity.
We shall learn this with diagrams here. First, create a node using
the same structure and find the location where it has to be inserted.

Imagine that we are inserting a node B (NewNode), between A

(LeftNode) and C (RightNode). Then point B.next to C −

NewNode.next −> RightNode;

It should look like this −

Now, the next node at the left should point to the new node.

LeftNode.next −> NewNode;

This will put the new node in the middle of the two. The new list
should look like this −

Insertion in linked list can be done in three different ways. They are
explained as follows −

Insertion at Beginning

In this operation, we are adding an element at the beginning of the

list.

#include <bits/stdc++.h>

#include <string>

using namespace std;

struct node {

int data;

struct node *next;

};

struct node *head = NULL;

struct node *current = NULL;

// display the list

void printList(){

struct node *p = head;

cout << "\n[";

//start from the beginning

while(p != NULL) {

cout << " " << p->data << " ";

p = p->next;

cout << "]";

//insertion at the beginning

void insertatbegin(int data){

//create a link

struct node *lk = (struct node*) malloc(sizeof(struct node));

lk->data = data;

// point it to old first node

lk->next = head;

//point first to new first node

head = lk;
}

int main(){

insertatbegin(12);

insertatbegin(22);

insertatbegin(30);

insertatbegin(44);

insertatbegin(50);

cout << "Linked List: ";

// print list

printList();

Output
Linked List:
[ 50 44 30 22 12 ]

Insertion at Ending

In this operation, we are adding an element at the ending of the

list.

#include <bits/stdc++.h>
#include <string>
using namespace std;
struct node {
int data;
struct node *next;
};
struct node *head = NULL;
struct node *current = NULL;

// display the list

void printList(){
struct node *p = head;
cout << "\n[";

//start from the beginning

while(p != NULL) {
cout << " " << p->data << " ";
p = p->next;
}
cout << "]";
}

//insertion at the beginning

void insertatbegin(int data){

//create a link
struct node *lk = (struct node*) malloc(sizeof(struct node));
lk->data = data;

// point it to old first node

lk->next = head;

//point first to new first node

head = lk;
}
void insertatend(int data){

//create a link
struct node *lk = (struct node*) malloc(sizeof(struct node));
lk->data = data;
struct node *linkedlist = head;

// point it to old first node

while(linkedlist->next != NULL)
linkedlist = linkedlist->next;
//point first to new first node
linkedlist->next = lk;
}
int main(){
insertatbegin(12);
insertatend(22);
insertatbegin(30);
insertatend(44);
insertatbegin(50);
cout << "Linked List: ";

// print list
printList();
}
Output
Linked List:
[ 50 30 12 22 44 ]

Insertion at a Given Position

In this operation, we are adding an element at any position within

the list.

#include <bits/stdc++.h>
#include <string>
using namespace std;
struct node {
int data;
struct node *next;
};
struct node *head = NULL;
struct node *current = NULL;

// display the list

void printList(){
struct node *p = head;
cout << "\n[";

//start from the beginning

while(p != NULL) {
cout << " " << p->data << " ";
p = p->next;
}
cout << "]";
}

//insertion at the beginning

void insertatbegin(int data){

//create a link
struct node *lk = (struct node*) malloc(sizeof(struct node));
lk->data = data;

// point it to old first node

lk->next = head;

//point first to new first node

head = lk;
}
void insertafternode(struct node *list, int data){
struct node *lk = (struct node*) malloc(sizeof(struct node));
lk->data = data;
lk->next = list->next;
list->next = lk;
}
int main(){
insertatbegin(12);
insertatbegin(22);
insertatbegin(30);
insertafternode(head->next,44);
insertafternode(head->next->next, 50);
cout << "Linked List: ";
// print list
printList();
}
Output
Linked List:
[ 30 22 44 50 12 ]

Deletion Operation
Deletion is also a more than one step process. We shall learn with
pictorial representation. First, locate the target node to be removed,
by using searching algorithms.

The left (previous) node of the target node now should point to the
next node of the target node −

LeftNode.next −> TargetNode.next;

This will remove the link that was pointing to the target node. Now,
using the following code, we will remove what the target node is
pointing at.

TargetNode.next −> NULL;

We need to use the deleted node. We can keep that in memory
otherwise we can simply deallocate memory and wipe off the target
node completely.

Similar steps should be taken if the node is being inserted at the

beginning of the list. While inserting it at the end, the second last
node of the list should point to the new node and the new node will
point to NULL.

Deletion in linked lists is also performed in three different ways.

They are as follows −

Deletion at Beginning

In this deletion operation of the linked, we are deleting an element

from the beginning of the list. For this, we point the head to the
second node.

#include <bits/stdc++.h>

#include <string>

using namespace std;

struct node {

int data;

struct node *next;

};

struct node *head = NULL;

struct node *current = NULL;

// display the list

void printList(){

struct node *p = head;

cout << "\n[";

//start from the beginning

while(p != NULL) {

cout << " " << p->data << " ";

p = p->next;

cout << "]";

//insertion at the beginning

void insertatbegin(int data){

//create a link

struct node *lk = (struct node*) malloc(sizeof(struct node));

lk->data = data;

// point it to old first node

lk->next = head;
//point first to new first node

head = lk;

void deleteatbegin(){

head = head->next;

int main(){

insertatbegin(12);

insertatbegin(22);

insertatbegin(30);

insertatbegin(44);

insertatbegin(50);

cout << "Linked List: ";

// print list

printList();

deleteatbegin();

cout << "Linked List after deletion: ";

printList();

Output
Linked List:
[ 50 44 30 22 12 ]
Linked List after deletion:
[ 44 30 22 12 ]

Deletion at Ending

In this deletion operation of the linked, we are deleting an element

from the ending of the list.
#include <bits/stdc++.h>

#include <string>

using namespace std;

struct node {

int data;

struct node *next;

};

struct node *head = NULL;

struct node *current = NULL;

// Displaying the list

void printList(){

struct node *p = head;

while(p != NULL) {

cout << " " << p->data << " ";

p = p->next;

// Insertion at the beginning

void insertatbegin(int data){

//create a link

struct node *lk = (struct node*) malloc(sizeof(struct node));

lk->data = data;

// point it to old first node

lk->next = head;
//point first to new first node

head = lk;

void deleteatend(){

struct node *linkedlist = head;

while (linkedlist->next->next != NULL)

linkedlist = linkedlist->next;

linkedlist->next = NULL;

int main(){

insertatbegin(12);

insertatbegin(22);

insertatbegin(30);

insertatbegin(44);

insertatbegin(50);

cout << "Linked List: ";

// print list

printList();

deleteatend();

cout << "\nLinked List after deletion: ";

printList();

Output
Linked List: 50 44 30 22 12
Linked List after deletion: 50 44 30 22

Deletion at a Given Position

In this deletion operation of the linked, we are deleting an element
at any position of the list.

#include <bits/stdc++.h>

#include <string>

using namespace std;

struct node {

int data;

struct node *next;

};

struct node *head = NULL;

struct node *current = NULL;

// display the list

void printList(){

struct node *p = head;

cout << "\n[";

//start from the beginning

while(p != NULL) {

cout << " " << p->data << " ";

p = p->next;

cout << "]";

//insertion at the beginning

void insertatbegin(int data){

//create a link
struct node *lk = (struct node*) malloc(sizeof(struct node));

lk->data = data;

// point it to old first node

lk->next = head;

//point first to new first node

head = lk;

void deletenode(int key){

struct node *temp = head, *prev;

if (temp != NULL && temp->data == key) {

head = temp->next;

return;

// Find the key to be deleted

while (temp != NULL && temp->data != key) {

prev = temp;

temp = temp->next;

// If the key is not present

if (temp == NULL) return;

// Remove the node

prev->next = temp->next;

int main(){
insertatbegin(12);

insertatbegin(22);

insertatbegin(30);

insertatbegin(44);

insertatbegin(50);

cout << "Linked List: ";

// print list

printList();

deletenode(30);

cout << "Linked List after deletion: ";

printList();

Output
Linked List:
[ 50 44 30 22 12 ]Linked List after deletion:
[ 50 44 22 12 ]

Doubly Linked Lists

Doubly Linked Lists contain three “buckets” in one node; one bucket
holds the data and the other buckets hold the addresses of the
previous and next nodes in the list. The list is traversed twice as the
nodes in the list are connected to each other from both sides.

 Link − Each link of a linked list can store a data called an

element.
 Next − Each link of a linked list contains a link to the next link
called Next.
 Prev − Each link of a linked list contains a link to the previous
link called Prev.
 Linked List − A Linked List contains the connection link to the
first link called First and to the last link called Last.

Doubly Linked List Representation

As per the above illustration, following are the important points to

be considered.

 Doubly Linked List contains a link element called first and last.
 Each link carries a data field(s) and a link field called next.
 Each link is linked with its next link using its next link.
 Each link is linked with its previous link using its previous link.
 The last link carries a link as null to mark the end of the list

Insertion at the Beginning

In this operation, we create a new node with three compartments,

one containing the data, the others containing the address of its
previous and next nodes in the list. This new node is inserted at the
beginning of the list.

#include <iostream>

#include <cstring>

#include <cstdlib>

#include <cstdbool>

struct node {

int data;

int key;
struct node *next;

struct node *prev;

};

//this link always point to first Link

struct node *head = NULL;

//this link always point to last Link

struct node *last = NULL;

struct node *current = NULL;

//is list empty

bool isEmpty(){

return head == NULL;

//display the doubly linked list

void printList(){

struct node *ptr = head;

while(ptr != NULL) {

printf("(%d,%d) ",ptr->key,ptr->data);
ptr = ptr->next;

//insert link at the first location

void insertFirst(int key, int data){

//create a link

struct node *link = (struct node*) malloc(sizeof(struct node));

link->key = key;

link->data = data;

if(isEmpty()) {

//make it the last link

last = link;

} else {

//update first prev link

head->prev = link;

}
//point it to old first link

link->next = head;

//point first to new first link

head = link;

int main(){

insertFirst(1,10);

insertFirst(2,20);

insertFirst(3,30);

insertFirst(4,1);

insertFirst(5,40);

insertFirst(6,56);

printf("\nDoubly Linked List: ");

printList();

return 0;
}

Deletion at the Beginning

This deletion operation deletes the existing first nodes in the doubly
linked list. The head is shifted to the next node and the link is
removed.

#include <iostream>

#include <cstring>
#include <cstdlib>

#include <cstdbool>

struct node {

int data;

int key;

struct node *next;

struct node *prev;

};

//this link always point to first Link

struct node *head = NULL;

//this link always point to last Link

struct node *last = NULL;

struct node *current = NULL;

//is list empty

bool isEmpty(){

return head == NULL;

}
//display the doubly linked list

void printList(){

struct node *ptr = head;

while(ptr != NULL) {

printf("(%d,%d) ",ptr->key,ptr->data);

ptr = ptr->next;

//insert link at the first location

void insertFirst(int key, int data){

//create a link

struct node *link = (struct node*) malloc(sizeof(struct node));

link->key = key;

link->data = data;

if(isEmpty()) {

//make it the last link

last = link;

} else {
//update first prev link

head->prev = link;

//point it to old first link

link->next = head;

//point first to new first link

head = link;

//delete first item

struct node* deleteFirst(){

//save reference to first link

struct node *tempLink = head;

//if only one link

if(head->next == NULL) {

last = NULL;
} else {

head->next->prev = NULL;

head = head->next;

//return the deleted link

return tempLink;

int main(){

insertFirst(1,10);

insertFirst(2,20);

insertFirst(3,30);

insertFirst(4,1);

insertFirst(5,40);

insertFirst(6,56);

printf("\nDoubly Linked List: ");

printList();

printf("\nList after deleting first record: ");

deleteFirst();

printList();

return 0;
}
Doubly Linked List: (6,56) (5,40) (4,1) (3,30) (2,20) (1,10)
List after deleting first record: (5,40) (4,1) (3,30) (2,20) (1,10)

Insertion at the End

In this insertion operation, the new input node is added at the end
of the doubly linked list; if the list is not empty. The head will be
pointed to the new node, if the list is empty.

#include <iostream>

#include <cstring>

#include <cstdlib>

#include <cstdbool>

struct node {

int data;

int key;

struct node *next;

struct node *prev;

};

//this link always point to first Link

struct node *head = NULL;

//this link always point to last Link

struct node *last = NULL;

struct node *current = NULL;

//is list empty

bool isEmpty(){

return head == NULL;

//display the doubly linked list

void printList(){

struct node *ptr = head;

while(ptr != NULL) {

printf("(%d,%d) ",ptr->key,ptr->data);

ptr = ptr->next;

//insert link at the first location

void insertFirst(int key, int data){

//create a link

struct node *link = (struct node*) malloc(sizeof(struct node));

link->key = key;

link->data = data;

if(isEmpty()) {

//make it the last link

last = link;

} else {

//update first prev link

head->prev = link;

//point it to old first link

link->next = head;

//point first to new first link

head = link;

//insert link at the last location

void insertLast(int key, int data){

//create a link

struct node *link = (struct node*) malloc(sizeof(struct node));

link->key = key;

link->data = data;

if(isEmpty()) {

//make it the last link

last = link;

} else {

//make link a new last link

last->next = link;

//mark old last node as prev of new link

link->prev = last;

//point last to new last node

last = link;

}
int main(){

insertFirst(1,10);

insertFirst(2,20);

insertFirst(3,30);

insertFirst(4,1);

insertLast(5,40);

insertLast(6,56);

printf("\nDoubly Linked List: ");

printList();
return 0;
Output
Doubly Linked List: (4,1) (3,30) (2,20) (1,10) (5,40) (6,56)

Circular Linked Lists

Circular linked lists can exist in both singly linked list and doubly
linked list.

Since the last node and the first node of the circular linked list are
connected, the traversal in this linked list will go on forever until it
is broken.
Circular singly linked list is a type of data structure that is made up of nodes
that are created using self referential structures. Each of these nodes contain
two parts, namely the data and the reference to the next list node.

Only the reference to the first list node is required to access the whole linked
list. This is known as the head. The last node in the list points to head or first
node of the list. That is the reason this is known as a circular linked list.

A program to implement circular singly linked list is given as follows.

Example
Live Demo
#include <iostream>
using namespace std;
struct Node {
int data;
struct Node *next;
};
struct Node* head = NULL;
void insert(int newdata) {
struct Node *newnode = (struct Node
*)malloc(sizeof(struct Node));
struct Node *ptr = head;
newnode->data = newdata;
newnode->next = head;
if (head!= NULL) {
while (ptr->next != head)
ptr = ptr->next;
ptr->next = newnode;
} else
newnode->next = newnode;
head = newnode;
}
void display() {
struct Node* ptr;
ptr = head;
do {
cout<<ptr->data <<" ";
ptr = ptr->next;
} while(ptr != head);
}
int main() {
insert(3);
insert(1);
insert(7);
insert(2);
insert(9);
cout<<"The circular linked list is: ";
display();
return 0;
}

Output
The circular linked list is: 9 2 7 1 3

In the above program, the structure Node forms the linked list node. It contains
the data and a pointer to the next linked list node. This is given as follows.

struct Node {
int data;
struct Node *next;
};

The function insert() inserts the data into the beginning of the linked list. It
creates a newnode and inserts the number in the data field of the newnode. If
the head is NULL, then newnode points to itself otherwise the last node in the
circular linked list points to newnode. Then the head points to the start of the
list i.e. to the newnode. This is given below.
void insert(int newdata) {
struct Node *newnode = (struct Node
*)malloc(sizeof(struct Node));
struct Node *ptr = head;
newnode->data = newdata;
newnode->next = head;
if (head!= NULL) {
while (ptr->next != head)
ptr = ptr->next;
ptr->next = newnode;
} else
newnode->next = newnode;
head = newnode;
}

The function display() displays the whole linked list. First ptr points to head.
Then it is continuously forwarded to the next node until all the data values of
the nodes are printed. This is given below.

void display() {
struct Node* ptr;
ptr = head;
do {
cout<< ptr->data <<" ";
ptr = ptr->next;
} while(ptr != head);
}

In the function main(), first various values are inserted into the circular linked
list by calling insert(). Then the linked list is displayed. This is given below.

int main() {
insert(3);
insert(1);
insert(7);
insert(2);
insert(9);
cout<<"The circular linked list is: ";
display();
return 0;
}
void push_back(int newElement) {

//1. allocate node

Node* newNode = new Node();

//2. assign data element

newNode->data = newElement;

//3. assign null to the next of new node

newNode->next = NULL;

//4. Check the list is empty or not,

// if empty make the new node as head
if(head == NULL) {
head = newNode;
newNode->next = head;
} else {

//5. Else, traverse to the last node

Node* temp = head;
while(temp->next != head)
temp = temp->next;

//6. Adjust the links

temp->next = newNode;
newNode->next = head;
}
}

The below is a complete program that uses above discussed concept to

insert new node at the end of the circular singly linked list.

#include <iostream>
using namespace std;

//node structure
struct Node {
int data;
Node* next;
};

class LinkedList {
private:
Node* head;
public:
LinkedList(){
head = NULL;
}

//Add new element at the end of the list

void push_back(int newElement) {
Node* newNode = new Node();
newNode->data = newElement;
newNode->next = NULL;
if(head == NULL) {
head = newNode;
newNode->next = head;
} else {
Node* temp = head;
while(temp->next != head)
temp = temp->next;
temp->next = newNode;
newNode->next = head;
}
}

//display the content of the list

void PrintList() {
Node* temp = head;
if(temp != NULL) {
cout<<"The list contains: ";
while(true) {
cout<<temp->data<<" ";
temp = temp->next;
if(temp == head)
break;
}
cout<<endl;
} else {
cout<<"The list is empty.\n";
}
}
};

// test the code

int main() {
LinkedList MyList;

//Add three elements at the end of the list.

MyList.push_back(10);
MyList.push_back(20);
MyList.push_back(30);
MyList.PrintList();

return 0;
}

The above code will give the following output:

The list contains: 10 20 30