Главная » Java, Структуры данных и алгоритмы » Однонаправленные связные списки

0

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

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

Рис. 4.6. Однонаправленный связный список. Обращения к элементам обозначены штриховыми стрелками, а ссылки к следующим узлам — сплошными. Объект null обозначен знаком 0. Ссылка head является единичной переменной экземпляра

Подобная система обращения одного узла к другому подобна циклическому доказательству, однако работа этой схемы довольно проста. Ссылка next внутри узла является звеном связи, или указателем на следующий узел. Таким образом, переход по ссылке next к следующему узлу называется переключением по указателю. Первый и последний узлы связного списка называются головой и хвостом списка соответственно. Хвост списка определим как узел с нулевым значением ссылки next, означающим, что список завершен. Описанный подобным образом связный список называется однонаправленным связным списком.

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

Точнее, пространство, занимаемое однонаправленным связным списком, содержащим п элементов, есть 0(п), так как содержит п узлов, а каждый узел занимает пространство 0(1), в котором хранятся ссылки на элемент и следующий узел. Для,реализации однонаправленного связного списка в Java опишем класс Node^ представленный фрагментом кода 4.10, который определяет формат объектов;, связанных с узлами, а также класс LinkedList (не показан), содержащий ссылку на головной узел списка и дополнительную информацию о сдиске (число элементов). Обратите внимание, что в целях экономии места комментарии Javadoc не включены во фрагмент кода 4.10 и другие фрагменты кодов в остальной части книги, вместо них используются внутритекстовые комментарии.

public class Node {

есть каждый узел является составным объектом, содержащим ссылку на некий элемент, а также на следующий узел (см. рис. 4.6).

// переменные экземпляра private Object element;

private Node next; // простые конструкторы public Node() { this(null, null);

}

public Nod6(0bject e, Node n) { element = e; next = n;

}

// аксессорные методы Object getElement() { return element;

}

Node getNext() { return next;

}

// модифицирующие методы void setElement(Object newElem) { element = newElem;

}

void setNext(Node newNext) { next = newNext;

}

}

Фрагмент кода 4.10. Реализация узла однонаправленного связного списка. В целях экономии места вместо комментариев Javadoc используются внутритекстовые комментарии

При этом легко добавляются и удаляются элементы в начало однонаправленного связного списка за время 0(1), как показано на рис. 4.7. , Создается нов|>ш узел и указатель next для него, который обращается к тому же объекту, что и узел head, а затем перенаправляет ссылку узла head к созданному узлу. Обратите внимание, что данная простая Процедура выполняется даже при пустом списке или при обращении head к нулевому объекту.     А

Также можно добавить элемент в конец однонаправленного связного списка за время 0(1), при условии, что имеется ссылка на конечный узел, как показано на рис. 4.8. В данном случае создается новый узел, ссылке next которого присваивается значение null, а ссылка next узла tail перенаправляется на новый узел, затем ссылке tail присваивается значение нового узла.

Рис. 4.7. Добавление элемента в начало однонаправленного связного списка: (а) до добавления элемента; (Ь) создание нового узла; (с) после добавления. Удаление элемента из начала списка является симметричной операцией, при которой последовательность действий обратная: (с), (Ь) и, наконец, (а)

(с)

(a)

(b)

Рис. 4.8. Добавление элемента в конец однонаправленного связного списка.

(a)  до добавления элемента; (Ь) создание нового узла; (с) после добавления. Обратите внимание: ссылка next для узла tail определяется на этапе

(b)     ,       и только после этого переменной tail присваивается значение ссылки нового узла (с)

(с)

(а)

(Ь)

Однако невозможно удалить конечный элемент однонаправленного связного списка за время 0(1). Даже при обращении ссылки tail непосредственно к последнему узлу списка для его удаления требуется доступ к предпоследнему узлу. Это один из тех случаев, когда говорится «попасть нельзя оттуда сюда», так как невозможно добраться до узла, расположенного перед узлом v, следуя по ссылке от v. Единственным способом является просмотр всего списка с самого начала до узла, ссылка next которого будет обращаться к v. Однако, если v является последним узлом, подобный переход по указателю займет много времени — пропорционально числу элементов списка, то есть время 0(я).

Далее рассмотрим реализацию всех АТД, представленных ранее, используя однонаправленный связной список.

Источник: Гудрич М.Т. Г93 Структуры данных и алгоритмы в Java / М.Т. Гудрич, Р. Тамассия; Пер. с англ. A.M. Чернухо. — Мн.: Новое знание, 2003. — 671 е.: ил.

По теме:

  • Комментарии