Linked list Flashcards
implementing a single linked list
#include (bits/stdc++.h> using namespace std;
struct Node{
int data;
Node* next;
Node(int x){
data=x;
next=NULL;
}
};
int main()
{
Node *head=new Node(10);
Node *temp1=new Node(20);
Node *temp2=new Node(30);
head->next=temp1;
temp1->next=temp2;
cout((head->data(("-->"((temp1->data(("-->"((temp2->data;
return 0;
}
traversal of a linked list from head to last node.
#include (bits/stdc++.h> using namespace std;
struct Node{
int data;
Node* next;
Node(int x){
data=x;
next=NULL;
}
};
void printlist(Node *head){
Node *curr=head;
while(curr!=NULL){
cout((curr->data((" ";
curr=curr->next;
}
}
int main()
{
Node *head=new Node(10);
head->next=new Node(20);
head->next->next=new Node(30);
head->next->next->next=new Node(40);
printlist(head);
return 0;
}
Recursive traversal of linked list
void traverse(Node* head)
{
if (head == NULL)
return;
// If head is not NULL, print current node // and recur for remaining list cout << head->data << " ";
traverse(head->next); }
Search in a linked list in both iterative and recursive approaches
#include (bits/stdc++.h> using namespace std;
struct Node{
int data;
Node* next;
Node(int x){
data=x;
next=NULL;
}
};
void printlist(Node *head){
Node *curr=head;
while(curr!=NULL){
cout((curr->data((" ";
curr=curr->next;
}cout((endl;
}
int search(Node * head, int x){
int pos=1;
Node *curr=head;
while(curr!=NULL){
if(curr->data==x)
return pos;
else{
pos++;
curr=curr->next;
}
}
return -1;
}
int main()
{
Node *head=new Node(10);
head->next=new Node(20);
head->next->next=new Node(30);
printlist(head);
cout(("Position of element in Linked List: "((search(head,20);
return 0;
}
Recursive approach
#include (bits/stdc++.h>
using namespace std;
struct Node{
int data;
Node* next;
Node(int x){
data=x;
next=NULL;
}
};
void printlist(Node *head){
Node *curr=head;
while(curr!=NULL){
cout((curr->data((" ";
curr=curr->next;
}cout((endl;
}
int search(Node * head, int x){
if(head==NULL)return -1;
if(head->data==x)return 1;
else{
int res=search(head->next,x);
if(res==-1)return -1;
else return res+1;
}
}
int main()
{
Node *head=new Node(10);
head->next=new Node(20);
head->next->next=new Node(30);
printlist(head);
cout(("Position of element in Linked List: "((search(head,20);
return 0;
}
insert at the beginning of Singly Linked List
#include (bits/stdc++.h> using namespace std;
struct Node{
int data;
Node* next;
Node(int x){
data=x;
next=NULL;
}
};
Node *insertBegin(Node *head,int x){
Node *temp=new Node(x);
temp->next=head;
return temp;
}
void printlist(Node *head){
Node *curr=head;
while(curr!=NULL){
cout((curr->data((" ";
curr=curr->next;
}
}
int main()
{
Node *head=NULL;
head=insertBegin(head,30);
head=insertBegin(head,20);
head=insertBegin(head,10);
printlist(head);
return 0;
}
insert a node at the end of linked list
#include (bits/stdc++.h> using namespace std;
struct Node{
int data;
Node* next;
Node(int x){
data=x;
next=NULL;
}
};
Node *insertEnd(Node *head,int x){
Node *temp=new Node(x);
if(head==NULL)return temp;
Node *curr=head;
while(curr->next!=NULL){
curr=curr->next;
}
curr->next=temp;
return head;
}
void printlist(Node *head){
Node *curr=head;
while(curr!=NULL){
cout((curr->data((" ";
curr=curr->next;
}
}
int main()
{
Node *head=NULL;
head=insertEnd(head,10);
head=insertEnd(head,20);
head=insertEnd(head,30);
printlist(head);
return 0;
}
delete first node of linked list
#include (bits/stdc++.h> using namespace std;
struct Node{
int data;
Node* next;
Node(int x){
data=x;
next=NULL;
}
};
void printlist(Node *head){
Node *curr=head;
while(curr!=NULL){
cout((curr->data((" ";
curr=curr->next;
}cout((endl;
}
Node *delHead(Node *head){
if(head==NULL)return NULL;
else{
Node *temp=head->next;
delete(head);
return temp;
}
}
int main()
{
Node *head=new Node(10);
head->next=new Node(20);
head->next->next=new Node(30);
printlist(head);
head=delHead(head);
printlist(head);
return 0; }
deletion of last node of a singly linked list
#include (bits/stdc++.h> using namespace std;
struct Node{
int data;
Node* next;
Node(int x){
data=x;
next=NULL;
}
};
void printlist(Node *head){
Node *curr=head;
while(curr!=NULL){
cout((curr->data((" ";
curr=curr->next;
}cout((endl;
}
Node *delTail(Node *head){
if(head==NULL)return NULL;
if(head->next==NULL){
delete head;
return NULL;
}
Node *curr=head;
while(curr->next->next!=NULL)
curr=curr->next;
delete (curr->next);
curr->next=NULL;
return head;
}
int main()
{
Node *head=new Node(10);
head->next=new Node(20);
head->next->next=new Node(30);
printlist(head);
head=delTail(head);
printlist(head);
return 0; }
Insertion at a given position in a linked list
Approach: To insert a given data at a specified position, the below algorithm is to be followed:
Traverse the Linked list upto position-1 nodes.
Once all the position-1 nodes are traversed, allocate memory and the given data to the new node.
Point the next pointer of the new node to the next of current node.
Point the next pointer of current node to the new node.
// C++ program for insertion in a single linked // list at a specified position #include (bits/stdc++.h> using namespace std;
// A linked list Node
struct Node {
int data;
struct Node* next;
};
// Size of linked list int size = 0;
// function to create and return a Node
Node* getNode(int data)
{
// allocating space
Node* newNode = new Node();
// inserting the required data newNode->data = data; newNode->next = NULL; return newNode; }
// function to insert a Node at required position
void insertPos(Node** current, int pos, int data)
{
// This condition to check whether the
// position given is valid or not.
if (pos ( 1 || pos > size + 1)
cout (( "Invalid position!" (( endl;
else {
// Keep looping until the pos is zero
while (pos--) {
if (pos == 0) {
// adding Node at required position Node* temp = getNode(data);
// Making the new Node to point to // the old Node at the same position temp->next = *current;
// Changing the pointer of the Node previous // to the old Node to point to the new Node *current = temp; } else // Assign double pointer variable to point to the // pointer pointing to the address of next Node current = &(*current)->next; } size++; } }
// This function prints contents
// of the linked list
void printList(struct Node* head)
{
while (head != NULL) {
cout (( " " (( head->data;
head = head->next;
}
cout (( endl;
}
// Driver Code
int main()
{
// Creating the list 3->5->8->10
Node* head = NULL;
head = getNode(3);
head->next = getNode(5);
head->next->next = getNode(8);
head->next->next->next = getNode(10);
size = 4; cout (( "Linked list before insertion: "; printList(head); int data = 12, pos = 3; insertPos(&head, pos, data); cout (( "Linked list after insertion of 12 at position 3: "; printList(head);
// front of the linked list data = 1, pos = 1; insertPos(&head, pos, data); cout (( "Linked list after insertion of 1 at position 1: "; printList(head);
// insertion at end of the linked list data = 15, pos = 7; insertPos(&head, pos, data); cout (( "Linked list after insertion of 15 at position 7: "; printList(head);
return 0; }
Sorted insert in a linked list
Algorithm:
Let input linked list is sorted in increasing order.
1) If Linked list is empty then make the node as
head and return it.
2) If the value of the node to be inserted is smaller
than the value of the head node, then insert the node
at the start and make it head.
3) In a loop, find the appropriate node after
which the input node (let 9) is to be inserted.
To find the appropriate node start from the head,
keep moving until you reach a node GN (10 in
the below diagram) who’s value is greater than
the input node. The node just before GN is the
appropriate node (7).
4) Insert the node (9) after the appropriate node
(7) found in step 3.
Implementation:
/* Program to insert in a sorted list */
#include (bits/stdc++.h>
using namespace std;
/* Link list node */
class Node {
public:
int data;
Node* next;
};
/* function to insert a new_node
in a list. Note that this
function expects a pointer to
head_ref as this can modify the
head of the input linked list
(similar to push())*/
void sortedInsert(Node** head_ref,
Node* new_node)
{
Node* current;
/* Special case for the head end */
if (*head_ref == NULL
|| (*head_ref)->data
>= new_node->data) {
new_node->next = *head_ref;
*head_ref = new_node;
}
else {
/* Locate the node before the
point of insertion */
current = *head_ref;
while (current->next != NULL
&& current->next->data
( new_node->data) {
current = current->next;
}
new_node->next = current->next;
current->next = new_node;
}
}
/* BELOW FUNCTIONS ARE JUST UTILITY TO TEST sortedInsert */
/* A utility function to
create a new node */
Node* newNode(int new_data)
{
/* allocate node */
Node* new_node = new Node();
/* put in the data */ new_node->data = new_data; new_node->next = NULL;
return new_node; }
/* Function to print linked list */
void printList(Node* head)
{
Node* temp = head;
while (temp != NULL) {
cout (( temp->data (( " ";
temp = temp->next;
}
}
/* Driver program to test count function*/
int main()
{
/* Start with the empty list */
Node* head = NULL;
Node* new_node = newNode(5);
sortedInsert(&head, new_node);
new_node = newNode(10);
sortedInsert(&head, new_node);
new_node = newNode(7);
sortedInsert(&head, new_node);
new_node = newNode(3);
sortedInsert(&head, new_node);
new_node = newNode(1);
sortedInsert(&head, new_node);
new_node = newNode(9);
sortedInsert(&head, new_node);
cout (( "Created Linked List\n";
printList(head);
return 0; } // This is code is contributed by rathbhupendra
Middle of a linked list
Naive approach=
#include (bits/stdc++.h>
using namespace std;
struct Node{
int data;
Node* next;
Node(int x){
data=x;
next=NULL;
}
};
void printlist(Node *head){
Node *curr=head;
while(curr!=NULL){
cout((curr->data((" ";
curr=curr->next;
}cout((endl;
}
void printMiddle(Node * head){
if(head==NULL)return;
int count=0;
Node *curr;
for(curr=head;curr!=NULL;curr=curr->next)
count++;
curr=head;
for(int i=0;i(count/2;i++)
curr=curr->next;
cout((curr->data;
}
int main()
{
Node *head=new Node(10);
head->next=new Node(20);
head->next->next=new Node(30);
head->next->next->next=new Node(40);
head->next->next->next->next=new Node(50);
printlist(head);
cout(("Middle of Linked List: ";
printMiddle(head);
return 0;
}
Efficient approach-
#include (bits/stdc++.h>
using namespace std;
struct Node{
int data;
Node* next;
Node(int x){
data=x;
next=NULL;
}
};
void printlist(Node *head){
Node *curr=head;
while(curr!=NULL){
cout((curr->data((" ";
curr=curr->next;
}cout((endl;
}
void printMiddle(Node * head){
if(head==NULL)return;
Node *slow=head,*fast=head;
while(fast!=NULL&&fast->next!=NULL){
slow=slow->next;
fast=fast->next->next;
}
cout((slow->data;
}
int main()
{
Node *head=new Node(10);
head->next=new Node(20);
head->next->next=new Node(30);
head->next->next->next=new Node(40);
head->next->next->next->next=new Node(50);
printlist(head);
cout(("Middle of Linked List: ";
printMiddle(head);
return 0;
}
finding the n-th node from the end of a given linked list
Method 1(Using length of Linked List) #include (bits/stdc++.h> using namespace std;
struct Node{
int data;
Node* next;
Node(int x){
data=x;
next=NULL;
}
};
void printlist(Node *head){
Node *curr=head;
while(curr!=NULL){
cout((curr->data((" ";
curr=curr->next;
}cout((endl;
}
void printNthFromEnd(Node * head,int n){
int len=0;
for(Node *curr=head;curr!=NULL;curr=curr->next)
len++;
if(len(n)
return;
Node *curr=head;
for(int i=1;i(len-n+1;i++)
curr=curr->next;
cout(((curr->data)((" ";
}
int main()
{
Node *head=new Node(10);
head->next=new Node(20);
head->next->next=new Node(30);
head->next->next->next=new Node(40);
head->next->next->next->next=new Node(50);
printlist(head);
cout(("Nth node from end of Linked List: ";
printNthFromEnd(head,2);
return 0;
}
Method 2(Using Two Pointers/References
#include (bits/stdc++.h>
using namespace std;
struct Node{
int data;
Node* next;
Node(int x){
data=x;
next=NULL;
}
};
void printlist(Node *head){
Node *curr=head;
while(curr!=NULL){
cout((curr->data((" ";
curr=curr->next;
}cout((endl;
}
void printNthFromEnd(Node * head,int n){
if(head==NULL)return;
Node *first=head;
for(int i=0;i(n;i++){
if(first==NULL)return;
first=first->next;
}
Node *second=head;
while(first!=NULL){
second=second->next;
first=first->next;
}
cout(((second->data);
}
int main()
{
Node *head=new Node(10);
head->next=new Node(20);
head->next->next=new Node(30);
head->next->next->next=new Node(40);
head->next->next->next->next=new Node(50);
printlist(head);
cout(("Nth node from end of Linked List: ";
printNthFromEnd(head,2);
return 0;
}
reversing a linked list in an iterative manner
Naive Code
#include (bits/stdc++.h>
using namespace std;
struct Node{
int data;
Node* next;
Node(int x){
data=x;
next=NULL;
}
};
void printlist(Node *head){
Node *curr=head;
while(curr!=NULL){
cout((curr->data((" ";
curr=curr->next;
}cout((endl;
}
Node *revList(Node *head){
vector(int> arr;
for(Node *curr=head;curr!=NULL;curr=curr->next){
arr.push_back(curr->data);
}
for(Node *curr=head;curr!=NULL;curr=curr->next){
curr->data=arr.back();
arr.pop_back();
}
return head;
}
int main()
{
Node *head=new Node(10);
head->next=new Node(20);
head->next->next=new Node(30);
printlist(head);
head=revList(head);
printlist(head);
return 0;
}
Efficient Code
#include (bits/stdc++.h>
using namespace std;
struct Node{
int data;
Node* next;
Node(int x){
data=x;
next=NULL;
}
};
void printlist(Node *head){
Node *curr=head;
while(curr!=NULL){
cout((curr->data((" ";
curr=curr->next;
}cout((endl;
}
Node *reverse(Node *head){
Node *curr=head;
Node *prev=NULL;
while(curr!=NULL){
Node *next=curr->next;
curr->next=prev;
prev=curr;
curr=next;
}
return prev;
}
int main()
{
Node *head=new Node(10);
head->next=new Node(20);
head->next->next=new Node(30);
printlist(head);
head=reverse(head);
printlist(head);
return 0;
}
Recursive reverse of a linked list
#include (bits/stdc++.h> using namespace std;
struct Node{
int data;
Node* next;
Node(int x){
data=x;
next=NULL;
}
};
void printlist(Node *head){
Node *curr=head;
while(curr!=NULL){
cout((curr->data((" ";
curr=curr->next;
}cout((endl;
}
Node *recRevL(Node *head){
if(head==NULL||head->next==NULL)return head;
Node *rest_head=recRevL(head->next);
Node *rest_tail=head->next;
rest_tail->next=head;
head->next=NULL;
return rest_head;
}
int main()
{
Node *head=new Node(10);
head->next=new Node(20);
head->next->next=new Node(30);
printlist(head);
head=recRevL(head);
printlist(head);
return 0;
}
Method 2- In this method a tail recursive solution is discussed to reverse the linked list. This method simply follows the iterative solution.
#include (bits/stdc++.h> using namespace std;
struct Node{
int data;
Node* next;
Node(int x){
data=x;
next=NULL;
}
};
void printlist(Node *head){
Node *curr=head;
while(curr!=NULL){
cout((curr->data((" ";
curr=curr->next;
}cout((endl;
}
Node *recRevL(Node *curr,Node *prev){
if(curr==NULL)return prev;
Node *next=curr->next;
curr->next=prev;
return recRevL(next,curr);
}
int main()
{
Node *head=new Node(10);
head->next=new Node(20);
head->next->next=new Node(30);
printlist(head);
head=recRevL(head,NULL);
printlist(head);
return 0;
}
Remove duplicates from a sorted single linked list
Algorithm:
Traverse the list from the head (or start) node. While traversing, compare each node with its next node. If the data of the next node is the same as the current node then delete the next node. Before we delete a node, we need to store the next pointer of the node
/* C++ Program to remove duplicates from a sorted linked list */ #include (bits/stdc++.h> using namespace std;
/* Link list node */
class Node
{
public:
int data;
Node* next;
};
/* The function removes duplicates from a sorted list */
void removeDuplicates(Node* head)
{
/* Pointer to traverse the linked list */
Node* current = head;
/* Pointer to store the next pointer of a node to be deleted*/ Node* next_next;
/* do nothing if the list is empty */ if (current == NULL) return;
/* Traverse the list till last node */
while (current->next != NULL)
{
/* Compare current node with next node */
if (current->data == current->next->data)
{
/* The sequence of steps is important*/
next_next = current->next->next;
free(current->next);
current->next = next_next;
}
else /* This is tricky: only advance if no deletion */
{
current = current->next;
}
}
}
/* UTILITY FUNCTIONS */
/* Function to insert a node at the beginning of the linked list */
void push(Node** head_ref, int new_data)
{
/* allocate node */
Node* new_node = new Node();
/* put in the data */ new_node->data = new_data;
/* link the old list off the new node */ new_node->next = (*head_ref);
/* move the head to point to the new node */ (*head_ref) = new_node; }
/* Function to print nodes in a given linked list */
void printList(Node *node)
{
while (node!=NULL)
{
cout((" "((node->data;
node = node->next;
}
}
/* Driver program to test above functions*/
int main()
{
/* Start with the empty list */
Node* head = NULL;
/* Let us create a sorted linked list to test the functions Created linked list will be 11->11->11->13->13->20 */ push(&head, 20); push(&head, 13); push(&head, 13); push(&head, 11); push(&head, 11); push(&head, 11);
cout(("Linked list before duplicate removal ";
printList(head);
/* Remove duplicates from linked list */ removeDuplicates(head);
cout(("\nLinked list after duplicate removal ";
printList(head);
return 0; }
// This code is contributed by rathbhupendra
Given a singly linked list of integers. The task is to display the linked list.
Example 1:
Input: LinkedList: 1->2->3->4->5 Output: 1 2 3 4 5 Constraints: 1 <= Number of nodes <= 100 0 <= value of nodes<= 103
vector displayList(Node *head)
{
vector v;
Node *temp = head;
while (temp != NULL) {
v.push_back(temp->data);
temp=temp->next;
}
return v;
}Given a singly linked list of size N. The task is to sum the elements of the linked list.
Example 1:
Input:
LinkedList: 1->2->3->4->5
Output: 15
Example 2:
Input:
LinkedList: 2->4->6->7->5->1->0
Output: 25
Your Task:
Your task is to complete the given function sumOfElements(), which takes head reference as argument and should return the sum of all the nodes in the Linked List.
Constraints:
1 <= n <= 100
1 <= value <= 103
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
int sumOfElements(Node *head)
{
int sum = 0;
Node* ptr;
ptr = head;
while (ptr != NULL) {
sum += ptr->data;
ptr = ptr->next;
}
return sum;
}
Count nodes of linked list
int getCount(struct Node* head){
int count = 0;
Node* current = head;
while (current != NULL) {
count++;
current = current->next;
}
return count;
}
Maximum And Minimum In Linked List
int maximum(Node *head)
{
int max = INT_MIN;
while (head != NULL) {
if (max < head->data) {
max = head->data;
}
head = head->next;
}
return max;
}
int minimum(Node *head)
{
int min = INT_MAX;
while (head != NULL) {
if (min > head->data) {
min = head->data;
}
head = head->next;
}
return min;
}
Search In Linked List
bool searchLinkedList(Node *head, int x)
{
Node* current = head;
while (current != NULL) {
if (current->data == x) {
return true;
}
current = current->next;
}
return false;
}Linked List Insertion at the end
Node *insertAtBegining(Node *head, int x) {
Node *temp = new Node(x);
temp->next=head;
return temp;
}
//Function to insert a node at the end of the linked list.
Node *insertAtEnd(Node *head, int x) {
Node*temp = new Node(x);
if(head == NULL){
return temp;
}
Node *curr=head;
while(curr->next!=NULL){
curr=curr->next;
}
curr->next=temp;
return head;
}
Given a linked list of size N and a key. The task is to insert the key in the middle of the linked list.
Example 1:
Input: LinkedList = 1->2->4 key = 3 Output: 1 2 3 4 Explanation: The new element is inserted after the current middle element in the linked list. Example 2:
Input: LinkedList = 10->20->40->50 key = 30 Output: 10 20 30 40 50 Explanation: The new element is inserted after the current middle element in the linked list and Hence, the output is 10 20 30 40 50.
Your Task:
The task is to complete the function insertInMiddle() which takes head reference and element to be inserted as the arguments. The printing is done automatically by the driver code.
Expected Time Complexity : O(N)
Expected Auxilliary Space : O(1)
Constraints:
1 <= N <= 104
Node* insertInMiddle(Node* head, int x)
{
if(head == NULL)
return NULL;
Node *a=head, *b=head;
while(1)
{
if(b->next==NULL)
break;
if( b->next->next==NULL)
break;
a=a->next;
b=b->next->next;
}
Node *c = new Node(x);
c->next=a->next;
a->next=c;
return head;
}
Linked List Insertion At Position
void insertAtPosition(Node *head, int pos, int data)
{
Node* temp=new Node(data);
int count=1;
while(head!=NULL) {
if(count==pos)
break;
head=head->next;
count++;
}
if(head==NULL)
return;
temp->next=head->next;
head->next=temp;
}
Insert In Sorted Linked List
Node * insertInSorted(Node * head, int data) {
Node *curr=head;
Node *temp=new Node(data);
if(head==NULL) {
return NULL;
}
if(head->data > temp->data) {
temp->next=head;
return temp;
}
while(curr->next!=NULL && curr->next->data < temp->data) {
curr=curr->next;
}
temp->next=curr->next;
curr->next=temp;
return head;
if(curr->next==NULL) {
curr=curr->next;
}
else {
curr->next=temp;
temp->next=NULL;
return head;
}
Delete Tail of Linked List
Node * deleteTail(Node *head)
{
if (head==NULL) return head;
else if (head->next == NULL) {
delete(head);
head = NULL;
}
else {
Node* ptr=head;
Node* ptr2=head;
while (ptr->next != NULL) {
ptr2=ptr;
ptr = ptr->next;
}
ptr2->next = NULL;
delete(ptr);
ptr=NULL;
return head; } }
Delete Head of Linked List
Node * deleteHead(Node *head)
{
if (head == NULL) return head;
Node * temp=head;
head=head->next;
temp->next=NULL;
delete temp; return head;
}
Linked List Delete at Position
Node * deleteAtPosition(Node *head,int pos)
{
if (pos==1) {
Node* temp = head;
head = head->next;
temp->next = NULL;
delete temp;
return head; } Node* curr = head; Node* prev = head;
int count = 1;
while (countnext;
}
Node* temp = curr->next;
prev->next = temp;
curr->next = NULL;
delete curr;
return head; }
Is Linked List Sorted
bool isSorted(Node * head)
{
if(head==NULL || head->next==NULL)
return true;
bool increasing=true;
bool decreasing=true;
Node * temp=head;
Node * temp2=head->next;
while(temp2)
{
if(temp2->datadata)
increasing=false;
temp2=temp2->next;
temp=temp->next;
}
temp=head;
temp2=head->next;
while(temp2)
{
if(temp2->data>temp->data)
decreasing=false;
temp2=temp2->next;
temp=temp->next;
}
return increasing||decreasing;
}
Join Two Linked Lists
Node * joinTheLists(Node * head1, Node * head2)
{
if (head1 == NULL or head2 == NULL ) return head1;
Node* curr = head1;
while (curr->next != NULL) {
curr = curr->next;
}
curr->next = head2;
return head1;
}Identical Linked Lists
while (head1 != NULL and head2 != NULL) {
if (head1->data != head2->data)
return false;
head1 = head1->next;
head2 = head2->next;
}
return true;
}Reverse a linked list
struct Node* reverseList(struct Node *head)
{
Node* preptr = NULL;
Node* currptr = head;
Node* nextptr;
while(currptr!=NULL){
nextptr=currptr->next;
currptr->next=preptr;
preptr=currptr;
currptr=nextptr;
}
return preptr;
}
Definition of a linked list
Linked Lists are linear or sequential data structures in which elements are stored at non-contiguous memory locations and are linked to each other using pointers.
Like arrays, linked lists are also linear data structures but in linked lists elements are not stored at contiguous memory locations. They can be stored anywhere in the memory but for sequential access, the nodes are linked to each other using pointers.
Advantages of Linked Lists over Arrays:
The size of the arrays is fixed, so we must know the upper limit on the number of elements in advance. Also, generally, the allocated memory is equal to the upper limit irrespective of the usage. On the other hand, linked lists are dynamic and the size of the linked list can be incremented or decremented during runtime.
Inserting a new element in an array of elements is expensive, because a room has to be created for the new elements, and to create room, existing elements have to shift.
On the other hand, nodes in linked lists can be inserted or deleted without any shift operation and is efficient than that of arrays.
Disadvantages of Linked Lists:
Random access is not allowed in Linked Lists. We have to access elements sequentially starting from the first node. So, we cannot do a binary search with linked lists efficiently with its default implementation. Therefore, lookup or search operation is costly in linked lists in comparison to arrays.
Extra memory space for a pointer is required with each element of the list.
Not cache-friendly. Since array elements are present at contiguous locations, there is a locality of reference which is not there in the case of linked lists.
Singly Vs Doubly Linked List (Advantages & Disadvantages
circular doubly linked list. It talks about its advantages and insertion
#include (bits/stdc++.h> using namespace std;
struct Node{
int data;
Node *prev;
Node* next;
Node(int d){
data=d;
prev=NULL;
next=NULL;
}
};
void printlist(Node *head){
if(head==NULL)return;
Node *p=head;
do{
cout((p->data((" ";
p=p->next;
}while(p!=head);
}
Node *insertAtHead(Node *head,int x){
Node *temp=new Node(x);
if(head==NULL){
temp->next=temp;
temp->prev=temp;
return temp;
}
temp->prev=head->prev;
temp->next=head;
head->prev->next=temp;
head->prev=temp;
return temp;
}
int main()
{
Node *head=new Node(10);
Node *temp1=new Node(20);
Node *temp2=new Node(30);
head->next=temp1;
temp1->next=temp2;
temp2->next=head;
temp2->prev=temp1;
temp1->prev=head;
head->prev=temp2;
head=insertAtHead(head,5);
printlist(head);
return 0;
}
