ECE 250 Algorithms and Data Structures

3.5 Linked Lists

Douglas Wilhelm Harder, M.Math. LEL

Department of Electrical and Computer Engineering
University of Waterloo
Waterloo, Ontario, Canada

ece.uwaterloo.ca
dwharder@alumni.uwaterloo.ca

© 2006-2013 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 efficiencies
 Linked 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 data
 Linked Lists
4

1 Linked Lists

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

1 Node Class

The node must store data and a pointer:

class Node {
public:
Node( int = 0, Node * = nullptr );

int value() const;

Node *next() const;

private:
int node_value;
Node *next_node;
};
 Linked Lists
6

1.1 Node Constructor

The constructor assigns the two member variables based on the

arguments
List::Node::Node( int e, Node *n ):
node_value( e ),
next_node( n ) {
// empty constructor
}

The default values are given in the class definition:

class Node {
public:
Node( int = 0, Node * = nullptr );
int value() const;
Node *next() const;
private:
int node_value;
Node *next_node;
};
 Linked Lists
7

Accessors

The two member functions are accessors which simply return the
node_value and the next_node member variables, respectively

int List::Node::value() const {

return node_value;
}

List::Node *List::Node::next() const {

return next_node;
}

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, getters
 Linked 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 next_node Next_node() or NextNode()
Prefix with “get” next_node get_next_node() / getNextNode()
Use an underscore next_node_ next_node()
Different names next_node next()

Always use the naming convention and coding styles used

by your employer—even if you disagree with them
• Consistency aids in maintenance
 Linked 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 {
public:
class Node {...};

private:
Node *list_head;
// ...
};
 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 order
 Linked 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 32-bit machine
 Linked Lists
12

Structure

Such a list could occupy memory as follows:

Linked List Object

 Linked Lists
13

Structure

The next_node pointers store the addresses

of the next node in the list
 Linked 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 value
– The next_node pointer is represented by an arrow
 Linked 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 values stored in the linked list
 Linked 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 push_front( int );
int front() const;
void pop_front();

– We may also want to access the head of the linked list

Node *begin() const;

Member functions that may change the object acted

upon are variously called mutators, modifiers,
and, when it involves changing a single member
variable, setters
 Linked 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 list_head pointer is set to nullptr

 Linked Lists
20

Linked Lists

Consider this simple (but incomplete) linked list class:

class List {
public:
class Node {...};
List();

// Accessors
bool empty() const;
int size() const;
int front() const;
Node *begin() const;
Node *end() const;
int count( int ) const;

// Mutators
void push_front( int );
int pop_front();
int erase( int );

private:
Node *list_head;
};
 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 nullptr
 Linked Lists
22

The Constructor

Thus, in the constructor, we assign list_head the value nullptr

List::List():list_head( nullptr ) {
// empty constructor
}

We will always ensure that when a linked list is empty, the list head
is assigned nullptr
 Linked 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 called
 Linked Lists
24

Static Allocation

Example:

