Welcome to ECE 250 Algorithms and Data Structures

Welcome to ECE 250 Algorithms and Data Structures

Linked Lists 1 Assignment What about assignment? Suppose you have linked lists: List lst1, lst2; lst1.push_front( lst1.push_front( lst2.push_front( lst2.push_front( 35 18 94

72 ); ); ); ); Linked Lists 2 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 lst2 Linked Lists 3 Assignment Because the only member variable of this class is list_head, the value it is storing (the address of the first node) is copied over It is equivalent to writing: lst2.list_head = lst1.list_head; Graphically: Linked Lists 4

Assignment Whats 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.pop_front(); This only affects the member variable from the object lst1 Linked Lists 5 Assignment Now, the second list lst2 is pointing to memory which has been

deallocated... What is the behavior if we make this call? lst2.pop_front(); The behaviour is undefined, however, soon this will probably lead to an access violation Linked Lists 6 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 lst1

Linked Lists 7 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 8

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.push_front( i ); } return ls; } and call List vec = initialize( 3, 6 ); Linked Lists 9

Return by Value Because ls is a local variable, it will be garbage collected once the function returnsthus, we would normally make a copy List initialize( int a, int b ) { List ls; for ( int i = b; i >= a; --i ) { ls.push_front( i ); } return ls; } Linked Lists 10

Return by Value Because ls is a local variable, it will be garbage collected once the function returnsthus, 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.push_front( i ); } return ls; } Linked Lists 11

Return by Value Because ls is a local variable, it will be garbage collected once the function returnsthus, we would normally make a copy Create a copy Call the destructor on ls List initialize( int a, int b ) { List ls; for ( int i = b; i >= a; --i ) { ls.push_front( i ); } return ls; }

Linked Lists 12 Return by Value Because ls is a local variable, it will be garbage collected once the function returnsthus, we would normally make a copy Create a copy Call the destructor on ls Remove the memory for ls from the stack List initialize( int a, int b ) { List ls; for ( int i = b; i >= a; --i ) { ls.push_front( i );

} return ls; } Linked Lists 13 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.push_front( i ); }

return ls; } Linked Lists 14 Return by Value Wouldnt it be easier to link vec.list_head to the first node in ls and then set ls.list_head = nullptr? List initialize( int a, int b ) { List ls; for ( int i = b; i >= a; --i ) { ls.push_front( i ); } return ls;

} Linked Lists 15 Return by Value Wouldnt it be easier to link vec.list_head to the first node in ls and then set ls.list_head = nullptr? The destructor called on ls does nothing and the memory List initialize( int a, int b ) { List ls; for it is popped from the stack for ( int i = b; i >= a; --i ) { ls.push_front( i ); }

return ls; } Linked Lists 16 Move Constructors The move constructor was added to the C++11 standard It is called when an rvalue is being assignedas 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 ):list_head( list.list_head ) { // make 'list' empty so that nothing is

// done when it is passed to the destructor list.list_head = nullptr; } Linked Lists 17 Assignment The right-hand 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.list_head Linked Lists

18 Assignment We will swap all the values of the member variables between the left- and right-hand sides rhs is already a copy, so we swap all member variables of it and *this List &operator = ( List rhs ) { // 'rhs' is passed by value--it is a copy of the // right-hand side of the assignment // Swap all the entries of the copy with this return *this; } Linked Lists 19

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 20 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( list_head, list.list_head ); } Linked Lists 21 Assignment Visually, we are doing the following:

List &List::operator = ( List rhs ) { swap( *this, rhs ); return *this; } Linked Lists 22 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 23 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 24 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 destructor is called on rhs rhs ) { std::swap( *this, rhs ); return *this;

} Linked Lists 25 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 destructor is called on rhs rhs ) { std::swap( *this, rhs ); Back in the calling function,

return *this; the two lists contain the } same values Linked Lists 26 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 Hinnant Linked Lists 27 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 Hinnant Linked Lists 28 Assignment What is the plan? First, we must pass by referenceno copying Ensure we are not assigning something to itself If the right-hand side is empty, its straight-forward:

Just empty this list Otherwise, step through the right-hand 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 list_head and not a next_node member variable Linked Lists 29

