Что такое односвязный список?

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

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

Последний узел всегда указывает на ноль, что определяет конец списка.

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

Как определить и инициализировать связанный список в c?

  • Мы должны создать структуру для предпочтительного типа, содержащую как минимум 2 члена, значение (данные в качестве примера) и указатель (следующий в качестве примера, который будет содержать ссылку на следующий узел).
typedef struct Node {
    int data;
    struct Node *next;
}node_t;
  • Рекомендуется определить головной элемент, который будет содержать указатель на первый узел нашего списка.
void main(void) //creating the head of list
{
    node_t *head = NULL;
    head = malloc(sizeof(node_t *));
    head->data = 12;
    head->next = NULL;
}
  • Чтобы составить список, нам нужны узлы, для этого эффективно создать функцию из основного для этой миссии.
  • Есть много способов добавить узлы, либо в начало, либо в конец.

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

  1. Создайте новый элемент и установите его значение
  2. Свяжите новый элемент, чтобы он указывал на начало списка
  3. Установите голову списка в качестве нашего нового элемента

void push(node_t **head, int value)
{
    node_t * item;
    //reserving a block of memory for that node(item)
    item = malloc(sizeof(node_t)); 
    //setting it's value 
    item->data = value;
    item->next = *head;
    *head = item;
}

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

void main(void) //creating the head of list
{
    node_t *head = NULL;
    head = malloc(sizeof(node_t *));
    head->data = 12;
    head->next = NULL;
    push(&head,123);
}

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

Но сначала, как нам пройтись по списку?

Рекомендуется использовать не голову, а другой указатель, называйте его как хотите, допустимcurrent.

Зачем нам нужен еще один указатель?

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

Представьте, что вы просматриваете список с помощью головы, в какой-то момент вы дойдете до конца. Ваш head->next будет NULL, что означает поздравление, вы дошли до конца, но потеряли список и не можете вернуться назад (только в односвязном списке).

Почему бы не выполнять итерацию как массив?

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

Теперь мы понимаем эти вопросы, наш указатель current будет отслеживать узел, в котором мы находимся, мы можем получить доступ к его значению и делать с ним все и что угодно. После этого нам нужно продвинуться по списку, чтобы сделать следующий шаг, поэтому он должен перейти к следующему узлу, current = current->next;.

int sum_node_vals(node_t * head)
{
  node_t * current = head;
  int sum = 0;
  while (current != NULL)
  {
          sum += current->val;
          current = current->next;
  }
  return (sum);
}

Во-вторых, как добавить узел в конец списка?:

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

void push(node_t * head, int val)
{
    node_t * current = head;
    //iterating the list till we reach the end
    while (current->next != NULL)
    {
        current = current->next;
    }
    //allocating memory for the next node
    current->next = (node_t *) malloc(sizeof(node_t));
    //setting up the value of the new node
    current->next->data = val;
    //set up the pointer to next node to null because
    //it is the end of the list 
    current->next->next = NULL;
}

Теперь перейдем к изучению того, как мы можем удалить узлы из списка.

Во-первых, как удалить первый узел из списка (выталкивание элементов из списка)?

Чтобы построить эту функцию, нам нужно выполнить следующие шаги:

  1. Возьмите следующий узел, на который указывает голова.
  2. Освободите головной узел и его данные.
  3. Голова должна быть следующим элементом, который мы сохранили на стороне.
void pop(node_t ** head)
{
    node_t * next_node = NULL;
    //checking if the head is null then there is nothing to delete
    if (*head == NULL)
    {
        exit(-1);
    }
     //1.
    next_node = (*head)->next;
    //2. if the data is type string it must be liberated as well
    free(*head);
    //3. 
    *head = next_node;
}

Во-вторых, как удалить узел из конца списка?

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

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

int delete(node_t * head)
{
    int trash= 0;
    node_t * current = head;
    //check if only one item is on the list if yes delete it 
    //and return the deleted value
    if (head->next == NULL)
    {
        trash= head->val;
        free(head);
        return (trash);
    }

    //get to the second to last node in the list by iterating the list
    //onece we have it break from the loop.

    //it may be confusing but imagine we have a list that has 3 items:

    //{"itm1"|next}->{"itm2"|next}->{"itm3"|next}->NULL

    //current->next->next will be pointing to 3th node (itm3) the while
    //loop condition is true execute the code inside it till the condition is 
    //incorrect meaning that we reached the end.

    //as an example when we are in "itm2" that means:
    //current("itm2")->next("itm3")->next(NULL) now break from the loop,
    //with current is ("itm2").
    while (current->next->next != NULL)
    {
        current = current->next;
    }

    //now current points to the second to last("itm2") item
    //of the list, so let's remove current->next("itm3").
    trash = current->next->val;
    free(current->next);
    current->next = NULL;
    return trash;

}

В-третьих, как удалить узел по определенному (индексу или значению)?

Это означает одно, нам нужно найти узел, соответствующий критериям, и удалить его. Вы правильно поняли! Для этого нам нужна петля.

Вот чему нам нужно следовать при запекании нашей функции:

  1. Итерация к узлу перед узлом, который мы хотим удалить
  2. Сохраните узел, который мы хотим удалить, во временном указателе.
  3. Установите следующий указатель предыдущего узла, чтобы он указывал на узел после узла, который мы хотим удалить.
  4. Удалить узел с помощью временного указателя

В следующем примере мы удалим элемент, который имеет то же значение, что и введенный:

int delete_using_value(node_t ** head, int val) {
    node_t * tempr = NULL;
    node_t * curent = *head;
    int trash = 0;
//Now you have a better understanding of the following conditions
//there is no need to explain
    if (val == NULL)
    {
        return (-1);
    }

    if (curent->next == NULL)
        return(-1);
//the following loop check for matches of val in the list
    while (curent->next->data != val)
    {
        if (curent->next == NULL)
            return -1;
        curent = curent->next;
    }

    tempr = curent->next;
    trash = tempr->data;
    curent->next = tempr->next;
    free(tempr);
    
    return(trash);
}

Упражнение :

Создайте свою версию функции void delete_using_index(node_t ** head, int index), которая удаляет узел по его индексу.

Примечание. вам нужно создать свою структуру, void add_item(node_t* head,intvalue) для заполнения списка и main для проверки ваших функций.

Заключение

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

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

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

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