Списки

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

Связный список- это структура данных, представляющая собой конечное множество упорядоченных элементов, связанных друг с другом посредством указателей. Каждый элемент этой структуры содержит поле с какими-либо данными, а также указатель (ссылку) на следующий и/или предыдущий элемент. По структуре связности выделяют односвязные, дву связные, кольцевые и некоторые другие списки.

Односвязный список (рис. 5.1) не слишком удобен, так как из одной точки есть возможность попасть лишь в следующую точку, двигаясь тем самым в конец. Когда кроме указателя на следующий элемент есть указатель и на предыдущий, то такой список называется двусвязным (рис. 5.2).

Рис. 5.1. Односвязный список

Рис. 5.2. Двусвязный список

Возможность двигаться как вперед, так и назад полезна для выполнения некоторых операций, но дополнительные указатели требуют задействования большего количества памяти, чем таковой необходимо в односвязном списке.

Для двух видов списков, описанных выше, существует подвид, называемый кольцевым списком (рис. 5.3). Сделать из односвязного списка кольцевой можно, добавив всего лишь один указатель в последний элемент, так чтобы он ссылался на первый. А для двусвязного потребуется два указателя: на первый и последний элементы.

Рис. 5.3. Кольцевой список

Помимо рассмотренных видов списочных структур есть и другие способы организации данных по типу «список». Они, как правило, во многом схожи с рассмотренными.

Стек

Стек характерен тем, что доступ к его элементам предоставляется лишь с одного конца, называемого вершиной стека; иначе говоря: стек - структура данных типа «список», функционирующая по принципу LIFO

{last in - first out, «последним пришел - первым вышел»). Изобразить эту структуру данных лучше в виде вертикального списка (рис. 5.4). В качестве примера можно привести, например, стопки каких-либо вещей, где чтобы воспользоваться одной из них нужно поднять все те вещи, что лежат выше нее.

Рис. 5.4. Стек

Впервые стек был предложен в 1946 году Аланом Тьюрингом как средство возвращения из подпрограмм. В 1955 году немцы Клаус Самельсон и Фридрих Бауэр из Технического университета Мюнхена использовали стек для перевода языков программирования и запатентовали идею в 1957 году. Но международное признание пришло к ним лишь в 1988 году.

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

Основные операции над стеком:

• • добавление элемента (push);
• • удаление элемента (pop);
• • чтение верхнего элемента.

Очередь

Структура данных «Очередь» использует принцип организации FIFO (First In, First Out - «первым пришел - первым вышел»). То есть очередь - это список, добавление элементов в который допустимо лишь в один его конец, а их извлечение производится с другого конца (рис. 5.5).

Рис. 5.5. Очередь

Элементу необходимо пройти весь список, прежде чем он станет доступным. В этом отношении работа со следующей структурой покажется несколько более удобной.

Дек

Дек {deque - double ended queue, «двухсторонняя очередь») - очередь с двумя концами (рис. 5.6). Это означает, что данный вид списка позволяет добавлять элементы в начало и в конец. Это же справедливо и для операции извлечения.

Рис. 5.6. Дек

Число основных операций, выполняемых над стеком и очередью, равно трем: добавление элемента, удаление элемента, чтение элемента. При этом не указывалось место структуры данных, активное в момент их выполнения, поскольку ранее оно однозначно определялось свойствами (определением) самой структуры.

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

• • добавление элемента в начало;
• • добавление элемента в конец;
• • удаление первого элемента;
• • удаление последнего элемента;
• • чтение первого элемента;
• • чтение последнего элемента.

На практике этот список может быть дополнен проверкой дека на пустоту, получением его размера и некоторыми другими операциями.