Linked Lists | CSE205 : DATA STRUCTURES AND ALGORITHMS | B.Tech CSE

byOne • • 2 min read
2

Linked Lists

A linked list is a linear data structure used for storing collection of data in the form of nodes.

Array vs Linked List:


1) SINGLE LINKED LIST:


1.1) Representation of Single Linked List:


CODE:

struct Node{
    int data;
    Node *next;
};
Node *head = nullptr;

1.2) Traversal in Singly Linked List:


CODE:

#include <iostream>
using namespace std;

struct Node{
    int data;
    Node *next;
};
Node *head = nullptr;

void PrintLinkedList(){
    cout << "Data element in Singly Linked List are: ";
    Node *current = head;
    while (current != nullptr){
        cout << current->data << " ";
        current = current->next;
    }
    cout << endl;
}

1.3) Insertion at the Beginning of Singly Linked List:


CODE:

#include <iostream>
using namespace std;

struct Node{
    int data;
    Node *next;
};
Node *head = nullptr;

void InsertAtFirst(int value){
    Node *newNode = new Node;
    newNode->data = value;
    newNode->next = head;
    head = newNode;
}

void PrintLinkedList(){
    cout << "Data element in Singly Linked List are: ";
    Node *current = head;
    while (current != nullptr){
        cout << current->data << " ";
        current = current->next;
    }
    cout << endl;
}

int main(){
    InsertAtFirst(5);
    InsertAtFirst(10);
    InsertAtFirst(15);
    PrintLinkedList();
}

OUTPUT:

Data element in Singly Linked List are: 15 10 5

1.4) Insertion at the End of Singly Linked List:


CODE:

#include <iostream>
using namespace std;

struct Node{
    int data;
    Node *next;
};
Node *head = nullptr;

void InsertAtEnd(int value){
    Node *newNode = new Node;
    newNode->data = value;
    newNode->next = nullptr;
    if(head == nullptr){
        head = newNode;
        return;
    }
    Node *current = head;
    while(current->next != nullptr){
        current = current->next;
    }
    current->next = newNode;
}

void PrintLinkedList(){
    cout << "Data element in Singly Linked List are: ";
    Node *current = head;
    while (current != nullptr){
        cout << current->data << " ";
        current = current->next;
    }
    cout << endl;
}

int main(){
    InsertAtEnd(5);
    InsertAtEnd(10);
    InsertAtEnd(15);
    PrintLinkedList();
    return 0;
}

OUTPUT:

Data element in Singly Linked List are: 5 10 15

1.5) Insertion at the Position of Singly Linked List:


CODE:

#include <iostream>
using namespace std;

struct Node{
    int data;
    Node *next;
};
Node *head = nullptr;

void InsertAtPosition(int pos, int value){
    Node *newNode = new Node;
    newNode->data = value;
    if (pos <= 0) {
        cout << "Position should be greater than 0." << endl;
        return;
    }
    if(pos == 1){
        newNode->next = head;
        head = newNode;
        return;
    }
    Node *current = head;
    for(int i = 1; i < pos-1 && current != nullptr; i++){
        current = current->next;
    }
    if(current == nullptr){
        cout << "Position is greater than the current list size." << endl;
        return;
    }
    newNode->next = current->next;
    current->next = newNode;
}

void PrintLinkedList(){
    cout << "Data element in Singly Linked List are: ";
    Node *current = head;
    while (current != nullptr){
        cout << current->data << " ";
        current = current->next;
    }
    cout << endl;
}

int main(){
    InsertAtPosition(1,5);
    InsertAtPosition(2,10);
    InsertAtPosition(2,15);
    PrintLinkedList();
    return 0;
}

OUTPUT:

Data element in Singly Linked List are: 5 15 10

1.6) Deletion at the Beginning of Singly Linked List:


CODE:

#include <iostream>
using namespace std;

struct Node{
    int data;
    Node *next;
};
Node *head = nullptr;

void InsertAtFirst(int value){
    Node *newNode = new Node;
    newNode->data = value;
    newNode->next = head;
    head = newNode;
}

void DeleteAtFirst(){
    if(head == nullptr){
        cout << "Empty Linked List!" << endl;
        return;
    }
   Node *current = head;
    head = head->next;
    delete current;
}

void PrintLinkedList(){
    cout << "Data element in Singly Linked List are: ";
    Node *current = head;
    while (current != nullptr){
        cout << current->data << " ";
        current = current->next;
    }
    cout << endl;
}

