Chapter 18 - Notes

Linked List vs. Dynamic Arrays

• The main advantage of a linked list is the fast (constant time) insertion and removal of elements anywhere in the linked list.

• std::list is a double-linked list, allowing traversal forwards and backwards.

• std::forward_list is a single-linked list, allow traversal in one direction only.

Linked List

• A linked list is a collection of nodes

• Each node contains the value or object of interest, and has pointer member variables pointing to the next node, or the previous node.

Operations

Declaration

std::list<int> linkInts; // list containing integers
std::list<float> listFloats; // list containing floats
std::list<Tuna> listTunas; // list containing objects of type Tuna

Iterators

• The iterator type for an std::list can be obtained by appending the container type with ::iterator

std::list<int>::iterator elementInList;

• If you require an iterator that cannot be used to modify the values, or invoke non-const functions, use const_iterator

std::list<int>::const_iterator elementInList;

Initialisation

Below are the different forms of instantiating an std::list

#include <list>
#include <vector>

int main ()
{
    // instantiate an empty list
    std::list <int> linkInts;

    // instantiate a list with 10 integers
    std::list<int> listWith10Integers(10);
    
    // instantiate a list with 4 integers, each value 99
    std::list<int> listWith4IntegerEach99 (10, 99);

    // create an exact copy of an existing list
    std::list<int> listCopyAnother(listWith4IntegerEach99);

    // a vector with 10 integers, each 2017
    std::vector<int> vecIntegers(10, 2017);

    // instantiate a list using values from another container
    std::list<int> listContainsCopyOfAnother(vecIntegers.cbegin(), vecIntegers.cend());
}

Inserting to the front or back

• Similar to std::deque, insertion at the front or back is done using the .push_front() and .push_back() member functions respectively.

linkInts.push_back(-1);
linkInts.push_front(2001);

Inserting to the middle

• The main reason you would use std::list over std::vector or std::deque is it's ability to quickly insert elements anywhere in the middle of the list.

• This is done with the .insert() member function

Form 1

iterator insert(iterator pos, const T& x)

• The function accepts the position of insertion as the first parameter, and the value to insert as the second.

• The function returns an iterator pointing to the element that was just inserted in the list.

Form 2

void insert(iterator pos, size_type n, const T& x)

• The function accepts the position of insertion as the first parameter, the value to insert as the last parameter, and the number of elements as variable n.

Form 3

void insert(iterator pos, InputIterator f, InputIterator l)

• This is a template function that accepts two input iterators indicating the bounds of the collection to insert.

Erasing elements

Erase one element

iterator erase (iterator position);

Erase a range of elements

iterator erase (iterator first, iterator last);

Reversing and Sorting

std::list has a special property that iterators pointing to elements in the container remain valid despite the rearrangement of elements, or insertion of new elements

• This is not true with std::vector or std::deque

To preserve this property, the std::list container has member functions .sort() and .reverse() as member functions despite similar algorithm functions provided.

The member function versions ensure that any iterators that exist prior to reversing or sorted are not invalidated when the relative position of an element is disturbed.

Reversing

std::list<int> linkInts{ 0, 1, 2, 3, 4, 5 };

linkInts.reverse();

Sorting

• Version with no parameters

linkInts.sort(); // sort in ascending order

• Version that allows you to define sort priorities via a binary predicate

bool SortPredicate_Descending (const int& lhs, const int& rhs)
{
    // define criteria for list::sort: return true for desired order
    return (lhs > rhs);
}

linkInts.sort(SortPredicate_Descending);

• The binary predicate takes two values, and returns true if the first value is to be logically less than the second.

• You can think of the binary predicate as "is LHS and RHS already in the order you'd expect?"

When the version without a binary predicate is used, the elements are sorted in ascending order, comparing the elements using operator<.

Sorting and removing instances of a class

If you have an std::list of a custom class type, you have to either:

• implement operator< for the class type that the std::list contains.

• supply a sorting binary predicate - a function that takes two values as the input and returns a Boolean value indicating whether the first value is smaller than the second.