C++ program to swap links of a Linked List

Question

In this code I tried to swap links in a linked list instead of swapping data.Please Review my code.

#include <iostream>
 template<class T>
 class LinkedList
 {
struct Node{
 T data;
 Node * next;
 Node(T val): data(val), next(nullptr){}
};
Node* head;
public:
 LinkedList() : head(nullptr) {}
 void insert(T val)
 {
 Node* node = new Node(val);
 Node* tmp = head;
 if(tmp == nullptr)
 {
 head = node;
 }
 else
 {
 while(tmp->next != nullptr)
 {
 tmp = tmp->next;
 }
 tmp->next = node;
 }
 }
 void swapLinks(T val1, T val2)
 {
 Node* prevNode1 = nullptr;
 Node* prevNode2 = nullptr;
 Node* nextNode1 = nullptr;
 Node* nextNode2 = nullptr;
 Node* node = head;
 Node* node1 = search(val1);
 Node* node2 = search(val2);
 while(node->next != node1)
 {
 node = node->next;
 }
 if(node->next == node1)
 {
 prevNode1 = node;
 nextNode1 = node1->next;
 }
 node = head;
 while(node-> next != node2)
 {
 node = node->next;
 }
 if(node->next == node2)
 {
 prevNode2 = node;
 nextNode2 = node2->next;
 }
 prevNode1->next = node2;
 Node* tmp = node2->next;
 node2->next = node1->next;
 prevNode2->next = node1;
 node1->next = tmp;
 }
 friend std::ostream & operator <<(std::ostream & os, LinkedList<T>& ll)
 {
 ll.display(os);
 return os;
 }
private:
 struct Node *search(T val)
 {
 Node* node = head;
 while(node != nullptr)
 {
 if(node->data == val)
 {
 return node;
 }
 node = node->next;
 }
 std::cerr << "No such element in the List \n";
 return nullptr;
 }
 void display(std::ostream& out = std::cout) const
 {
 Node* node = head;
 while(node != nullptr)
 {
 out << node->data <<" ";
 node = node->next;
 }
 }
};
int main()
{
 LinkedList<int> ll1;
 ll1.insert(10);
 ll1.insert(15);
 ll1.insert(12);
 ll1.insert(13);
 ll1.insert(28);
 ll1.insert(14);
 ll1.insert(16);
 std::cout << "LinkedList1 : "<< ll1 <<"\n";
 ll1.swapLinks(12, 14);
 std::cout << ll1 <<"\n";
}

Is there any another solution or better solution? Please suggest.

• Loki Astari: Much easier to this if you have a doubly linked list.

Answer 1

This works as long as 2 conditions are met.

1. val1 and val2 are in the list.
2. Neither are in the head node.

Otherwise you access stuff via null pointers:

 void swapLinks(T val1, T val2)
 {
 Node* prevNode1 = nullptr;
 Node* prevNode2 = nullptr;
 Node* nextNode1 = nullptr;
 Node* nextNode2 = nullptr;
 Node* node = head;
 Node* node1 = search(val1);
 Node* node2 = search(val2);
 // This will not find values in the "head node"
 // If the value is in head the you will not find a previous node.
 // You need to take into account this special case at the bottom.
 while(node->next != node1)
 {
 node = node->next;
 }
 if(node->next == node1)
 {
 prevNode1 = node;
 nextNode1 = node1->next;
 }
 node = head;
 // This will not find values in the "head node"
 // If the value is in head the you will not find a previous node.
 // You need to take into account this special case at the bottom.
 while(node-> next != node2)
 {
 node = node->next;
 }
 if(node->next == node2)
 {
 prevNode2 = node;
 nextNode2 = node2->next;
 }
 // HERE YOU HAVE some issues.
 // prevNode1 or prevNode2 or node1 or node2 may be nullptr
 // If any of these values are null the code below will be UB.
 prevNode1->next = node2;
 Node* tmp = node2->next;
 node2->next = node1->next;
 prevNode2->next = node1;
 node1->next = tmp;
 }