COMPGROUPS.NET | Search | Post Question | Groups | Stream | About | Register

### Strange kind of doubly-linked list

• Email
• Follow

```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?
```
 0
Reply nospam_timur (26) 7/28/2004 4:15:51 PM

See related articles to this posting

```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
to offset from the beginning of the item structure.  But that saving
seems inconsequential.

-paul-
--
Paul E. Black (p.black@acm.org)
```
 0
Reply p.black (279) 7/28/2004 8:24:03 PM

```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".
```
 0
Reply ajo (1601) 7/28/2004 9:48:05 PM

```"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.

```
 0
Reply newspub2 (159) 7/28/2004 11:05:30 PM

```"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
possible to delete an element in O(1) time, which is not true of
because you can't traverse the list backwards.  Could I call this a

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.
```
 0
Reply nospam_timur (26) 7/29/2004 3:42:06 AM

```* Timur Tabi:
>
> it's possible to delete an element in O(1) time, which is not true of

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?
```
 0
Reply alfps (7389) 7/29/2004 4:40:04 AM

```Timur Tabi wrote:
....
>
> Does anyone know what this kind of linked list called?

A very low scoring project in CS202?
```
 0
Reply uce (418) 7/29/2004 7:49:01 PM

```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
>
> 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.

All we need now is a name for this kind of linked list!
```
 0
Reply nospam_timur (26) 7/29/2004 10:53:05 PM

```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
>possible to delete an element in O(1) time, which is not true of
>because you can't traverse the list backwards.  Could I call this a

Assuming you are referring to the ones to which LIST_HEAD, LIST_ENTRY,
LIST_FOREACH, LIST_INSERT_*, etc., apply, they are "almost but not

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
Reading email is like searching for food in the garbage, thanks to spammers.
```
 0
Reply nospam252 (1722) 7/30/2004 1:08:27 AM

8 Replies
41 Views

Similar Articles

12/11/2013 5:09:42 PM
[PageSpeed]

Similar Artilces:

queue as a circular list and doubly list
Hello I would like to get simple program using queue as a circular and doubly list. For myprogram I can pop from rear. So I would like to get the correct one. Could someone help me? Myat Su myatsuhlaingster@gmail.com said: > Hello > I would like to get simple program using queue as a circular and doubly > list. > For myprogram I can pop from rear. So I would like to get the correct > one. > Could someone help me? The best way to get a simple program is to write one. If you have difficulty writing one, consider obtaining the appropriate reference literature, either fro...

I am trying to create a linked list of 15 random numbers. The list is to be populated by inserting new nodes from the front. Can someone give me an example of how to do this? I'm not sure where to start. Thanks. dmattis writes: > I am trying to create a linked list of 15 random numbers. > The list is to be populated by inserting new nodes from the front. > Can someone give me an example of how to do this? I'm not sure where > to start. This tutorial might help. http://www.fortunecity.com/skyscraper/false/780/linklist.html dmattis wrote: > > I am trying to c...

Hi All- I am currently trying to phase some new Kyocera mass printers into our network, but am having some issues with getting them connected. I have found that most of them will not work unless I force 100, full duplex and not autonegotioation. I am trying to get these printers connected through a cat 4006 and a cat 6513. I have several printers that will not get a link light whatsoever unless we place a hub between the printer and the catalyst, no matter if i set it to not negotiate....but with a hub inbetween, everything works fine. Has anyone ever seen this issue? TIA, M Is there a...

hi, i have written a function in adding a node to the linked list but this only adds "1" to the list as i get in the output I'm using borland c++ compiler The code ------------------------------------------------------------- #include <alloc.h> #include <stdio.h> #include <string.h> void append(struct node **, int ); void display(struct node *); struct node { int data; struct node *link; }; void main() { struct node *p; p = NULL; //printf("the number of elements in the linked list are: = %d", count(p)); append(&p, 1); append(&p, 5); ...

