Каков метод от указателя к указателю для более простого обхода связанных списков? [дубликат]

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

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

struct node *head;

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

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

Я согласен с комментариями об использовании контейнеров 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;
}

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

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

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
}

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

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

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

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: Если вы занимаетесь встраиваемым программированием, где пространство все еще может иметь значение, это может оказаться нежизнеспособным решением (хотя некоторые встраиваемые среды в наши дни тоже довольно громоздки).

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