int main(){
    cout << "#for empty linked list:" << endl;
    DeleteAtFirst();
    cout << "#after inserting value in linked list:" << endl;
    InsertAtFirst(5);
    InsertAtFirst(10);
    InsertAtFirst(15);
    PrintLinkedList();
    cout << "#after deleting first value in linked list:" << endl;
    DeleteAtFirst();
    DeleteAtFirst();
    PrintLinkedList();
}

OUTPUT:

#for empty linked list:
Empty Linked List!
#after inserting value in linked list:
Data element in Singly Linked List are: 15 10 5 
#after deleting first value in linked list:
Data element in Singly Linked List are: 5 

1.7) Deletion at the End of Singly Linked List:


CODE:

#include <iostream>
using namespace std;

struct Node{
    int data;
    Node *next;
};
Node *head = nullptr;

void InsertAtFirst(int value){
    Node *newNode = new Node;
    newNode->data = value;
    newNode->next = head;
    head = newNode;
}

void DeleteAtEnd(){
    if(head == nullptr){
        cout << "Empty Linked List!" << endl;
        return;
    }
    if(head->next == nullptr){
        delete head;
        head = nullptr;
        return;
    }
    Node *current = head;
    while(current->next->next != nullptr){
        current = current->next;
    }
    delete current->next;
    current->next = nullptr;
}

void PrintLinkedList(){
    cout << "Data element in Singly Linked List are: ";
    Node *current = head;
    while (current != nullptr){
        cout << current->data << " ";
        current = current->next;
    }
    cout << endl;
}

int main(){
    cout << "#for empty linked list:" << endl;
    DeleteAtEnd();
    cout << "#after inserting value in linked list:" << endl;
    InsertAtFirst(5);
    InsertAtFirst(10);
    InsertAtFirst(15);
    PrintLinkedList();
    cout << "#after deleting last value in linked list:" << endl;
    DeleteAtEnd();
    DeleteAtEnd();
    PrintLinkedList();
}

OUTPUT:

#for empty linked list:
Empty Linked List!
#after inserting value in linked list:
Data element in Singly Linked List are: 15 10 5 
#after deleting last value in linked list:
Data element in Singly Linked List are: 15 

1.8) Deletion at the Position of Singly Linked List:


CODE:

#include <iostream>
using namespace std;

struct Node{
    int data;
    Node *next;
};
Node *head = nullptr;

void InsertAtFirst(int value){
    Node *newNode = new Node;
    newNode->data = value;
    newNode->next = head;
    head = newNode;
}

void DeleteAtPosition(int pos){
    if(head == nullptr){
        cout << "Empty Linked List!" << endl;
        return;
    }
    if (pos <= 0){ 
         cout << "Position must be greater than 0!" << endl; 
          return; 
     }
    Node *current = head;
    if(pos == 1){
        head = current->next;
        delete current;
        return;
    }
    for(int i = 1; i < pos-1 && current != nullptr; i++){
        current = current->next;
    }
    if(current == nullptr || current->next == nullptr){
        cout << "Position does not exist!" << endl;
        return;
    }
    Node *next = current->next->next;
    delete current->next;
    current->next = next;
}

void PrintLinkedList(){
    cout << "Data element in Singly Linked List are: ";
    Node *current = head;
    while (current != nullptr){
        cout << current->data << " ";
        current = current->next;
    }
    cout << endl;
}

int main(){
    cout << "#for empty linked list:" << endl;
    DeleteAtPosition(1);
    cout << "#after inserting value in linked list:" << endl;
    InsertAtFirst(5);
    InsertAtFirst(10);
    InsertAtFirst(15);
    PrintLinkedList();
    cout << "#after deleting position 2 value in linked list:" << endl;
    DeleteAtPosition(2);
    PrintLinkedList();
     cout << "#after deleting position 3 value in linked list:" << endl;
    DeleteAtPosition(3);
    PrintLinkedList();
}

OUTPUT:

#for empty linked list:
Empty Linked List!
#after inserting value in linked list:
Data element in Singly Linked List are: 15 10 5 
#after deleting position 2 value in linked list:
Data element in Singly Linked List are: 15 5 
#after deleting position 3 value in linked list:
Position does not exit!
Data element in Singly Linked List are: 15 5

2) TWO-WAY LINKED LIST:


2.1) Representation of Double Linked List:


CODE:

struct Node{
    int data;
    Node *next;
    Node *prev;
};
Node *head = nullptr;

2.2) Traversal in Double Linked List:


CODE:

#include <iostream>
using namespace std;

struct Node{
    int data;
    Node *next;
    Node *prev;
};
Node *head = nullptr;

void PrintLinkedList(){
    cout << "Data element in Double Linked List are: ";
    Node *current = head;
    while (current != nullptr){
        cout << current->data << " ";
        current = current->next;
    }
    cout << endl;
}

