Связанные списки: вставка в конце с использованием последнего указателя

Question

Я изучаю связанные списки и хочу знать, правильна ли следующая программа (в основном функция InsertAtEnd), которую я сделал для вставки элементов в конец списка.

Основная идея заключается в том, что* HEAD указывает на первый элемент списка, а * LAST указывает на последний элемент.Это экономит время и вычисления при переходе к последнему элементу списка и последующем добавлении элементов.

#include<stdio.h>
#include<stdlib.h>

// Structure for the list element/node
struct node 
{
 int data; // Stores the data
 struct node *next; // Points to the next element in the list.
};

int InsertAtEnd(struct node **, struct node **, int); /*Declaration of the function which 
                                                    inserts elements at the end.*/

int main()
{
 struct node *HEAD=NULL; //Points to the first element in the list.
 struct node *LAST=NULL; //Points to the last element in the list.
 int i=1;

 for(i=1;i<11;i++)
   {
     InsertAtEnd(&HEAD,&LAST,i);
   }
 }

// Function to insert element at the end.
int InsertAtEnd(struct node **headref,struct node **lastref,int i)
 {
   struct node *newnode=malloc(sizeof(struct node)); /*Allocates memory for the newnode 
                                                     and store the address in pointer 
                                                     newnode*/
   newnode->data=i; // Assign value to the data variable of the newnode.
   newnode->next=NULL; // Assign NULL to the next pointer of the newnode.

   if(*headref==NULL) //Checks if the list is empty.
    {
      *headref=newnode; // Places the address of the new node in HEAD pointer.
      *lastref=newnode; // Places the address of the new node in LAST pointer.

       return 0; //Exit function
    }

/* If the list is not empty, then make the next pointer of the present last node point to the new node*/

   (*lastref)->next=newnode;

   *lastref=(*lastref)->next; // Increment LAST to point to the new last node.

    return 0;
}

Вопросы, которые я хочу специально задать:

a) Вышекод для добавления элементов в конце (т.е. функция InsertAtEnd) правильно?(Примечание: я проверил его на своей машине, и он работает, как и ожидалось. Но я все еще хочу подтвердить от вас, люди)

b) Эффективен ли код (функция InsertAtEnd)?

c)Повлияет ли эффективность кода (функция InsertAtEnd), если я попытаюсь составить более длинный список.

d) Существуют ли более эффективные и простые алгоритмы для вставки элементов в конце?Вы можете направить меня к ним?

Answer 1

а) Кажется правильным

б) Это так. Вы можете сделать функцию возврата недействительной, потому что вам не нужно это возвращаемое значение int

в) Нет. Другими словами, время выполнения постоянно.

г) Мальлок требует времени. Вы можете использовать технику буферизации, чтобы заранее распределить порции по узлам, а затем взять следующий узел из буфера. Когда буфер становится пустым, выделите еще один фрагмент. Размеры чанка могут быть сконфигурированы или даже (сложны) вычислены с использованием статистических алгоритмов.

Более того, вы не проверяете NULL-возвращение malloc, но оно может завершиться с ошибкой.

Answer 2

а) Да, это должно работать (при условии, что ваш список никогда не будет поврежден и имеет headref! = NULL, но lastref == NULL).

Какой смысл возвращаемого значения, если оно всегда равно 0?

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

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

в) Нет. Это O (1). Как видите, циклы или что-либо еще не задействованы, вы делаете те же самые шаги независимо от того, есть ли в списке 5 или 5000 элементов.

d) Вы можете избежать проверки того, что список пуст, используя сторож, то есть фиктивный узел вместо заголовка. Вы просто размещаете узел где-то в памяти и устанавливаете lastref на него. Теперь вам не нужно обрабатывать наличие пустого списка в качестве особого случая.

Answer 3

а) Результат malloc не проверяется.Он может вернуть NULL в условиях нехватки памяти, вызывая сбой.Думаю, остальная часть алгоритма верна.

B + C + D) Это очень эффективно;O (1) означает, что время, необходимое для вставки элемента LAST, является постоянным.На самом деле я не могу придумать более простой и эффективный алгоритм.

Answer 4

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

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

Answer 5

Извините, это не отвечает на вопрос, но я подумал, что вы найдете его полезным. Я предлагаю небольшое изменение подхода:

int InsertAtEnd(struct node ***, int); /*Declaration of the function which 
                                         inserts elements at the end.*/

struct node *HEAD=NULL; //Points to the first element in the list.
struct node **LAST=&HEAD; //Points to the last (NULL) *pointer* in the list.

// Function to insert element at the end.
int InsertAtEnd(struct node ***lastrefref,int i) // no need to pass HEAD
{
    struct node *newnode=malloc(sizeof(struct node)); /*Allocates memory for the newnode 
                                                        and store the address in pointer 
                                                        newnode*/

    // And here we should be checking for errors...

    newnode->data=i; // Assign value to the data variable of the newnode.
    newnode->next=NULL; // Assign NULL to the next pointer of the newnode.

    **lastrefref = newnode; // Put new element at end of list
    *lastrefref=&(newnode->next); // Update last pointer location
}

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

struct <anything> ***

начинает глупеть, ум.

Answer 6

а) Я думаю, что ваш код правильный в том смысле, что он делает то, что вы ожидаете.Возможно, вы захотите проверить возвращаемое значение malloc.

b) Ваш код, на мой взгляд, также эффективен.Единственное, о чем я мог подумать, это строка *lastref=(*lastref)->next;, которую я бы заменил на *lastref=newnode;.Но я думаю, что это будет оптимизировано почти каждым компилятором автоматически.

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

d) Я не думаю, что insertAtEnd может быть реализован серьезно быстрее.Вы можете попытаться непрерывно хранить элементы в памяти и проверить, не вернулись ли malloc.

. Единственное, что я лично делаю при реализации таких вещей:собственная структура для всей структуры данных связанных списков (содержащая size и head - и lastElement -точки)

Я бы не стал ограничивать список для храненияцелые числа, но произвольные элементы (например, void* с)