int f() {
List ls; // ls is declared as a local variable on the stack

ls.push_front( 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

pls->push_front( n );
cout << pls->front() << 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.push_front( 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 ( list_head == nullptr ) {
return true;
} else {
return false;
}
}

Better yet:
bool List::empty() const {
return ( list_head == nullptr );
}
 Linked Lists
28

Node *begin() const

The member function Node *begin() const is easy enough to

implement:

List::Node *List::begin() const {

return list_head;
}

This will always work: if the list is empty, it will return nullptr
 Linked Lists
29

Node *end() const

The member function Node *end() const equals whatever the

last node in the linked list points to
– In this case, nullptr

List::Node *List::end() const {

return nullptr;
}
 Linked Lists
30

int front() const

To get the first value in the linked list, we must access the node to
which the list_head is pointing

Because we have a pointer, we must use the -> operator to call the
member function:
int List::front() const {
return begin()->value();
}
 Linked Lists
31

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 program

 Linked Lists
32

int front() const

Instead, we can use an exception handling mechanism where we

thrown an exception

We define a class
class underflow {
// empty
};
and then we throw an instance of this class:
throw underflow();
 Linked Lists
33

int front() const

Thus, the full function is

int List::front() const {
if ( empty() ) {
throw underflow();
}

return begin()->value();
}
 Linked Lists
34

int front() const

Why is empty() better than

int List::front() const {
if ( list_head == nullptr ) {
throw underflow();
}

return list_head->node_value;
}
?

Two benefits:
– More readable
– If the implementation changes we do nothing
 Linked Lists
35

void push_front( int )

Next, let us add a value to the list

If it is empty, we start with:

and, if we try to add 81, we should end up with:

 Linked Lists
36

void push_front( 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 list_head

We can do this as follows:

list_head = new Node( 81, nullptr );

We could also use the default value...

 Linked Lists
37

void push_front( int )

Suppose however, we already have a non-empty list

Adding 70, we want:

 Linked Lists
38

void push_front( 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 list_head

We can do this as follows:

list_head = new Node( 70, list_head );
 Linked Lists
39

void push_front( int )

Thus, our implementation could be:

void List::push_front( int n ) {

if ( empty() ) {
list_head = new Node( n, nullptr );
} else {
list_head = new Node( n, begin() );
}
}
 Linked Lists
40

void push_front( int )

We could, however, note that when the list is empty,

list_head == 0, thus we could shorten this to:

void List::push_front( int n ) {

list_head = new Node( n, list_head );
}
 Linked Lists
41

void push_front( int )

Are we allowed to do this?

void List::push_front( int n ) {
list_head = new Node( n, begin() );
}

Yes: the right-hand side of an assignment is evaluated first

– The original value of list_head is accessed first before the function
call is made
 Linked Lists
42

void push_front( int )

Question: does this work?

void List::push_front( int n ) {

Node new_node( n, begin() );
list_head = &new_node;
}

Why or why not? What happens to new_node?

How does this differ from

void List::push_front( int n ) {

Node *new_node = new Node( n, begin() );
list_head = new_node;
}
 Linked Lists
43

int pop_front()

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
44

int pop_front()

Easy enough:
int List::pop_front() {
int e = front();
list_head = begin()->next();
return e;
}

Unfortunately, we have some problems:

– The list may be empty
– We still have the memory allocated for the node containing 70
 Linked Lists
45

int pop_front()

Does this work?

int List::pop_front() {
if ( empty() ) {
throw underflow();
}

int e = front();
delete begin();
list_head = begin()->next();
return e;
}
 Linked Lists
46

int pop_front()

int List::pop_front() {
if ( empty() ) {
throw underflow();
}

int e = front();

delete begin();

list_head = begin()->next();

return e;
}
 Linked Lists
47

int pop_front()

int List::pop_front() {
if ( empty() ) {
throw underflow();
}

int e = front();

delete begin();

list_head = begin()->next();

return e;
}
 Linked Lists
48

int pop_front()

int List::pop_front() {
if ( empty() ) {
throw underflow();
}

int e = front();

delete begin();

list_head = begin()->next();

return e;
}
 Linked Lists
49

int pop_front()

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
50

int pop_front()

The correct implementation assigns a temporary pointer to point to

the node being deleted:

int List::pop_front() {
if ( empty() ) {
throw underflow();
}

int e = front();
Node *ptr = list_head;
list_head = list_head->next();
delete ptr;
return e;
}
 Linked Lists
51

int pop_front()

int List::pop_front() {
if ( empty() ) {
throw underflow();
}

int e = front();

Node *ptr = begin();

list_head = begin()->next();

delete ptr;

return e;
}
 Linked Lists
52

int pop_front()

int List::pop_front() {
if ( empty() ) {
throw underflow();
}

int e = front();

Node *ptr = begin();

list_head = begin()->next();

delete ptr;

return e;
}
 Linked Lists
53

int pop_front()

int List::pop_front() {
if ( empty() ) {
throw underflow();
}

int e = front();

Node *ptr = begin();

list_head = begin()->next();

delete ptr;

return e;
}
 Linked Lists
54

int pop_front()

int List::pop_front() {
if ( empty() ) {
throw underflow();
}

int e = front();

Node *ptr = begin();

list_head = begin()->next();

delete ptr;

return e;
}
 Linked Lists
55

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 integer
 Linked Lists
56

Stepping through a Linked List

The process of stepping through a linked list can be thought of as

being analogous to a for-loop:
– 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 object
 Linked Lists
57

Stepping through a Linked List

Thus, we have:

for ( Node *ptr = begin(); ptr != end(); ptr = ptr->next() ) {

// do something
// use ptr->fn() to call member functions
// use ptr->var to assign/access member variables
}
 Linked Lists
58

Stepping through a Linked List

Analogously:

for ( Node *ptr = begin(); ptr != end(); ptr = ptr->next() )

for ( int i = 0; i != N; ++i )
 Linked Lists
59

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 to
 Linked Lists
60

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

ptr->value()
 Linked Lists
61

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
ptr->next()
 Linked Lists
62

Stepping through a Linked List

ptr != nullptr and thus we evaluate the loop and increment the
pointer

This last increment causes ptr == nullptr

 Linked Lists
63

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 it
 Linked Lists
64

int count( int ) const

To implement int count(int) const, we simply check if the

argument matches the value 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 count
 Linked Lists
65

int count( int ) const

The implementation:

int List::count( int n ) const {

int node_count = 0;

for ( Node *ptr = begin(); ptr != end(); ptr = ptr->next() ) {

if ( ptr->value() == n ) {
++node_count;
}
}

return node_count;
}
 Linked Lists
66

int erase( int )

To remove an arbitrary value, 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 with

 Linked Lists
67

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 next_node

We could supply the member function

void set_next( Node * );
however, this would be globally accessible

Possible solutions:
– Friends
– Nested classes
– Inner classes
 Linked Lists
68

C++ Friends

In C++, you could explicitly break encapsulation by declaring the

class List to be a friend of the class Node:

class A {
private:
int class_size;
// ... declaration ...
friend class B;
};

Now, any member function of class B has access to all private

member variables of class A
 Linked Lists
69

C++ Friends

For example, if the Node class was one class, and the List class was
a friend of the Node class, List::erase could modify nodes:

int List::erase( int n ) {

int node_count = 0;
// ...

for ( Node *ptr = begin(); ptr != end(); ptr = ptr->next() ) {

// ...

if ( some condition ) {
ptr->next_node = ptr->next()->next();
// ...
++node_count;
}
}

return node_count;
}
 Linked Lists
70

Nested Classes

In C++, you can nest one class inside another, which is what we do:
class Outer {
private:
class Nested {
private:
int node_value;
public:
int get() const;
void set( int );
};

Nested stored;

public:
int get() const;
void set( int );
};
 Linked Lists
71

Nested Classes

The function definitions are as one would expect:

int Outer::Nested::get() const {

return node_value;
}

void Outer::Nested::set( int n ) {

node_value = n;
}
int Outer::get() const {
return stored.get();
}

void Outer::set( int n ) {

// Not allowed, as node_value is private
// stored.node_value = n;

stored.set( n );
}
 Linked Lists
72

Inner Classes

In Java/C#, there is also the notion of an inner class

– This is an elegant object-oriented 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 = list_head; ptr != this; ptr = ptr->next() ) {

} // empty loop body

return posn;
}
 Linked Lists
73

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 it
 Linked Lists
74

Destructor

Thus, we need a destructor:

class List {
private:
Node *list_head;
public:
List();
~List();
// ...etc...
};
 Linked Lists
75

Destructor

The destructor has to delete any memory which had been allocated
but has not yet been deallocated

This is straight-forward enough:

while ( !empty() ) {
pop_front();
}
 Linked Lists
76

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
77

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
– Assignment
 Linked Lists
78

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
79

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
80

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
81

Modifying Arguments

Pass by reference could be used to modify a list

void reverse( List &list ) {
List tmp;

while ( !list.empty() ) {
tmp.push_front( ls.pop_front() );
}

// All the member variables of 'list' and 'tmp' are swapped

std::swap( list, tmp );

// The memory for 'tmp' will be cleaned up

}
 Linked Lists
82

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 ( List::Node *ptr = begin();

ptr != end(); ptr = ptr->next() ) {
sum += ptr->value();
++count;
}

return sum/count;
}

Note: this reveals a weakness in our model—we will discuss iterators later…
 Linked Lists
83

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 send_copy( 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
84

Modifying Arguments

First, the list prim is created and three values are pushed onto it

void send_copy( 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.push_front( i*i );
}

send_copy( prim );

std::cout << prim.empty() << std::endl;

return 0;
}
 Linked Lists
85

Modifying Arguments

Next, we call send_copy and assigns the parameter ls a copy of

the argument prim
– The default is to copy member variables:
ls.list_head = prim.list_head
void send_copy( 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.push_front( i*i );
}

send_copy( prim );

std::cout << prim.empty() << std::endl;

return 0;
}
 Linked Lists
