Пишем простой список на C10.11.2024 13:31

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

В статье хочу показать как написать простой список на 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);

#endif

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

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

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

Реализация list.h

#include 
#include "list.h"
#include 

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.

#include 
#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; ilength; 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. Если есть вопросы или поправки пишите в комментариях.

Пока, Хабр!

© Habrahabr.ru