Главная » Java, Структуры данных и алгоритмы » Реализация double-ended queue на основе двусвязного списка

0

Так как дек предусматривает возможность добавления и удаления объектов на обоих концах списка, его реализация на основе однонаправленного связного списка не может быть эффективной (см. п. 4.3.1). Однако существует тип связного списка, который обладает большими возможностями, в том числе добавлением и удалением элементов на обоих концах списка, которые выполняются за время 0(1), — двусвязный список. Узел двусвязного списка содержит две ссылки — ссылку к следующему узлу списка next и ссылку к предыдущему узлу списка prev. Java-реализация узлов двусвязного списка представлена фрагментом кода 4.13.

Для упрощения программирования рекомендуется добавлять специальные узлы на обоих концах списка: узел header перед первым узлом списка и узел trailer непосредственно после последнего узда списка. Данные «холостые», или сигнальные узлы не содержат элементов. Узел header содержит действительную ссылку next и нулевую ссылку prev, в то время как узел trailer — действительную ссылку prev и нулевую ссылку next. Пример такого двусвязного списка вместе с сигнальными узлами представлен на рис. 4.9. Обратите внимание, что объекты связного списка хранят эти сигнальные узлы, а также Счетчик size, содержащий количество элементов в списке (не считая сигнальных узлов).

Добавление или удаление элементов на одном из концов двусвязного списка выполняется за время 0(1) (см. рис. 4.10). Ссылка prev устраняет необходимость просмотра всего списка для доступа к предпоследнему узлу.

Рис. 4.9. Пример двусвязного списка с сигнальными узлами header и trailer на концах списка. В пустом списке эти сигнальные узлы будут обращаться друг к другу. Нулевая ссылка prev узла header и нулевая ссылка next узла trailer не приводятся

Таким образом, прежде чем добавить новый элемент е, можно считать, что имеется узел р, который находится перед тем участком, куда следует поместить е, и узел q, который размещается за ним. Чтобы добавить новый элемент е между этими двумя узлами (один или оба из которых могут быть сигнальными), создадим новый узел /, ссылки prev и next которого относятся к р и q соответственно, а затем адресуем ссылку next узла р и ссылку prev узла q к узлу t.

Аналогично, если необходимо удалить элемент узла /, предполагав^ что с обеих сторон t находятся узлы р и q (и эти узлы действительно существуют, так как применяются сигнальные узлы). Чтобы удалить узел находящийся между двумя узлами р и достаточно перенаправить их ссылки друг к другу, а не к узлу t. При этом не нужно изменять поля узла так как сборщик мусора освободит выделенное для узла t место, если на него не будет активных ссылок.

class DLNode {

private Object element; private DLNode next, prev; DLNode() { this(null, null, null); } DLNode(Object e, DLNode p, DLNode n) { element = e; next = n; prev = p;

‘ }

void setElement(Object newElem) { element = newElem; } void setNext(DLNode newNext) { next = newNext; } void setPrev(DLNode newPrev) { prev = newPrev; } Object getElement() { return element; } DLNode getNext() { return next; } DLNode getPrev() { return prev; }

}

Фрагмент кода 4.13. Реализация узла двусвязного списка

Рис. 4.10. Операции над двусвязным списком с использованием сигнальных узлов header и trailer: (а) добавление элемента в начале списка; (Ь) состояние после добавления и перед удалением элемента из конЦй списка; (с) удаление элемента из конца списка; (d) состояние после удаления

(d)

(a)

(b)

(с)

public class MyDeque implements Deque {

DLNode header, trailer; // сигнальные узлы int size; // число элементов

public MyDeque() { // инициализация пустого дека header = new DLNode(); trailer = new DLNode();

header.setNext(trailer); // header обращается к trailer trailer.setPrev(header); // trailer обращается к header size = 0;

}

public Object first() throws DequeEmptyException { if (isEmpty())

throw new DequeEmptyExceptionfDeque is empty."); return header.getNext() getElement();

}

public void insertFirst(Object o) { DLNode second = header.getNext(); DLNode first = new DLNode(o, header, second); second .setPrev(fi rst); header.setNext(first); size++;

}

public Object removeLast() throws DequeEmptyException { if (isEmpty())

throw new DequeEmptyException("Deque is empty."); DLNode last = trailer.getPrev(); Object о = last.getElement(); DLNode secondtolast = last.getPrev(); trailer.setPrev(secondtolast); secondtolast setNext(trailer);

size———————— ;

return o;

}

Фрагмент кода 4.14. Части реализации АТД «дек» на основе двусвязного списка. Обратите внимание, что благодаря использованию сигнальных узлов нет необходимости специально описывать исключительные случаи, например, при пустом списке или для случая, если список станет пустым после выполнения операции. Методы insert First и remove Last представлены на рис. 4.10

Таким образом, двусвязный спиЬок позволяет реализс*вывать все методы АТД «дек» за время 0(1). Во фрагменте кода 4.14 представлены части реализации дека на основе двусвязного списка. Обратите внимание на использование сигнальных уздов и присвоение им первоначальных значений конструктором класса MyDeque.

В табл. 4.3 показано время выполнения методов при реализации дека на основе двусвязного списка. Видно, что в таблице указаны худшие показатели времени выполнения 0(1) методов дека при данной реализации.

Метод

Время

size

0(1)

isEmpty

. 0(1)

first

0(1)

last

0(1)

insertFirst

0(1)

insertLast

0(1)

removeFirst

0(1)

removeLast

0(1)

Таблица 4.3. Выполнение дека, реализованного на основе двусвязного списка. Размер занимаемого пространства есть 0(п)у где п — число элементов дека

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

По теме:

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