I am currently trying to sort a singly linked list in descending order. Realizing there is no straightforward way to do that with only a next pointer, I opted for the approach of sorting the list in ascending order first, then reversing the list, so that the items are sorted in descending order.
Edit 1: I'm trying to ensure that the items are stored in descending order based on how frequently they are accessed in the linked list. The printing is just to help me check the order of the linked list.
Edit 2: Minimum Working Example as Requested:
main.c
#include <stddef.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
typedef struct node_struct {
char *name;
int accessCount;
struct node_struct *next;
}Knowledge_Node;
int knowledge_put();
int knowledge_get();
void printList();
void sortList();
void reverseList();
Knowledge_Node *head = NULL;
int main(int argc, char*argv[]){
// Putting James into the linked list
knowledge_put("James");
//Get the James node twice
knowledge_get("James");
knowledge_get("James");
//Add Carrie to the linked list
knowledge_put("Carrie");
//Get the Carrie node thrice
knowledge_get("Carrie");
knowledge_get("Carrie");
knowledge_get("Carrie");
// Add adams to linked list
knowledge_put("Adams");
knowledge_get("Adams");
printList();
}
Add Node Function
int knowledge_put(char * name) {
Knowledge_Node *node = (Knowledge_Node *)malloc(sizeof(Knowledge_Node));
if (node == NULL) {
return -3;
}
node->name = (char *)malloc(sizeof(char) * 255);
if (node->name == NULL){
return -3;
}
strncpy(node->name, name, strlen(name) + 1);
node->accessCount = 0;
node->next = head;
head = node;
sortList();
}
Retrieve Node Function
int knowledge_get(char * name){
Knowledge_Node *search = head;
while (search != NULL){
if (strcmp(search->name, name) == 0){
search->accessCount = search->accessCount + 1;
sortList();
return 0;
}
search = search->next;
}
return -1;
}
Sort List Function:
void sortList(){
Knowledge_Node *temp = head;
Knowledge_Node *backPtr = head;
Knowledge_Node *prevNode = NULL;
while (temp != NULL){
Knowledge_Node *nextNode = temp->next;
//currentNode is assigned to temp, which is the pointer used to iterate through the list
Knowledge_Node *currentNode = temp;
//Doing a simple check to see if nextNode has something
if (nextNode != NULL) {
if(nextNode != NULL){
if (currentNode->accessCount > nextNode->accessCount) {
//If previousNode is NULL it means currentNode is the head of //the linked list
//There's different logic to handle each case
if (prevNode != NULL){
prevNode->next = nextNode;
nextNode->next = currentNode;
currentNode->next = NULL;
} else if (prevNode == NULL){
currentNode->next = nextNode->next;
nextNode->next = currentNode;
head = nextNode;
}
}
}
}
//Assigning of previousNode. We'll need this for the linking/un-linking //process
prevNode = currentNode;
temp = temp->next;
}
reverseList();
}
Reverse List Function:
void reverseList(){
//Initialise three pointers, which we'll use to reverse the links of the
//linked list
Knowledge_Node *prevNode = NULL;
Knowledge_Node *currentNode = head;
Knowledge_Node *nextNode = NULL;
//This is where the linked list reversal is done
while (currentNode != NULL){
nextNode = currentNode->next;
currentNode->next = prevNode;
prevNode = currentNode;
currentNode = nextNode;
}
//Previous Node points to the last node in the original list, so let's
//make it the new head
head = prevNode;
}
Print List Function:
void printList() {
Knowledge_Node *temp = head;
while (temp != NULL){
printf("%s %d\n", temp->name, temp->accessCount);
temp = temp->next;
}
}
Expected Output:
Carrie 3
James 2
Adams 1
Actual Output:
Adams 1
Carrie 3
James 2
The ascending sort seems to work fine on its own, without the reverse sort.
Hopefully someone can guide me based on this as to how I can change the sortList algorithm to make it sort in ascending, then descending order properly
Removed rest of content to keep things brief