Question

Swap two adjacent elements by adjusting only the links (and not the data) using
a. singly linked lists
b. doubly linked lists

Answer 1

(a) Sample data structure for the list in C++ language is as follows

struct node

{

int data;

struct node* next;

}l-list, temp_0, temp, temp, temp_1;

Suppose next is the pointer used to form the linked list and points to the next element and l-list is the pointer to the first element of the list. Also temp_0, temp and temp_1 are the temporary element pointers used for traversing the list.

Now let us suppose the temp points to element of the linked list, temp_0 points to the previous elementand temp_1 is the next element of the linked list.

For swapping two elements, (in C++ pointer style)

temp_0->next = temp_1

temp = temp_1->next

temp_1->next = temp

(b) Sample data structure for the list is as follows

struct node

{

int data;

struct node* next_0;

struct node* next;

}l-list, temp_0, temp, temp, temp_1;

Suppose next_0 and next is the pointer used to form the linked list where next_0 is the pointer to the previous element of the current element and next is the pointer to the next element of the list. l-list is the pointer to the first element of the list. Also temp_0, temp and temp_1 are the temporary element pointers used for traversing the list.

Now let us suppose the temp points to element of the linked list, temp_0 points to the previous elementand temp_1 is the next element of the linked list.

For swapping two elements, (in C++ pointer style)

temp_0->next = temp_1

temp = temp_1->next

temp_1->next = temp

Note: Only usefulness of the doubly linked list is in the calculation of temp_0 where it can be calculated as temp_0 = temp->next_0. Whereas in the case of singly linked list to calculate temp_0 we have to iterate from the starting of the list to the previous element of the current element.