2.3) Insertion at the Beginning of Double Linked List:


CODE:

#include <iostream>
using namespace std;

struct Node{
    int data;
    Node *next;
    Node *prev;
};
Node *head = nullptr;

void InsertAtFirst(int value){
    Node *newNode = new Node;
    newNode->data = value;
    newNode->next = head;
    newNode->prev = nullptr;
    if(head != nullptr){
        head->prev = newNode;
    }
    head = newNode;
}

void PrintLinkedList(){
    cout << "Data element in Double Linked List are: ";
    Node *current = head;
    while (current != nullptr){
        cout << current->data << " ";
        current = current->next;
    }
    cout << endl;
}

int main(){
    InsertAtFirst(5);
    InsertAtFirst(10);
    InsertAtFirst(15);
    PrintLinkedList();
}

OUTPUT:

Data element in Double Linked List are: 15 10 5

2.4) Insertion at the End of Double Linked List:


CODE:

#include <iostream>
using namespace std;

struct Node{
    int data;
    Node *next;
    Node *prev;
};
Node *head = nullptr;

void InsertAtEnd(int value){
    Node *newNode = new Node;
    newNode->data = value;
    newNode->next = nullptr;
    newNode->prev = nullptr;
    if(head == nullptr){
        head = newNode;
        return;
    }
    Node *current = head;
    while(current->next != nullptr){
        current = current->next;
    }
    current->next = newNode;
    newNode->prev = current;
}

void PrintLinkedList(){
    cout << "Data element in Double Linked List are: ";
    Node *current = head;
    while (current != nullptr){
        cout << current->data << " ";
        current = current->next;
    }
    cout << endl;
}

int main(){
    InsertAtEnd(5);
    InsertAtEnd(10);
    InsertAtEnd(15);
    PrintLinkedList();
    return 0;
}

OUTPUT:

Data element in Double Linked List are: 5 10 15

2.5) Insertion at the Position of Double Linked List:


CODE:

#include <iostream>
using namespace std;

struct Node{
    int data;
    Node *next;
    Node *prev;
};
Node *head = nullptr;

void InsertAtPosition(int pos, int value){
    Node *newNode = new Node;
    newNode->data = value;
    if (pos <= 0) {
        cout << "Position should be greater than 0." << endl;
        return;
    }
    if(pos == 1){
        newNode->next = head;
        newNode->prev = nullptr;
        if(head != nullptr){
            head->prev = newNode;
        }
        head = newNode;
        return;
    }
    Node *current = head;
    for(int i = 1; i < pos-1 && current != nullptr; i++){
        current = current->next;
    }
    if(current == nullptr){
        cout << "Position is greater than the current list size." << endl;
        return;
    }
    newNode->next = current->next;
    newNode->prev = current;
    if(current->next != nullptr){
        current->next->prev=newNode;
    }
    current->next = newNode;
}

void PrintLinkedList(){
    cout << "Data element in Double Linked List are: ";
    Node *current = head;
    while (current != nullptr){
        cout << current->data << " ";
        current = current->next;
    }
    cout << endl;
}

int main(){
    InsertAtPosition(1,5);
    InsertAtPosition(2,10);
    InsertAtPosition(2,15);
    PrintLinkedList();
    return 0;
}

OUTPUT:

Data element in Double Linked List are: 5 15 10

2.6) Deletion at the Beginning of Double Linked List:


CODE:

#include <iostream>
using namespace std;

struct Node{
    int data;
    Node *next;
    Node *prev;
};
Node *head = nullptr;

void InsertAtFirst(int value){
    Node *newNode = new Node;
    newNode->data = value;
    newNode->next = head;
    newNode->prev = nullptr;
    if(head != nullptr){
        head->prev = newNode;
    }
    head = newNode;
}

void DeleteAtFirst(){
    if(head == nullptr){
        cout << "Empty Linked List!" << endl;
        return;
    }
   Node *current = head;
    head = head->next;
    if(head != nullptr){
        head->prev = nullptr;
    }
    delete current;
}

void PrintLinkedList(){
    cout << "Data element in Double Linked List are: ";
    Node *current = head;
    while (current != nullptr){
        cout << current->data << " ";
        current = current->next;
    }
    cout << endl;
}

int main(){
    cout << "#for empty linked list:" << endl;
    DeleteAtFirst();
    cout << "#after inserting value in linked list:" << endl;
    InsertAtFirst(5);
    InsertAtFirst(10);
    InsertAtFirst(15);
    PrintLinkedList();
    cout << "#after deleting first value in linked list:" << endl;
    DeleteAtFirst();
    DeleteAtFirst();
    PrintLinkedList();
}

OUTPUT:

