Last Updated on July 27, 2023 by Mayank Dham
A linked list is a type of data structure that stores a sequence of elements, each of which points to the next element in the sequence. Linked lists are made up of nodes, each of which contains data as well as a pointer to the next node in the sequence. The first node is referred to as the head node, and the last node is referred to as the tail node. Because they can be dynamically resized, linked lists are commonly used in programming to implement other data structures such as stacks, queues, and hash tables. In this section, we will be discussing how we swap two nodes in linked list
.
How to Swap Two Nodes in Linked List Without Swapping Data?
In this problem, we will be discussing how we can swap nodes directly by changing links rather than swapping out the data. We will be given a linked list and two keys say x and y, and we have to swap the nodes of the linked list having these keys as data.
Note: All the keys in the linked list are unique, i.e. no two nodes in the linked list will have the same data.
Understanding How swapping nodes in a linked list Works
Let’s try to understand what the actual problem is, so basically here, we will be given a linked list and two keys x and y. We will have to iterate the linked list and search for the nodes with keys x and y. Once we got the nodes with the keys x and y, we will have to swap these nodes. We can swap nodes of linked list either by swapping their data or by changing the links (swapping nodes). Here we will be swapping the nodes by changing the links of the nodes.
Input:
Keys are 2 and 4 (x=2 and y=4).
Output (After swapping the nodes):
Which method of swapping is more efficient, swapping by data or swapping by nodes?
In LinkedList, if we have to swap the data of two nodes, it’s easy if there are fewer fields, and it would also take less time but if the data inside the nodes is large then swapping that amount of data can limit the speed of the process. For this reason, swapping nodes is preferred.
Now let’s move to the approach section, there we will see how we will solve the above problem of searching the nodes and swapping.
Approach to swap two nodes in linked list without swapping data
Swapping nodes seem easy if the nodes to be swapped are adjacent, but then it becomes difficult for the following cases:
- The first case is when x and y are not adjacent.
- Or may be either of x and y is head nodes.
- Or maybe either x or y is the last node.
- And there can be a case where x and/or y may not even be present in the linked list.
The idea is to search for the two nodes with keys x and y, if any of them is not present then return null otherwise change the next pointers of the two nodes.
Algorithm to swap the nodes in a linked list without swapping data
- Search for x and y nodes in the LinkedList.
- If any of them is NULL, return.
- Take 4 pointers as previousX, currentX, previousY, currentY to denote the previous and current nodes of x and y respectively.
- If x is not head of the linked list, then change previousX->next = currentY and if x is head of the linked list then make node y as the new head of the linked list.
- If y is not head of the linked list, then change previousY->next = currentX and if y is the head of the linked list then make node x as the new head of the linked list.
- Finally, swap the next pointers of the current nodes as currentX->next to currentY->next.
Dry Run
Let me dry run this for a small test case, then it will be much clearer to understand. In the following example, we have a linked list, and we need to swap the two nodes having keys as 2 and 4.
Code Implementation
#include <stdio.h>
#include <stdlib.h>
/* A linked list node */
struct Node {
int data;
struct Node* next;
};
void swapNodes(struct Node** head_ref, int x, int y)
{
if (x == y)
return;
struct Node *prevX = NULL, *currX = *head_ref;
while (currX && currX->data != x) {
prevX = currX;
currX = currX->next;
}
struct Node *prevY = NULL, *currY = *head_ref;
while (currY && currY->data != y) {
prevY = currY;
currY = currY->next;
}
if (currX == NULL || currY == NULL)
return;
if (prevX != NULL)
prevX->next = currY;
else // Else make y as new head
*head_ref = currY;
// If y is not head of linked list
if (prevY != NULL)
prevY->next = currX;
else // Else make x as new head
*head_ref = currX;
// Swap next pointers
struct Node* temp = currY->next;
currY->next = currX->next;
currX->next = temp;
}
/* Function to add a node at the beginning of List */
void push(struct Node** head_ref, int new_data)
{
/* allocate node */
struct Node* new_node
= (struct Node*)malloc(sizeof(struct Node));
/* put in the data */
new_node->data = new_data;
/* link the old list off the new node */
new_node->next = (*head_ref);
/* move the head to point to the new node */
(*head_ref) = new_node;
}
/* Function to print nodes in a given linked list */
void printList(struct Node* node)
{
while (node != NULL) {
printf("%d ", node->data);
node = node->next;
}
}
/* Driver program to test above function */
int main()
{
struct Node* start = NULL;
/* The constructed linked list is:
1->2->3->4->5->6->7 */
push(&start, 7);
push(&start, 6);
push(&start, 5);
push(&start, 4);
push(&start, 3);
push(&start, 2);
push(&start, 1);
printf("\n Linked list before calling swapNodes() ");
printList(start);
swapNodes(&start, 4, 3);
printf("\n Linked list after calling swapNodes() ");
printList(start);
return 0;
}
#include <bits stdc++.h="">
using namespace std;
class Node {
public:
int data;
Node* next;
};
void swapNodes(Node** head_ref, int x, int y)
{
if (x == y)
return;
Node *previousX = NULL, *currentX = *head_ref;
while (currentX && currentX->data != x) {
previousX = currentX;
currentX = currentX->next;
}
Node *previousY = NULL, *currentY = *head_ref;
while (currentY && currentY->data != y) {
previousY = currentY;
currentY = currentY->next;
}
if (currentX == NULL || currentY == NULL)
return;
if (previousX != NULL)
previousX->next = currentY;
else
*head_ref = currentY;
if (previousY != NULL)
previousY->next = currentX;
else
*head_ref = currentX;
Node* temp = currentY->next;
currentY->next = currentX->next;
currentX->next = temp;
}
void push(Node** head_ref, int new_data)
{
Node* new_node = new Node();
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
void printList(Node* node)
{
while (node != NULL) {
cout << node->data << " ";
node = node->next;
}
}
int main()
{
Node* start = NULL;
push(&start, 5);
push(&start, 4);
push(&start, 3);
push(&start, 2);
push(&start, 1);
swapNodes(&start, 2, 4);
printList(start);
return 0;
}
class Node {
int data;
Node next;
Node(int d)
{
data = d;
next = null;
}
}
class LinkedList {
Node head;
public void swapNodes(int x, int y)
{
if (x == y)
return;
Node prevX = null, currX = head;
while (currX != null && currX.data != x) {
prevX = currX;
currX = currX.next;
}
Node prevY = null, currY = head;
while (currY != null && currY.data != y) {
prevY = currY;
currY = currY.next;
}
if (currX == null || currY == null)
return;
if (prevX != null)
prevX.next = currY;
else
head = currY;
if (prevY != null)
prevY.next = currX;
else
head = currX;
Node temp = currX.next;
currX.next = currY.next;
currY.next = temp;
}
public void push(int new_data)
{
Node new_Node = new Node(new_data);
new_Node.next = head;
head = new_Node;
}
public void printList()
{
Node tNode = head;
while (tNode != null) {
System.out.print(tNode.data + " ");
tNode = tNode.next;
}
}
public static void main(String[] args)
{
LinkedList llist = new LinkedList();
llist.push(5);
llist.push(4);
llist.push(3);
llist.push(2);
llist.push(1);
llist.swapNodes(2, 4);
llist.printList();
}
}
class LinkedList(object):
def __init__(self):
self.head = None
class Node(object):
def __init__(self, d):
self.data = d
self.next = None
def swapNodes(self, x, y):
if x == y:
return
prevX = None
currX = self.head
while currX != None and currX.data != x:
prevX = currX
currX = currX.next
prevY = None
currY = self.head
while currY != None and currY.data != y:
prevY = currY
currY = currY.next
if currX == None or currY == None:
return
if prevX != None:
prevX.next = currY
else:
self.head = currY
if prevY != None:
prevY.next = currX
else:
self.head = currX
temp = currX.next
currX.next = currY.next
currY.next = temp
def push(self, new_data):
new_Node = self.Node(new_data)
new_Node.next = self.head
self.head = new_Node
def printList(self):
tNode = self.head
while tNode != None:
print(tNode.data , end =" ")
tNode = tNode.next
llist = LinkedList()
llist.push(5)
llist.push(4)
llist.push(3)
llist.push(2)
llist.push(1)
print("Linked list before calling swapNodes() ")
llist.printList()
llist.swapNodes(2, 4)
print("\nLinked list after calling swapNodes() ")
llist.printList()
Output
1 4 3 2 5
Time Complexity: O(n), where n is the number of nodes present in the LinkedList.
Space Complexity: O(1), no extra space is used.
Conclusion
Swapping nodes in a linked list is a fundamental operation that involves exchanging the positions of two nodes within the structure. This process is essential for reorganizing data, sorting the list, or implementing various algorithms without modifying the actual data stored in the nodes. Swapping nodes can be efficiently achieved by changing the links between the nodes rather than swapping their data. By employing this approach, we can efficiently swap nodes in a linked list without the need for extra memory space. This technique is particularly useful when dealing with large data elements or when there is a need for bidirectional traversal within the linked list.
PrepBytes.
## Frequently Asked Questions (FAQs)
Here are some of the frequently asked questions related to swapping nodes in a linked list
**Q1. What is swapping in data structures?**
Swapping in data structures refers to the process of exchanging the values or positions of two elements within the structure. It is a fundamental operation used to rearrange elements, modify the order, or update the content of nodes in various data structures such as arrays, linked lists, trees, and more. Swapping is commonly employed to reorganize data to achieve a desired arrangement or to facilitate specific algorithms.
**Q2. Explain swapping 2 nodes in linked list**
In the context of data structures like linked lists, swapping two nodes means interchanging the positions of these nodes. The process involves adjusting the pointers of the adjacent nodes to maintain the integrity of the data structure. Swapping nodes in a linked list can be useful when reordering elements, sorting the list, or implementing algorithms that require rearrangement of elements without changing their values.
**Q3. What is the syntax of the swap() function?**
The “swap()” function is not a standard function available in all programming languages or libraries. Its implementation varies depending on the context and the specific data structure you are working with.