Strange kind of doubly-linked list

I saw some code today for a linked list that was not like anything I've seen before, and I was hoping someone could tell me what it's called. In a normal doubly-linked list, the 'next' pointer points to the next element in the list, and the 'previous' pointer points to the previous element in the list. The code I say today is a little different. The 'previous' pointer actuallly points direectly to the 'next' pointer of the previous element. Obviously, you can't use the 'previous' pointer to traverse the list backwards, so I don't know what the value of this type of list is. The only thing I could think of is that it's basically a singly-linked list, but it allows you to remove an element without knowing what the 'head' pointer is. However, wouldn't it be simpler if each element of the list had a pointer directly to the head? Does anyone know what this kind of linked list called?

nospam_timur@tabi.org (Timur Tabi) writes: > The code I say today is a little different. The 'previous' pointer > actuallly points direectly to the 'next' pointer of the previous > element. ... > The only thing I could think of is that it's basically a > singly-linked list, but it allows you to remove an element without > knowing what the 'head' pointer is. However, wouldn't it be simpler > if each element of the list had a pointer directly to the head? I'm not familiar with it, but I agree with your analysis of it's possible use. Deletion takes O(n) if the pointer is to the head (of the list). The "stub" back pointer allows deletion in constant time (if you can a pointer to the item to be deleted). Pointing to the previous pointer (instead of the previous item) allows (very) slightly faster access to the "next" pointer: you don't have to offset from the beginning of the item structure. But that saving seems inconsequential. -paul- -- Paul E. Black (p.black@acm.org)

On Wed, 28 Jul 2004, Paul E. Black wrote: > > nospam_timur@tabi.org (Timur Tabi) writes: >> The code I say today is a little different. The 'previous' pointer >> actuallly points direectly to the 'next' pointer of the previous >> element. ... >> The only thing I could think of is that it's basically a >> singly-linked list, but it allows you to remove an element without >> knowing what the 'head' pointer is. However, wouldn't it be simpler >> if each element of the list had a pointer directly to the head? > > I'm not familiar with it, but I agree with your analysis of [its] > possible use. Deletion takes O(n) if the pointer is to the head (of > the list). I don't follow you there. Are you thinking of the deletion algorithm that shuffles node contents "forward," rather than changing pointers, e.g. void SlowButConvenientDelete(node *p) { if (p->next == NULL) free(p); else { memcpy(p, p->next, sizeof *p); SlowButConvenientDelete(p->next); } } I usually write deletion routines like this: void FastButInconvenient(node **p) { if (p == NULL || *p == NULL) return; *p = (*p)->next; free(p); } (Notice the double indirection in the parameter, there. This function would be called as in 'FastButInconvenient(&q->next)'.) > The "stub" back pointer allows deletion in constant time > (if you can [provide?] a pointer to the item to be deleted). > > Pointing to the previous pointer (instead of the previous item) allows > (very) slightly faster access to the "next" pointer: you don't have > to offset from the beginning of the item structure. But that saving > seems inconsequential. I initially assumed the pointer to the previous "next" pointer would allow some kind of elegant code with fewer "special cases" than the usual delete routine. But I can't it figure out. Could the OP (Timur Tabi) please post the insertion and deletion routines for the linked list in question? I think we'd all be interested in seeing what exactly is going on here.[1] -Arthur [1] - For some suitable definition of "all".

"Arthur J. O'Dwyer" <ajo@nospam.andrew.cmu.edu> wrote in news:Pine.LNX.4.60-041.0407281740400.11035@unix46.andrew.cmu.edu: <snip> >> The "stub" back pointer allows deletion in constant time >> (if you can [provide?] a pointer to the item to be deleted). >> >> Pointing to the previous pointer (instead of the previous item) allows >> (very) slightly faster access to the "next" pointer: you don't have >> to offset from the beginning of the item structure. But that saving >> seems inconsequential. > > I initially assumed the pointer to the previous "next" pointer > would allow some kind of elegant code with fewer "special cases" > than the usual delete routine. But I can't it figure out. The only special case that I can spot is deletion of the first element /if/ the 'prev' pointer for that element refers to the pointer to the first element outside of the list (say, in a struct holding the list information or just any old pointer to the first element used as the 'root' of the list). I often use something similar locally when processing linked lists so that you can unlink any node (including the first) without explicitely dealing with it as a special case. > Could the OP (Timur Tabi) please post the insertion and deletion > routines for the linked list in question? I think we'd all be > interested in seeing what exactly is going on here.[1] > > > -Arthur > > [1] - For some suitable definition of "all". I'm interested... it's seems like a really odd thing to do, so I'm wondering why! Normally, if you're processing a linked list you'll have traversed it and I think it a rare occurance to do deletions from a list based only on a pointer to the node. Typically the the previous nodes pointer (or the head) is available since the node has just been 'walked' over in the operation before this one. Ian Woods -- There is no sig.

