Linked Lists - CSE205: Data Structures and Algorithms | B.Tech CSE Notes PDF | FineNotes4U

One 0

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;
};

1.2) Traversal in Singly Linked List:


CODE:

void traverseList(Node* head){
    Node *temp = head; // Start from head

    // Loop until end of list
    while (temp != nullptr){
        cout << temp->data << " -> ";
        temp = temp->next;
    }
    cout << "NULL" << endl;
}

EXAMPLE CODE:

#include <iostream>
using namespace std;

// Node structure
struct Node {
    int data;    // Stores data
    Node* next;  // Pointer to the next node
};

// Function to traverse and print the linked list
void traverseList(Node* head) {
    Node* temp = head;  // Start from head

    while (temp != NULL) {
        cout << temp->data << " -> ";
        temp = temp->next;
    }
    cout << "NULL" << endl; // Indicate end of the list
}

// Function to create a new node
Node* createNode(int value) {
    Node* newNode = new Node(); // Allocate memory for a new node
    newNode->data = value;      // Assign value
    newNode->next = NULL;       // Set next pointer to NULL
    return newNode;
}

int main() {
    // Creating nodes manually
    Node* head = createNode(10);
    head->next = createNode(20);
    head->next->next = createNode(30);
    head->next->next->next = createNode(40);

    cout << "Linked List: ";
    traverseList(head);

    return 0;
}

OUTPUT:

Linked List: 10 -> 20 -> 30 -> 40 -> NULL

1.3) Insertion at the Beginning of Singly Linked List:


CODE:

#include <iostream>
using namespace std;

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

// Function to insert a node at the beginning
void insertAtBeginning(Node*& head, int value) {
    Node* newNode = new Node(); // Step 1: Create a new node
    newNode->data = value;      // Step 2: Assign data
    newNode->next = head;       // Step 3: Link new node to old head
    head = newNode;             // Step 4: Update head
}

// Function to traverse and print the linked list
void traverseList(Node* head) {
    Node* temp = head;
    while (temp != NULL) {
        cout << temp->data << " -> ";
        temp = temp->next;
    }
    cout << "NULL" << endl;
}

int main() {
    Node* head = NULL; // Initially, the list is empty

    // Inserting elements at the beginning
    insertAtBeginning(head, 40);
    insertAtBeginning(head, 30);
    insertAtBeginning(head, 20);
    
    //Taking Extra Multiple Inputs by User
    int n, value;
    cin >> n;  // number of extra elements
    for (int i = 0; i < n; i++) {
        cin >> value;
        insertAtBeginning(head, value);
    }

    cout << "Linked List after insertions: ";
    traverseList(head); // Print the list

    return 0;
}

INPUT:

3
5 10 15

OUTPUT:

Linked List after insertions: 15 -> 10 -> 5 -> 20 -> 30 -> 40 -> NULL

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 finenotes4u✨

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. 😍

Tags

Post a Comment

Post a Comment

Previous Post Next Post