Пишем простой список на C

Привет, Хабр!

В статье хочу показать, как написать простой список на C, а именно пародию на ArrayList из Java.

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

Начнем

Создадим заголовочный файл list.h и .c файл к нему. Если вы не знаете что это такое и как с этим работать, то можете прочитать об этом ниже.

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

#ifndef LIST_H #define LIST_H  typedef struct List {   int* data;   int length;   int capacity; } List;  List* new_list(); void list_add(List* list, int el); int* list_get(List* list, int pos); void list_remove(List* list, int pos); void list_free(List* list);  #endif

List — эта структура списка, data — это указатель на элементы списка, length — это длинна списка, а capacity — это вместимость списка, ну и new_list возвращает указатель на созданный список.

Я думаю нам пока-что хватит этих функций и структуры. Теперь зайдем в list.c. Там подключаем этот заголовочный файл через #include «list.h», и реализуем функции!

Сразу дам код, и буду его объяснять.

#include <stdlib.h> #include "list.h" #include <stdio.h>  List* new_list() {   List* list = (List*) malloc(sizeof(List));   if(list == NULL) {     return NULL;   }   list->data = malloc(sizeof(int) * 1);   if (list->data == NULL) {     free(list);     return NULL;   }   list->capacity = 1;   list->length = 0;   return list; }  void list_add(List* list, int el) {   if(list->length == list->capacity) {     list->capacity *= 2;     list->data = realloc(list->data, sizeof(int) * list->capacity);   }   list->data[list->length++] = el; }  int* list_get(List* list, int pos) {   if(pos >= 0 && pos < list->length)     return &list->data[pos];   printf("%s\n", "return NULL");   return NULL; } void list_remove(List* list, int pos) {   if(pos >= 0 && pos < list->length){     for (int i = pos; i < list->length - 1; i++) {       list->data[i] = list->data[i + 1];     }     list->length--;   } }  void list_free(List* list) {   free(list->data);   free(list); }

Объяснение функций

new_list — Тут создается список. Мы выделяем под него память, и если на устройстве не хватило места (malloc вернет NULL) то сразу возвращаем NULL. Далее выделяем память память под data, то есть наши элементы, и если на устройстве не хватило места, то освобождаем память выделенную для объекта list, и возвращаем NULL. Также устанавливаем стандартную вместимость (1), и начальную длину (0).

list_add(List*, int) — Тут добавляем элемент в список, передав список и добавляемый элемент. И если длинна списка будет совпадать с вместимостью, умножаем вместимость вдвое. И с помощью realloc меняем размер выделенной памяти для списка. И после всего этого, в конец добавляем переданный элемент.

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

list_get(List*, int) — возвращает элемент из списка по указанной позиции. В параметры передаем список и позицию элемента. И если позиция будет в промежутке от 0 до длинны списка, то возвращаем элемент, иначе возвращаем NULL.

list_remove(List*, int pos) — удаляем элемент по указанной позиции, идет таже проверка из list_get, и просто сдвигаем элементы после удаленной позиции назад. Далее просто уменьшаем длину списка.

list_free(List*) — освобождает память выделенную под data и сам список. Все просто.

Пример использования

Просто создадим список, добавим элементы, удалим элемент под индексом 1, и выводим все элементы на экран.

Компилируем код — clang main.c list.c, и запускаем ‑./a.out. Может отличаться в зависимости от OC, я использую Linux и компилятор Clang.

#include <stdio.h> #include "list.h"  int main() {   List* list = new_list();   list_add(list, 12);   list_add(list, 83);   list_add(list, 212);   list_add(list, 0);    list_remove(list, 1);    for(int i=0; i<list->length; i++) {     printf("pos: %d = %d\n", i, *list_get(list, i));   }   list_free(list); }

Output: pos: 0 = 12 pos: 1 = 212 pos: 2 = 0

Конец

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

Пока, Хабр!