86

Modifying Arguments

When send_copy returns, the destructor is called on the

parameter ls

void send_copy( 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.push_front( i*i );
}

send_copy( prim );

std::cout << prim.empty() << std::endl;

return 0;
}
 Linked Lists
87

Modifying Arguments

When send_copy returns, the destructor is called on the

parameter ls

void send_copy( 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.push_front( i*i );
}

send_copy( prim );

std::cout << prim.empty() << std::endl;

return 0;
}
 Linked Lists
88

Modifying Arguments

When send_copy returns, the destructor is called on the

parameter ls

void send_copy( 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.push_front( i*i );
}

send_copy( prim );

std::cout << prim.empty() << std::endl;

return 0;
}
 Linked Lists
89

Modifying Arguments

Back in main(), prim.list_head 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 send_copy( 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.push_front( i*i );
}

send_copy( prim );

std::cout << prim.empty() << std::endl;

return 0;
}
 Linked Lists
90

Modifying Arguments

What do we really want?

void send_copy( 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.push_front( i*i );
}

send_copy( prim );

std::cout << prim.empty() << std::endl;

return 0;
}
 Linked Lists
91

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 send_copy( 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.push_front( i*i );
}

send_copy( prim );

std::cout << prim.empty() << std::endl;

return 0;
}
 Linked Lists
