List

The <#7764#>List<#7764#> class is the most basic linked data structure class in the system. It is templated by element type and it stores its elements in <#7765#>ListNodes<#7765#>, which can be referenced through <#7766#>ContainerNode<#7766#> pointers. Figure~#fig:List1#7761> contains a coding sample showing the construction of empty <#7767#>Lists<#7767#> and some operations with elements and <#7768#>ContainerNodes<#7768#>. <#7762#>
Figure 2.4: <#7800#>List<#7800#> objects
#figure7762#

<#7762#> Note that receiveing <#7801#>ContainerNode<#7801#> pointers as return values is useful since they providing entry points into the list and enable operations such as <#7795#>predecessor()<#7795#> and <#7796#>successor()<#7796#> to run in constant time. When we consider the doubly-linked list (<#7802#>DList<#7802#>) class, this feature will also permit constant time linking and unlinking of list nodes. It is possible to construct new <#7803#>List<#7803#> objects from existing ones using both 59 constructors and the assignment operator, as shown in Figure~#fig:List3#7797> below. These operations iterate through the source <#7804#>List<#7804#>, inserting elements in the same order into the destination <#7805#>List<#7805#>. Note that if this presents an efficiency problem, <#7806#>Collections<#7806#> should be used. These implement reference counting (see Section~#sec:collection#7798>). <#7799#>
Figure 2.5: <#7821#>List<#7821#> constructors
#figure7799#

<#7799#> <#7822#>Lists<#7822#> are the default implementation for <#7823#>Sequences<#7823#>, which will be discussed in Section~#sec:sequence#7819>. The default implementation for <#7824#>Sets<#7824#> and <#7825#>MSets<#7825#> (multisets) is <#7826#>SortedList<#7826#>, a child class of <#7827#>List<#7827#>. <#7820#>When the LINK interface switches to STk, <#7828#>Lists<#7828#> will have special significance since they will be implemented using the same underlying memory structure as STk objects<#7820#>. <#7829#>1. Creation<#7829#>


<#7831#>
<#7833#>
Figure 2.5: <#7821#>List<#7821#> constructors
List<#7856#>;SPMlt;<#7856#>Item<#7858#>;SPMgt;<#7858#> l;
<#7833#>
<#7837#>
Construct a singly-linked list <#7860#>l<#7860#>.

<#7837#>

<#7831#>

<#7842#>
<#7844#>
List<#7862#>;SPMlt;<#7862#>Item<#7864#>;SPMgt;<#7864#> l2(c);
<#7844#>
<#7848#>
Construct a singly-linked list <#7866#>l2<#7866#> and initialize it with the elements of <#7853#>Container<#7853#> <#7868#>c<#7868#> such that the elements are in the same order.

<#7848#>

<#7842#>

<#7854#>2. Operations<#7854#>


<#7874#>
<#7876#>
List<#8138#>;SPMlt;<#8138#>Item<#8140#>;SPMgt;<#8140#>& operator=(List<#8142#>;SPMlt;<#8142#>Item<#8144#>;SPMgt;<#8144#>& list)
<#7876#>
<#7881#>
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. <#8146#>O(n)<#8146#>

<#7881#>

<#7874#>

<#7886#>
<#7888#>
int size()
<#7888#>
<#7893#>
Return the number of items stored in the current list. In order to allow a smooth interface with Scheme, no element count is maintained. <#8148#>O(n)<#8148#>

<#7893#>

<#7886#>

<#7898#>
<#7900#>
Bool memberQ(Item& item)
<#7900#>
<#7905#>
Indicate whether item is in list or not. <#8150#>O(n)<#8150#>

<#7905#>

<#7898#>

<#7910#>
<#7912#>
Bool sortedQ() const
<#7912#>
<#7917#>
Return FALSE. <#8152#>O(1)<#8152#>.

<#7917#>

<#7910#>

<#7922#>
<#7924#>
ContainerNode* search(Item& item)
<#7924#>
<#7929#>
Search for item and return a pointer to the node which contains it. <#8154#>O(n)<#8154#>

<#7929#>

