Where does the 1st links prev. pointer point to in doubly linked list? 
Author Message
 Where does the 1st links prev. pointer point to in doubly linked list?





: >
: >: [>Does the prev. pointer in the first link point to itself or to NULL like
: >: [>the last links next pointer does?
: >
: >: ------- Just like the last pointer in a singly linked list
: >: (or doubly for that matter) assign it to NULL. It is probably
: >: a bad idea (and complicates your code) to have the terminating
: >: pointers point to their own structures.
: >[...]
: >
: >I don't believe there is an inherent "goodness" or "badness" about
: >the choice of terminators in a linked list between "itself" and
: >NULL.  A traversal using the former method would look like:
: >
: >  p = head;
: >  while (p->next != p) {
: >    p = p->next;
: >    /* do work */
: >  }
: >
: >while the latter would look like:
: >
: >  p = head;
: >  while (p->next != NULL) {
: >    p = p->next;
: >    /* do work */
: >  }
: >
: >assuming our linked list has a "head node" that does not contain
: >data, only a "next" pointer.  (This is a common device to save that
: >extra "if p != NULL" check if we use a "head pointer" rather than a
: >"head node".)
: >
: >As you can see, no real difference and certainly no complications.

: Not for a traversal no, but inserting and deleting are made *much*
: simpler if instead of using NULL to mark the end of the list one
: uses a pointer back to a dummy anchor entry.  (See recent parallel
: thread on doubly linked list.)

: >Having said that, NULL is a better idea because it is common (and
: >hopefully as a result, obvious).  That doesn't mean the other method
: >is a "bad idea".

: Indeed not.  By that reasoning the bulk of C code is not badly
: written as one might deduce from observation, but well written
: because most of it is written like that.

: John
: --
: John Winters.  Wallingford, Oxon, England.

--
*************begin r.s. response*****************

        1) regarding head and tail pointer
           to self rather than null ...
           interesting and unusual ...
           such would be obscuring to analysis,
           but what other use is there to
           variation from
           ( academic computer science )
           usual practice ?

        2) regarding dummy or sentinel nodes ...
           this old idea was common practice
           ( in one form or another ) during
           1960s in fortran and assembly ...
           practice was abandoned by 1980 in
           academic computer science
           for good reasons ...
           a) simple singly linked list is
              commonly taught,  but is only one
              ( simple ) kind of,  data-structure
              ...
              what about 2-3 or binary trees with
              sentinels at every leaf because
              programmer can not manage standard
              practice ???

           b) {*filter*} data-structures where there may
              be no intuitive place for sentinels
              ...

        a 'programmer' who can not manage standard
        ( academic computer science ) practice,
        regarding such,  probably should not assume
        such responsibilities ...

*************end r.s. response*******************
Ralph Silverman



Sat, 28 Aug 1999 03:00:00 GMT  
 
 [ 1 post ] 

 Relevant Pages 

1. Where does the 1st links prev. pointer point to in doubly linked list?

2. Safely updating a doubly-linked list

3. doubly linked list in 1 field

4. ct: Re: doubly linked list in 1 field

5. Doubly linked lists

6. Heterogeneous Doubly Linked List

7. Doubly linked list.

8. Doubly linked list (again, sorry)

9. Need example of Doubly circular linked list

10. Doubly Linked List

11. Heterogeneous Doubly Linked List

12. Safe doubly-linked list/tree implementation?

 

 
Powered by phpBB® Forum Software