Question? Leave a message!




Linked Lists

Linked Lists
ECE 250 Algorithms and Data Structures Linked Lists Douglas Wilhelm Harder, M.Math. LEL Department of Electrical and Computer Engineering University of Waterloo Waterloo, Ontario, Canada ece.uwaterloo.ca dwharderalumni.uwaterloo.ca © 20062013 by Douglas Wilhelm Harder. Some rights reserved.Linked Lists 2 Outline In this topic, we will look at linked lists – The Node and List classes – Accessors and mutators – The implementation of various member functions – Stepping through a linked list – Defining the copy and assignment operator – Defining move constructors and move assignment operators – Discussed efficienciesLinked Lists 3 Definition A linked list is a data structure where each object is stored in a node As well as storing data, the node must also contains a reference/pointer to the node containing the next item of dataLinked Lists 4 Linked Lists 1 We must dynamically create the nodes in a linked list Thus, because new returns a pointer, the logical manner in which to track a linked lists is through a pointer A Node class must store the data and a reference to the next node (also a pointer) Linked Lists 5 Node Class 1 The node must store data and a pointer: class Node private: int element; Node nextnode; public: Node( int = 0, Node = nullptr ); int retrieve() const; Node next() const; ;Linked Lists 6 Node Constructor 1.1 The constructor assigns the two member variables based on the arguments Node::Node( int e, Node n ): element( e ), nextnode( n ) // empty constructor The default values are given in the class definition: class Node private: int element; Node nextnode; public: Node( int = 0, Node = nullptr ); int retrieve() const; Node next() const; ;Linked Lists 7 Accessors The two member functions are accessors which simply return the element and the nextnode member variables, respectively int Node::retrieve() const return element; Node Node::next() const return nextnode; Member functions that do not change the object acted upon are variously called accessors, readonly functions, inspectors, and, when it involves simply returning a member variable, gettersLinked Lists 8 Accessors In C++, a member function cannot have the same name as a member variable Possible solutions: Member Member Variables Functions Vary capitalization nextnode Nextnode() or NextNode() Prefix with “get” nextnode getnextnode() / getNextNode() Use an underscore nextnode nextnode() Different names nextnode next() Always use the naming convention and coding styles used by your employer—even if you disagree with them • Consistency aids in maintenanceLinked Lists 9 Linked List Class Because each node in a linked lists refers to the next, the linked list class need only link to the first node in the list The linked list class requires member variable: a pointer to a node class List private: Node listhead; // ... ;Linked Lists 10 Structure To begin, let us look at the internal representation of a linked list Suppose we want a linked list to store the values 42 95 70 81 in this orderLinked Lists 11 Structure A linked list uses linked allocation, and therefore each node may appear anywhere in memory Also the memory required for each node equals the memory required by the member variables – 4 bytes for the linked list (a pointer) – 8 bytes for each node (an int and a pointer) • We are assuming a 32bit machineLinked Lists 12 Structure Such a list could occupy memory as follows: Linked List ObjectLinked Lists 13 Structure The nextnode pointers store the addresses of the next node in the listLinked Lists 14 Structure Because the addresses are arbitrary, we can remove that information:Linked Lists 15 Structure We will clean up the representation as follows: list We do not specify the addresses because they are arbitrary and: – The contents of the circle is the element – The nextnode pointer is represented by an arrowLinked Lists 16 Operations First, we want to create a linked list We also want to be able to: – insert into, – access, and – erase from the elements stored in the linked listLinked Lists 17 Operations We can do them with the following operations: – Adding, retrieving, or removing the value at the front of the linked list void pushfront( int ); int front() const; void popfront(); – We may also want to access the head of the linked list Node head() const; Member functions that may change the object acted upon are variously called mutators, modifiers, and, when it involves changing a single member variable, settersLinked Lists 18 Operations All these operations relate to the first node of the linked list We may want to perform operations on an arbitrary node of the linked list, for example: – Find the number of instances of an integer in the list: int count( int ) const; – Remove all instances of an integer from the list: int erase( int );Linked Lists 19 Linked Lists Additionally, we may wish to check the state: – Is the linked list empty bool empty() const; – How many objects are in the list int size() const; The list is empty when the listhead pointer is set to nullptrLinked Lists 20 Linked Lists Consider this simple (but incomplete) linked list class: class List private: Node listhead; public: List(); // Accessors bool empty() const; int size() const; int front() const; Node head() const; int count( int ) const; // Mutators void pushfront( int ); int popfront(); int erase( int ); ;Linked Lists 21 Linked Lists The constructor initializes the linked list We do not count how may objects are in this list, thus: – we must rely on the last pointer in the linked list to point to a special value – in C++, that standard value is nullptrLinked Lists 22 The Constructor Thus, in the constructor, we assign listhead the value nullptr List::List():listhead( nullptr ) // empty constructor We will always ensure that when a linked list is empty, the list head is assigned nullptrLinked Lists 23 Allocation The constructor is called whenever an object is created, either: Statically The statement List ls; defines ls to be a linked list and the compiler deals with memory allocation Dynamically The statement List pls = new List(); requests sufficient memory from the OS to store an instance of the class – In both cases, the memory is allocated and then the constructor is calledLinked Lists 24 Static Allocation Example: int f() List ls; // ls is declared as a local variable on the stack ls.pushfront( 3 ); cout ls.front() endl; // The return value is evaluated // The compiler then calls the destructor for local variables // The memory allocated for 'ls' is deallocated return 0; Linked Lists 25 Dynamic Allocation Example: List f( int n ) List pls = new List(); // pls is allocated memory by the OS plspushfront( n ); cout plsfront() endl; // The address of the linked list is the return value // After this, the 4 bytes for the pointer 'pls' is deallocated // The memory allocated for the linked list is still there return pls; Linked Lists 26 Static Allocation What if I do List f() List ls; // ls is declared as a local variable on the stack ls.pushfront( 3 ); cout ls.front() endl; // The return value is evaluated // The compiler then calls the destructor for local variables // The memory allocated for 'ls' is deallocated return ls; Linked Lists 27 bool empty() const Starting with the easier member functions: bool List::empty() const if ( listhead == nullptr ) return true; else return false; Better yet: bool List::empty() const return ( listhead == nullptr ); Linked Lists 28 Node head() const The member function Node head() const is easy enough to implement: Node List::head() const return listhead; This will always work: if the list is empty, it will return nullptrLinked Lists 29 int front() const To get the first element in the linked list, we must access the node to which the listhead is pointing Because we have a pointer, we must use the operator to call the member function: int List::front() const return head()retrieve(); Linked Lists 30 int front() const The member function int front() const requires some additional consideration, however: – what if the list is empty If we tried to access a member function of a pointer set to nullptr, we would access restricted memory The operating system would terminate the running programLinked Lists 31 int front() const Instead, we can use an exception handling mechanism where we thrown an exception We define a class class underflow // emtpy ; and then we throw an instance of this class: throw underflow();Linked Lists 32 int front() const Thus, the full function is int List::front() const if ( empty() ) throw underflow(); return head()retrieve(); Linked Lists 33 int front() const Why is emtpy() better than int List::front() const if ( listhead == nullptr ) throw underflow(); return listheadelement; Two benefits: – More readable – If the implementation changes we do nothingLinked Lists 34 void pushfront( int ) Next, let us add an element to the list If it is empty, we start with: and, if we try to add 81, we should end up with:Linked Lists 35 void pushfront( int ) To visualize what we must do: – We must create a new node which: • stores the value 81, and • is pointing to 0 – We must then assign its address to listhead We can do this as follows: listhead = new Node( 81, nullptr ); We could also use the default value...Linked Lists 36 void pushfront( int ) Suppose however, we already have a nonempty list Adding 70, we want:Linked Lists 37 void pushfront( int ) To achieve this, we must we must create a new node which: • stores the value 70, and • is pointing to the current list head – we must then assign its address to listhead We can do this as follows: listhead = new Node( 70, listhead );Linked Lists 38 void pushfront( int ) Thus, our implementation could be: void List::pushfront( int n ) if ( empty() ) listhead = new Node( n, nullptr ); else listhead = new Node( n, head() ); Linked Lists 39 void pushfront( int ) We could, however, note that when the list is empty, listhead == 0, thus we could shorten this to: void List::pushfront( int n ) listhead = new Node( n, listhead ); Linked Lists 40 void pushfront( int ) Are we allowed to do this void List::pushfront( int n ) listhead = new Node( n, head() ); Yes: the righthand side of an assignment is evaluated first – The original value of listhead is accessed first before the function call is made Linked Lists 41 void pushfront( int ) Question: does this work void List::pushfront( int n ) Node newnode( n, head() ); listhead = newnode; Why or why not What happens to newnode How does this differ from void List::pushfront( int n ) Node newnode = new Node( n, head() ); listhead = newnode; Linked Lists 42 int popfront() Erasing from the front of a linked list is even easier: – We assign the list head to the next pointer of the first node Graphically, given: we want:Linked Lists 43 int popfront() Easy enough: int List::popfront() int e = front(); listhead = head()next(); return e; Unfortunately, we have some problems: – The list may be empty – We still have the memory allocated for the node containing 70Linked Lists 44 int popfront() Does this work int List::popfront() if ( empty() ) throw underflow(); int e = front(); delete head(); listhead = head()next(); return e; Linked Lists 45 int popfront() int List::popfront() if ( empty() ) throw underflow(); int e = front(); delete head(); listhead = head()next(); return e; Linked Lists 46 int popfront() int List::popfront() if ( empty() ) throw underflow(); int e = front(); delete head(); listhead = head()next(); return e; Linked Lists 47 int popfront() int List::popfront() if ( empty() ) throw underflow(); int e = front(); delete head(); listhead = head()next(); return e; Linked Lists 48 int popfront() The problem is, we are accessing a node which we have just deleted Unfortunately, this will work more than 99 of the time: – The running program (process) may still own the memory Once in a while it will fail ... ... and it will be almost impossible to debug http://xkcd.com/379/Linked Lists 49 int popfront() The correct implementation assigns a temporary pointer to point to the node being deleted: int List::popfront() if ( empty() ) throw underflow(); int e = front(); Node ptr = listhead; listhead = listheadnext(); delete ptr; return e; Linked Lists 50 int popfront() int List::popfront() if ( empty() ) throw underflow(); int e = front(); Node ptr = head(); listhead = head()next(); delete ptr; return e; Linked Lists 51 int popfront() int List::popfront() if ( empty() ) throw underflow(); int e = front(); Node ptr = head(); listhead = head()next(); delete ptr; return e; Linked Lists 52 int popfront() int List::popfront() if ( empty() ) throw underflow(); int e = front(); Node ptr = head(); listhead = head()next(); delete ptr; return e; Linked Lists 53 int popfront() int List::popfront() if ( empty() ) throw underflow(); int e = front(); Node ptr = head(); listhead = head()next(); delete ptr; return e; Linked Lists 54 Stepping through a Linked List The next step is to look at member functions which potentially require us to step through the entire list: int size() const; int count( int ) const; int erase( int ); The second counts the number of instances of an integer, and the last removes the nodes containing that integerLinked Lists 55 Stepping through a Linked List The process of stepping through a linked list can be thought of as being analogous to a forloop: – We initialize a temporary pointer with the list head – We continue iterating until the pointer equals nullptr – With each step, we set the pointer to point to the next objectLinked Lists 56 Stepping through a Linked List Thus, we have: for ( Node ptr = head(); ptr = nullptr; ptr = ptrnext() ) // do something // use ptrfn() to call member functions // use ptrvar to assign/access member variables Linked Lists 57 Stepping through a Linked List Analogously: for ( Node ptr = head(); ptr = nullptr; ptr = ptrnext() ) for ( int i = 0; i = N; ++i )Linked Lists 58 Stepping through a Linked List With the initialization and first iteration of the loop, we have: ptr = nullptr and thus we evaluate the body of the loop and then set ptr to the next pointer of the node it is pointing toLinked Lists 59 Stepping through a Linked List ptr = nullptr and thus we evaluate the loop and increment the pointer In the loop, we can access the value being pointed to by using ptrretrieve()Linked Lists 60 Stepping through a Linked List ptr = nullptr and thus we evaluate the loop and increment the pointer Also, in the loop, we can access the next node in the list by using ptrnext()Linked Lists 61 Stepping through a Linked List ptr = nullptr and thus we evaluate the loop and increment the pointer This last increment causes ptr == nullptrLinked Lists 62 Stepping through a Linked List Here, we check and find ptr = nullptr is false, and thus we exit the loop Because the variable ptr was declared inside the loop, we can no longer access itLinked Lists 63 int count( int ) const To implement int count(int) const, we simply check if the argument matches the element with each step – Each time we find a match, we increment the count – When the loop is finished, we return the count – The size function is simplification of countLinked Lists 64 int count( int ) const The implementation: int List::count( int n ) const int nodecount = 0; for ( Node ptr = list(); ptr = nullptr; ptr = ptrnext() ) if ( ptrretrieve() == n ) ++nodecount; return nodecount; Linked Lists 65 int erase( int ) To remove an arbitrary element, i.e., to implement int erase( int ), we must update the previous node For example, given if we delete 70, we want to end up withLinked Lists 66 Accessing Private Member Variables Notice that the erase function must modify the member variables of the node prior to the node being removed Thus, it must have access to the member variable nextnode We could supply the member function void setnext( Node ); however, this would be globally accessible Possible solutions: – Friends – Nested classes – Inner classesLinked Lists 67 C++ Friends In C++, you explicitly break encapsulation by declaring the class List to be a friend of the class Node: class Node Node next() const; // ... declaration ... friend class List; ; Now, inside erase (a member function of List), you can modify all the member variables of any instance of the Node classLinked Lists 68 C++ Friends For example, the erase member function could be implemented using the following code: int List::erase( int n ) int nodecount = 0; // ... for ( Node ptr = head(); ptr = nullptr; ptr = ptrnext() ) // ... if ( some condition ) ptrnextnode = ptrnext()next(); // ... ++nodecount; return nodecount; Linked Lists 69 Nested Classes In C++, you can nest one class inside another class Outer private: class Nested private: int element; public: int get() const; void set( int ); ; Nested stored; public: int get() const; void set( int ); ;Linked Lists 70 Nested Classes The function definitions are as one would expect: int Outer::Nested::get() const return element; void Outer::Nested::set( int n ) element = n; int Outer::get() const return stored.get(); void Outer::set( int n ) // Not allowed, as element is private // stored.element = n; stored.set( n ); Linked Lists 71 Inner Classes In Java/C, there is also the notion of an inner class – This is an elegant objectoriented solution – Any instance of the inner class is linked to the instance of the outer class that created it – That inner class can access the member variables of the outer class If Node was an inner class of List, the node could determine its position with the list (not possible in C++): int List::Node::position() const int posn = 1; for ( Node ptr = listhead; ptr = this; ptr = ptrnext() ) // empty loop body return posn; Linked Lists 72 Destructor We dynamically allocated memory each time we added a new int into this list Suppose we delete a list before we remove everything from it – This would leave the memory allocated with no reference to itLinked Lists 73 Destructor Thus, we need a destructor: class List private: Node listhead; public: List(); List(); // ...etc... ;Linked Lists 74 Destructor The destructor has to delete any memory which had been allocated but has not yet been deallocated This is straightforward enough: while ( empty() ) popfront(); Linked Lists 75 Destructor Is this efficient It runs in O(n) time, where n is the number of objects in the linked list Given that delete is approximately 100× slower than most other instructions (it does call the OS), the extra overhead is negligible...Linked Lists 76 Making Copies Is this sufficient for a linked list class Initially, it may appear yes, but we now have to look at how C++ copies objects during: – Passing by value (making a copy), and – AssignmentLinked Lists 77 Pass by Value Recall that when you pass an integer to a function, a copy is made, so any changes to that parameter does not affect the original: include iostream void increment( int n ) ++n; int main() int counter = 0; increment( counter ); std::cout counter std::endl; // counter is still 0 Linked Lists 78 Pass by Reference If you want to change the value, you can pass by reference: include iostream void increment( int n ) ++n; int main() int counter = 0; increment( counter ); std::cout counter std::endl; // counter is now 1 Linked Lists 79 Pass by Pointer (C) In C, you would pass the address of the object to change it: include stdio.h void increment( int pn ) ++(pn); int main() int counter = 0; increment( counter ); printf( "d", counter ); // counter is now 1 Linked Lists 80 Modifying Arguments Pass by reference could be used to modify a list void reverse( List list ) List tmp; while ( list.empty() ) tmp.pushfront( ls.popfront() ); // All the member variables of 'list' and 'tmp' are swapped std::swap( list, tmp ); // The memory for 'tmp' will be cleaned up Linked Lists 81 Modifying Arguments If you wanted to prevent the argument from being modified, you could declare it const: double average( List const ls, int min, int max ) double sum = 0, count = 0; for ( Node ptr = head(); ptr = nullptr; ptr = ptrnext() ) sum += ptrretrieve(); ++count; return sum/count; Note: this reveals a weakness in our model—we will discuss iterators later…Linked Lists 82 Modifying Arguments What if you want to pass a copy of a linked list to a function—where the function can modify the passed argument, but the original is unchanged – By default, all the member variables are simply copied over into the new instance of the class – This is the default copy constructor – Because a copy is made, the destructor must also be called on it void sendcopy( List ls ) // The compiler creates a new instance and copies the values // The function does something with 'ls' // The compiler ensures the destructor is called on 'ls' Linked Lists 83 Modifying Arguments First, the list prim is created and three elements are pushed onto it void sendcopy( List ls ) // The compiler creates a new instance and copies the values // The function does something with 'ls' // The compiler ensures the destructor is called on 'ls' int main() List prim; for ( int i = 2; i = 4; ++i ) prim.pushfront( ii ); sendcopy( prim ); std::cout prim.empty() std::endl; return 0; Linked Lists 84 Modifying Arguments Next, we call sendcopy and assigns the parameter ls a copy of the argument prim – The default is to copy member variables: ls.listhead = prim.listhead void sendcopy( List ls ) // The compiler creates a new instance and copies the values // The function does something with 'ls' // The compiler ensures the destructor is called on 'ls' int main() List prim; for ( int i = 2; i = 4; ++i ) prim.pushfront( ii ); sendcopy( prim ); std::cout prim.empty() std::endl; return 0; Linked Lists 85 Modifying Arguments When sendcopy returns, the destructor is called on the parameter ls void sendcopy( List ls ) // The compiler creates a new instance and copies the values // The function does something with 'ls' // The compiler ensures the destructor is called on 'ls' int main() List prim; for ( int i = 2; i = 4; ++i ) prim.pushfront( ii ); sendcopy( prim ); std::cout prim.empty() std::endl; return 0; Linked Lists 86 Modifying Arguments When sendcopy returns, the destructor is called on the parameter ls void sendcopy( List ls ) // The compiler creates a new instance and copies the values // The function does something with 'ls' // The compiler ensures the destructor is called on 'ls' int main() List prim; for ( int i = 2; i = 4; ++i ) prim.pushfront( ii ); sendcopy( prim ); std::cout prim.empty() std::endl; return 0; Linked Lists 87 Modifying Arguments When sendcopy returns, the destructor is called on the parameter ls void sendcopy( List ls ) // The compiler creates a new instance and copies the values // The function does something with 'ls' // The compiler ensures the destructor is called on 'ls' int main() List prim; for ( int i = 2; i = 4; ++i ) prim.pushfront( ii ); sendcopy( prim ); std::cout prim.empty() std::endl; return 0; Linked Lists 88 Modifying Arguments Back in main(), prim.listhead still stores the address of the Node containing 16, memory that has since been returned to the OS – Additionally, the destructor will be called on prim once main() exits void sendcopy( List ls ) // The compiler creates a new instance and copies the values // The function does something with 'ls' // The compiler ensures the destructor is called on 'ls' int main() List prim; for ( int i = 2; i = 4; ++i ) prim.pushfront( ii ); sendcopy( prim ); std::cout prim.empty() std::endl; return 0; Linked Lists 89 Modifying Arguments What do we really want void sendcopy( List ls ) // The compiler creates a new instance and copies the values // The function does something with 'ls' // The compiler ensures the destructor is called on 'ls' int main() List prim; for ( int i = 2; i = 4; ++i ) prim.pushfront( ii ); sendcopy( prim ); std::cout prim.empty() std::endl; return 0; Linked Lists 90 Modifying Arguments What do we really want – We really want a copy of the linked list – If this copy is modified, it leaves the original unchanged void sendcopy( List ls ) // The compiler creates a new instance and copies the values // The function does something with 'ls' // The compiler ensures the destructor is called on 'ls' int main() List prim; for ( int i = 2; i = 4; ++i ) prim.pushfront( ii ); sendcopy( prim ); std::cout prim.empty() std::endl; return 0; Linked Lists 91 Copy Constructor You can modify how copies are made by defining a copy constructor – The default copy constructor simply copies the member variables – In this case, this is not what we want The signature for the copy constructor is Classname( Classname const ); In this case, we would define the member function List( List const );Linked Lists 92 Copy Constructor If such a function is defined, every time an instance is passed by value, the copy constructor is called to make that copy Additionally, you can use the copy constructor as follows: List ls1; ls1.pushfront( 4 ); ls1.pushfront( 2 ); List ls2( ls1 ); // make a copy of ls1 When an object is returned by value, again, the copy constructor is called to make a copy of the returned valueLinked Lists 93 Copy Constructor Thus, we must define a copy constructor: – The copy constructor allows us to initialize the member variables List::List( List const list ):listhead( nullptr ) // Make a copy of list We now want to go from toLinked Lists 94 Copy Constructor Naïvely, we step through list and call pushfront( int ): List::List( List const list ):listhead( nullptr ) for ( Node ptr = list.head(); ptr = nullptr; ptr = ptrnext() ) pushfront( ptrretrieve() ); Does this work – How could we make this work – We need a pushback( int ) member function: List::List( List const list ):listhead( nullptr ) for ( Node ptr = list.head(); ptr = nullptr; ptr = ptrnext() ) pushback( ptrretrieve() ); Linked Lists 95 Copy Constructor Unfortunately, to make pushback( int ) more efficient, we need a pointer to the last node in the linked list – We require a listtail member variable – Otherwise, pushback( int ) becomes a Q(n) function 2 • This would make the copy constructor Q(n ) – In Project 1, you will define and use the member variable listtailLinked Lists 96 Copy Constructor First, make life simple: if list is empty, we are finished, so return List::List( List const list ):listhead( nullptr ) if ( list.empty() ) return; Linked Lists 97 Copy Constructor Otherwise, the list being copied is not empty… List::List( List const list ):listhead( nullptr ) if ( list.empty() ) return; Linked Lists 98 Copy Constructor Copy the first node—we no longer modifying listhead List::List( List const list ):listhead( nullptr ) if ( list.empty() ) return; pushfront( list.front() ); Linked Lists 99 Copy Constructor We need what we want to copy next and where we want to copy it List::List( List const list ):listhead( nullptr ) if ( list.empty() ) return; pushfront( list.front() ); Note, we will need to loop through the list… How about a for loopLinked Lists 100 Copy Constructor We modify the next pointer of the node pointed to by copy List::List( List const list ):listhead( nullptr ) if ( list.empty() ) return; pushfront( list.front() ); for ( Node original = list.head()next(), copy = head(); original = nullptr; original = originalnext(), copy = copynext() ) copynextnode = new Node( originalretrieve(), nullptr ); Linked Lists 101 Copy Constructor Then we move each pointer forward: List::List( List const list ):listhead( nullptr ) if ( list.empty() ) return; pushfront( list.front() ); for ( Node original = list.head()next(), copy = head(); original = nullptr; original = originalnext(), copy = copynext() ) copynextnode = new Node( originalretrieve(), nullptr ); Linked Lists 102 Copy Constructor We’d continue copying until we reach the end List::List( List const list ):listhead( nullptr ) if ( list.empty() ) return; pushfront( list.front() ); for ( Node original = list.head()next(), copy = head(); original = nullptr; original = originalnext(), copy = copynext() ) copynextnode = new Node( originalretrieve(), nullptr ); Linked Lists 103 Assignment What about assignment – Suppose you have linked lists: List lst1, lst2; lst1.pushfront( 35 ); lst1.pushfront( 18 ); lst2.pushfront( 94 ); lst2.pushfront( 72 );Linked Lists 104 Assignment This is the current state: Consider an assignment: lst2 = lst1; What do we want What should this do – The default is to copy the member variables from lst1 to lst2Linked Lists 105 Assignment Because the only member variable of this class is listhead, the value it is storing (the address of the first node) is copied over It is equivalent to writing: lst2.listhead = lst1.listhead; Graphically:Linked Lists 106 Assignment What’s wrong with this picture – We no longer have links to either of the nodes storing 72 or 94 – Also, suppose we call the member function lst1.popfront(); – This only affects the member variable from the object lst1Linked Lists 107 Assignment Now, the second list lst2 is pointing to memory which has been deallocated... – What is the behavior if we make this call lst2.popfront(); – The behaviour is undefined, however, soon this will probably lead to an access violationLinked Lists 108 Assignment Like making copies, we must have a reasonable means of assigning – Starting with – We need to erase the content of lst2 and copy over the nodes in lst1Linked Lists 109 Assignment First, to overload the assignment operator, we must overload the function named operator = – This is a how you indicate to the compiler that you are overloading the assignment (=) operator The signature is: List operator = ( List );Linked Lists 110 Return by Value Now, suppose you create the following function: List initialize( int a, int b ) List ls; for ( int i = b; i = a; i ) ls.pushfront( i ); return ls; and call List vec = initialize( 3, 6 );Linked Lists 111 Return by Value Because ls is a local variable, it will be garbage collected once the function returns—thus, we would normally make a copy List initialize( int a, int b ) List ls; for ( int i = b; i = a; i ) ls.pushfront( i ); return ls; Linked Lists 112 Return by Value Because ls is a local variable, it will be garbage collected once the function returns—thus, we would normally make a copy – Create a copy List initialize( int a, int b ) List ls; for ( int i = b; i = a; i ) ls.pushfront( i ); return ls; Linked Lists 113 Return by Value Because ls is a local variable, it will be garbage collected once the function returns—thus, we would normally make a copy – Create a copy List initialize( int a, int b ) – Call the destructor on ls List ls; for ( int i = b; i = a; i ) ls.pushfront( i ); return ls; Linked Lists 114 Return by Value Because ls is a local variable, it will be garbage collected once the function returns—thus, we would normally make a copy – Create a copy List initialize( int a, int b ) – Call the destructor on ls List ls; – Remove the memory for ls from the stack for ( int i = b; i = a; i ) ls.pushfront( i ); return ls; Linked Lists 115 Return by Value Why are we allocating and deallocating so much memory – Until C++11, this was the only way List initialize( int a, int b ) List ls; for ( int i = b; i = a; i ) ls.pushfront( i ); return ls; Linked Lists 116 Return by Value Wouldn’t it be easier to link vec.listhead to the first node in ls and then set ls.listhead = nullptr List initialize( int a, int b ) List ls; for ( int i = b; i = a; i ) ls.pushfront( i ); return ls; Linked Lists 117 Return by Value Wouldn’t it be easier to link vec.listhead to the first node in ls and then set ls.listhead = nullptr – The destructor called on ls List initialize( int a, int b ) does nothing and the memory List ls; for it is popped from the stack for ( int i = b; i = a; i ) ls.pushfront( i ); return ls; Linked Lists 118 Move Constructors The move constructor was added to the C++11 standard – It is called when an rvalue is being assigned—as an rvalue, it will be deleted anyway – The instance ls is being deleted as soon as it is copied – If a move constructor is defined, it will be called instead of a copy constructor List( List list ):listhead( list.listhead ) // make 'list' empty so that nothing is // done when it is passed to the destructor list.listhead = nullptr; Linked Lists 119 Assignment The righthand side is passed by value (a copy is made) The return value is passed by reference List operator = ( List rhs ); Note that rhs is a copy of the list, it is not a pointer to a list – Use rhs.head() or rhs.listheadLinked Lists 120 Assignment We will swap all the values of the member variables between the left and righthand sides – rhs is already a copy, so we swap all member variables of it and this List operator = ( List rhs ) // 'rhs' is passed by valueit is a copy of the // righthand side of the assignment // Swap all the entries of the copy with this return this; Linked Lists 121 Assignment Under C++11, the following is the appropriate implementation: List List::operator = ( List rhs ) std::swap( this, rhs ); // Memory for rhs was allocated on the stack // and the destructor will delete it return this; Linked Lists 122 Assignment Until compilers are C++11 compliant, this may be necessary: List List::operator = ( List rhs ) swap( rhs ); // Memory for rhs was allocated on the stack // and the destructor will delete it return this; void List::swap( List list ) std::swap( listhead, list.listhead ); Linked Lists 123 Assignment Visually, we are doing the following: List List::operator = ( List rhs ) swap( this, rhs ); return this; Linked Lists 124 Assignment Visually, we are doing the following: – Passed by value, the copy constructor is called to create rhs List List::operator = ( List rhs ) std::swap( this, rhs ); return this; Linked Lists 125 Assignment Visually, we are doing the following: – Passed by value, the copy constructor is called to create rhs – Swapping the member variables of this and rhs List List::operator = ( List rhs ) std::swap( this, rhs ); return this; Linked Lists 126 Assignment Visually, we are doing the following: – Passed by value, the copy constructor is called to create rhs – Swapping the member variables of this and rhs – We return and the List List::operator = ( List rhs ) destructor is called on rhs std::swap( this, rhs ); return this; Linked Lists 127 Assignment Visually, we are doing the following: – Passed by value, the copy constructor is called to create rhs – Swapping the member variables of this and rhs – We return and the List List::operator = ( List rhs ) destructor is called on rhs std::swap( this, rhs ); return this; – Back in the calling function, the two lists contain the same valuesLinked Lists 128 Assignment Can we do better – This idea of copy and swap is highly visible in the literature – If the copy constructor is written correctly, it will be fast – Is it always the most efficient Consider the calls to new and delete – Each of these is very expensive… – Would it not be better to reuse the nodes if possible Reference: Howard HinnantLinked Lists 129 Assignment Can we do better – This idea of copy and swap is highly visible in the literature – If the copy constructor is written correctly, it will be fast – Is it always the most efficient Consider the calls to new and delete – Each of these is very expensive… – Would it not be better to reuse the nodes if possible – No calls to new or delete Reference: Howard HinnantLinked Lists 130 Assignment What is the plan – First, we must pass by reference—no copying – Ensure we are not assigning something to itself – If the righthand side is empty, it’s straightforward: • Just empty this list – Otherwise, step through the righthand side list and for each node there • If there is a corresponding node in this, copy over the value, else • There is no corresponding node; create a new node and append it – If there are any nodes remaining in this, delete them – Special case: • Dealing with the first node which is pointed to by listhead and not a nextnode member variableLinked Lists 131 Assignment The implementation must be more carefully written List List::operator = ( List const rhs ) if ( this == rhs ) return this; if ( rhs.empty() ) while ( empty() ) popfront(); return this; Linked Lists 132 Assignment if ( empty() ) listhead = new Node( rhs.front() ); else head()element = rhs.front(); Node thisnode = listhead, rhsnode = rhs.head()next(); while ( rhsnode = 0 ) if ( thisnodenext() == 0 ) thisnodenextnode = new Node( rhsnoderetrieve() ); thisnode = thisnodenext(); else thisnodenext(); thisnodeelement = rhsnoderetrive(); rhsnode = rhsnodenext(); Linked Lists 133 Assignment while ( thisnodenext() = 0 ) Node tmp = thisnodenext(); thisnodenextnode = thisnodenext()next(); delete tmp; return this; Linked Lists 134 Move Assignment Similarly, we need a move assignment: List List::operator = ( List rhs ) while ( empty() ) popfront(); listhead = rhs.head(); rhs.listhead = 0; return this; Linked Lists 135 Linked Lists Thus, the complete class is: class List private: Node listhead; void swap( List ); public: // Constructors and destructors List(); List( List const ); // Accessors bool empty() const; List( List ); int size() const; List(); int front() const; Node head() const; // Assignment operators int count( int ) const; List operator = ( List const ); // Mutators List operator = ( List ); void pushfront( int ); int popfront(); int erase( int ); ;Linked Lists 136 Linked Lists With asymptotic analysis of linked lists, we can now make the following statements: front arbitrary back insertQ(1) O(n)Q(n) accessQ(1) O(n)Q(n) eraseQ(1) O(n)Q(n) these become Q(1) if we have a tail pointerLinked Lists 137 Efficient Allocation In all our examples, we use new and delete to allocate and deallocate nodes – This is exceptionally inefficient – It requires the operating system to allocate and deallocate memory with each node – Could we preallocate memory for a number of nodes and use them – SuggestionsLinked Lists 138 Efficient Allocation Consider the following strategy: – Allocate an array of N nodes – The address of the node is the index in the array • Therefore, nextnode is an integer – Each time we require a new node, use one of these – If all the nodes in the block are used, we double the size of the array of the allocated nodes and move the objects over To track which nodes are being used, we could use a stack – Initially, the stack would contain the values from 0 to N– 1 – If we need an unused entry in the array, pop the next index from the top of the stack – If we no longer are using a node, push its index onto the stackLinked Lists 139 Efficient Allocation We would use 1 to represent the end of the list – More intelligently, we would define a constant: int const NULL = 1;Linked Lists 140 Efficient Allocation After a few calls to pushfront and erase, we could end up with an allocation as follows:Linked Lists 141 Efficient Allocation If we wanted to call popfront, we would: – Push 4 onto the stack – Updated listhead to be 7Linked Lists 142 Efficient Allocation If we wanted to call popfront, we would: – Push 4 onto the stack – Updated listhead to be 7 The result:Linked Lists 143 Efficient Allocation If we wanted to push 99 onto the front of this list, we would: – Get to top of the stack, 6 – At this location, place 99 and the current value of listhead – Update listhead = 6Linked Lists 144 Efficient Allocation This results in:Linked Lists 145 Efficient Allocation Originally, we would require n calls to new() to insert n objects into the linked list – This updated allocation strategy requires lg(n) calls to new and n copiesLinked Lists 146 Summary We have considered the implementation of linked lists in C++ – Aspects of the Node class – Accessors and mutators – The implementation of various member functions – Stepping through a linked list – Defining the copy and assignment operator – Defining move constructors and move assignment operators – Discussed efficienciesLinked Lists 147 References nd Donald E. Knuth, The Art of Computer Programming, Volume 3: Sorting and Searching, 2 Ed., Addison Wesley, 1998, §5.4, pp.248379. Wikipedia, https://en.wikipedia.org/wiki/Linkedlist http://stackoverflow.com/erroraspxerrorpath=/questions/8848363/rvaluereferencewithassignementoperator These slides are provided for the ECE 250 Algorithms and Data Structures course. The material in it reflects Douglas W. Harder’s best judgment in light of the information available to him at the time of preparation. Any reliance on these course slides by any party for any other purpose are the responsibility of such parties. Douglas W. Harder accepts no responsibility for damages, if any, suffered by any party as a result of decisions made or actions based on these course slides for any other purpose than that for which it was intended.
Website URL
Comment