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

0

Предположим, необходимо создать АТД «список» с помощью дважды связного списка. В самом простом случае узлы двусвязного списка будут соответствовать позиции АТД. Другими словами, каждый узел реализует интерфейс Position и, следовательно, содержит метод element(), который возвращает элемент, хранящийся в данном узле. Таким образом, сами узлы выступают в качестве позиций, имея двойственный характер: с одной стороны, это внутренние узлы связного списка, а с другой — традиционные позиции. Таким образом, для каждого узла v можно задать переменные next и prev, осуществляющие обращения соответственно к последующему и предыдущему узлам (которые могут быть просто сигнальными узлами, обозначающими начало или конец списка). Далее с точки зрения позиции в S «откроем» позицию р, чтобы найти узел v. Эта операция выполняется с помощью приведения типа позиции к узлу. Поскольку действия осуществляются с узлами, можно выполнить метод before(/?), возвращая v.prev (при условии, что v.prev не является головным сигнальным узлом, иначе это приведет к ошибке). Таким образом, позиции списка при реализации двусвязным списком используют преимущества объектно-ориентированного программирования, причем для этого не требуются дополнительные затраты места и времени. Кроме того, данный подход позволяет скрыть детали реализации, что обеспечивает возможность неоднократного использования кода, так как пользователь не будет знать, что позиционные объекты, передаваемые и возвращаемые как параметры, в действительности являются объектами узлов.

Во фрагменте кода 5.3 показан Java-Knacc DNode для узлов двусвязного списка, представляющих позиции АТД. Этот класс напоминает класс

DLNode, показанный фрагментом кода 4.13. Из фрагмента кода 5.3 видно, что переменные next и prev являются закрытыми ссылками на другие объекты класса DNode. Благодаря закрытости этих ссылок обеспечивается необходимая степень инкапсуляции, поскольку способ реализации узлов скрыт. Более того, с помощью указанных простых переменных двусвязный список можно использовать для выполнения всех методов АТД За время 0(1). Отсюда следует, что двусвязный список является эффективной реализацией АТД «список».

class DNode implements Position {

private DNode prev, next; // ссылки на предшествующий и последующий

// узлы

private Object element; // элемент, хранящийся в данной позиции

// конструктор

public DNode(DNode newPrev, DNode newNext, Object elem) { prev = newPrev; next = newNext;

element = elem; }

// метод интерфейса Position

public Object element() throws InvalidPositionException { if ((prev == null) && (next == null))

throw new lnvalidPositionException("Positionisnotinalist!M); return element;

}

// аксессорные методы public DNode getNext() { return next; } public DNode getPrev() { return prev; } // методы обновления

public void setNext(DNode newNext) { next = newNext; } public void setPrev(DNode newPrev) { prev = newPrev; } public void setElement(Object newElement) { element = newElement; }

Фрагмент кода 5.3. Класс DNode, реализующий узел двусвязного списка и интерфейс Position (АТД). Обратите внимание на использование методов доступа и обновления для обработки переменных

Метод element класса DNode реализует исключение InvalidPositionException, если поля next и prev обращаются к нулевому объекту. Код этого исключения представлен во фрагменте кода 5.4.

// исключение исполняющей среды для несуществующих позиций public class InvalidPositionException extends RuntimeException { public lnvalidPositionException(String err) { super(err);

}

}

Фрагмент кода 5.4. Исключение InvalidPositionException для позиций, неверно указанных при выполнении программы. Следует отметить, что данный класс является наследником класса RuntimeException, который описывает условия ошибки, возникающие в ходе выполнения

Рассмотрим реализацию метода insertAfter(p,e), который выполняет вставку новогб элемента е после позиции р. Создадим новый узел v, в котором будет храниться объект е, «вплетаем» v в список, после чего обновляем ссылки next и prev соседних с v узлов. Псевдокод данного метода представлен во фрагменте кода 5.5 и наглядно продемонстрирован на рис. 5.6. Возвращаясь к рассмотрению сигнальных узлов (п. 4.4.2), обратите внимание на выполнение алгоритма даже при р — последней имеющейся позиции.

