Добавление и удаление элементов в линейном списке - C (СИ)

Формулировка задачи:

В линейном списке удалить и добавить по отдельности элементы: -первый -второй -последний -предпоследний

Решение задачи: «Добавление и удаление элементов в линейном списке»

Листинг программы

#include <stdio.h> 
#include <stdlib.h>
#include <malloc.h>
 
struct node {
        void* val;
        struct node* next;
        struct node* prev;
};
 
typedef struct {
        struct node* head, *tail;
} list_t;
 
void list_init(list_t* ls) { ls->head = ls->tail = NULL; }
void list_push_back(list_t* ls, void* val);
void list_pop_back(list_t* ls);
void list_pop_front(list_t* ls);
void list_clear(list_t* ls);
 
int main(void){
        int i;
        struct node* p;
        list_t ls;
        list_init(&ls);
        for(i = 1; i < 10; ++i)
                list_push_back(&ls, (void*)i);
 
        list_pop_front(&ls);
        list_pop_front(&ls);
        list_pop_back(&ls);
        list_pop_back(&ls);
 
        for(p = ls.head; p != NULL; p = p->next)
                printf("%d ", (int)p->val);
        putchar('\n');
 
        for(p = ls.tail; p != NULL; p = p->prev)
                printf("%d ", (int)p->val);
        list_clear(&ls);
    getchar();
    return 0;
}
 
//добавить в хвост списка
void list_push_back(list_t* ls, void* val){
        struct node* p = (struct node*)malloc(sizeof(struct node));
        if(p == NULL)
                return;
        p->prev = p->next = NULL;
        p->val  = val;
 
        if(ls->head == NULL)
                ls->head = ls->tail = p;
        else {
                p->prev = ls->tail;
                ls->tail->next = p;
                ls->tail = p;
        }
}
 
//удалить с хвоста списка
void list_pop_back(list_t* ls){
        struct node* t;
        if(ls->tail != NULL){
                t = ls->tail;
                ls->tail = ls->tail->prev;
                free(t);
                if(ls->tail != NULL)
                        ls->tail->next = NULL;
                else
                        ls->head = NULL;
        }
}
 
//удалить с головы списка
void list_pop_front(list_t* ls){
        struct node* t;
        if(ls->head != NULL){
                t = ls->head;
                ls->head = ls->head->next;
                free(t);
                if(ls->head != NULL)
                        ls->head->prev = NULL;
                else
                        ls->tail = NULL;
        }
}
 
//удалить всё
void list_clear(list_t* ls){
        while(ls->head != NULL)
                list_pop_front(ls);
}

Объяснение кода листинга программы

В данном коде реализован динамический линейный список, который позволяет добавлять и удалять элементы как с головы, так и с хвоста списка. Список представлен двумя указателями: head и tail, которые указывают на начало и конец списка соответственно. Каждый элемент списка состоит из указателя на предыдущий элемент (prev), указателя на следующий элемент (next) и значения (val). Функция list_init инициализирует список, устанавливая head и tail в NULL. Функция list_push_back добавляет новый элемент в конец списка. Она выделяет память под новый узел, инициализирует его поля и добавляет его в конец списка. Функция list_pop_back удаляет последний элемент из списка. Она получает ссылку на последний элемент списка, освобождает память под ним и удаляет ссылки на него в предыдущем и следующем элементах. Если после удаления последнего элемента список оказывается пустым, оба указателя (head и tail) устанавливаются в NULL. Функция list_pop_front удаляет первый элемент из списка. Она получает ссылку на первый элемент списка, освобождает память под ним и удаляет ссылки на него в следующем элементе и в самом списке (head). Если после удаления первого элемента список оказывается пустым, оба указателя (head и tail) устанавливаются в NULL. Функция list_clear полностью очищает список, последовательно удаляя все его элементы с помощью функции list_pop_front. В функции main создается экземпляр списка, инициализируется с помощью функции list_init. Затем в список добавляются 10 элементов с помощью функции list_push_back. После этого удаляются первые два элемента списка с помощью функций list_pop_front, затем удаляется последний элемент с помощью функции list_pop_back. В конце выводится содержимое списка с помощью цикла.