Hi I want to know that do "head" and "tail" store any value like the other nodes?? thanks
+4
A:
Head node has a reference to the next node, and a null reference to the previous node.
Tail node has a reference to the previous node, and a null reference to the next done.
daedlus
2010-05-30 07:47:19
-1. How would you traverse from head or tail if they have both prev and next reference set null?
nikc
2010-05-30 07:53:04
why do you think from above that they have both prev and next on both to null?The head node is the starting node that has only the ref to next.like wise tail has ref to its prev node only.
daedlus
2010-05-30 07:55:09
Well, I realize (after rereading) what you write isn't what you mean. I read it as *ref to next node and ref to prev node set to null*. I removed my down vote, but perhaps you should revise your language slightly to eliminate possibilities for misunderstanding.
nikc
2010-05-30 07:58:31
This is still wrong. The head and tail nodes do store values (assuming the list isn't empty).
Matthew Flaschen
2010-05-30 07:59:45
@nikc, I've reworked the wording. Hopefully it's easier to understand. @Flaschen, This is true; the head node in the diagram stores 12 and the tail node stores 37. Also, for empty lists, there is no head or tail node (they are `null`), assuming the list is implemented the traditional way.
strager
2010-05-30 08:02:28
you are right mathew
daedlus
2010-05-30 08:03:58
Worth upvoting after revision.
Esko
2010-05-30 08:16:47
+2
A:
Head and tail nodes should be identical to any other node. The only difference being, head hasn't a reference to a previous node, and tail hasn't a reference to a next node.
Unless, your implementation is a circularly linked list, where head references tail as previous node, and tail references head as next node.
nikc
2010-05-30 07:55:29
+1
A:
A doubly-linked list is a specialized graph data structure.
If you think of a doubly-linked list as a graph, you see every node has data, even if it has only one connection. In a doubly-linked list, which is a complete graph (where there is a path from any given node to any other given node), inner nodes contain two references (one for either direction in the list), and outer nodes (head/tail) contain only one reference (which is a reference back to the node you may have accessed this node from).
Head and tail nodes are only special in that they only have one reference instead of two. They are still part of the graph data structure you are representing.
strager
2010-05-30 08:07:34
+4
A:
Depends on the specific implementation of the linked list. Both ways can be made to work, but having extra "head/tail" elements greatly simplifies the implementation of many operations like insert/remove (since you can always be sure there will be a next/previous element, saving a lot of conditional code to deal with the start/end of the list).
Since you tagged your question as Java, i suggest you take a look at the JDK source code of java.util.LinkedList. You will find that in this specific implementation head and tail do not refer to an element.
If you really want to understand the advantage of extra head/tail nodes its probably most instructive if you implement a simple double linked list by yourself to experience the difference in complexity for the insert/remove methods firsthand.
In other languanges that allow pointer arithmetic, there is often only an extra head node which also serves as the tail node at the same time.
Durandal
2010-05-30 08:09:10
A:
As Scot said above the structure of Doubly Linked Lists are shown there. I think it is the Wikipedia Image.
Please refer this link and you will be surely got the idea on it.
http://richardbowles.tripod.com/cpp/linklist/doublist.htm
Head and tail should be identical to all other nodes at the List. But there are bit difference from Circular D. Linked Lists and this features are not dealing with them.
Regarding to the Doubly Linked Lists the difference is head hasn't a reference to a previous node + tail hasn't a reference to a next node. This is a simple data structure for Doubly Linked Lists.
udsha
2010-05-30 09:25:01