CODEWITHSUNDEEP
cprintftreenode
MsSingularity
MsSingularity

Reputation: 45

C: how to print a list in reverse order?

I am trying to print a list of tree_nodes in reverse order:

Current prompt example: /helloFellow/hello/root / >

Desired result: root/hello/helloFellow / >

What is a way to do this efficiently?

// *prints the prompt (e.g. /bar/baz/ >) in every iteration of the main loop
// *show all directories on the path in correct order
void show_prompt(struct tree_node *cwd) {
    struct tree_node *parDir = cwd->parent;
    struct tree_node *originalDir = cwd;

    while (cwd->parent != NULL) {
        printf("/");
        printf("%s", cwd->parent->string_buffer);
        cwd = cwd->parent;
    }
    cwd = originalDir;
    printf("/ >");
}

Upvotes: 1

Views: 1493

Answers (2)

Andrés AG
Andrés AG

Reputation: 419

As Kenney pointed out, you could use recursion. Another solution is just to modify your linked list to contain pointers in both directions i.e. to the previous and next elements in the list. Then you also keep pointers to the head and tail of the list. You could encapsulate this using two structures like:

struct ListNode {
    struct ListNode *prev;
    struct ListNode *tail;
};

struct LinkedList {
    struct ListNode *head;
    struct ListNode *tail;
};

The pros of doing this is that this (and other operations like insert at the tail) can be done very easily. On the down side, you also need more memory for each node and to keep track of more pointers.

Btw, since you asked for efficiently generally speaking recursion is more expensive than a normal loop implementations because every recursive call entails stuff like creating a new frame in the stack for the function and so on. This is not to say that you shouldnt use it. Recursive solutions are very elegant and sometimes much better i.e. efficient/easier than other alternatives. Furthermore, in many cases they are very well optimised by the compiler!

Upvotes: 0

Kenney
Kenney

Reputation: 9093

You could use recursion:

void print_path( struct tree_node * cwd ) {
    if ( cwd->parent != NULL )
        print_path( cwd->parent );
    printf( "%s/", cwd->string_buffer );
}

Upvotes: 4

Related Questions