The <#8462#>DList<#8462#>, or doubly-linked list, class is useful for implementing
algorithms in which it is essential that constant-time splicing and
unsplicing of list elements be supported. The node type used
with this data structure differs from that of <#8463#>List<#8463#> since it contains
a predecessor pointer. However, the <#8464#>Container<#8464#> hierarchy ensures
that objects of class <#8465#>List<#8465#> and <#8466#>DList<#8466#> can interact easily.
Copy construction, inter-assignment, and comparison of <#8467#>Container<#8467#>
objects are still automatic.
Code using <#8468#>DList<#8468#> objects is similar to that using <#8469#>List<#8469#> objects;
most methods are the same (the exceptions are enumerated below).
As with the singly-linked <#8470#>List<#8470#> object, <#8471#>ContainerNode<#8471#> pointers
provide are used by the programmer to keep track of individual nodes,
as shown in Figure~#fig:DList1#8459>.
<#8460#>
Figure 2.8:
<#8542#>DList<#8542#>
#figure8460#
<#8460#>
Some important applications such as bucket sorting require that
nodes be spliced in and out of various doubly-linked lists very
frequently. Such applications cannot be implemented efficiently
using singly-linked lists due to the search overhead required to
find predecessors of moving nodes. The <#8543#>DList<#8543#> class has additional
methods which allow insertion and removal of <#8544#>ContainerNodes<#8544#> from
the <#8545#>List<#8545#> (as opposed to elements), illustrated in
Figure~#fig:DList3#8540>.
<#8541#>
Figure 2.9:
Special <#8560#>DList<#8560#> operations
#figure8541#
<#8541#>
Once again, comparison and display of <#8561#>SimpleContainer<#8561#> objects
is consistent. The example in Figure~#fig:DList2#8558>
provides another illustration.
<#8559#>
Figure 2.10:
Comparisons of <#8574#>List<#8574#> and <#8575#>DList<#8575#>
#figure8559#
<#8559#>
<#8576#>DList<#8576#> objects have the same methods as <#8577#>List<#8577#> objects with the
following exceptions:
<#8578#>1. Creation<#8578#>
<#8580#>
<#8582#>
Figure 2.10:
Comparisons of <#8574#>List<#8574#> and <#8575#>DList<#8575#>
<#8593#>
<#8597#> Construct a doubly-linked list <#8615#>l2<#8615#> and initialize
it with the elements of <#8602#>Container<#8602#> <#8617#>l<#8617#> such that the
elements are in the same order. <#8597#> <#8591#>
<#8625#>
<#8630#> If the current list is different from the passed list,
then remove any elements in the current list and iterate
through the elements of the passed list, inserting them
into the current list. <#8686#>O(n)<#8686#> <#8630#> <#8623#>
<#8635#>
<#8637#>
ContainerNode*
insert(ContainerNode *cn)
<#8637#>
<#8642#> Insert the item stored in node <#8644#>cn<#8644#>
at the beginning of the list. <#8688#>O(1)<#8688#>.
This enables users who have saved pointers to
certain elements to move them between <#8661#>DLists<#8661#> efficiently. <#8690#>O(1)<#8690#> <#8642#> <#8635#>
<#8648#>
<#8650#>
ContainerNode*
unlink(ContainerNode *cn)
<#8650#>
<#8655#> Remove a node from the list. <#8692#>O(1)<#8692#> <#8655#> <#8648#>