92

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

Class_name( Class_name const & );

In this case, we would define the member function

List( List const & );
 Linked Lists
93

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.push_front( 4 );
ls1.push_front( 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 value
 Linked Lists
94

Copy Constructor

Thus, we must define a copy constructor:

– The copy constructor allows us to initialize the member variables
List::List( List const &list ):list_head( nullptr ) {
// Make a copy of list
}

We now want to go from

to
 Linked Lists
95

Copy Constructor

Naïvely, we step through list and call push_front( int ):

List::List( List const &list ):list_head( nullptr ) {
for ( Node *ptr = list.begin(); ptr != list.end(); ptr = ptr->next() ) {
push_front( ptr->value() );
}
}

Does this work?

– How could we make this work?
– We need a push_back( int ) member function:

List::List( List const &list ):list_head( nullptr ) {

for ( Node *ptr = list.begin(); ptr != list.end(); ptr = ptr->next() ) {
push_back( ptr->value() );
}
}
 Linked Lists
96

Copy Constructor

Unfortunately, to make push_back( int ) more efficient, we need a

pointer to the last node in the linked list
– We require a list_tail member variable
– Otherwise, push_back( int ) becomes a Q(n) function
• This would make the copy constructor Q(n2)

– In Project 1, you will define and use the member variable list_tail
 Linked Lists
97

Copy Constructor

First, make life simple: if list is empty, we are finished, so return

List::List( List const &list ):list_head( nullptr ) {
if ( list.empty() ) {
return;
}

}
 Linked Lists
98

Copy Constructor

Otherwise, the list being copied is not empty…

List::List( List const &list ):list_head( nullptr ) {
if ( list.empty() ) {
return;
}

}
 Linked Lists
99

Copy Constructor

Copy the first node—we no longer modifying list_head

List::List( List const &list ):list_head( nullptr ) {
if ( list.empty() ) {
return;
}

push_front( list.front() );

}
 Linked Lists
100

Copy Constructor

We need what we want to copy next and where we want to copy it

List::List( List const &list ):list_head( nullptr ) {
if ( list.empty() ) {
return;
}

push_front( list.front() );

}
Note, we will need to loop through the list… How about a for loop?
 Linked Lists
101

Copy Constructor

We modify the next pointer of the node pointed to by copy

List::List( List const &list ):list_head( nullptr ) {
if ( list.empty() ) {
return;
}

push_front( list.front() );

for (
Node *original = list.begin()->next(), *copy = begin();
original != list.end();
original = original->next(), copy = copy->next()
) {
copy->next_node = new Node( original->value(), nullptr );
}
}
 Linked Lists
102

Copy Constructor

Then we move each pointer forward:

List::List( List const &list ):list_head( nullptr ) {
if ( list.empty() ) {
return;
}

push_front( list.front() );

for (
Node *original = list.begin()->next(), *copy = begin();
original != list.end();
original = original->next(), copy = copy->next()
) {
copy->next_node = new Node( original->value(), nullptr );
}
}
 Linked Lists
103

Copy Constructor

We’d continue copying until we reach the end

List::List( List const &list ):list_head( nullptr ) {
if ( list.empty() ) {
return;
}

push_front( list.front() );

for (
Node *original = list.begin()->next(), *copy = begin();
original != list.end();
original = original->next(), copy = copy->next()
) {
copy->next_node = new Node( original->value(), nullptr );
}
}
 Linked Lists
104

Assignment

What about assignment?

– Suppose you have linked lists:

List lst1, lst2;

lst1.push_front( 35 );
lst1.push_front( 18 );
lst2.push_front( 94 );
lst2.push_front( 72 );
 Linked Lists
105

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
106

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
107

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.pop_front();
– This only affects the member variable from the object lst1
 Linked Lists
108

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
109

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
110

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
111

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
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

List initialize( int a, int b ) {

List ls;

for ( int i = b; i >= a; --i ) {

ls.push_front( 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 ) {
List ls;

for ( int i = b; i >= a; --i ) {

ls.push_front( 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
– 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
115

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
– Call the destructor on ls List initialize( int a, int b ) {
List ls;
– Remove the memory for ls
from the stack for ( int i = b; i >= a; --i ) {
ls.push_front( i );
}

return ls;
}
 Linked Lists
116

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
117

Return by Value

Wouldn’t 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
118

Return by Value

Wouldn’t 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 ) {
for it is popped from the stack List ls;

for ( int i = b; i >= a; --i ) {

ls.push_front( i );
}

return ls;
}
 Linked Lists
119

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 ):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
120

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.begin() or rhs.list_head
 Linked Lists
121

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
122

Assignment

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
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 );
– Back in the calling function, return *this;
the two lists contain the }
same values
 Linked 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 Hinnant

 Linked 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 Hinnant

 Linked 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 right-hand side is empty, it’s 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
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() ) {
pop_front();
}

return *this;
}
 Linked Lists
