Algo: Linked Lists

Question 1

Algorithm for insertAtBeginning implementation

Answer 1

1. Create a new Node
2. Point the new Node’s next pointer to the current head.
3. Update the head of the linked list as the new node.// Function to Insert a new node at the beginning of the list
   void insertAtBeginning(int value) {
   Node* newNode = new Node();
   newNode->data = value;
   newNode->next = head;
   head = newNode;
   }

Question 2

Algorithm for insertAtEnd implementation

Answer 2

1. Create a new Node
2. If the linked list is empty, update the head as the new node.
3. Otherwise traverse till the last node of the linked list.
4. Update the next pointer of the last node from NULL to new node.// Function Insert a new node at the end of the list
   void insertAtEnd(int value) {
   Node* newNode = new Node();
   newNode->data = value;
   newNode->next = NULL;

    // If the list is empty, update the head to the new node
    if (!head) {
        head = newNode;
        return;
    }
   
    // Traverse to the last node
    Node* temp = head;
    while (temp->next) {
        temp = temp->next;
    }
   
    // Update the last node's next to the new node
    temp->next = newNode;  }

Question 3

Algorithm for insertAtPosition implementation

Answer 3

1. Check if the provided position by the user is a valid poistion.
2. Create a new node.
3. Find the node at position -1.
4. Update the next pointer of the new node to the next pointer of the current node.
5. Update the next pointer of the current node to new node.// Function to Insert a new node at a specific position in the list
   void insertAtPosition(int value, int position) {
   if (position < 1) {
   cout &laquo_space;“Position should be >= 1.” &laquo_space;endl;
   return;
   }

    if (position == 1) {
        insertAtBeginning(value);
        return;
    }
   
    Node* newNode = new Node(); 
    newNode->data = value;     
   
    // Traverse to the node before the desired position
    Node* temp = head;
    for (int i = 1; i < position - 1 && temp; ++i) {
        temp = temp->next;
    }
   
    // If the position is out of range, print an error message
    if (!temp) {
        cout << "Position out of range." << endl;
        delete newNode;
        return;
    }
   
    // Insert the new node at the desired position
    newNode->next = temp->next;
    temp->next = newNode;  }

Question 4

Algorithm for deleteFromBeginning

Answer 4

1. Check whether the Head of the linked list is not NULL. If Head is equal to NULL return as the linked list is empty, there is no node present for deletion.
2. Store the head of the linked list in a temp pointer.
3. Update the head of the linked list to next node.
4. Delete the temporary node stored in the temp pointer.// Function to Delete the first node of the list
   void deleteFromBeginning() {
   if (!head) {
   cout &laquo_space;“List is empty.” &laquo_space;endl;
   return;
   }

    Node* temp = head; 
    head = head->next; 
    delete temp;        }

Question 5

Algorithm for deleteFromEnd implementation

Answer 5

1. Verify whether the linked is empty or not before deletion.
2. If the linked list has only one node, delete head and set head to NULL.
3. Traverse till the second last node of the linked list.
4. Store the last node of the linked list in a temp pointer.
5. Pointer the next pointer of the second last node to NULL.
6. Delete the node represented by the temp pointer.// Function to Delete the last node of the list
   void deleteFromEnd() {
   if (!head) {
   cout &laquo_space;“List is empty.” &laquo_space;endl;
   return;
   }

    if (!head->next) {
        delete head;   
        head = NULL;   
        return;
    }
   
    // Traverse to the second-to-last node
    Node* temp = head;
    while (temp->next->next) {
        temp = temp->next;
    }
       
    //  Delete the last node
    delete temp->next; 
    // Set the second-to-last node's next to NULL
    temp->next = NULL;   }

Question 6

Algorithm for deleteFromPosition implementation

Answer 6

1. Check if the provided postion by the users is a valid position in the linked list or not.
2. Find the node at position -1.
3. Save node to be deleted in a temp pointer.
4. Set the next pointer of the current node to the next pointer of the node to be deleted.
5. Set the next pointer of temp to NULL.
6. Delete the node represented by temp pointer.// Function to Delete a node at a specific position in the list
   void deleteFromPosition(int position) {
   if (position < 1) {
   cout &laquo_space;“Position should be >= 1.” &laquo_space;endl;
   return;
   }

    if (position == 1) {
        deleteFromBeginning();
        return;
    }
   
    Node* temp = head;
    for (int i = 1; i < position - 1 && temp; ++i) {
        temp = temp->next;
    }
   
    if (!temp || !temp->next) {
        cout << "Position out of range." << endl;
        return;
    }
    // Save the node to be deleted
    Node* nodeToDelete = temp->next; 
    // Update the next pointer
    temp->next = temp->next->next;   
     // Delete the node
    delete nodeToDelete;              }

Question 7

Algorithm for display implementation

Answer 7

1. Check if the Head pointer of the linked list is not equal to NULL.
2. Set a temp pointer to the Head of the linked list.
3. Until temp becomes null:
4. Print temp->data
5. Move temp to the next node.// Function to print the nodes of the linked list
   void display() {
   if (!head) {
   cout &laquo_space;“List is empty.” &laquo_space;endl;
   return;
   }

    Node* temp = head;
    while (temp) {
        cout << temp->data << " -> "; 
        temp = temp->next;
    }
    cout << "NULL" << endl;   }

Question 8

Struct and class definition for linked list (include constructor)

Answer 8

// Structure for a node in the linked list
struct Node {
int data;
Node* next;
};

// Define the linked list class
class LinkedList {
// Pointer to the first node in the list
Node* head;

public:
// Constructor initializes head to NULL
LinkedList() : head(NULL) {}
…
};