В качестве введения. Для чего эта статья?

Эта статья призвана резюмировать приобретенные знание полученные в процессе обучения программированию. Так вышло, что я попал на обучение на программиста, скажем так, "по-взрослому". Поэтому первым языком стал Си. Основы языка дались легко благодаря опыту работы с языками программирования PHP, JavaScript, C# и Python. Но позднее процесс обучения вышел на новый уровень, связанный со структурами данных. И начались мои страдания.

Оказалось, что моего опыта "кодинга" всякой мелочи недостаточно, опытные пользователи бы сказали, что в интернете существует множество статей по реализации тех же списков, но они мне не подходили. В конечном итоге до всего пришлось доходить самостоятельно, лишь используя имеющиеся статьи. Теперь в этой серии статей я попытаюсь зафиксировать свой опыт. Я всего лишь еще учусь, поэтому в решениях возможны некорректность в реализации, поэтому советам по улучшениям буду рад. А быть может мои статьи помогут еще кому-нибудь.

В чем особенность этих статей? Как говорят еще в научном сообществе -- актуальность, новизна. Каждое решение будет ориентированно и оптимизировано на работу с большим объемом данных. И по крайней мере я попытаюсь так сделать. Все задачи будут решены с использованием языка Си. Статей будет несколько, каждая будет посвящена одному конкретному решению и его реализации. В каждой статье оставлю ссылки на другие, по другим решениям.

Условия реализации следующие. Все программы будут реализовываться для работы в ОС Ubuntu. Возможен их запуск в Unix-подобных системах. Другие специфические особенности будут мной указаны непосредственно в самой статье по конкретному решению.

Ну а теперь к делу. Реализация простого варианта списка:

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

В самом простом, элементарном варианте, наш список состоит из двух вещей: Первое - общая структура списка, и второе - структура элемента списка. Попробуем реализовать эту радость.

Создадим заголовочный файл: database.h:

#include <stdio.h> // стандартная библиотека Си
#include <string.h> // для работы со строками
#include <stdlib.h> // для работы с памятью

// структура элемента списка
typedef struct list_item {
    void *data; // по этому указателю мы храним какие-то данные
    struct list_item *next; // это у нас ссылка на следующий указатель
    struct list_item *prev; // это у нас ссылка на предыдущий указатель
} list_item;

// Общая структура списка
typedef struct list {
    int count; // информация о размере списка
    list_item *head; // это ссылка на головной элемент
    list_item *tail; // это у нас ссылка на последний элемент (хвост списка)
} list;

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

Теперь с этим списком нам нужно произвести кое-какие операции. Для начала его нужно создать, как сущность, сам список, а затем добавить в него некоторые элементы, какие-то в начало, а какие-то в конец. С этими элементами мы затем будем работать, попытаемся найти по ключу, по значению, удалим какой-нибудь на выбор. Естественно мы захотим вывести весь список на экран и посмотреть, а что там вообще есть...

Попробуем реализовать все эти функции. В том же самом заголовочном файле "database.h" ниже под структурами обозначим прототипы функций.

list * db_create(); // создает список. возвращает список.

Перейдем теперь в файл "main.c" - это наш главный файл программы, который мы будем компилировать. Оформляем заготовок программы.

#include "database.h" // не забудем подключить наш заголовочный файл

int main(int argc, const char** argv) {
		// code
}

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

list * db_create() {
  	// Создадим указатель на переменную структуры списка и выделим немного памяти для нее
    list *lst = (list*)malloc(sizeof(list));
    
    // задаем первоначальные значения
    lst->count = 0; // наш список пуст
    lst->head = NULL; // первого элемента у нас нет
    lst->tail = NULL; // и последнего тоже
    
    return lst;
}

Возвращаемся в функцию main, вызываем наш список.

int main(int argc, const char** argv) {
		list *database = create(); // список мы создали
}

Теперь мы немного с этим списком поработаем. А чтобы было с чем работать мы туда, для начала, попробуем добавить первые данные. Добавлять мы будем следующим образом, мы укажем некий индекс, который будет сигнализировать куда добавлять элемент в начало или конец, ну и сами данные в виде строки. Ну и также в нашу функцию мы будем передавать указатель на список, чтобы она понимала, куда ей это счастье наше добавлять.
В нашем заголовочном файле "database.h" ниже пишем новый прототип:

void db_insert(list *lst, int index, char *data);

В файле "main.c":

void db_insert(list *lst, int index, char *data) {
		// создадим указатель переменной элемента списка, 
		// и присвоим ему значение указателя на первый элемент списка
  	list_item *base = lst->head;
  
  	// создадим указатель переменной на новый элемент и выделим под него память
		list_item *new_item = (list_item*)malloc(sizeof(list_item));
  
  	// выделим память внутри самого элемента структуры куда принимаем данные,
  	// и получим указатель на него,
  	// strlen() нужен, чтобы выделенная память была равна длинне полученной строки.
  	new_item->data = malloc(sizeof(char) * strlen(data)); 
  	strcpy(new_item->data, data); // копируем туда данные
  	
  	// Пришла пора решить куда мы определим элемент,
  	// т.к. у нас еще нет элементов, lst->head вернет нам NULL.
  	// Следовательно нужно условие, при создании первого элемента списка.
  	if (base == NULL) {
      	// Этот элемент единственный, а значит его указатели будут NULL.
      	new_item->next = NULL;
        new_item->previous = NULL;
				
      	// При этом, он сам будет первым и последним в списке.
        lst->first = new_item;
        lst->last = new_item;
        lst->count++; // Увеличем кол-во на единицу
        return;
    }
  
  	// Если индекс, который пришел будет меньше нуля, то будем вставлять в конец
  	if (index < 0) {
    		// голова теперь будет ссылаться на новый элм. впереди себя
      	base->prev = new_item; 
        new_item->previous = NULL; 
        new_item->next = base; // а ссылка на след. элм. у нового будет на голову

        lst->head = new_item; // назначаем новый элемент головой
    } else { // тут все в обратном порядке
    		base = lst->tail; // перейдем в хвост списка
      	
      	// пусть он теперь ссылаеться на новый элемент
      	base->next = new_item;
      	new_item->next = NULL; // Новый не будет иметь ссылки на следующий
      	new_prev->prev = base; // А предыдущий у него будет хвост списка
      
      	lst->tail = new_item; // Назначаем новый элемент хвостом списка
    }
  lst->count++; // увеличим размер на единицу
}

