Singly linked list into doubly linked list (C)

Question

I have this function called display that shows the contents of my linked list from start to finish and I would like for it to go from finish to start when it is done.

I am trying to turn this singly linked list into a doubly linked list, but I am having trouble understanding just how *next in this code knows to go to next, and how to make *prev go to previous.

I tried to create a function called displayReverse, but that did not work.

Does anyone have any advice? Thanks in advance

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// map number to name
const char *map[] = { "zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine" };

// data structure
typedef struct Data
{
    int number;
    char name[5];
} data_t;

// define the item (node) of a linked list
typedef struct Node
{
    data_t data;
    struct Node *next; 
    struct Node *prev;
} node_t;

// declare of functions
// add(node_t **, node_t) - it is function signature
void add(node_t **, node_t);
void print_node(node_t *);
void display(node_t **);
void freeList(node_t **);

int main(int argc, char const *argv[])
{
    node_t *list = NULL; // the head of a linked list

    for (int i = 0; i < sizeof(map) / sizeof(map[0]); ++i)
    {
        node_t node = { .data.number = i };
        strcpy(node.data.name, map[i]);
        add(&list, node);
    }

    puts("The linked list is: ");
    display(&list);
    freeList(&list);
    return 0;
}

void add(node_t **head, node_t node)
{
    node_t *tmp = (node_t *)malloc(sizeof(node_t));
    tmp->data = node.data;
    tmp->next = *head;
    tmp->prev = *head;
    *head = tmp;
}

void display(node_t **head)
{
    node_t *ptr = *head;
    while (ptr != NULL)
    {
        print_node(ptr);
        ptr = ptr->next;
    }
}

void freeListReverse(node_t **head)
{
    node_t *tmp;
    while (*head != NULL)
    {
        tmp = *head;
        *head = (*head)->prev;
        free(tmp);
    }
}

void freeList(node_t **head)
{
    node_t *tmp;
    while (*head != NULL)
    {
        tmp = *head;
        *head = (*head)->next;
        free(tmp);
    }
}

void print_node(node_t *node)
{
    printf("node: %d, %s, len of name %ld; next: %p\n",
           node->data.number, node->data.name, strlen(node->data.name), node->next);
}

Warning: `char name[5];` is too short for 5-character data like `"three"` to be stored as strings because there are no room for the terminating null-character. — MikeCAT, Mar 16 '23 at 12:25
weirdly enough, three doesnt get cut off , but thank you i will fix this part — clubmix, Mar 16 '23 at 12:26
@clubmix _three doesnt get cut off_: that's not weird, what you see here is _undefined behaviour_ (google that), which includes "apparently working fine". That being said, I'd start with a pencil and piece of paper. Represent the list elements by boxes and the pointers by arrows pointing to boxes. — Jabberwocky, Mar 16 '23 at 12:30
@clubmix that being said: you mention `displayReverse` function that does not work. Well, then show us that function, then we might tell you why it doesn't work. — Jabberwocky, Mar 16 '23 at 12:34
Your `add` function already is broken. You should start with pen&paper and draw the oerations you need to do to make the correct links. — Gerhardh, Mar 16 '23 at 12:45

chqrlie · Answer 1 · 2023-03-16T12:58:56.337

There are some problems in the code:

strcpy(node.data.name, map[i]); copies the string from the array to the local temporary node structure's name field but some of the strings will not fit into an array of 5 bytes as they need 6 bytes including the null terminator. Modify the definition of name to char name[6]; or greater.
In the add function, tmp->prev = *head; is incorrect. You should update the prev node of the node pointed to by head if prevent to point to the newly allocated node pointed to by tmp. tmp->prev should be initialized to NULL.
there is no pointer to the last node un the list, so you will have to first scan the entire list to locate the last node, then you can iterate along the prev chain to print the list contents in reverse.
freeListReverse does not work because it start from head, it should first locate the last node as for printing.
the printing functions should take a const node *head argument instead of a pointer to the head pointer.

Here is a modified version with error checking:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// map number to name
const char *map[] = {
    "zero", "one", "two", "three", "four",
    "five", "six", "seven", "eight", "nine"
};

// data structure
typedef struct Data {
    int number;
    char name[8];
} data_t;

// define the item (node) of a linked list
typedef struct Node {
    data_t data;
    struct Node *next;
    struct Node *prev;
} node_t;

// declare of functions
// add(node_t **, node_t) - it is function signature
node_t *add(node_t **, node_t);
void print_node(const node_t *);
void display(const node_t *);
void display_reverse(const node_t *);
void freeList(node_t **);

