Что такое метод указателя на указатель для более простого обхода связанных списков?

Ответ 1

Я думаю, вы имеете в виду двойной указатель, как в "указателе на указатель", который очень эффективен для вставки в конце одиночного списка или древовидной структуры. Идея состоит в том, что вам не нужен специальный случай или "трейлинг-указатель", чтобы следовать указателю обхода, как только вы найдете конец (указатель NULL). Поскольку вы можете просто разыменовать указатель на указатель (он указывает на последний node следующий указатель!) Для вставки. Что-то вроде этого:

T **p = &list_start;
while (*p) {
   p = &(*p)->next;
}
*p = new T;

вместо следующего:

T *p = list_start;
if (p == NULL) {
    list_start = new T;
} else {
    while (p->next) {
        p = p->next;
    }
    p->next = new T;
}

ПРИМЕЧАНИЕ.. Это также полезно для создания эффективного кода удаления для отдельного списка. В любой момент, когда *p = (*p)->next удалит node, вы "смотрите" (конечно, вам все равно нужно очистить хранилище node).

Ответ 2

Под "двойным указателем", я думаю, вы имеете в виду "указатель на указатель". Это полезно, поскольку позволяет исключить специальные случаи для указателей на голову или хвост. Например, учитывая этот список:

struct node {
    struct node *next;
    int key;
    /* ... */
};

struct node *head;

Если вы хотите найти node и удалить его из списка, метод с одним указателем будет выглядеть так:

if (head->key == search_key)
{
    removed = head;
    head = head->next;
}
else
{
    struct node *cur;

    for (cur = head; cur->next != NULL; cur = cur->next)
    {
        if (cur->next->key == search_key)
        {
            removed = cur->next;
            cur->next = cur->next->next;
            break;
         }
    }
}

В то время как метод указателя на указатель намного проще:

struct node **cur;

for (cur = &head; *cur != NULL; cur = &(*cur)->next)
{
    if ((*cur)->key == search_key)
    {
        removed = *cur;
        *cur = (*cur)->next;
        break;
    }
}

Ответ 3

Я думаю, вы имеете в виду дважды связанные списки, где node выглядит примерно так:

struct Node {
(..) data // The data being stored in the node, it can be of any data type
Node *next; // A pointer to the next node; null for last node
Node *prev; // A pointer to the previous node; null for first node
}

Ответ 4

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

Вот как вы обычно вставляете в список:

typedef struct _Node {
    void * data;
    Node * next;
} Node;

Node * insert( Node * root, void * data ) {
    Node * list = root;
    Node * listSave = root;

    while ( list != null ) {
        if ( data < list->data ) {
            break;
        }

        listSave = list;
        list = list->next;
    }

    Node * newNode = (Node*)malloc( sizeof(Node) );
    newNode->data = data;
    /* Insert at the beginning of the list */
    if ( listSave == list ) {
        newNode->next = list;
        list = newNode;
    }
    /* Insert at the end of the list */
    else if ( list == null ) {
        listSave->next = newNode;
        newNode->next = null;
        list = root;
    }
    /* Insert at the middle of the list */
    else {
        listSave->next = newNode;
        newNode->next = list;
        list = root;
    }

    return list;
}

Обратите внимание на всю дополнительную проверку, которую вы должны выполнить, в зависимости от того, происходит ли вставка в начале, конце или середине списка. Сравните это с методом двойной стрелки:

void insert( Node ** proot, void * data ) {
    Node ** plist = proot;

    while ( *plist != null ) {
        if ( data < (*plist)->data ) {
            break;
        }

        plist = &(*plist)->next;
    }

    Node * newNode = (Node *)malloc( sizeof(Node) );
    newNode->data = data;
    newNode->next = *plist;
    *plist = newNode;
}

Как показал Эван Теран, это хорошо работает для одиночно связанных списков, но когда он вдвойне связан, вы в конечном итоге преодолеваете столько же, сколько не манипуляций, как случай с одним указателем. Другая обратная сторона заключается в том, что вы проходите две разметки указателя для каждого обхода. Хотя код выглядит более чистым, он, вероятно, работает не так быстро, как один код указателя.

Ответ 5

Вероятно, вы имеете в виду список с двойной связью, причем один из указателей идет вперед, а другой - назад. Это позволяет вам перейти к следующему и предыдущему узлам для данного node, не запомнив последний один или два найденных узла (как в односвязном списке).

Но одна вещь, которую я обнаружил, которая сделала код еще более элегантным, всегда состояла из двух фиктивных элементов в списке всегда, первого и последнего. Это избавляет от краев случаев для вставки и удаления, так как вы всегда действуете на node в середине списка.

Например, создается пустой список:

first = new node
last = new node
first.next = last
first.prev = null
last.next = null
last.prev = first
// null <- first <-> last -> null

Очевидно, что перемещение списка слегка изменено (только для версии с прямой версией):

curr = first.next
while curr <> last:
    do something with curr
    curr = curr.next

Вставки намного проще, поскольку вам не нужно беспокоиться о том, вставляете ли вы начало или конец списка. Вставить перед текущей точкой:

if curr = first:
    raise error
add = new node
add.next = curr
add.prev = curr.prev
curr.prev.next = add
curr.prev = add

Удаления также проще, избегая случаев краев:

if curr = first or curr = last:
    raise error
curr.prev.next = curr.next
curr.next.prev = curr.prev
delete curr

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

Предостережение 1: Если вы выполняете встроенное программирование, где пространство по-прежнему может иметь значение, это может оказаться не жизнеспособным решением (хотя в наши дни некоторые встроенные среды также довольно хмурые).

Caveat 2: Если вы используете язык, который уже предоставляет возможности связанного списка, вероятно, лучше сделать это, а не сворачивать свои собственные (кроме особых обстоятельств).