Linked List in C++
What is linked list in C++?
In C++, a linked list is a type of data structure used to store a sequence of elements. Unlike arrays, the elements (called nodes) in a linked list are not stored next to each other in memory. Each node has two parts: one holds the data, and the other holds the address of the next (or previous) node in the list. This makes it easy to add or remove elements without shifting other items around. Linked List in C++ is data structures and alternative to arrays, where every node of the linked list is made up of two parts data and pointer.
- Data: It stores the data of the node.
- Pointer: It stores the address of the next node.
What is Linked List in C++?
A linked list is a chain of nodes that are connected to one another using pointers. Each node in a linked list has the following two things –
- Data: Value stored in Linked List Data Structure
- Next Pointer: Contains the address to the next node
Comparison with Arrays
Arrays are sequential and contiguous structures. Linked lists are non-contiguous structures i.e. each node in the linked list is scattered all over memory and need not be contiguous.
This has a significant advantage as in the case of arrays we need to pre-declare the size of the array
- We can not increase the size of the array on requirement once the size is defined
- If the declared size of the array is too large and the requirement later is lesser, the size of the array can not be reduced, thus waste of memory.
However, in the case of Linked List, we can increase/decrease the size or number of nodes in real-time.
Types of Linked List
There are three types of Linked lists majorly –
Singly Linked List
In C++ Singly Linked List is a simple data structure that has a sequence of nodes connected to each other with pointers.
- Data:- Value held
- Next Pointer:- Contains the address of the next node in sequence
Syntax of a singly linked list:-
class node { int data; node *next; };
Doubly Linked List in C++
Doubly Linked Lists allows users to navigate through both the ends of a linked list, i.e., from head to tail and from tail to head. The beginning of the linked list is called header and the last node is the tail.
Syntax for doubly linked list:-
struct Node
{
int Data;
Struct Node* next;
Struct Node* prev;
}; Circular Linked List in C++
In a circular linked list, each node has the link to the next node, and the last node does not points to null rather points to the head of the list.
Syntax for a singly circular linked list:-
struct node
{
int data;
struct node *next;
}Construction of a Linked List
This set of code will create a new empty node in a linked list which will be storing integer type of data.
struct node
{
int data;
struct node *next;
};class Node{
public:
int data;
Node *next;
};C++ : Operations on Linked List
Insertion operations on linked list
- Insertion at beginning
- Insertion at end
- Insertion in between of nodes.
Deletion operations on linked list
- Deletion at beginning
- Deletion at end
- Deletion of a specific node.
Other operations on linked list
- Reverse a linked list
- Search an element in linked list
- Find middle of the linked list
- Fold a linked list
C++ Code for Creating/Deleting from a Linked List
We will cover the following methods –
- Method 1: Using struct
- Method 2: Using class but with external functions
- Method 3: Using class and member functions
#include< bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node* next;
// Pointer pointing towards next node
};
void insertFront (struct Node **head, int data)
{
// dynamically create memory for this newNode
struct Node *newNode = (struct Node *) malloc (sizeof (struct Node));
// assign data value
newNode->data = data;
// change the next node of this newNode
// to current head of Linked List
newNode->next = *head;
//re-assign head to this newNode
*head = newNode;
}
void deleteFront (struct Node *&head)
{
struct Node *temp = head;
// if there are no nodes in Linked List can't delete
if (head == NULL)
{
cout << "Linked List Empty, nothing to delete";
return;
}
// move head to next node *head = (*head)->next;
cout << "Value deleted: " << temp->data << endl;
// Node *temp = head;
head = head->next;
delete temp;
}
void display (struct Node *node)
{
cout << "\n\n";
// as linked list will end when Node is Null
while (node != NULL)
{
cout << node->data << " "; node = node->next;
}
cout << "\n" << endl;
}
int main ()
{
struct Node *head = NULL;
// Need '&' i.e. address as we need to change head
insertFront (&head, 6);
insertFront (&head, 12);
insertFront (&head, 18);
insertFront (&head, 24);
insertFront (&head, 30);
// No '&' as head is not changed
display (head);
deleteFront (head);
deleteFront (head);
display (head);
return 0;
}
Output
30 24 18 12 6 Value deleted: 30 Value deleted: 24 18 12 6
#include< iostream>
using namespace std;
class Node
{
public:
int data;
Node *next;
};
void insertFront(Node** head, int data){
// dynamically create memory for this newNode
Node* newNode = (Node*) malloc(sizeof(Node));
// assign data value
newNode->data = data;
// change the next node of this newNode
// to current head of Linked List
newNode->next = *head;
//re-assign head to this newNode
*head = newNode;
}
void deleteFront(Node *&head){
Node* temp = head;
// if there are no nodes in Linked List can't delete
if(head == NULL)
{
cout << "Linked List Empty, nothing to delete" ;
return;
}
// move head to next node *head = (*head)->next;
cout << "Value deleted: " << temp->data << endl;
head = head->next;
delete temp;
}
void display(Node* node){
cout << "\n\n";
// as linked list will end when Node is Null
while(node!=NULL)
{
cout << node->data << " "; node = node->next;
}
cout << "\n" << endl;
}
int main() {
Node* head = NULL;
// Need '&' i.e. address as we need to change head
insertFront(&head,6);
insertFront(&head,12);
insertFront(&head,18);
insertFront(&head,24);
insertFront(&head,30);
// No '&' as head is not changed
display(head);
deleteFront(head);
deleteFront(head);
display(head);
return 0;
}
Output
30 24 18 12 6 Value deleted: 30 Value deleted: 24 18 12 6
#include< iostream>
using namespace std;
class Node
{
public:
int data;
Node *next;
};
class LinkedList
{
private:
Node* head;
public:
LinkedList() { // constructor
head = NULL;
}
void insertFront(int data);
void deleteFront();
void display();
};
void LinkedList::insertFront(int data){
Node* newNode = new Node();
// assign data value
newNode->data = data;
// change the next node of this newNode
// to current head of Linked List
newNode->next = head;
//re-assign head to this newNode
head = newNode;
}
void LinkedList::deleteFront(){
Node* temp = head;
// if there are no nodes in Linked List can't delete
if(head == NULL)
{
cout << "Linked List Empty, nothing to delete" ;
return;
} // move head to next node head = head->next;
cout << "Value deleted: " << temp->data << endl;
head = head->next;
delete temp;
}
void LinkedList::display(){
cout << "\n\n";
// temporary variable to traverse
Node* node = head;
// as linked list will end when Node is Null
while(node!=NULL)
{
cout << node->data << " "; node = node->next;
}
cout << "\n" << endl;
}
int main() {
LinkedList* linked_list = new LinkedList();
// Need '&' i.e. address as we need to change head
linked_list->insertFront(6);
linked_list->insertFront(12);
linked_list->insertFront(18);
linked_list->insertFront(24);
linked_list->insertFront(30);
// No '&' as head is not changed
linked_list->display();
linked_list->deleteFront();
linked_list->deleteFront();
linked_list->display();
return 0;
}
Output
30 24 18 12 6 Value deleted: 30 Value deleted: 24 18 12 6
Login/Signup to comment