Алгоритм insertAfter(/?,e): Create a new node v y.setElement(e)

y.setPrev(p) { связывает v с предшествующим узлом } y.setNext(p.getNext()) { связывает v с последующим узлом } (p.getNext()).setPrev(i/) { связывает ранее следовавший за р узел с v } p.setNext(v) { связывает р с новым последующим узлом v } return v { позиция элемента е }

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

Алгоритмы методов insertBefore, insertFirst и insertLast аналогичны алгоритму метода insertAfter и предложены для рассмотрения в упражнении М-5.4. Рассмотрим метод remove(/?), который удаляет элемент е, хранящийся в позиции р. При этом перенаправим ссылки двух соседних с р узлов друг на друга, после чего р удаляется из списка. Видно, что после удаления р ни один узел не будет указывать на него, следовательно, место, выделенное для р, будет утилизировано «сборщиком мусора». Алгоритм показан фрагментом кода 5.6 и наглядно продемонстрирован на рис. 5.7. Возвращаясь к рассмотрению сигнальных узлов, обратите внимание, что этот алгоритм выполняется, даже если р является первой, последней и единственной позицией в списке.

(а)

(b)

(С)

Рис. 5.6. Добавление нового узла после позиции «Балтимор»: (а) до вставки; (Ь) создание нового узла и его связывание; (с) послб вставки

 

(a)

(b)

(c)

Рис. 5.7. Удаление объекта, хранящегося в позиции «Париж»: (а) до удаления; (Ь) удаление старого узла; (с) после удаления (и сбора мусора)

 

Алгоритм remove (/?):

t <- p.element { временная переменная для обозначения }

{ возвращаемого значения } (p.getPrev()).setNext(p.getNext()) { удаление р } (p.getNext()).setPrev(p.getPrev()) p.setPrev(null) { неверная позиция р } p.setNext(null) return t

Фрагмент кода 5.6. Удаление элемента е, хранящегося в позиции р связного списка

Во фрагментах кода 5.8-5.10 представлены отрывки Java-icrcacca Node List, который реализует АТД «список» с помощью двусвязного списка. Особый интерфейс List представлен во фрагменте кода 5.7.

public interface List { public int size(); public boolean isEmptyO;

public boolean isFirst(Position p) throws InvalidPositionException; ‘ public boolean isLast(Position p) throws InvalidPositionException; public Position first() throws EmptyContainerException; public Position last() throws EmptyContainerException; public Position before (Position p)

throws InvalidPositionException, BoundaryViolationException; public Position after (Position p)

throws InvalidPositionException, BoundaryViolationException; public Position insertBefore (Position p, Object element)

throws InvalidPositionException; public Position insertAfter (Position p, Object element)

throws InvalidPositionException; public Position insertFirst(Object element); public Position insertLast(Object element);

public Object remove(Position p) throws InvalidPositionException; public Object replaceElement (Position p, Object element)

throws InvalidPositionException; public void swapElements (Position a, Position b) throws InvalidPositionException;

}

Фрагмент кода 5.7. Интерфейс List

При обработке ошибок используются следующие исключения:

EmptyContainerException: генерируется при попытке доступа к элементам пустого списка (например, с помощью метода first).

BoundaryViolationException: генерируется при попытке доступа к элементу списка, позиция которого не входит в диапазон позиций данного списка.

InvalidPositionException: генерируется, если передаваемая в качестве аргумента позиция недействительна (например, является нулевой ссылкой или не относится к данному списку).

Во фрагменте кода 5.8 показаны переменные класса NodeList, его конструктор, несколько методов доступа и «удобный» метод checkPosition, который в целях безопасности проверяет и «раскрывает» позицию, преобразуя ее назад в объект класса DNode. Фрагмент кода 5.9 содержит дополнительные методы доступа и обновления, а фрагмент 5.10 — дополнительные методы обновления.