int main(int argc, char const *argv[]) {
    node_t *list = NULL; // the head of a linked list

    for (size_t i = 0; i < sizeof(map) / sizeof(map[0]); ++i) {
        node_t node = { .data.number = i };
        if (strlen(map[i]) + 1 > sizeof(node.data.name)) {
            fprintf(stderr, "string too long: %s\n", map[i]);
            continue;
        }
        strcpy(node.data.name, map[i]);
        if (add(&list, node) == NULL) {
            fprintf(stderr, "out of memory for %s\n", map[i]);
        }
    }
    puts("The linked list is: ");
    display(list);
    puts("");
    puts("The linked list in reverse is: ");
    display_reverse(list);
    freeList(&list);
    return 0;
}

node_t *add(node_t **head, node_t node) {
    node_t *tmp = (node_t *)malloc(sizeof(node_t));
    if (tmp) {
        tmp->data = node.data;
        tmp->next = *head;
        tmp->prev = NULL;
        if (*head) {
            (*head)->prev = tmp;
        }
        *head = tmp;
    }
    return tmp;
}

void print_node(const node_t *node) {
    printf("node: %d, %s, len of name %zu; prev: %p, next: %p\n",
           node->data.number, node->data.name, strlen(node->data.name),
           (void *)node->prev, (void *)node->next);
}

void display(const node_t *head) {
    for (const node_t *ptr = head; ptr != NULL; ptr = ptr->next) {
        print_node(ptr);
    }
}

void display_reverse(const node_t *head) {
    const node_t *ptr = head;
    if (ptr) {
        while (ptr->next) {
            ptr = ptr->next;
        }
        while (ptr != NULL) {
            print_node(ptr);
            ptr = ptr->prev;
        }
    }
}

void freeList(node_t **head) {
    while (*head != NULL) {
        node_t *tmp = *head;
        *head = (*head)->next;
        free(tmp);
    }
}

Output:

The linked list is:
node: 9, nine, len of name 4; prev: 0x0, next: 0x6000015b92c0
node: 8, eight, len of name 5; prev: 0x6000015b92e0, next: 0x6000015b92a0
node: 7, seven, len of name 5; prev: 0x6000015b92c0, next: 0x6000015b9280
node: 6, six, len of name 3; prev: 0x6000015b92a0, next: 0x6000015b9260
node: 5, five, len of name 4; prev: 0x6000015b9280, next: 0x6000015b9240
node: 4, four, len of name 4; prev: 0x6000015b9260, next: 0x6000015b9220
node: 3, three, len of name 5; prev: 0x6000015b9240, next: 0x6000015b9200
node: 2, two, len of name 3; prev: 0x6000015b9220, next: 0x6000015b91e0
node: 1, one, len of name 3; prev: 0x6000015b9200, next: 0x6000015b91c0
node: 0, zero, len of name 4; prev: 0x6000015b91e0, next: 0x0

The linked list in reverse is:
node: 0, zero, len of name 4; prev: 0x6000015b91e0, next: 0x0
node: 1, one, len of name 3; prev: 0x6000015b9200, next: 0x6000015b91c0
node: 2, two, len of name 3; prev: 0x6000015b9220, next: 0x6000015b91e0
node: 3, three, len of name 5; prev: 0x6000015b9240, next: 0x6000015b9200
node: 4, four, len of name 4; prev: 0x6000015b9260, next: 0x6000015b9220
node: 5, five, len of name 4; prev: 0x6000015b9280, next: 0x6000015b9240
node: 6, six, len of name 3; prev: 0x6000015b92a0, next: 0x6000015b9260
node: 7, seven, len of name 5; prev: 0x6000015b92c0, next: 0x6000015b9280
node: 8, eight, len of name 5; prev: 0x6000015b92e0, next: 0x6000015b92a0
node: 9, nine, len of name 4; prev: 0x0, next: 0x6000015b92c0

Traversing the list to get to the last element can be avoided by making the list circular. — nielsen, Mar 16 '23 at 13:00
@nielsen: yes indeed, but circular lists are more difficult to handle as the end test is not a comparison to `NULL`. The OP has probably not studied this yet. — chqrlie, Mar 16 '23 at 13:02
Thank you very much for your work, in print_node function you wrote it like (void *)node->prev, (void *)node->next); Why is adding void* necessary? — clubmix, Mar 16 '23 at 13:12
@clubmix: the `%p` format expects a pointer to `void` or one the `char` types. For strict conformance, the cast is recommended. The reason is some of th e pointer types might have a different representation on some exotic platforms such as the antique *Cray-1*. On most platforms today especially on all POSIX compliant platforms, it has no effect. — chqrlie, Mar 16 '23 at 14:40
To add to chqrlie's answer, see [this](https://stackoverflow.com/questions/24867814/printfp-and-casting-to-void) or [this](https://stackoverflow.com/questions/7290923/when-printf-is-an-address-of-a-variable-why-use-void). — user1801359, Mar 16 '23 at 14:46

Singly linked list into doubly linked list (C)

1 Answers1