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

byOne • • 14 min read
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. 😍

4.7 / 488 rates

Post a Comment

Previous Post Next Post

Ad blocker detected!

We have detected that you are using adblocking plugin in your browser.
The revenue we earn by the advertisements is used to manage this website, we request you to whitelist our website in your adblocking plugin.