public class NodeList implements List {

protected int numElts;                                                          // число элементов списка

• protected DNode header, trailer; // сигнальные узлы // конструктор; время 0(1) public NodeList() { numElts = 0;

header = new DIMode(null, null, null); // создает header trailer = new DNode(header, null, null); // создает trailer header.setNext(trailer); // создает взаимосвязь между header и

trailer }

// функция безопасности; время 0(1). protected DNode checkPosition(Position p) throws InvalidPositionException { if (p == null)

throw new InvalidPositionException

("Null Position passed to NodeList."); if (p == header)

throw new InvalidPositionException

("The header node is not a valid position"); if (p == trailer)

throw new InvalidPositionException

("The trailer node is not a valid position");

try {

DNode temp = (DNode)p;

if ((temp.getPrev() == null) II (temp.getNext() == null)) throw new InvalidPositionException

("Position does not belong to a valid NodeList"); return temp; } catch (ClassCastException e) {

8 Зак 2456

throw new InvalidPositionException

("Position is of wrong type for this container.11);

}

}

// обычные методы доступа:

public int size() { return numElts; }                                                     // время 0(1)

public boolean isEmpty() { return (numElts < 1); J // время 0(1) public boolean isFirst(Position p)     // время 0(1)-

throws InvalidPositionException { DNode v = checkPosition(p); return v.getPrev() == header;

}

Фрагмент кода 5.8. Части класса NodeList: переменные, конструктор, функция безопасности и несколько простых методов доступа (см. фрагменты кода 5.9 и 5.10)

public Position first()                                          // время 0(1)

throws EmptyContainerException { if (isEmpty())

throw new EmptyContainerExceptionf’List is empty"); return header.getNext();

}

public Position last() .                                         // время 0(1)

throws EmptyContainerException { if (isEmptyO)

throw new EmptyContainerException("List is empty"); return trailer.getPrev();

}

public Position before(Position p)                           // время 0(1)

throws InvalidPositionException, BoundaryViolationException { DNode v = checkPosition(p); DNode prev = v.getPrev(); if (prev == header)

throw new BoundaryViolationException ("Cannot advance past the beginning of the list"); return prev;

}

public Position insertBefore(Position p, Object element)

throws InvalidPositionException {                                     // время 0(1)

DNode v = checkPosition(p); numElts++;

DNode newNode = new DNode(v.getPrev(), v, element);

v.getPrev().setNext(newNode);

v.setPrev(newNode);

return newNode;

}.

public Position insertFirst(Object element) {                                            // время 0(1)

numElts++;

DNode newNode = new DNode(header, header.getNext(), element);

header.getNext().setPrev(newNode);

header.setNext(newNode);

return newNode;

}

Фрагмент кода 5.9. Дополнительные методы доступа и вставки класса Node List (см. фрагменты кода 5.8 и 5.10)

public Object remove( Position p)                                     // время 0(1)

throws InvalidPositionException { DNode v = checkPosition(p); numElts—;

DNode vPrev = v.getPrev(); DNode yNext = v.getNext(); vPrev.setNext(vNext); vNext.setPrev(vPrev); Object vElem = v.element();

// удаляет позицию из списка, делая ее недействительной

v.setPrev(null);

return vElem;

}

public Object replaceElement(Position p. Object element) throws InvalidPositionException { // время 0(1) DNode v = checkPosition(p); Object oldElt = v.element(); v.setElement(element); return oldElt;

}

public void swapElements(Position a, Position b)

throws InvalidPositionException { // время 0(1) DNode pA = checkPosition(a); DNode pB = checkPosition(b); Object temp = pA.element(); pA.setElement(pB.element()); pB.setElement(temp);

}

Фрагмент кода 5.10. Дополнительные методы удаления и обновления класса NodeList. Обратите внимание, что механизм превращения позиции в недействительную в методе remove соответствует одной из проверок, выполняемых функцией checkPosition (см. фрагменты кодов 5.8 и 5.9)

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

По теме:

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