"Arthur J. O'Dwyer" <ajo@nospam.andrew.cmu.edu> wrote in message news:<Pine.LNX.4.60-041.0407281740400.11035@unix46.andrew.cmu.edu>... > Could the OP (Timur Tabi) please post the insertion and deletion > routines for the linked list in question? I think we'd all be > interested in seeing what exactly is going on here.[1] Paul is correct - pointing to the head wouldn't be useful because it would still take O(n) to delete an entry, just like it does for a singly-linked list. That's because you need to find the pointer to the previous element in order to properly delete the current element. Having the current element's "previous" pointer point to the "next" pointer of the previous element eliminates that. The code actually comes from some BSD linked-list macros. I'll dig it up and post them. What I'm trying to figure out is whether this type of linked list is singly-linked or doubly-linked. It's not singly-linked, because it's possible to delete an element in O(1) time, which is not true of singly-linked lists. On the other hand, it's not doubly-linked, because you can't traverse the list backwards. Could I call this a 1.5-linked list? As for the performance enhancement, it's not really there. Using the C language on x86 as an example, the offset into the structure of the "next" pointer is always a constant known at compile time. That means that updating the "next" pointer would be the instruction "mov [ebx+N], eax", where N is the offset. The above technique would replace that with "mov [ebx], eax". However, on any modern x86 system, the performance difference is zero.

* Timur Tabi: > > it's possible to delete an element in O(1) time, which is not true of > singly-linked lists. In general. If you can guarantee a next element and no pointers to that element it's rather easy to do. Often the belief that O(1) deletion is not possible for singly linked lists goes hand in hand with the belief that O(1) insert/delete isn't possible for arrays (or more generally in combination with O(1) random read/write access), and other such erronous "can't do" beliefs; I think it's got to do with modern textbooks being just rehashes of the most trivial stuff from earlier books, where the authors feel they need to justify introduction of various things by giving a "no can do" impression. Now regarding the original question. Assuming the design is intentional and meaningful the reason why the back-pointer points to to previous node's next-pointer is probably that in certain cases it can point to some _other_ pointer that is not necessarily in a list node -- my guess would be that one such case is the first node. -- A: Because it messes up the order in which people normally read text. Q: Why is it such a bad thing? A: Top-posting. Q: What is the most annoying thing on usenet and in e-mail?

alfps@start.no (Alf P. Steinbach) wrote in message news:<41087d55.1227530718@news.individual.net>... > * Timur Tabi: > > > > it's possible to delete an element in O(1) time, which is not true of > > singly-linked lists. > > In general. If you can guarantee a next element and no pointers to that > element it's rather easy to do. I'm not sure how meaningful that kind of guarantee is. It sounds like you're saying that I can provide O(1) deletions with a singly-linked list as long as I only try to delete the first element. That's like guaranteeing I won't die as long as I live forever. > Assuming the design is intentional and meaningful the reason why the > back-pointer points to to previous node's next-pointer is probably that in > certain cases it can point to some _other_ pointer that is not necessarily in a > list node -- my guess would be that one such case is the first node. Ah, I see your point. All we need now is a name for this kind of linked list!

In article <53bb806a.0407281942.77b2b8a4@posting.google.com> Timur Tabi <nospam_timur@tabi.org> writes: >The code actually comes from some BSD linked-list macros. I'll dig it >up and post them. If you are referring to those in <sys/queue.h>, there is a manual page for them as well: queue(3). >What I'm trying to figure out is whether this type of linked list is >singly-linked or doubly-linked. It's not singly-linked, because it's >possible to delete an element in O(1) time, which is not true of >singly-linked lists. On the other hand, it's not doubly-linked, >because you can't traverse the list backwards. Could I call this a >1.5-linked list? Assuming you are referring to the ones to which LIST_HEAD, LIST_ENTRY, LIST_FOREACH, LIST_INSERT_*, etc., apply, they are "almost but not quite doubly linked". The "CIRCLEQ" objects are the only ones that are "full" doubly linked, and the "TAILQ" objects are (via "cheating") able to go backwards. Various BSD variants also include a few more varieties of lists in the queue(3) macros. -- In-Real-Life: Chris Torek, Wind River Systems Salt Lake City, UT, USA (40�39.22'N, 111�50.29'W) +1 801 277 2603 email: forget about it http://web.torek.net/torek/index.html Reading email is like searching for food in the garbage, thanks to spammers.