Связные списки

Одномерный массив с возможностью его свободного изменения называется списком.

-- М. Сибуя, Т. Ямамото - Алгоритмы обработки данных

Связный список (linked list) это одна из простейших структур данных, состоящая из связных между собой объектов, называемых узлами (node). Каждый узел состоит из двух полей:

• данных; и
• указателя на следующий узел.

struct node
{
    int data;
    struct node *next;
};

Графически узел будем представлять следующим образом:

Указатель next содержит или адрес следующего узла (рисунок A) или специальное значение NULL (нулевой указатель, рисунок B), которое используется как маркер конца списка.

Рассмотрим пример создания простейшего списка из трех элементов. Для начала создадим три узла и у каждого из них указатель next установим в значение NULL:

struct node a, b, c;
a.data = 1;
b.data = 2;
c.data = 3;
a.next = b.next = c.next = NULL;

На рисунке показан результат создания трех независимых узлов:

Теперь свяжем узлы между собой:

a.next = &b;
b.next = &c;

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

Связный список, содержащий только один указатель на следующий элемент, называется односвязным. Связный список, содержащий два поля указателя – на следующий элемент и на предыдущий, называется двусвязным.

Головой списка (head) называется его первый элемент, а последний элемент - хвостом (tail). Иногда для головы создают отдельный узел, не содержащий данных.

Реализация односвязного списка

Определим некоторые операции, которые можно выполнять над списками:

• добавление нового элемента в начало списка;
• добавление нового элемента в конец списка;
• удаление первого элемента в списке;
• удаление последнего элемента в списке;
• поиск элемента в списке;
• определение длины списка;
• объединение двух списков;
• и т.д.

Изменим структуру для отдельных элементов списка, сделав поле data указателем на void. Кроме того, для удобства работы добавим два пользовательских типа node_t и node_ptr_t.

typedef struct node  node_t;
typedef struct node* node_ptr_t;

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

В нашей реализации мы будем использовать пустой узел (т.е. узел без полезной нагрузки) в качестве головы списка:

void list_init(node_ptr_t *head)
{
    *head = (node_ptr_t)malloc(sizeof(node_t));
    if (*head == NULL)
    {
        fprintf(stderr, "Can't allocate memory\n");
        exit(1);
    }
    (*head)->next = NULL;
    (*head)->data = NULL;
}

Добавление элемента в начало списка:

void list_add(node_ptr_t head, void* data)
{
    node_ptr_t new_node = (node_ptr_t)malloc(sizeof(node_t));
    if (new_node == NULL)
    {
        fprintf(stderr, "Can't allocate memory\n");
        exit(1);
    }

    new_node->data = data;
    new_node->next = head->next;
    head->next = new_node;
}

Добавление элемента в конец списка:

void list_add_tail(node_ptr_t head, void* data)
{
    node_ptr_t new_node = (node_ptr_t)malloc(sizeof(node_t));
    if (new_node == NULL)
    {
        fprintf(stderr, "Can't allocate memory\n");
        exit(1);
    }
    new_node->data = data;
    new_node->next = NULL;

    node_ptr_t current = head->next;
    if (current == NULL) {
        head->next = new_node;
    } else {
        while (current->next != NULL)
        {
            current = current->next;
        }
        current->next = new_node;
    }
}

Удаление элемента с головы списка:

node_ptr_t list_del(node_ptr_t head)
{
    node_ptr_t temp = NULL;
    if (head->next != NULL)
    {
        temp = head->next;
        head->next = head->next->next;
    }
    return temp;
}

Макрос для прохода по всем элементам списка:

#define list_for_each(pos, head) \
    for (pos = (head)->next; pos != NULL; pos = pos->next)

Пример использования макроса для вывода всех элементов списка и вычисления его длины:

void list_print(node_ptr_t head)
{
    node_ptr_t current;
    list_for_each(current, head)
        printf("%d\n", *((int*)current->data));
}

unsigned int list_length(node_ptr_t head)
{
    node_ptr_t current;
    unsigned int length = 0;

    list_for_each(current, head)
        length++;

    return length;
}

Задания

Задача 1: Напишите функцию list_reverse(L), которая разворачивает список L.

Задача 2: Напишите функцию list_count(L, e), которая подсчитывает число вхождений элемента e в список L.

Задача 3: Напишите функцию list_get(L, index), которая возвращает элемент по индексу index.

Задача 4: Напишите функцию list_destroy(L), которая освобождает память из под списка L (обратите внимание, что память нужно освобождать из под каждого элемента в отдельности).

Задача 5: Напишите функцию list_insert(L, index, e), которая вставляет элемент e в список L по индексу index.

Задача 6: Напишите функцию list_merge(L1, L2), которая объединяет список L1 cо списком L2.