7
\$\begingroup\$

Looking for feedback on this code to reverse a double linked list. Things I am potentially looking for but missed -> redundant operations, extra / unnecessary arithmetic, improvement in code style. Thank yoU!


typedef struct Node {
    int data;
    struct Node* next;
    struct Node* prev;
} Node;


void reverse(Node** head) {

    Node* curr = *head;
    Node* prev_ptr = NULL;
    Node* next_ptr = NULL;
    while (curr != NULL) {
        prev_ptr = curr->prev;
        next_ptr = curr->next;
        curr->prev = next_ptr;
        curr->next = prev_ptr;
        (*head) = curr;
        curr = next_ptr;

    }

}
\$\endgroup\$

2 Answers 2

8
\$\begingroup\$

You don't need to reverse a doubly linked list, which is an O(n) operation.

Just define a structure that will hold the head and tail of the list.

struct List
{
  Node* head;
  Node* tail;
  unsigned int count; // you can also keep track of number of nodes to access the count in O(1)
}

Functions manipulating the list shall now accept List* list rather then Node** head. They will also have to contain logic that checks and assigns the tail, but none of the operations should get any more complex in terms of its big-O time complexity.

Now traversing the list in reversed order is just matter of traversing the list from tail to head, rather then head to tail direction.

Doubly linked list without a tail is basically a singly linked list with capability to traverse back from where you already traversed forward, but never directly from the tail towards the head (without additional effort).

\$\endgroup\$
5
  • \$\begingroup\$ Never thought of it that way...nice. \$\endgroup\$
    – r4bb1t
    Jul 7, 2020 at 7:32
  • \$\begingroup\$ Works fine with a few instances of Node. Yet with a program with many instances (potentially most empty), this approach now obliges increase memory footprint for what could be a rarely used function. Might/might not be worth it. Depends on larger use of Node. I suspect it is a win, but not certainly. \$\endgroup\$ Jul 7, 2020 at 8:41
  • \$\begingroup\$ @chux-ReinstateMonica Linked lists (doubly, singly) are generaly not a very good choice for a big amount of items, because they allocate small chunks of memory for every new item. Something like C++'s std::vector should be preferred. Doubly linked list is to be used where its features can be taken advantage of (that is if you want bidirectional iteration). If you don't need backward iteration, you should be fine with a singly linked list. \$\endgroup\$
    – slepic
    Jul 7, 2020 at 10:02
  • \$\begingroup\$ @chux-ReinstateMonica For example hash table is an array of singly linked lists, yes most of them are probably empty, yes it would take up more memory if doubly linked list was used. But no, doubly linked list is not used by hash table, because hash table never needs to iterate those lists backwards. \$\endgroup\$
    – slepic
    Jul 7, 2020 at 10:04
  • \$\begingroup\$ Correction: hash table is not array of singly linked lists. It can be implemented that way but there are other ways to implement a hash table... \$\endgroup\$
    – slepic
    Jul 9, 2020 at 4:32
5
\$\begingroup\$

Seems simple and straightforward enough that you may not get many answers. The one thing that you're definitely missing is unit tests. Have you tested that your code works? for a two-element list? for a one-element list? for an empty list?

Your extra blank lines (after the { and before the two }s) are unidiomatic; most programmers would say that your reader has better things to do with that screen real estate.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.