Привет, Хабр!
В статье хочу показать, как написать пародию на ArrayList из Java.
Сразу скажу, я не профессионал в C, и могу допускать ошибки, если вы найдете таковые то напишите в комментариях, я обязательно исправлю эти моменты. Также статья нацелена на новичков из за довольно простой темы.
Начнем
Создадим заголовочный файл list.h и .c файл к нему. Если вы не знаете что это такое и как с этим работать, то можете прочитать об этом ниже.
Заголовочные файлы
Чтоб сделать свою программу модульной, то есть разделить код на несколько файлов, а не писать всю программу в одном файле, есть заголовочные файлы. В них содержится информация такие как шаблоны функции, структуры и тд. К каждому заголовочному файлу, нужно сделать файл-реализатор, там уже функции из заголовочного файла будут имплементированы. Также при компиляции нужно указывать реализаторы (Например clang main.c list.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);
#endifList - эта структура списка, data - это указатель на элементы списка, length - это длинна списка, а capacity - это вместимость списка, ну и new_list возвращает указатель на созданный список.
Я думаю нам пока-что хватит этих функций и структуры. Теперь зайдем в list.c. Там подключаем этот заголовочный файл через #include "list.h", и реализуем функции!
Сразу дам код, и буду его объяснять.
Реализация 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. Если есть вопросы или поправки пишите в комментариях.
Пока, Хабр!
Комментарии (57)
includedlibrary
10.11.2024 10:43заголовочный файл - это интерфейс, с реализатор это класс который имплементирует этот интерфейс
В си нет классов. И в общем случае заголовочный файл - это не интерфейс. Там могут быть описаны только типы данных без прототипов функций.
К каждому заголовочному файлу, нужно сделать файл-реализатор
В заголовочных файлах можно указать имя внешего символа, который будет создан линкером или вообще компилятором другого языка, так что си файл с реализацией не всегда обязателен.
list->data = realloc(list->data, sizeof(int) * list->capacity);realloc может возвращать NULL вслучае нехватки памяти, у вас нет на это проверки.
printf("%s\n", "return NULL");Почему бы просто не использовать puts?
Xedox_SlimeLime Автор
10.11.2024 10:43Спасибо за поправки, сейчас их применю к статье.
Насчет интерфейсов и классов, я хотел чтобы джависты хотябы примерно поняли как это работает и зачем
Apoheliy
10.11.2024 10:43Ещё небольшие "5 копеек":
В list_add/get/remove/free проверять, что list передали не NULL, и list->data не крэшнет приложение;
list_add - сделать гарантию сохранности данных в случае ошибки. Как минимум не менять capacity и data, пока не проверишь результат realloc. Для возврата признака ошибки лучше сделать возвращаемое значение int;
list_get лучше не использовать print. Лучше вообще ничего не выводить: консоли может не быть (микроконтроллеры и всё такое), или на экране может быть какая-то важная информация и "разбавлять" её фразами return NULL - это не очень хорошо.
azarov_den
10.11.2024 10:43typedef struct s_list { void *content; struct s_list *next; }Структура универсального односвязного списка. Capacity нет смысла хранить в каждом узле, лишнее место занимает. Если next == null, то это конец списка.
Создание нового элемента с добавлением содержимого.t_list *ft_lstnew(void *content) { t_list *list; list = (t_list *)malloc(sizeof(t_list)); if (!(list)) return ((void *)0); list->content = content; list->next = (void *)0; return (list); }Добавление в конец списка:
void ft_lstadd_back(t_list **lst, t_list *new) { t_list *last; if (*lst == (void *)0) { *lst = new; return ; } last = ft_lstlast(*lst); last->next = new; }Уничтожение списка, del - указатель на функцию высвобождения содержимого:
void ft_lstclear(t_list **lst, void (*del)(void *)) { t_list *first_p; t_list *tmp; first_p = *lst; if (*lst == (void *)0) return ; while (first_p) { del(first_p->content); first_p->content = (void *)0; first_p = first_p->next; } while ((*lst)) { tmp = (*lst)->next; free(*lst); *lst = tmp; } *lst = (void *)0; }Xedox_SlimeLime Автор
10.11.2024 10:43Круто конечно, но я создавал список похожий на список (ArrayList) из Java.
azarov_den
10.11.2024 10:43забыл дописать в объявлении структуры t_list
typedef struct s_list { void *content; struct s_list *next; } t_list;
includedlibrary
10.11.2024 10:43У автора динамический массив aka vector из c++. а не односвязный список. Да и в универсальных решениях на основе void* смысла не вижу - они будут работать медленне, лучше использовать подход из ядра linux, где для каждого списка/дерева создаётся отдельная структура, но в неё встраивается структура с указателями:
https://litux.nl/mirror/kerneldevelopment/0672327201/app01lev1sec2.html
azarov_den
10.11.2024 10:43Если динамический хочет и в С, то нужно творить магию макросов. У автора динамического ничего нет. Обычный связанный список описал.
includedlibrary
10.11.2024 10:43Макросы-то зачем? Динамический массив - это массив, размер которого не известен на этапе компиляции и может меняться во время исполнения. Если вы имеете в виду дженерики, то в си их можно сделать и без макросов - как вы через void*, или как в ядре linux - через встраивание структуры.
azarov_den
10.11.2024 10:43Да, ерундду сморозил. Давно перешёл на С#, деградирую потихоньку.
ryanl
10.11.2024 10:43Если вы давно перешли на сишарп то должны были понять, что под списком имеется ввиду динамический массив, это видно по содержимому типа. Столько шума вместо этого...
azarov_den
10.11.2024 10:43А пардоньте, не внимательный прочел по диагонали. Странно что вообще заголовок называется "простой список", получается здесь речь вообще не о списке.
Xedox_SlimeLime Автор
10.11.2024 10:43Я немного не понял о чем вы написали, можете обьяснить?
miksoft
10.11.2024 10:43includedlibrary выше уже описал - вы реализовали не список, а динамический массив. В данном случае массив целых чисел (int).
А список - это как-то так - https://learnc.info/adt/linked_list.html и https://ru.wikipedia.org/wiki/Связный_список
Xedox_SlimeLime Автор
10.11.2024 10:43Но список вроде и есть динамический массив?.. Ну или я слишком привык к Джаве. В любом случае, спасибо.
miksoft
10.11.2024 10:43Нет. В простейших списках (односвязный, двусвязный) невозможно обращаться к элементу по его индексу, по крайней мере, под капотом. А вы спокойно делаете return &list->data[pos];
Xedox_SlimeLime Автор
10.11.2024 10:43Это вид списка. В джаве тойже есть интерфейс List и например реализация ArrayList, и это список а не динамический массив. И там я обращаюсь именно по индексам.
playermet
10.11.2024 10:43Здесь возникает терминологическая путаница. Есть абстратный тип данных "список", который и подразумевается в названии ArrayList в Java. Есть структура данных "связный список". В среде программистов С и С++ говоря "список" чаще всего подразумевают именно структуру данных, а аналог ArrayList называют динамическим массивом или вектором. Как раз чтобы не возникало путаницы в Java выбрали название ArrayList а не просто List.
sshikov
10.11.2024 10:43в Java выбрали название ArrayList а не просто List.
В java List это интерфейс, а ArrayList одна из его реализаций. Вторая, сюрприз, сюрприз - LinkedList.
playermet
10.11.2024 10:43Вопрос был не в том, существует ли связный список и еще 9 других реализаций List в Java (спасибо, кэп?). А в путанице терминов в статье и комментариях и выборе имен.
sshikov
10.11.2024 10:43Как раз чтобы не возникало путаницы в Java выбрали название ArrayList а не просто List.
Я говорю тут лишь о том, что в Java выбирали названия слегка не так, как у вас написано, и просто List на самом деле это интерфейс (и строго говоря, он не подразумевает например односвязного списка), а реализации у него есть разные. То что вы до этого написали - у меня никаких вопросов не вызывает, тут вы совершенно правы. И что обычно списком таки называют связанную указателями структуру, а не динамический массив/вектор - я совершенно согласен.
playermet
10.11.2024 10:43и просто List на самом деле это интерфейс (и строго говоря, он не подразумевает например односвязного списка)
Я в курсе, он то как раз и соответствует упомянутому выше АТД список. Но его могли назвать например Enumerable (или Sequence), а ArrayList назвать просто List, как это сделали в C# (LinkedList там тоже есть, а еще там есть свой ArrayList, но его отличие от List только в отсутствии типизации элементов). Но в Java все же решили сделать именно так, с акцентом что это список реализованный массивом.
azarov_den
10.11.2024 10:43Вполне возможно, что в Java List это таки связанный список. Под капот не смотрел. Но за счёт перегрузки операторов вы можете воспользоваться скобочками и достучаться до элемента. Вот и получается название ArrayList - мол я связанный список List, но со мной можно обращаться как с массивом Array. Есть же вообще понятие ассоциативный массив. Который вообще может быть реализован тысячами способами. Тем же связанным списком, бинарными деревьями, каша-таблицами.
playermet
10.11.2024 10:43Вполне возможно, что в Java List это таки связанный список
Нет. Как сказано выше, в Java List это просто интерфейс для упорядоченных контейнеров. Всего у него есть 10 стандартных реализаций, среди которых ArrayList, который динамический массив, и LinkedList, который связный список. Их исходники буквально посмотреть можно.
А еще в Java нет перегрузки операторов.
Serpentine
10.11.2024 10:43У вас в заголовочном файле list.h отсутствует объявление функции list_free(), которая вызывается в программе. Clang разве не выдал вам предупреждения со словами типа
implicit declaration of function ...?Xedox_SlimeLime Автор
10.11.2024 10:43просто я писал статью и одновременно писал код, и забыл добавить туда эту функцию. Сейчас исправлю.
JerryI
10.11.2024 10:43Та, вы учитесь чему нибудь с предыдущей статьи? Там вы также писали код сразу в материал не проверив. Кажется одного раза должно быть достаточно чтобы что-то изменить в повествовании
Xedox_SlimeLime Автор
10.11.2024 10:43Я сначало проверял код, потом вставлял в хабр, и потом вспомнил что нужна еще функция освобождения.
Kotofay
10.11.2024 10:43Можно сэкономить целый указатель и уменьшить фрагментацию:
#include <stdio.h> #include <stdlib.h> #define SPEEDLIST typedef struct LinkedListNode { LinkedListNode * next; #ifdef SPEEDLIST LinkedListNode * prev; #endif } LinkedListNode; typedef struct { LinkedListNode *head, *tail, *current; } LinkedList; LinkedList * newLinkedList() { LinkedList * ret = ( LinkedList * ) malloc( sizeof( LinkedList ) ); if( ret != NULL ) ret->current = ret->head = ret->tail = ( LinkedListNode * )NULL; return ret; } void * pushBack( LinkedList * ll, size_t sizeData ) { if( ll == NULL ) return NULL; LinkedListNode * newNode = ( LinkedListNode * ) calloc( 1U, sizeof( LinkedListNode ) + sizeData ); if( newNode == NULL ) return NULL; if( ll->tail == NULL && ll->head == NULL ) { ll->tail = ll->head = newNode; } else { #ifdef SPEEDLIST newNode->prev = ll->tail; #endif ll->tail->next = newNode; ll->tail = newNode; } return ( ( unsigned char * ) newNode ) + sizeof( LinkedListNode ); } void * last( LinkedList * ll ) { if( ll == NULL ) return NULL; if( ll->tail == NULL && ll->head == NULL ) { return NULL; } else { return ( ( unsigned char * )ll->tail ) + sizeof( LinkedListNode ); } return NULL; } int main() { typedef struct { int foo; double bar; } Payload; if( LinkedList * ll = newLinkedList() ) { if( Payload * pl = ( Payload * ) pushBack( ll, sizeof( Payload ) ) ) { pl->foo = 1; pl->bar = 2.3; } if( Payload * pl = ( Payload * ) pushBack( ll, sizeof( Payload ) ) ) { pl->foo = 4; pl->bar = 5.6; } if( Payload * pl = ( Payload * ) last( ll ) ) { printf( "Payload : %d, %lf\n", pl->foo, pl->bar ); // -> Payload : 4, 5.600000 } } return 0; }Xedox_SlimeLime Автор
10.11.2024 10:43Я пишу не связный список, а скорее вектор из плюсов. Или список из джавы.
Kotofay
10.11.2024 10:43public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>Жаль. ArrayList и LinkedList имплементируют интерфейс List.
Xedox_SlimeLime Автор
10.11.2024 10:43Я знаю, но в джаве под списком чаще всего подразумевают именно ArrayList.
alef13
10.11.2024 10:43Ужасная статья, ужасная. Я теперь уснуть не смогу - буду вспоминать realloc на каждую вставку элемента (странно что на удаление нет - забыл?), увеличение на 2 вместо sizeof, поэлементное присваивание вместо memcpy/memmove, и сам принцип этой непонятной библиотеки не укладывается в элегантный и быстрый язык. В общем предлагаю удалить, пока кто-то не начал по ней изучать C
Xedox_SlimeLime Автор
10.11.2024 10:43Я написал про оптимизацию плохую. В удалении да, забыл.
alexxisr
10.11.2024 10:43Возможно в удалении и не надо. Если мы список однажды загружаем и потом почти не изменяем, например.
includedlibrary
10.11.2024 10:43А где вы увидели realloc на каждую вставку? Автор тут всё верно сделал - он каждый раз увеличивает вместимость в двое:
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; }
includedlibrary
10.11.2024 10:43Приятно видеть, что вас заинтересовал Си. Но по-моему вы слишком спешите. Не надо писать статью про каждую изученную тему. Сначала изучите Си, как следует, потом уже думайте про написание статей. И писать про структуры данных - плохая идея, эта тема уже изъезженна (если только вы не изобретёте какую-то специфическую структуру для решения какой-то проблемы). Если хочется писать, лучше описать реализацию своего проекта средней/высокой сложности или разобрать какую-нибудь нетриваиальную тему. Потому что тривиальные уже разобрали по нескольку раз.
Xedox_SlimeLime Автор
10.11.2024 10:43Думаю вы правы. Но в случае со списками я уже знал как они работают под капотом, тк я писал свою реализаци ArrayList на Java. А когда изучил базу про выделение памяти и указатели полностью понял как их писать.
includedlibrary
10.11.2024 10:43Да, но тема с динамическими массивами уже сотни раз описана в учебниках. Описана она там лучше, соответственно не стоит писать про это. Потому что любой, кто захочет изучить си, в состоянии открыть учебник и прочитать его. Если человек на это не способен, то он и программистом никогда не станет. То же самое касается и почти всех структур данных/общеизвестных алгоритмов - проще открыть учебник Кормена и посмотреть в нём (некоторые ещё могут читать Кнута), там и реализация есть, пусть и на псевдокоде, и асимптотический анализ, и даже задачи, в которых можно тот или иной алгоритм и структуру применить.
Jessy_James
10.11.2024 10:43В реализации list.h:
#include "list.h". Нужна статья на эту тему ;)
serge_nn
Никогда еще не видел на Хабре такой безграмотной статьи. Я имею в виду русский язык, а не C. Трудно было включить spell check?
Xedox_SlimeLime Автор
А что это?... Я исправлю все ошибки.
includedlibrary
https://ru.wikipedia.org/wiki/Система_проверки_правописания
Xedox_SlimeLime Автор
Спасибо.
evgeniy_kudinov
В поисковиках можно поискать по ключевым словам "проверка орфографии онлайн" и будет в выдаче полно инструментов для проверки орфографии и не только.
Tarmik
Могу поспорить, см. https://habr.com/ru/articles/337138/#comment_10398504
:)