Assignment The implementation must be more carefully written List &List::operator = ( List const &rhs ) { if ( this == &rhs ) { return *this; } if ( rhs.empty() ) { while ( !empty() ) { pop_front(); } return *this; } Linked Lists 30

Assignment if ( empty() ) { list_head = new Node( rhs.front() ); } else { head()->element = rhs.front(); } Node *this_node = list_head, *rhs_node = rhs.head()->next(); while ( rhs_node != 0 ) { if ( this_node->next() == 0 ) { this_node->next_node = new Node( rhs_node->retrieve() ); this_node = this_node->next(); } else { this_node->next();

this_node->element = rhs_node->retrive(); } rhs_node = rhs_node->next(); } Linked Lists 31 Assignment while ( this_node->next() != 0 ) { Node *tmp = this_node->next(); this_node->next_node = this_node->next()->next(); delete tmp; }

return *this; } Linked Lists 32 Move Assignment Similarly, we need a move assignment: List &List::operator = ( List &&rhs ) { while ( !empty() ) { pop_front(); } list_head = rhs.head(); rhs.list_head = 0; return *this;

} Linked Lists 33 Linked Lists Thus, the complete class is: class List { private: Node *list_head; void swap( List & ); public: // Constructors and destructors List(); List( List const & );

List( List && ); ~List(); // Assignment operators List &operator = ( List const & ); const; List &operator = ( List && ); // Accessors bool empty() const; int size() const; int front() const; Node *head() const; int count( int ) // Mutators

void push_front( int ); int pop_front(); int erase( int ); Linked Lists 34 Linked Lists With asymptotic analysis of linked lists, we can now make the following statements: insert access erase

* front Q(1) Q(1) Q(1) arbitrary O(n) O(n) O(n) these become Q(1) if we have a tail pointer back

Q(n) * Q(n) * Q(n) Linked Lists 35 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 pre-allocate memory for a number of nodes and use them? Suggestions?

Linked Lists 36 Efficient Allocation Consider the following strategy: Allocate an array of N nodes The address of the node is the index in the array Therefore, next_node 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 stack Linked Lists 37 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 38

Efficient Allocation After a few calls to push_front and erase, we could end up with an allocation as follows: Linked Lists 39 Efficient Allocation If we wanted to call pop_front, we would: Push 4 onto the stack Updated list_head to be 7 Linked Lists 40

Efficient Allocation If we wanted to call pop_front, we would: Push 4 onto the stack Updated list_head to be 7 The result: Linked Lists 41 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 list_head

Update list_head = 6 Linked Lists 42 Efficient Allocation This results in: Linked Lists 43 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 copies

Linked Lists 44 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 efficiencies Linked Lists 45 References Donald E. Knuth, The Art of Computer Programming, Volume 3: Sorting and Searching, 2nd Ed., Addison Wesley, 1998, 5.4, pp.248-379. Wikipedia, https://en.wikipedia.org/wiki/Linked_list http://stackoverflow.com/error?aspxerrorpath=/questions/8848363/rvalue-reference-with-assignement-operator

These slides are provided for the ECE 250 Algorithms and Data Structures course. The material in it reflects Douglas W. Harders 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.

Recently Viewed Presentations

  • Minneapolis VAMC CNH Oversight Team Annual Review of Contract ...

    Minneapolis VAMC CNH Oversight Team Annual Review of Contract ...

    (Exception is when a veteran is on hospice: VA will pay R&B, MC will pay for hospice agency to provide end of life meds, hospice staffing, consultation) Medications: VA does not supply routine medications for the CNH patient - CNH...
  • A.U.H.S.D, Katella High; Anger Management Presentation

    A.U.H.S.D, Katella High; Anger Management Presentation

    Anger Management Presentation to KHS By Sean Ferrell AUHSD Social Work Intern Katella High School has identified a population of students who are in need of a formalized Anger Management Group. The creation and facilitation of an Anger Management Group...
  • Legal Refresher In-Service - World Beyond War

    Legal Refresher In-Service - World Beyond War

    Incorporating the latest advances in brain scanning and neuroscience, Dutton demonstrates that the brilliant neurosurgeon who lacks empathy has more in common with a Ted Bundy who kills for pleasure than we may wish to admit, and that a mugger...
  • Welcome to Siddharth College

    Welcome to Siddharth College

    Belong to minority Community: User has to select ―YES‖ or ―NO‖ whether user belongs to Minority Community . ... Address / District /Village/City/Town . Is . Correspondence Address same as Permanent? (Select Yes/No radio button) State / Taluka / Pin...
  • Applications of GAs: TSP & Sorting &DiPres

    Applications of GAs: TSP & Sorting &DiPres

    in Michigan-style Classifier Systems When solving optimization problems it is desirable to replace good solutions whereas in LCS replacing a very good classifier is quite dangerous, because the system's real-time performance might drop significantly after a "few good" rules have...
  • We We Are Are Learnin Learnin g g

    We We Are Are Learnin Learnin g g

    Compass points N E W S NE SE SW NW 000° 045° 090° 135° 180° 225° 270° 315° Measuring bearings * Grade D WALT WILF MUST be able to measure angles SHOULD understand the rules of bearings COULD understand how...
  • Revolution! In what ways have you participated in

    Revolution! In what ways have you participated in

    Romanticism: A Historical Approach. ... Support your answer with evidence from the poems, your knowledge of the historical context from the PowerPoint and/or your personal knowledge. Literary Rebellion. Romanticism, in some aspects, is a rebellion against the literary movement that...
  • WhAT WOULD YOU SAY?

    WhAT WOULD YOU SAY?

    My daughter told me this was a nice place. They moved me in here and told me this was my place. Where did my purse go? This is my room and they come in and out all of the time....