1

I am doing a refresher on CS fundamentals.
I have a question on linked lists.

There are some cases that a dummy node is used (in the head of the list mainly) to assist in the implementation.

I see that if it is missing (i.e. if an approach without using a dummy node is followed) the code becomes "messy" (at least I do it messy since I am rusty on these stuff....)

I was wondering are there cases that an algorithm is not possible to be solved without using a dummy node?
Can you give an example?

And are there specific characteristics of the problem at hand that give away that a dummy node is the only way to go?

Note: I don't tag a specific language but just in case my prefered is Java

Cratylus
  • 52,998
  • 69
  • 209
  • 339

3 Answers3

3

No, there are not any algorithms that are not possible without having a dummy node, it is just there for convenience and keeping the code clean. Without a dummy you have to take special consideration e.g. when deleting the last node of a linked list or traversing an empty linked list – in these cases the dummy acts as a sentinel that keeps the core algorithm for traversal and removal simpler.

Svante
  • 50,694
  • 11
  • 78
  • 122
BrokenGlass
  • 158,293
  • 28
  • 286
  • 335
2

The advantage of having a dummy node (called a sentinel in some texts) is that it's no longer necessary to check for null elements in the list, in a way, it's an instance of the Null Object pattern, making the implementation of some algorithms simpler.

Other than that, there won't be any difference in the algorithms that can be solved using either implementation (with or without a dummy node). For example, Oracle's implementation of the LinkedList class uses a dummy node, but other vendors are free to write a dummy-less version of the class, since it's an implementation detail that won't make any difference to the outside world.

Óscar López
  • 232,561
  • 37
  • 312
  • 386
0

Without some way of unambiguously marking the end of the list, it can be impossible to unambiguously interpret nested lists. See: Why do we need `nil`?

You could, of course check if a node is the final node by keeping a pointer to it, but that is unattractive in no small part because it is inefficient.

Community
  • 1
  • 1
Marcin
  • 48,559
  • 18
  • 128
  • 201
  • 1
    May be I am missunderstanding your reference but a `null` pointer marking the end of the list is not a dummy node.At least I never thought of it that way.A dummy node in the end would be a non `null` node having a special value indicating the end.Or am I missunderstanding your answer? – Cratylus Jan 31 '12 at 18:48
  • @user384706: Yes, you are misunderstanding my answer, and the linked question. `nil` is not the same thing as a null pointer. Java is not the only programming language. – Marcin Jan 31 '12 at 18:53