Фиктивные узлы в реализации связанного списка - PullRequest
Новая
       69

Фиктивные узлы в реализации связанного списка

2 голосов
/ 06 апреля 2019

Я пытаюсь реализовать Единый связанный список.

Требования: 1. Вставьте в порядке данных 2. Снять с головы

Нужно ли иметь фиктивный узел в моей реализации? Также должен ли фиктивный узел располагаться в начале или конце списка?

Я гуглил ответ и обнаружил, что фиктивные узлы полезны при удалении последнего узла в списке. Но я не мог понять как. Может кто-нибудь объяснить?

Ответы [ 2 ]

1 голос
/ 06 апреля 2019

Связанные списки выглядят так: 

struct list_node {
    struct list_node *next;
    void *data;
};

struct list_node *head;

Вам никогда не нужны фиктивные узлы в связанных списках в C.

Пустые узлы предназначены для реализации операции «удалить текущий» в односвязных списках на языках, которые не предоставляют указатели на указатели. Вот и все.

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

Однако в Си лучше обслуживать, сохраняя указатель на следующий узел. В начале итерации это указатель на head; после запуска это указатель list_node::next, где list_node - это ранее просмотренный узел.

1 голос
/ 06 апреля 2019

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

Учитывая ваши требования, вы должны определить структуру списка, которая содержит указатель на начало списка и указатель на хвостиз списка.Это приведет к тому, что обе операции, вставка в конце и удаление из головки, будут работать n постоянное время.

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

Вотпростой пример: 

struct list_elem_s {
    struct list_elem_s *next;
    int data;
    //... other payload fields
};

struct list_s {
    struct list_elem_s *head;
    struct list_elem_s *tail;
};

// initialize a list as empty
void list_initialize(struct list_s *list) {
    list->head = list->tail = NULL;
}

// free all elements from a list
void list_delete(struct list_s *list,
                 void (*free_node)(struct list_elem_s *node)) {
    struct list_elem_s *node;
    while ((node = list->head) != NULL) {
        list->head = node->next;
        node->next = NULL;
        if (free_node)
            free_node(node);
    }
    list->tail = NULL;
}

// add a node at the tail
void list_push(struct list_s *list, struct list_elem *node) {
    node->next = NULL;
    if (list->tail) {
        list->tail->next = node;
    } else {
        list->head = node;
    }
    list->tail = node;
}

// remove a node at the head
struct list_elem *list_pop_head(struct list_s *list) {
    struct list_elem_s *node;
    if ((node = list->head) != NULL) {
        if ((list->head = node->next) == NULL)
            list->tail = NULL;
    }
    return node;
}
...