На этом функция вставки готова, теперь вставим что-нибудь в наш список. В функции main пишем.

int main(int argc, const char** argv) {
		list *database = create(); // список мы создали
  	
  	insert(database, 0, "One");
  	insert(database, 1, "Two");
  	insert(database, -1, "Three");
}

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

char * db_read(list *lst, int index) {
  	list_item *base;	
  	int middle = lst->count / 2; // Вычисляем середину списка
  
    if (index > middle) { // если индекс больше середины
    		base = lst->tail;
      	for (int i = lst->count; i > index; i--)
        		base = base->prev;
    } else { // если индекс меньше середины
    		base = lst->head;
      	for (int i = 0; i < index; i++)
        		base = base->next;
    }
    
		// Если элемента нет
    if (base == NULL) {
        printf("\033[3;31mError! The list item was not found...\n\033[0m");
        return NULL;
    }
  	
    char *value = malloc(sizeof(char) * strlen(base->data)); // Выделяем память под строку
    strcpy(value, base->data); // копируем данные

    return value; // возвращаем полученное значение
}

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

int db_search(list *lst, char *data) {
    int i = 0; // организуем счетчик
    list_item *base = lst->first; // перейдем к первому элементу
  	// воспользуемся функцией strcmp, чтобы сравнить перебираемые строки
    while (strcmp(base->data, data) != 0) {
        // пока строки не совпадут с тем что бы ищем, будем перебирать элементы
      	base = base->next; 
        i++;
    }
    return i; // получив совпадение просто вернем полученный индекс
}

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

list_item * get_element(list *lst, int index) {
  	list_item *base;	
  	int middle = lst->count / 2; // Вычисляем середину списка
  
    if (index > middle) { // если индекс больше середины
    		base = lst->tail;
      	for (int i = lst->count; i > index; i--)
        		base = base->prev;
    } else { // если индекс меньше середины
    		base = lst->head;
      	for (int i = 0; i < index; i++)
        		base = base->next;
    }
    
		// Если элемента нет
    if (base == NULL) {
        printf("\033[3;31mError! The list item was not found...\n\033[0m");
        return NULL;
    }
  	return base; // возвращаем элемент
}

Перепишем нашу функцию read:

char * db_read(list *lst, int index) {
  	list_item *base = get_element(lst, index);
  	if (base == NULL)
      	return NULL;
    
  	char *value = malloc(sizeof(char) * strlen(base->data)); // Выделяем память под строку
    strcpy(value, base->data); // копируем данные

    return value; // возвращаем полученное значение
}

То же самое с функцией delete:

void db_delete(list *lst, int index) {
    list_item *base = get_element(lst, index);
    list_item *prev, *next;
  
  	if (base == NULL)
      	return;
    
    prev = base->previous; // получение предыдущего элемента
    next = base->next; // мы получаем следующий элемент
  	
  	// переопределение указателя для предыдущего элемента на следующий
    if (prev != NULL)
        prev->next = base->next;
    
  	// И тоже самое для предыдущего элемента
    if (next != NULL)
        next->previous = base->previous; 

    free(base); // Освобождаем память 
    lst->count--; // уменьшаем длинну списка на единицу
}

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

int main(int argc, const char** argv) {
		list *database = create(); // список мы создали
  	
  	insert(database, 0, "One"); // добавим несколько элементов
  	insert(database, 1, "Two");
  	insert(database, -1, "Three");
  
  	char *value = read(database, 1); // Получим One
  	printf("Value %s", value);
  	
  	int index = search(database, "One"); // получим 1
  	printf("Index: %d", index);
  
  	db_delete(database, 1); // удалит элемент One
  
  	// Пришла пора посмотреть, что там в нашем списке
  	db_print(database);
}

Нам теперь нужна функция, которая поможет нам вывести содержимое списка на экран. Делается это следующим образом:

void db_print(list *lst) {
    list_item *base = lst->first; // переходим к началу списка
    puts("\033[43m***Printing a list***\033[0m");
     
    if (lst->count == 0) { // если список пустой, так и говорим
        printf("The list is empty\n");
        return;
    }
  	
		int i = 0; // организуем счетчик
    while (base != NULL) { // Пока все элементы не кончаться мы будем их перебирать
        printf("ID: %d || Data: %s\n", i, (char*)base->data); // выводя на экран
        base = base->next;
        i++;
    }
  	// В конце покажем какой размер у нашего списка
    printf("Base size: %d\n", lst->count);
}

Такой вот простой способ организации двусвязного списка. Работает как положено, но у него есть один существенный минус. Что если элементов в списке будет не 3, ни 10, ни даже 1000, а будет их 1млн? Как показало испытание, генерация списка размером в 1млн заняло порядка 20 секунд. 10млн - 15 минут. И это только генерация, а поиск и чтение по такому огромному списку тоже не сильно быстрее. Пришлось несколько подумать над решением этой проблемы, и в следующей статье я объясню как ее решил.

Следующая статья: Динамические структуры данных на Си: Список - Продвинутая версия