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

0

Одним изрозможных вариантов является реализация последовательности на основе двусвязного списка. В этом случае все методы АТД «список» реализуются таким образом, что время их выполнения равно 0(1). Методы же АТД «вектор» также могут быть реализованы с помощью . двусэяздого списка,, хотя’д ,м$нее.эффективно. В частности^ для эффективного выполнения методов списка (с использованием позиций в качестве указателей места доступа и обновления списка) не обязательно явно сохранять разряды элементов последовательности. Другими словами, для выполнения операции elemAtRank(r) необходимо переходить по ссылке от одного конца списка к другому, до тех пор пока не обнаружится узел, содержащий элемент с разрядом г. Чтобы несколько облегчить задачу, поиск можно начать с ближайшего конца последовательности, в результате чего время выполнения составит

Q(min(r + 1, л – г)), то есть О(п). Худшими условиями является

r=ln / 2J-

Операции insertAtRank(r,e) и removeAtRank(r) также используют переход по ссылке для обнаружения узла, содержащего элемент с разрядом г, после’ чего добавляют либо удаляют указанный узел, как показано на рис. 5.6 и 5.7. При такой реализации время выполнения insertAtRank(r,e) и removeAtRank(r) будет

0(min(r + 1, п – г + 1)),

что соответствует О(п). Преимущество этого подхода состоит в том, что при г = 0 или г= п, как в случае адаптации АТД «вектор» к АТД «дек», рассмотренному в п. 5.1.1, время выполнения операций insert At Rank(r,e) и removeAtRank(r) есть 0(1).

Во фрагменте кода 5.12 показаны отрывки Java-реализации интерфейса Sequence на основе двусвязного списка. Здесь видно, что данной реализацией является класс NodeSequence, который наследует (в соответствии с правилами наследования классов) реализацию списка из п. 5.3.2. Как и родительский класс NodeList, класс NodeSequence использует класс DNode, который реализует узлы двусвязного списка. Кроме того, класс-наследник применяет внутренний метод безопасности checkRank(r), который генерирует исключение Boundary Violation Exception при недействительном значении разряда г, то есть

г < 0 или г > п— 1.

Наихудшие условия выполнения методов вектора, реализованных на основе двусвязного списка, аналогичны условиям реализации с помощью массива (см. табл. 5.2), за исключением метода elemAtRank. При реализации на основе двусвязного списка требуется пространство 0(п), что пропорционально числу элементов, представленных в последовательности. В то же время при реализации на основе массива требуемое пространство пропорционально длине этого массива. Но, с другой стороны, реализация метода elemAtRank более эффективна на основе массива, так как

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

public class NodeSequence extends NodeList implements Sequence { // проверяет, находится ли разряд в интервале [O.numElt-1]; время 0(1). protected void checkRank(int rank)

throws BoundaryViolationException { if (rank < О II rank >= numElts)

throw new BoundaryViolationException("Rank" + rank + " is invalid for this sequence of " + numElts + "elements.");

}

public Position atRank (int rank) { // время 0(1) DNode node; checkRank(rank);

if (rank <= size()/2) { // просматривает последовательность // от начала node = header.getNext(); for (int i=0; i < rank; i++) node = node.getNext();

}

else { // просматривает последовательность с конца node = trailer.getPrevQ; for (int i=1; i < size() – rank; i++) node = node.getPrev();

}

return node;

}

II… (пропускаем методы elemAtRank(r) и rankOf(p)) public void insertAtRank (int rank, Object element)

throws BoundaryViolationException { // время 0(n) if (rank == size()) // в данном случае не выполняется checkRank .

ipsertLast(element); else {

checkRank(rank);

insertBefore(atRank(rank), element);

}

}

public Object removeAtRank (int rank) // время 0(n) throws BoundaryViolationException { checkRank(rank); return remove(atRank(rank));

}

public Object replaceAtRank (int rank. Object element)

throws BoundaryViolationException { // время 0(n)

checkRank(rank);

return replaceElement(atRank(rank),element);

Фрагмент кода 5.12. Части реализации интерфейса Sequence на основе двусвязного списка

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

По теме:

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