How can I change the location of a node in a previously created two-way circular linked list without changing the data in it?
(First of all, I'm sorry for my bad English, English is not my native language.)
We took the exam for the "Data Structures" course at our university. The last question was given like this.
Check out the code given below. Complete the missing function.
#include <stdio.h>
#include <stdlib.h>
struct Node
{
int data;
struct Node* next;
struct Node* pre;
};
struct Node* node_create(int data)
{
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
new_node->data = data;
new_node->next = NULL;
new_node->pre = NULL;
return new_node;
}
void node_add(struct Node** head, struct Node* new_node)
{
struct Node* list = *head;
if(*head == NULL)
{
new_node->next = new_node;
new_node->pre = new_node;
*head = new_node;
}
else
{
while(list->next != *head)
{
list = list->next;
}
list->next = new_node;
(*head)->pre = new_node;
new_node->next = *head;
new_node->pre = list;
}
}
void node_list(struct Node** head)
{
struct Node* list = *head;
if(*head == NULL)
{
printf("\nEmpty Linked List!\n");
return;
}
do{
//printf("(%p) %p - %d-> (%p)", list->pre,list,list->data,list->next);
printf("%d-> ", list->data);
list = list->next;
}while(list != *head);
}
void node_delete(struct Node** head, int data)
{
if(*head == NULL)
{
printf("\nEmpty Linked List!\n");
return;
}
struct Node* list = *head;
struct Node* end = *head;
if( list->data == data )
{
if(list->next == list)
{
free(list);
*head = NULL;
}
else
{
while(end->next != *head)
{
end = end->next;
}
*head = list->next;
end->next = *head;
(*head)->pre = end;
free(list);
}
}
else
{
while(list->data != data && list->next != *head)
{
list = list->next;
}
if(list->data != data && list->next == *head)
{
printf("No value for delete!\n");
return;
}
(list->pre)->next = list->next;
(list->next)->pre = list->pre;
free(list);
}
printf("\nDelete of complited!\n");
}
void node_sorting(struct Node** head)
{
}
int main()
{
struct Node* head = NULL;
struct Node* new_node = NULL;
int select = 0, data = 0, one = 1;
while(one == 1)
{
printf("\n\nNode Add (1)\n");
printf("Node List (2)\n");
printf("Node Delete (3)\n");
printf("Node Sorting (4)\n");
printf("\nSelect: ");
scanf("%d", &select);
if(select == 1)
{
printf("\nData: ");
scanf("%d", &data);
new_node = node_create(data);
node_add(&head, new_node);
}
else if(select == 2)
{
node_list(&head);
}
else if(select == 3)
{
printf("\nData to delete: ");
scanf("%d", &data);
node_delete(&head, data);
}
else if(select == 4)
{
node_sorting(&head);
}
}
return 0;
}
Thinking that the problem was easy and could be solved with the bubble algorithm, I wrote the following code as an answer.
void node_sorting(struct Node** head)
{
struct Node* list = *head;
struct Node* tolist = *head;
if(*head == NULL)
{
printf("\nEmpty Linked List!\n");
return;
}
if((*head)->next == *head)
{
printf("A single-element linked list cannot be sorted.");
return;
}
do{
tolist = list->next;
list = list->next;
while(tolist != *head)
{
if(list->data > tolist->data)
{
int temp = 0;
temp = tolist->data;
tolist->data = list->data;
list->data = temp;
}
tolist = tolist->next;
}
}while(list != *head);
}
However, when the results were announced, I learned that I failed the exam and got a 0 in the question above.
When I talked to the professor teaching the course, I got the following answer. "The answer you wrote is just a scam. If I used this in real life, could cause serious damage. Never change the data. Change the position of the nodes."
I didn't understand what this was. I researched this for 1 week and found the following resources.
Inserting data in a sorted Circular Linked List
Inserting a element in a singly circular linked list in sorted manner
Insert element into a sorted Circular Double Linked List
None of these are suitable for sorting an existing doubly circular linked list. Any file or text that you can share with me that suits my request will be very helpful to me. Thank you very much in advance.
The idea is that you update the pre and next members so that the nodes get placed in a different order.
Here is an implementation of merge sort that uses that principle. It consists of these steps:
pre, next pointers have to be updated.Here are the functions to add to your code to make it work like that:
struct Node* extract_head(struct Node** head) {
struct Node *node = *head;
// Detach node from the list it is in
node->pre->next = node->next;
node->next->pre = node->pre;
// Make next node the new head
*head = node == node->next ? NULL : node->next;
// Return the node we have extracted
return node;
}
struct Node* get_middle_node(struct Node* head) {
if (!head) return head;
struct Node *last = head->pre;
// Walk forward and backwards until the two pointers meet:
while (head != last) {
head = head->next; // Forward
if (head == last) break;
last = last->pre; // Backward
}
return head;
}
struct Node* merge(struct Node* left, struct Node* right) {
struct Node *newHead = NULL;
while (left || right) { // While there are nodes to merge...
// Move the node with the least value into a new circular list
node_add(&newHead, extract_head(
!right || left && left->data < right->data ? &left : &right
));
}
return newHead;
}
struct Node* split_at(struct Node *head, struct Node *at) {
struct Node *tail = at->pre;
at->pre = head->pre;
head->pre->next = at;
head->pre = tail;
tail->next = head;
// Return the pointer to the second half that was separated
return at;
}
struct Node* merge_sort(struct Node* head) {
return !head || head->next == head ? head // One node only? => is sorted
// Split in two, sort each, and merge:
: merge(merge_sort(split_at(head, get_middle_node(head))),
merge_sort(head));
}
void node_sorting(struct Node** head)
{
*head = merge_sort(*head);
}
Not your question, but the code you provided has some strange particularities. For instance, you have in node_add and node_delete some while loops that traverse the whole list only to stop at the last node in the list. But this last node is the predecessor of the head node, so you could just have looked at (*head)->pre to find it!