#for empty linked list:
Empty Linked List!
#after inserting value in linked list:
Data element in Double Linked List are: 15 10 5 
#after deleting first value in linked list:
Data element in Double Linked List are: 5 

2.7) Deletion at the End of Double Linked List:


CODE:

#include <iostream>
using namespace std;

struct Node{
    int data;
    Node *next;
    Node *prev;
};
Node *head = nullptr;

void InsertAtFirst(int value){
    Node *newNode = new Node;
    newNode->data = value;
    newNode->next = head;
    newNode->prev = nullptr;
    if(head != nullptr){
        head->prev = newNode;
    }
    head = newNode;
}

void DeleteAtEnd(){
    if(head == nullptr){
        cout << "Empty Linked List!" << endl;
        return;
    }
    if(head->next == nullptr){
        delete head;
        head = nullptr;
        return;
    }
    Node *current = head;
    while(current->next != nullptr){
        current = current->next;
    }
    if(current->prev != nullptr){
        current->prev->next = nullptr;
    }
    else{
        head = nullptr;
    }
    delete current;
}

void PrintLinkedList(){
    cout << "Data element in Double Linked List are: ";
    Node *current = head;
    while (current != nullptr){
        cout << current->data << " ";
        current = current->next;
    }
    cout << endl;
}

int main(){
    cout << "#for empty linked list:" << endl;
    DeleteAtEnd();
    cout << "#after inserting value in linked list:" << endl;
    InsertAtFirst(5);
    InsertAtFirst(10);
    InsertAtFirst(15);
    PrintLinkedList();
    cout << "#after deleting last value in linked list:" << endl;
    DeleteAtEnd();
    DeleteAtEnd();
    PrintLinkedList();
}

OUTPUT:

#for empty linked list:
Empty Linked List!
#after inserting value in linked list:
Data element in Double Linked List are: 15 10 5 
#after deleting last value in linked list:
Data element in Double Linked List are: 15 

2.8) Deletion at the Position of Double Linked List:


CODE:

#include <iostream>
using namespace std;

struct Node{
    int data;
    Node *next;
    Node *prev;
};
Node *head = nullptr;

void InsertAtFirst(int value){
    Node *newNode = new Node;
    newNode->data = value;
    newNode->next = head;
    newNode->prev = nullptr;
    if(head != nullptr){
        head->prev = newNode;
    }
    head = newNode;
}

void DeleteAtPosition(int pos){
    if(head == nullptr){
        cout << "Empty Linked List!" << endl;
        return;
    }
    if (pos <= 0){ 
         cout << "Position must be greater than 0!" << endl; 
          return; 
     }
    Node *current = head;
    if(pos == 1){
        head = current->next;
        if(head != nullptr){
            head->prev = nullptr;
        }
        delete current;
        return;
    }
    for(int i = 1; i < pos && current != nullptr; i++){
        current = current->next;
    }
    if(current == nullptr){
        cout << "Position does not exist!" << endl;
        return;
    }
    if(current->next != nullptr){
        current->next->prev = current->prev;
    }
    if(current->prev != nullptr){
        current->prev->next = current->next;
    }
    delete current;
}

void PrintLinkedList(){
    cout << "Data element in Double Linked List are: ";
    Node *current = head;
    while (current != nullptr){
        cout << current->data << " ";
        current = current->next;
    }
    cout << endl;
}

int main(){
    cout << "#for empty linked list:" << endl;
    DeleteAtPosition(1);
    cout << "#after inserting value in linked list:" << endl;
    InsertAtFirst(5);
    InsertAtFirst(10);
    InsertAtFirst(15);
    PrintLinkedList();
    cout << "#after deleting position 2 value in linked list:" << endl;
    DeleteAtPosition(2);
    PrintLinkedList();
     cout << "#after deleting position 3 value in linked list:" << endl;
    DeleteAtPosition(3);
    PrintLinkedList();
}

OUTPUT:

#for empty linked list:
Empty Linked List!
#after inserting value in linked list:
Data element in Double Linked List are: 15 10 5 
#after deleting position 2 value in linked list:
Data element in Double Linked List are: 15 5 
#after deleting position 3 value in linked list:
Position does not exit!
Data element in Double Linked List are: 15 5

🚨Thanks for visiting classpdfindia✨

Welcome to a hub for 😇Nerds and knowledge seekers! Here, you'll find everything you need to stay updated on education, notes, books, and daily trends.

💗 Bookmark our site to stay connected and never miss an update!

💌 Have suggestions or need more content? Drop a comment below, and let us know what topics you'd like to see next! Your support means the world to us. 😍

4.94 / 169 rates

2 Comments

Post a Comment
Previous Post Next Post