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 a Linked List ?
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.
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.
#include<iostream>
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;
}
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;
}
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;
}
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
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Login/Signup to comment