4.3: Bidirectional Lists

Last updated
Save as PDF

Page ID: 49277

Wikibooks - Data Structures
Wikipedia

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

Sometimes we want Data Structures/List Structures to move backward in a list too. A Bidirectional List allows the list to be searched forwards and backwards. A Bidirectional list implements an additional iterator function, move-previous().

Bidirectional List<item-type> ADT

get-begin():Bidirectional List Iterator<item-type>

Returns the list iterator (we'll define this soon) that represents the first element of the list. Runs in \(O(1)\) time.

get-end():Bidirectional List Iterator<item-type>

Returns the list iterator that represents one element past the last element in the list. Runs in \(O(1)\) time.

insert(iter:Bidirectional List Iterator<item-type>, new-item:item-type)

Adds a new element immediately before iter. Runs in \(O(N)\) time.

remove(iter:Bidirectional List Iterator<item-type>)

Removes the element immediately referred to by iter. After this call, iter will refer to the next element in the list. Runs in \(O(N)\) time.

is-empty():Boolean

True iff there are no elements in the list. Has a default implementation. Runs in \(O(1)\) time.

get-size():Integer

Returns the number of elements in the list. Has a default implementation. Runs in \(O(N)\) time.

get-nth(n:Integer):item-type

Returns the nth element in the list, counting from 0. Has a default implementation. Runs in \(O(N)\) time.

set-nth(n:Integer, new-value:item-type)

Assigns a new value to the nth element in the list, counting from 0. Has a default implementation. Runs in \(O(N)\) time.

Bidirectional List Iterator<item-type> ADT

get-value():item-type

Returns the value of the list element that this iterator refers to. Undefined if the iterator is past-the-end.

set-value(new-value:item-type)

Assigns a new value to the list element that this iterator refers to. Undefined if the iterator is past-the-end.

move-next()

Makes this iterator refer to the next element in the list. Undefined if the iterator is past-the-end.

move-previous()

Makes this iterator refer to the previous element in the list. Undefined if the iterator refers to the first list element.

equal(other-iter:List Iterator<item-type>):Boolean

True iff the other iterator refers to the same list element as this iterator.

All operations run in \(O(1)\) time.