Sign in to follow this  
Eternal

Reason for "dummy" elements in a list ?!

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

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this