Doubly linked list implementation with dummy head and tail

Question

I have the folowing: typedef struct d_node d_node_t;

struct d_node
    {
        void *data;
        d_node_t *next;
        d_node_t *prev;
    };
typedef struct d_list d_list_t;
struct d_list
    {
        d_node_t head;
        d_node_t tail;
    };

How can I implement d_list_t *DListCreate(void) function?

Your definition of `struct d_list` seems wrong to me. `head` and `tail` should be pointers shouldn't they? — cleblanc, Sep 17 '18 at 16:40
If the requirement is that you have dummy objects at each end, then I'd guess that you just need to make head.next point to tail and tail.prev point to head. — Rup, Sep 17 '18 at 16:41
It's really odd to have a fixed head and tail. As @cleblanc points out, these should be pointers as these change frequently. — tadman, Sep 17 '18 at 16:41
The typedefs make sense if the non-pointer members of d_list are dummies and only their dummy.head.next points to actual head and dummy.tail.prev points to actual tail. Seems somewhat double-indirect, but should work. Probably dummy.tail.next = NULL and dummy.head.prev=NULL. — Yunnosch, Sep 17 '18 at 16:45
It's requirement, we'll use iterator to work with the list afterwards. But I have no Idea how to implement the required DListCreate — Ann, Sep 17 '18 at 16:45
You just need to allocate memory for it and then fill in head.next and tail.prev. Set all the other pointers to NULL, or just calloc the memory in the first place. — Rup, Sep 17 '18 at 16:48
@Yunnosch The signature is `d_list_t *DListCreate(void)`, so I assume it needs to be malloced? — Rup, Sep 17 '18 at 16:50
@Rup That is a good point. Yes, the prototype implies to alloc and return, the alternative to use a global variable and return a pointer to it is of course ludicrous. Thanks for spotting. — Yunnosch, Sep 17 '18 at 17:01

score 2 · Answer 1 · answered Sep 17 '18 at 16:52

I have no Idea how to implement the required DListCreate

Your DListCreate() function will probably create an empty list, right? That means no actual nodes, just the dummy head and tail nodes. So... ask yourself, what should head->next point to if there are no actual nodes? Likewise, what should tail->prev point to? All you need to do to create an empty list is to create one of your d_list structures, and then set the head and tail pointers appropriately.

Hint: the address of myDList.tail is &(myDList.tail).

score 2 · Answer 2 · answered Sep 17 '18 at 17:07

2

d_list_t *DListCreate(void)
{
    d_list_t *myDList = (d_list_t*)malloc(sizeof(d_list_t));

    if (new_d_list == NULL)
    {
        return(NULL);

    }
   &(myDList.tail)->data = NULL;
   &(myDList.tail)->next = NULL;
   &(myDList.tail)->prev = &(myDList.head)

   &(myDList.head)->data = NULL;
   &(myDList.head)->next = &(myDList.tail);
   &(myDList.head)->prev = NULL;

   return(myDList);
}

answered Sep 17 '18 at 17:07

Ann

25
9

Mostly looks good! I think you need `myDList->head` and `tail` though, since `myDList` is a pointer. You could then just use `myDList->head.data` etc. rather than dereferencing them and using `->` to access the members. – Rup Sep 17 '18 at 17:09
1

Oh, FWIW some posters here feel strongly that you [should not cast the result of malloc](https://stackoverflow.com/questions/605845/do-i-cast-the-result-of-malloc) (although I'm fine either way) – Rup Sep 17 '18 at 17:13
You've also mixed up `new_d_list` and `myDList` - you need to be consistent. – Rup Sep 17 '18 at 17:15
Yes, you're right. – Ann Sep 17 '18 at 17:17
@Ann Update your answer accordingly to help further readers. – kiran Biradar Sep 17 '18 at 17:23
A simpler way to say `&(myDList.tail)->next` is `myDList.tail.next`. You only need to take the address of `myDList.tail` in order to assign it to `head`'s `next` pointer. So, for example, `myDList.head.next = &(myDList.tail);`. – Caleb Sep 17 '18 at 18:10

Doubly linked list implementation with dummy head and tail

2 Answers2