C++ Data Structures - Doubly Linked List Other Related Topics

C++ - Swap node values of a Doubly Linked List



There are many instances where it is required to swap value of two nodes while working with a list. This can be achieved by traversing to the interested nodes and swap their values if the nodes are valid. For example - if the given list is 10->20->30->40->50. After swapping values of first and fourth nodes, the list will become 40->20->30->10->50.

The function swapNodeValues is created for this purpose which is a 4-step process.

void swapNodeValues(int node1, int node2) {
  
  //1. count the number of nodes in the list
  Node* temp = head;
  int N = 0;
  while(temp != NULL) {
    N++;
    temp = temp->next;
  }

  //2. check if the swap positions are valid entries
  if(node1 < 1 || node1 > N || node2 < 1 || node2 > N)
    return;

  //3. traverse to the nodes where values to be swapped
  Node* pos1 = head;
  Node* pos2 = head;
  for(int i = 1; i < node1; i++) {
    pos1 = pos1->next;
  }
  for(int i = 1; i < node2; i++) {
    pos2 = pos2->next;
  }

  //4. swap the values of two nodes
  int val = pos1->data;
  pos1->data = pos2->data;
  pos2->data = val;
} 

The below is a complete program that uses above discussed concept to swap values of two given nodes of a doubly linked list.

#include <iostream>
using namespace std;

//node structure
struct Node {
    int data;
    Node* next;
    Node* prev;
};

class LinkedList {
  private:
    Node* head;
  public:
    LinkedList(){
      head = NULL;
    }
 
    //Add new element at the end of the list
    void push_back(int newElement) {
      Node* newNode = new Node();
      newNode->data = newElement;
      newNode->next = NULL;
      newNode->prev = NULL; 
      if(head == NULL) {
        head = newNode;
      } else {
        Node* temp = head;
        while(temp->next != NULL)
          temp = temp->next;
        temp->next = newNode;
        newNode->prev = temp;
      }    
    }

    //swap node values
    void swapNodeValues(int node1, int node2) {
      
      Node* temp = head;
      int N = 0;
      while(temp != NULL) {
        N++;
        temp = temp->next;
      }

      if(node1 < 1 || node1 > N || node2 < 1 || node2 > N)
        return;

      Node* pos1 = head;
      Node* pos2 = head;
      for(int i = 1; i < node1; i++) {
        pos1 = pos1->next;
      }
      for(int i = 1; i < node2; i++) {
        pos2 = pos2->next;
      }

      int val = pos1->data;
      pos1->data = pos2->data;
      pos2->data = val;
    } 

    //display the content of the list
    void PrintList() {
      Node* temp = head;
      if(temp != NULL) {
        cout<<"The list contains: ";
        while(temp != NULL) {
          cout<<temp->data<<" ";
          temp = temp->next;
        }
        cout<<"\n";
      } else {
        cout<<"The list is empty.\n";
      }
    }   
};

// test the code 
int main() {
  LinkedList MyList;

  //Add five elements in the list.
  MyList.push_back(10);
  MyList.push_back(20);
  MyList.push_back(30);
  MyList.push_back(40);
  MyList.push_back(50);

  //Display the content of the list.
  MyList.PrintList();

  //swap values of node=1 and node=4
  MyList.swapNodeValues(1, 4);

  //Display the content of the list.
  MyList.PrintList();
  
  return 0; 
}

The above code will give the following output:

The list contains: 10 20 30 40 50 
The list contains: 40 20 30 10 50