What is the proper name of a singly linked list containing a double pointer?

Question

Recently, I saw this:

struct node {
    node*  pNext;
    node** pPrevNext;
};

void insert_before(node** pNext, node* toInsert) {
    toInsert->pNext = *pNext;
    toInsert->pPrevNext = pNext;
    if (*pNext) (*pNext)->pPrevNext = &toInsert->pNext;
    *pNext = toInsert;
};

// node *a, *b;
// insert_before(a->pPrevNext, b);

It looks like a singly linked list, but containing a pointer to the previous node's next pointer. My question is simply: what is this called? Without its "true name", searches for information about this data structure turn up empty on StackOverflow and the internet at large.

Note that it's not a doubly linked list, which would look like this:

struct node {
    node* pNext;
    node* pPrev;
};

Maybe I'm missing something here, not being much of a C/C++ -er, but isn't a node's pointer to the previous node's next pointer pretty much a pointer to a pointer to that node? ...and what's the use? — Matt Ball, Aug 04 '12 at 01:48
@Matt Ball The use is to allow O(1) deletion or insert-before. — Jim Balter, Aug 04 '12 at 04:42
@Blair: can you explain the third point in your edit? It seems to me that the insert operation for this modified doubly linked list still needs to write to three nodes. I don't understand how this property differs between this kind of list node and a more standard doubly linked list node. — Michael Burr, Aug 15 '12 at 14:03
Also, point two doesn't apply at all to many doubly linked list implementations (such as the one in Linux's `list.h`) - there are no special cases for insert/remove because none of the node pointers is ever NULL. — Michael Burr, Aug 15 '12 at 14:37
@MichaelBurr -- after contemplating your question, I now believe the additional statements I made in my edit to be incorrect. As such, I've removed them. — Blair Holloway, Aug 16 '12 at 19:06

stark · Accepted Answer · 2021-06-11T14:08:39.270

6

It's called a doubly linked list because it has two pointers. You can get the previous node from a macro like container_of(*node.pPrevNext, node, pNext) so it's logically equivalent to a standard doubly-linked list also.

Note: The interesting question is whether an XOR list is considered singly-linked or doubly-linked? See XOR Doubly Linked List

edited Jun 11 '21 at 14:08

answered Aug 04 '12 at 02:32

stark

12,615
3
33
50

score 1 · Answer 2 · answered Aug 04 '12 at 01:47

1

I don't think there is any standard name for this; it's a sort of restricted version of the doubly-linked list because you can walk pointers in the full doubly-linked list to get all the information that's available here.

answered Aug 04 '12 at 01:47

Ernest Friedman-Hill

80,601
10
150
186

score 1 · Answer 3 · answered Aug 04 '12 at 04:41

1

It's a singly-linked list that allows a node to be deleted, or to have a node inserted ahead of it, in O(1) time. There's no name for it because there's no reason to use it ... a doubly-linked list is better.

answered Aug 04 '12 at 04:41

Jim Balter

16,163
3
43
66

score 0 · Answer 4 · answered Aug 04 '12 at 02:35

0

It's a singly linked list designed to behave like a doubly linked one. You can delete an element by

*pPrevNext = pNext;

The only thing keeping it from being a doubly linked list is poor understanding of the concept on the part of the writer.

answered Aug 04 '12 at 02:35

std''OrgnlDave

3,912
1
25
34

What is the proper name of a singly linked list containing a double pointer?

4 Answers4