0

I'm currently trying to implement a doubly linked list. It has head and tail Node pointers. However, the head and tail are not actually pointing to informative nodes. For example, head is pointing to not the first node itself but a dummy node that has no data in it. So, head->next gives you the first node. In order to insert a node, we should create these dummy nodes (dummyHead and dummyTail) and make the connection between head and dummyHead. I'm confused about in which place should I do this creation.

Remy Lebeau
  • 555,201
  • 31
  • 458
  • 770
tgmn
  • 1
  • 2
  • 2
    Draw pictures. When you are having trouble wrapping your head around Linked Lists or any other graphing problem, draw the sucker. See what it looks like. Draw all of the steps required to perform the operation in question on the list. Compare the drawings to what you have coded or plan to code. Heck, use the drawings as as the basis for the code. – user4581301 Oct 22 '19 at 17:36
  • 1
    Sidenote: I find using an empty node as the `head` causes problems. Could just be me, but when I write a linked list, `head` is just a pointer to the first node, not a node itself. The `tail` would be the same. If `head` is a pointer to the first node then `head` is nothing but another `next` node by another name and this one difference can be abstracted away by using a pointer to the `head` pointer, making many of the operations you need to perform on a linked list MUCH simpler. [Example of pointer-to-pointer in action](https://stackoverflow.com/a/22122095/4581301) – user4581301 Oct 22 '19 at 17:37
  • Don't reinvent the wheel: [std;::list](https://en.cppreference.com/w/cpp/container/list). Also; a linked list is in *most* cases a *horrible* data structure to use with modern machines. – Jesper Juhl Oct 22 '19 at 17:43
  • ***head is pointing to an empty node*** I assume your code has some way of telling that the node is empty. bool flag? Is it a requirement to have this empty node as the head? If not you may want to rethink that decision. – drescherjm Oct 22 '19 at 17:53
  • 1
    Life is easier when `head` and `tail` are pointing to valid nodes, not dummy nodes. Is there a reason for the dummy node(s)? – Thomas Matthews Oct 22 '19 at 19:33
  • ***I'm confused about in which place should I do this creation.*** Probably in a constructor for your list class. – drescherjm Oct 22 '19 at 20:14
  • @ThomasMatthews not actually . I have to implement it in that way because the text specification wants me to implement it in that way. – tgmn Oct 23 '19 at 05:12

0 Answers0