Структуры данных — двусвязный список

  • В этой теме 0 ответов, 1 участник, последнее обновление 3 месяца, 3 недели назад сделано Васильев Владимир Сергеевич.
Просмотр 0 веток ответов
  • Автор
    Сообщения
    • #6532
      @admin
      StudLance.ru

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

      1. для удаления элемента X по указателю на узел из односвязного списка нам требовалось O(N) операций, так как сначало было необходимо найти ссылку на узел, стоящий перед X — а для этого выполнялся перебор элементов списка (в худшем случае — обход всех узлов, т.е. N). В двусвязном списке мы за 1 операцию можем получить нужную ссылку — значит удаление элемента выполнится за O(1). Если вам не знакомы обозначения O(N), O(1) — загляните в статью «Анализ сложности алгоритмов. Примеры«;
      2. важно, что это каснется не только удаления, но и многих других операций — в частности вставки. Это также окажет влияние при хранении данных упорядоченными (упорядоченный связный список — это уже другая структура данных).
      3. каждый узел хранит дополнительный указатель — это лишние несколько байтов. Мелочь, но таких узлов много — в списке из миллиона узлов наберется несколько лишних мегабайтов.

      Узел списка хранит данные и два указателя. Сам же список задается парой — указатель на начало (first) и указатель на конец (last). Используя указатель на конец мы можем, например, обойти список в обратном направлении. Схематично структуры списка и узла показана в виде ER-диаграммы:

      В качестве примера рассмотрим алгоритм сортировки списка методом выбора. При таком алгоритме, весь список условно разделяется на две части — отсортированную и остальную. Постепенно (на каждом шаге) из элементов неупорядоченной части выбирается минимальный элемент и добавляется в конец отсортированной части. Затем, размер упорядоченной части увеличивается на 1 элемент. Процесс продолжается до тех пор, пока в отсортированной части не окажутся все элементы списка. Схематично этот процесс показан на рисунке, где используются следующие обозначения:

      • овалы — переменные типа указателей снаружи списка, например min — указатель на минимальный элемент списка;
      • сплошные и штриховые линии — указатели, при этом если они относятся к операции (изменение значение указателя) — то штриховая линия задает старое значение, а сплошная — новое;
      • ромб около линии задает шаг алгоритма (операцию). Так, например, на третьем шаге указатель border меняет свое значение на border->next;
      • пунктирная линия соответствует операции обмена значений двух узлов (поля value).

      Ниже приведена блок-схема этого алгоритма:

      StudLance.ru

Просмотр 0 веток ответов
  • Для ответа в этой теме необходимо авторизоваться.
×