I have a double-linked list. I need to know if it is possible to remove just one of an item, instead of all that match the given criteria with the remove() command. Any thoughts? [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] deanfamily wrote: > I have a double-linked list. I need to know if it is possible to remove just > one of an item, instead of all that match the given criteria with the > remove() command. Any thoughts? cont.erase(find_if(cont.begin(), cont.end(), your_predicate_ftor...

I am trying to design an object with connections to parent and child objects of the same class. I can't seem to produce an implementatin without draw backs. It's code follows (along with some questions and problems in comments): #include <iostream> class Node { protected: Node* parent; Node* child; std::string name; private: void init() { parent = 0; child = 0; name = ""; } public: Node() { init(); } Node(const std::string name) { init(); this->setName(name); } Node(const Node& node) { init(); set(node); } virtual ~Node() { /...

Dear, I wreated a small program that make a linked list of factorials of numbers, I don't have expirience with templates so I will bee thankfull if anybody can make the same with templates(change my small program), becouse I don't understand a templates. Program is commpilled with Visual C++ 6.0. (Escouse mee first version of program was incorect becouse variable :"i" was seted to 1, a true value is 0). Thanks in advance ! Robert ! // fact.cpp : Defines the entry point for the console applicatio...

dear group, /*Linked list in C*/ #include<stdio.h> #include<stdlib.h> struct node { int data; struct node *next; }a; void init(int data) { struct node *p; p = malloc(sizeof *p); if(!p) { printf("mem error"); exit(EXIT_FAILURE); } a.data = data; a.next = NULL; p = &a; } int main(void) { unsigned int i,j; for(j=0;j<6;j++) { scanf("%d",&i); init(i); } while(a.next != NULL) { for(j=0;j<6;j++) printf("value = %d\n",a.data); } return 0; } This is not the first time I am imp...

Here's the problem: I have two linked lists of integers (list1 and list2) that are already in sequential order, and I need to combine them into one list in sequential order (newList). Any thoughts? [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] deanfamily wrote: > Here's the problem: > I have two linked lists of integers (list1 and list2) that are already in > sequential order, and I need to combine them into one list in sequential > order (newList). Any thoughts? 1) Algorithm. It ...

Hello, I have a simple program to create strings from the corresponding double/integer values. For any data type similar to int, I have a template set up in a file misc.h: ************************************************************************************* //misc.h #ifndef __MISC_H__ #define __MISC_H__ #include <string> //!Convert any numerical quantity (int, long, uint*_t, time_t, etc) to a string template <class X> string numtostr(X number); //I have explicitly overloaded it for double: //!Convert a double to a string string numtostr(double number); #endif I have th...

Hi, I'm fairly new to coding in C. Currently I'm writing a system call (I know this is not a kernel developers group, but this question, I think can be answered here too as it is not kernel development specific), which involves creating a linked list. Now I want to have a global pointer to the head of the list even after I exit the system call.So my question is how do I do this? and after its done how can I get a handle to that reference so that its possible to perform operations on the list in other system calls. Thank you very much in advance. -Sumedh. "rage" <sumedh...

Hello everyone. I have a problem with my program... and i kinda dunno what to do.. everything seems to work ok, but i'm getting corrupted double-linked list error =\. *** glibc detected *** corrupted double-linked list: 0x080aff40 *** Program received signal SIGABRT, Aborted. 0xaf7037b2 in _dl_sysinfo_int80 () from /lib/ld-linux.so.2 (gdb) bt #0 0xaf7037b2 in _dl_sysinfo_int80 () from /lib/ld-linux.so.2 #1 0xaf5b4f41 in raise () from /lib/tls/libc.so.6 #2 0xaf5b66e7 in abort () from /lib/tls/libc.so.6 #3 0xaf5e857e in __fsetlocking () from /lib/tls/libc.so.6 #4 0xaf5f2297 in mallop...

How do we reverse a singly linked list without using extra memory.Extra pointers can however be used saki wrote: > > How do we reverse a singly linked list without using extra > memory. Extra pointers can however be used /* ======================================================= */ /* believed necessary and sufficient for NULL terminations */ /* Reverse a singly linked list. Reentrant (pure) code */ nodeptr revlist(nodeptr root) { nodeptr curr, nxt; if (root) { /* non-empty list */ curr = root->next; root->next = NULL; /* terminate ne...

pointers to elements in a Linked-List?
I have a Linked-List and would like to create pointers to elements in this list. e.g I would like two pointers that point to each of their elements in the Linked-List. But there should always be exactly 5 nodes between these pointers. Does this make any sense or are there some more efficient way to access certain elements in a Linked-List? Paminu wrote On 10/12/05 15:26,: > I have a Linked-List and would like to create pointers to elements in this > list. > > e.g I would like two pointers that point to each of their elements in the > Linked-List. But there should alway...

deleting an element from the linked list
Hi.. really I need some help... I trying to delet an element from a linked list, where the head of this list is inside of an array of pointers... the big problem, is because when i am deleting the current element I verify that the element was really deleted, but if I access the head of the list and considering that for this case I have just one element the head of the list ISN'T empty... why is it happening???? here is some parts of my subroutine, perhaps someone can help me... Subroutine flagbadtop Implicit None Type listI Integer::ii0,ii1 Type(listI), Pointer :: nexti End Typ...