Создать связанный список очередей за линейное время - PullRequest
Новая
       4

Создать связанный список очередей за линейное время

0 голосов
/ 12 февраля 2019

Я придумал этот способ создания связанного списка в C: 

void queue(Node ** head, Node * object)
{
    Node * tmp = (Node *)malloc(sizeof(Node));
    *tmp = *object;
    Node *last = get_Last((*head));
    if (last) {
        last->next = tmp;
        tmp->next = NULL;
    }
    else {
        (*head) = tmp;
        tmp->next = NULL;
    }
}

Идея довольно проста, передать указатель на объект на queue(...), затем пройти по списку, чтобы найти последнийузел, а затем отредактируйте несколько указателей.Однако то, что мне не совсем нравится, это функция get_Last(...): 

Node * get_Last(Node * head)
{

    if (!head) {
        return NULL;
    }
    while (head->next) {
        head = head->next;
    }
    return head;
}

Эта функция означает, что если queue(...) когда-либо окажется в цикле, тогда алгоритм, который я придумал, имеет O (n²)временная сложность, которая слишком велика для чего-то такого простого, как создание связанного списка.Что можно сделать, чтобы снизить сложность до O (n)?Я думаю, queue(...) все еще нужен адрес последнего узла, но как мне получить его без цикла?

1 Ответ

0 голосов
/ 13 февраля 2019

Вы уверены, что элементы должны быть вставлены в конец списка?Вставка / удаление в начале связанного списка - бесплатно O(1).

Если вы действительно хотите получить эффективный список FIFO, лучший способ сделать это, безусловно, сохранить адрес хвоста.элемент.Он требует только постоянной памяти и позволяет O(1) вставлять в хвост.

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

...