<#7922#>

<#7934#>
<#7936#>
Bool emptyQ()
<#7936#>
<#7941#>
Return true if list is empty. <#8156#>O(1)<#8156#>

<#7941#>

<#7934#>

<#7946#>
<#7948#>
Item get()
<#7948#>
<#7953#>
Return first element in the of list and remove it. <#8158#>O(1)<#8158#> <#7955#>Caution:<#7955#> If the list is empty, this routine returns an uninitialized <#7956#>Item<#7956#> object.

<#7953#>

<#7946#>

<#7960#>
<#7962#>
Item first()
<#7962#>
<#7967#>
Return the first item. <#8160#>O(1)<#8160#> <#7969#>Caution:<#7969#> If the list is empty, this routine returns an uninitialized <#7970#>Item<#7970#> object.

<#7967#>

<#7960#>

<#7974#>
<#7976#>
Item last()
<#7976#>
<#7981#>
Return the last item. <#8162#>O(n)<#8162#> <#7983#>Caution<#7983#> If the list is empty, this routine returns an uninitialized <#7984#>Item<#7984#> object.

<#7981#>

<#7974#>

<#7988#>
<#7990#>
ContainerNode* prepend(Item item)
<#7990#>
<#7995#>
Insert the item at the beginning of list. <#8164#>O(1)<#8164#>

<#7995#>

<#7988#>

<#8000#>
<#8002#>
ContainerNode* insert(Item item)
<#8002#>
<#8007#>
Insert the item at the beginning of the list. <#8166#>O(1)<#8166#> The redundancy in naming is to maintain naming consistency with <#8128#>Collection<#8128#> member functions.

<#8007#>

<#8000#>

<#8012#>
<#8014#>
ContainerNode* append(Item item)
<#8014#>
<#8019#>
Append the item to the back of list. <#8168#>O(n)<#8168#>

<#8019#>

<#8012#>

<#8024#>
<#8026#>
ContainerNode* insertBefore(Item item, ContainerNode *n)
<#8026#>
<#8031#>
Insert the item before node n. <#8170#>O(1)<#8170#>

<#8031#>

<#8024#>

<#8036#>
<#8038#>
ContainerNode* insertAfter(Item item, ContainerNode *n)
<#8038#>
<#8043#>
Insert the item after node n. <#8172#>O(1)<#8172#>

<#8043#>

<#8036#>

<#8048#>
<#8050#>
void remove(Item item)
<#8050#>
<#8055#>
Remove the item from list and delete the <#8129#>ListNode<#8129#> which contained it. <#8174#>O(n)<#8174#>

<#8055#>

<#8048#>

<#8060#>
<#8062#>
void clear()
<#8062#>
<#8067#>
Remove all items from the list and delete their associated <#8130#>ListNodes<#8130#>. <#8176#>O(n)<#8176#> <#8069#>Note:<#8069#> This will become <#8178#>O(1)<#8178#> with the Scheme interface, since periodic garbage collection cleans up memory

<#8067#>

<#8060#>

<#8073#>
<#8075#>
ContainerNode* predecessor(const ContainerNode *n)
<#8075#>
<#8080#>
Return the node preceding <#8180#>n<#8180#> in list order. <#8182#>O(1)<#8182#>

<#8080#>

<#8073#>

<#8085#>
<#8087#>
ContainerNode* successor(const ContainerNode *n) const
<#8087#>
<#8092#>
Return the node succeeding <#8184#>n<#8184#> in list order. <#8186#>O(1)<#8186#>

<#8092#>

<#8085#>

<#8097#>
<#8099#>
ostream& display(ostream& os)
<#8099#>
<#8104#>
Output the list to the output stream <#8106#>os<#8106#>. Uses <#8107#>Container::displayItem(...)<#8107#> to display each element. <#8188#>O(n)<#8188#>

<#8104#>

<#8097#>

<#8111#>
<#8113#>
int rank(Item& item)
<#8113#>
<#8118#>
Return the position of the item in the list. <#8190#>O(n)<#8190#>

<#8118#>

<#8111#>