• Post Reply Bookmark Topic Watch Topic
  • New Topic

Circular LinkedList: Dummy Heads and Tails  RSS feed

 
Shyam Prasad Murarka
Ranch Hand
Posts: 209
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Dear Readers,
I have successfully made a Circular LinkedList work with two pointers,i.e., one for the head and the other for the tail. Now, I have read that the performance of this list can be improved by using "dummy" heads and tails.
What is the meaning of these "dummies"? How do I use them? What makes them so special?
 
Rusty Shackleford
Ranch Hand
Posts: 490
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Strictly speaking, a circular linked list doesn't have a tail.

A dummy head node, makes it easier to write code to insert/delete/search a linked list, not sure if it makes it run more efficiently by itself. As you know ,the head is not really a node, as it doesn't do anything other then point to the first node. A dummy head node is placed between the head and the list. Sometimes it is used to hold global info of the list(ie number of nodes, highest & lowerst values, ect).

In a doubly linked list a dummy head node is particularily useful, the next reference points to the first node, and the previous reference points to the end of the list. In essence that creates a circular linked list that you can easily traverse in both directions.

An example of creating a doubly linked list with a dummy head node is Node head = new Node(null,null, null); To insert at the front of the list is head.setNext(new Node(item, head.getNext(), null).
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!