Jump to content
  • Advertisement
Sign in to follow this  

Reason for "dummy" elements in a list ?!

This topic is 4516 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi, I just started to revisit some stuff from my algorithms and data-structures course and noticed my professor uses empty dummy-elements at the beginning and end of his linked list class(es). His constructor then looks like this (JAVA):
public List(Object StartEmpty, Object EndEmpty)
//Link constructor parameters are "data" and "next element"
        Start = new Link(StartEmpty, null);
        End = new Link (EndEmpty, Start);  
        Start.Next = End; 

"Link" is a list element and the constructor is called like List list = new List("dummy","dummy"); Well, I can't figure out what the point of those two extra elements is, am I retarded or is there really no point ? ;) *rant* I hate his horrible German/Java-mix programs, with all the glorious setzeAktuellerZeigerZurueck() and erstelleEinenAktionsAbhoerer() methods*/rant*

Share this post

Link to post
Share on other sites
I remember using ONE dummy element in my early college classes but not two.

The reason the dummy elements exist is to remove "special" cases in the code to manage the list.

Without at least 1 dummy element there is no way to implmenet the following cases identically:

1) Adding an element to the beginning of a list
2) Adding an element in the middle of the list
3) Adding an element to the end of the list

at best you can make 2 of those 3 follow the same logic branch without using dummy node(s). The middle case isn't special, I just included it because it can either be the same as case 1, or the same as case 3 ... but not both.

A similar situation arises for deleting:

1) Removing the first element of a list
2) Removing the last element of a list

So the dummy nodes simply exist to make writing the code easier, primarily while learning.

Share this post

Link to post
Share on other sites
Yup, dummy exist as helpful representation of empty elements, which NULL pointers are not. The reason is simply that most the time when using a dummy node instead of a NULL, that saves you the obligation to handle complicated special cases.
For a linked list that might look not so difficult, but I've recently tried to implement a red black tree without using dummy nodes... It was a nightmare (especially node deletion) I didnt want to use them because I'm the kind of guy who likes playing with the raw things like pointers... but I quickly changed my mind and used dummy nodes (which are weak references to some extend). And things turned to be a hell lot better :)

Share this post

Link to post
Share on other sites
Sign in to follow this  

  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!