132

Assignment

if ( empty() ) {
list_head = new Node( rhs.front() );
} else {
begin()->node_value = rhs.front();
}

Node *this_node = list_head,

*rhs_node = rhs.begin()->next();

while ( rhs_node != 0 ) {
if ( this_node->next() == 0 ) {
this_node->next_node = new Node( rhs_node->value() );
this_node = this_node->next();
} else {
this_node->next();
this_node->node_value = rhs_node->value();
}

rhs_node = rhs_node->next();
}
 Linked Lists
133

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
134

Move Assignment

Similarly, we need a move assignment:

List &List::operator = ( List &&rhs ) {
while ( !empty() ) {
pop_front();
}

list_head = rhs.begin();
rhs.list_head = 0;

return *this;
}
 Linked Lists
135

Linked Lists

Thus, the complete class is:

class List {
private:
Node *list_head;
void swap( List & );

public:
// Constructors and destructors
List();
List( List const & ); // Accessors
List( List && ); bool empty() const;
~List(); int size() const;
int front() const;
// Assignment operators Node *begin() const;
Node *end() const;
List &operator = ( List );
int count( int ) const;
List &operator = ( List && );
// Mutators
void push_front( int );
int pop_front();
int erase( int );
};
 Linked Lists
136

Linked Lists

With asymptotic analysis of linked lists, we can now make the

following statements:

front arbitrary back

insert Q(1) O(n) Q(n) *
access Q(1) O(n) Q(n) *
erase Q(1) O(n) Q(n)

*
these become Q(1) if we have a tail pointer
 Linked 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 pre-allocate memory for a number of nodes and use them?
– Suggestions?
 Linked 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, 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
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 push_front and erase, we could end up with an

allocation as follows:
 Linked Lists
141

Efficient Allocation

If we wanted to call pop_front, we would:

– Push 4 onto the stack
– Updated list_head to be 7
 Linked Lists
142

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
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 list_head
– Update list_head = 6
 Linked 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 copies
 Linked 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 efficiencies
 Linked Lists
147

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. 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.