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;
}
Reason for "dummy" elements in a list ?!
Author
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):
"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*
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.
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.
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 :)
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 :)
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement