What is a Linked List?

Связный список — это последовательность значений, где каждое значение живет в своем собственном узле, и каждый узел содержит указатель на следующий узел. Список знает о своем первом узле (head); оттуда вы можете добраться до любого другого узла, следуя по цепочке указателей next.

В отличие от массива, связному списку не требуется единый непрерывный блок памяти. Добавление элемента в начало (head) выполняется за O(1): достаточно создать новый узел и направить его на текущую голову. Компромисс заключается в том, что получение n-го элемента выполняется за O(n), так как нам приходится проходить по цепочке по одному узлу за раз.

Пять основных операций со связным списком:

1. AddFirst: Добавить значение в начало списка.
2. AddLast: Добавить значение в конец списка.
3. Get: Вернуть значение по заданному индексу.
4. Remove: Удалить значение по заданному индексу.
5. Size: Вернуть количество хранящихся в данный момент значений.

Давайте сначала создадим класс Node, а затем построим LinkedList на его основе!