Thread: Doubly Linked List Multiple Nodes

  1. #1
    Registered User
    Join Date
    Oct 2019
    Posts
    20

    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.
    Last edited by bob432; 02-19-2022 at 06:04 PM.

  2. #2
    Registered User
    Join Date
    May 2009
    Posts
    4,139
    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.
    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.." Bill Bryson

  3. #3
    Registered User
    Join Date
    Feb 2019
    Posts
    967
    Good luck. You do realize on Linux the 'default' charset seems to be UTF-8, don't you?

    Code:
    $ touch αρχείο
    $ touch файл
    $ touch ファイル
    $ touch ملف
    $ ls -go
    total 0
    -rw-rw-r-- 1 0 fev 19 21:17 αρχείο
    -rw-rw-r-- 1 0 fev 19 21:18 файл
    -rw-rw-r-- 1 0 fev 19 21:17 ملف
    -rw-rw-r-- 1 0 fev 19 21:18 ファイル

  4. #4
    Registered User
    Join Date
    May 2009
    Posts
    4,139
    Quote Originally Posted by stahta01 View Post
    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.
    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.." Bill Bryson

  5. #5
    Registered User
    Join Date
    May 2009
    Posts
    4,139
    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.
    Last edited by stahta01; 02-19-2022 at 07:44 PM.
    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.." Bill Bryson

  6. #6
    Registered User
    Join Date
    Dec 2017
    Posts
    1,391
    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.
    A long time ago being crazy meant something. - Charles Manson

  7. #7
    Registered User
    Join Date
    Apr 2021
    Posts
    92
    @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)
    Last edited by aghast; 02-25-2022 at 04:05 PM. Reason: indentation

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 3
    Last Post: 10-19-2015, 07:23 AM
  2. Replies: 2
    Last Post: 10-31-2012, 02:31 AM
  3. singly linked list to doubly linked list
    By t48j in forum C Programming
    Replies: 3
    Last Post: 03-23-2005, 06:37 PM
  4. swap nodes in doubly linked list
    By noob2c in forum C++ Programming
    Replies: 1
    Last Post: 09-15-2003, 10:21 PM
  5. Replies: 10
    Last Post: 10-18-2002, 06:35 AM

Tags for this Thread