Абстрактные структуры даных

Односвязный список/Singly Linked List

Односвязный список - это абстрактная структура даных, которая имеет следующие свойства:

  1. Последовательные элементы связаны указателем
  2. Последний элемент указывает на null-значение
  3. Может рости в размере
  4. Может быть настолько большим сколько надо (пока не закончится память)
  5. Не тратит лишнюю память

Очередь или Queue

Еще одним абстрактным простым типом данных есть Очередь/Queue.

Очередь реализует принцып первый вошел первый вышел (FIFO - first in first out). Каждый из вас уже видел очередь в своей жизни, когда стоял за билетами в кино или теарт. Очередь имеет голову(head) и хвост(tail), которые соответственно есть люди в начале очереди и в конце. Самый первый человек в очереди уйдет первым, последний - соответственно последним)).

Стек/Stack

Одной из самых простых абстрактных структур даных есть Стек. Стек работает по принцыпу "последний зашел первый ушел" (LIFO - last in first out). Стек поддерживает две основные операции: pop i push. Конечно можно расширять функционал структуры. Если использовать простые типы даных, то стек, конечно, реализуется с помощью массивов.