Как правильно называется односвязный список, содержащий двойной указатель?

Недавно я увидел это:

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);

Он выглядит как односвязный список, но содержит указатель на следующий указатель предыдущего узла. У меня простой вопрос: как это называется? Без «настоящего имени» поиск информации об этой структуре данных оказывается пустым в StackOverflow и в Интернете в целом.

Обратите внимание, что это не двусвязный список, который выглядел бы так:

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

c c++ data-structures linked-list doubly-linked-list
person Blair Holloway    schedule 04.08.2012    source источник
comment
Может быть, я что-то упускаю здесь, не будучи в значительной степени C/C++ -er, но разве указатель узла на следующий указатель предыдущего узла не является в значительной степени указателем на указатель на этот узел? ...и какая польза?   -  person Matt Ball    schedule 04.08.2012
comment
@Matt Ball Использование состоит в том, чтобы разрешить удаление или вставку O (1) перед.   -  person Jim Balter    schedule 04.08.2012
comment
@Blair: можете ли вы объяснить третий пункт в вашем редактировании? Мне кажется, что операция вставки для этого измененного двусвязного списка все равно должна писать в три узла. Я не понимаю, чем отличается это свойство между таким узлом списка и более стандартным узлом двусвязного списка.   -  person Michael Burr    schedule 15.08.2012
comment
Кроме того, пункт два вообще не применяется ко многим реализациям двусвязных списков (например, к list.h в Linux) — нет особых случаев для вставки/удаления, потому что ни один из указателей узлов никогда не равен NULL.   -  person Michael Burr    schedule 15.08.2012
comment
@MichaelBurr - обдумав ваш вопрос, я теперь считаю, что дополнительные утверждения, которые я сделал в своем редактировании, неверны. Соответственно, я их удалил.   -  person Blair Holloway    schedule 16.08.2012

Ответы (4)


arrow_upward
6
arrow_downward

Он называется двусвязным списком, поскольку имеет два указателя. Вы можете получить предыдущий узел из макроса, такого как container_of(*node.pPrevNext, node, pNext), поэтому он также логически эквивалентен стандартному двусвязному списку.

Примечание. Интересный вопрос: считается ли список XOR односвязным или двусвязным? См. двухсвязный список XOR.

person stark    schedule 04.08.2012

arrow_upward
1
arrow_downward

Я не думаю, что для этого существует какое-либо стандартное название; это своего рода ограниченная версия двусвязного списка, потому что вы можете перемещаться по указателям в полном двусвязном списке, чтобы получить всю доступную здесь информацию.

person Ernest Friedman-Hill    schedule 04.08.2012

arrow_upward
1
arrow_downward

Это односвязный список, который позволяет удалить узел или вставить узел перед ним за время O(1). Для него нет имени, потому что нет причин его использовать... двусвязный список лучше.

person Jim Balter    schedule 04.08.2012

arrow_upward
0
arrow_downward

Это односвязный список, предназначенный для поведения двусвязного списка. Вы можете удалить элемент,

*pPrevNext = pСледующий;

Единственное, что мешает ему быть двусвязным списком, — это плохое понимание концепции со стороны автора.

person std''OrgnlDave    schedule 04.08.2012