Thread: Doubly Linked List Multiple Nodes

I have an assignment in a programming class where we are traversing directory paths. I have two structs, one for Nodes and another for the List itself as such:

Code:

struct Node
{
  int level;
  int order;
  char *path;
  struct Node *next;
  struct Node *prev;
};


struct List
{
  struct Node *head;
  struct Node *tail;
};

In this assignment we have to insert sort elements into a doubly linked list by their PATH alphabetically (which I can do). Next we have to sort the list by the LEVEL numerically in ascending order, lowest level to highest level. However, in between the LEVEL and the PATH is an ORDER integer. This number is not sorted, it just exists and is incremented based on specific rules that don't really matter for this explanation. My issue is that I cannot seem to be able to sort the LEVEL while still keeping the PATH that corresponds to that level with it.
My linked list prints out like this LEVEL:ORDER:PATH

For example it would look something like this when sorted by the path:

1:0:/home/Downloads/folder1
2:0:/home/Downloads/folder1/README.txt
2:0:/home/Downloads/folder1/c3
3:0:/home/Downloads/folder1/c3/Simulator
4:0:/home/Downloads/folder1/c3/Simulator/d.c
3:0:/home/Downloads/folder1/c3/win32.c
2:0:/home/Downloads/folder1/c4
3:0:/home/Downloads/folder1/c4/Driver
3:0:/home/Downloads/folder1/c4/thrd-p.c
3:0:/home/Downloads/folder1/c4/thrd-w.c

Then sorting it by the LEVEL would look like this, where the ORDER is mixed but the LEVEL is ascending and the LEVEL stayed with its corresponding PATH:

1:1:/home/Downloads/folder1
2:1:/home/Downloads/folder1/README.txt
2:2:/home/Downloads/folder1/c3
2:3:/home/Downloads/folder1/c4
3:1:/home/Downloads/folder1/c3/Simulator
3:2:/home/Downloads/folder1/c3/win32.c
3:3:/home/Downloads/folder1/c4/Driver
3:4:/home/Downloads/folder1/c4/thrd-p.c
3:5:/home/Downloads/folder1/c4/thrd-w.c
4:1:/home/Downloads/folder1/c3/Simulator/d.c

Note: I would post my code but we are not allowed to do so to get help, I have posted as much as I am allowed to without being considered cheating. Any help is appreciated.

Are you creating an new link list with the new sorted order?
Or, are you sorting an existing link list?
Does the assignment require one of the two ways to be used or is it open to you being able to select the way to do it?

Tim S.

Originally Posted by stahta01

Are you creating an new link list with the new sorted order?
Or, are you sorting an existing link list?
Does the assignment require one of the two ways to be used or is it open to you being able to select the way to do it?

Tim S.

Order do you have just a single link list sorted by two things at once?

As in a sorted double link list with two things it is sorted by.

Tim S.

FYI: If the string/char array is not allocated correctly using malloc or another method you might get the problem you describe.

And, after doing a char array malloc you need to do strcpy instead of an assignment "=" to copy the string.

Tim S.

My issue is that I cannot seem to be able to sort the LEVEL while still keeping the PATH that corresponds to that level with it.

Could you clarify?

Are you saying that you wrote a sort routine for the list that moves the levels around but doesn't move the paths around? If you are reordering a list by exchanging data and not links then you need to exchange all of the data (but not the links!) to keep it together.

If you are talking about the paths losing their sort order when the levels are sorted then that would mean you need a "stable" sort. Mergesort is generally stable.

@op,

From your question, it sounds like you are creating new nodes when you sort into a new order. You could solve your problem by starting with one list, removing the nodes from the list in order, and inserting the same node into the new list:

while (old_list.head != NULL)

node = remove_first_node(old_list)
insertion_sort_node(new_list, node)