https://repl.it/@IlyaSiganov/List#main.c

<aside> 👩‍🏫 Можно написать на Си со структурами и функциями, а можно на С++ с методами и интерфейсами, если знаете как.

</aside>

На этой практике мы познакомимся с Абстрактными Типами Данных. Разберем Список, как один из видов АТД. Напишем две реализации Списка - Связный Список и Список на основе массива. Проведем бенчмарк скорости работы двух реализаций в разных задачах.

Теория

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

Список

Рассмотрим матмодель списка - множество объектов, упорядоченное по индексу элемента в списке. Мы хотим иметь возможность применять следующий операции над списком:

• GetAt(index) - взять элемент из списка по индексу
• Insert(index, element) - вставить элемент по индексу
  • Append(element) - вставить элемент в конец списка(стека)
  • Prepend(element) - вставить элемент в начало списка(очереди)
• Delete(index) - удалить элемент по индексу
  • Pop() - удалить элемент с конца списка(стека) и получить этот элемент
  • Dequeue() - удалить элемент с начала списка(очереди)
• Length() - получить длину списка

Содержимое файла-интерфейса list.h. Его менять нельзя, подключайте его в ваших реализациях с помощью #include "list.h".

// это файл list.h
#ifndef LIST_LIST_H
#define LIST_LIST_H

typedef struct List List; // не специфицированная структура, конкретные реализации должны быть описаны в c-файлах
List *NewList(); // создание пустого списка

void Append(List *, int); // вставка элемента в конец списка
void Prepend(List *, int); // вставка элемента в начало списка
void AppendAll(List *, const List *); // вставить все элементы одного списка в конец другого. Происходит глубокое копирование листа справа. Если удален правый лист, то у левого листа данные не исчезают.
void InsertAt(List *, int, int); // вставка элемента после индекса

void RemoveAt(List *, int); // удаление элемента по индексу
void RemoveAll(List *); // удаление всех элементов из списка

int Pop(List *); // удаление элемента с конца списка, функция возвращает удаленный элемент
int Dequeue(List *); // удаление элемента с начала списка, функция возвращает удаленный элемент

int Length(const List *); // вычисление длины списка
int GetAt(const List *, int); // взятие элемента списка по индексу

#endif //LIST_LIST_H

Реализовать Список можно разными способами:

• линейно связный список
• список на основе массива.

Линейно связный список