Talk:Doubly-linked list/Element definition: Difference between revisions
Content added Content deleted
(Questions about the use of NOT NULL in the Ada 2005 version) |
(Doubly-linked lists are better when circular) |
||
| Line 1: | Line 1: | ||
The Ada 2005 version includes links Next and Previous with the Not Null attributes. How does one designate either end of the doubly linked list without the null link? Another way to ask is, what does the previous link access at the head of the list, and what does the Next link access at the end of the list? --[[User:Waldorf|Waldorf]] 22:56, 18 July 2008 (UTC) |
The Ada 2005 version includes links Next and Previous with the Not Null attributes. How does one designate either end of the doubly linked list without the null link? Another way to ask is, what does the previous link access at the head of the list, and what does the Next link access at the end of the list? --[[User:Waldorf|Waldorf]] 22:56, 18 July 2008 (UTC) |
||
:Actually, the pointers should never be invalid in a doubly-linked list element. The idea is that the head of the list, if any, is indicated by an element rather than by a state of. This is a great advantage of doubly-linked lists. There is no need to mark the ends, because the operations of removal and insertion in fact do not require the list head. In a circular list these operations become more efficient. Further, insertion can be written in a way that it will automatically remove the inserted element from its previous list. To summarize, the advantage is that the elements do not know their lists. |
|||
:Well, this might become tricky if empty list as an object is needed. In that case to keep a pointer to the first element would of course kill the idea. A technique to handle this is to have a special head element, which does not contain any data and is never visited when data has to be accessed. Of course there there are problems too. One well known problem is a need of downcasting in an OO design. It can solved by making head element implementing the interface of other nodes with null operations, as they never called anyway. --[[User:Dmitry-kazakov|Dmitry-kazakov]] 09:24, 19 July 2008 (UTC) |
|||
Revision as of 09:24, 19 July 2008
The Ada 2005 version includes links Next and Previous with the Not Null attributes. How does one designate either end of the doubly linked list without the null link? Another way to ask is, what does the previous link access at the head of the list, and what does the Next link access at the end of the list? --Waldorf 22:56, 18 July 2008 (UTC)
- Actually, the pointers should never be invalid in a doubly-linked list element. The idea is that the head of the list, if any, is indicated by an element rather than by a state of. This is a great advantage of doubly-linked lists. There is no need to mark the ends, because the operations of removal and insertion in fact do not require the list head. In a circular list these operations become more efficient. Further, insertion can be written in a way that it will automatically remove the inserted element from its previous list. To summarize, the advantage is that the elements do not know their lists.
- Well, this might become tricky if empty list as an object is needed. In that case to keep a pointer to the first element would of course kill the idea. A technique to handle this is to have a special head element, which does not contain any data and is never visited when data has to be accessed. Of course there there are problems too. One well known problem is a need of downcasting in an OO design. It can solved by making head element implementing the interface of other nodes with null operations, as they never called anyway. --Dmitry-kazakov 09:24, 19 July 2008 (UTC)