DList

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#>
DList<#8605#>;SPMlt;<#8605#>Item<#8607#>;SPMgt;<#8607#> l;
<#8582#>
<#8586#>

Construct a doubly-linked list <#8609#>l<#8609#>.


<#8586#>


<#8580#>

<#8591#>

<#8593#>
List<#8611#>;SPMlt;<#8611#>Item<#8613#>;SPMgt;<#8613#> l2(l);
<#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#>

<#8603#>2. Operations<#8603#>


<#8623#>

<#8625#>
List<#8678#>;SPMlt;<#8678#>Item<#8680#>;SPMgt;<#8680#>& operator=(List<#8682#>;SPMlt;<#8682#>Item<#8684#>;SPMgt;<#8684#>& list)
<#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#>