This class examines list iteration, and compares the 22.3 Iteration Here is an example of the use of iteration to add the elements of List<int> z. The First() member function is used to set Current_Pos to point to the first element. Then, iteration continues until !z returns FALSE, bumping Current_Pos to the next Node on each iteration.
main
{
22.4 Copy Construction
template <class T>
List_Head = new Node<T>; // make a new list header node
Here is an assignment operator for List. In this operator, the lhs
template <class Etype>
Delete_List(); // throw away old lhs
Node<Etype> *old_current = Value.Current_Pos; // save rhs current
Current_Pos = List_Head = new Node<Etype>;
for( Value.First( ); !Value; ++Value )
Current_Pos>Next = 0;
return *this;
2.5 Miscellaneous Notes on List
QUESTION: If the list is empty, First does nothing. Is this a ANSWER: 23 Comparison of Array and Linked Implementations
array and linked-list implementation's running time for List operations
Note that operator ++ is the prefix operator, not the postfix operator.
If Current Pos_is NULL, the operator returns the Element of the header Node
(which presumably has some special value indicating that it's the header).
int sum = 0;
for (z.First(); !z; ++z)
sum = sum + z();
}
List<T>::List(List<T> & Value)
{
Node<T> *P; // pointer to traverse new list (i.e., *this)
Node<T> *Q; // pointer to traverse Value
P = List_Head;
for (Q = Value.List_Head>Next; Q; Q = Q>Next)
{
P>Next = new Node<T>;
P>Next>Element = Q>Element;
P = P>Next;
if (Q == Value.Current_Pos)
Current_Pos = P;
}
}
Current_Pos is unchanged. Also, the rhs Current_Pos is set to the equivalent
node from the rhs. The old lhs internal list is deleted and the list
is rebuilt from scratch.
const List<Etype> &List<Etype>:: operator = ( List<Etype> & Value )
{
if( this == &Value ) // Don't copy to yourself!
return *this;
Node<Etype> *new_current; // new Current_Pos for lhs
{
Current_Pos>Next = new Node<Etype>( Value( ), Current—Pos>Next );
Current_Pos = Current_Pos>Next;
if (Value.Current_Pos == old_current)
new_current = Current_Pos;
}
Value.Current_Pos = old_current; // restore rhs Current_Pos
Current_Pos = new_current; // lhs equivalent for Current_Pos
}
reasonable thing to do?
Operation |
Array |
Linked
|
Is Empty? |
length == 0 O(1) |
List_Head>Next == NULL O(1)
|
Find |
Scan array O(n) |
Scan list O(n)
|
First |
Set Current_Pos O(1) |
Set Current_Pos O(1)
|
Remove |
Shift elements down O(n) |
Delete node O(1)
|
Insert |
Shift elements up O(n) |
O(1)
|
Storage |
O(n) |
Used O(n) storage for links, too
|