`class LinkedList<ValueType>`

This class stores an ordered list of values similar to an array. It supports traditional array selection using square brackets, but also supports inserting and deleting elements. It is similar in function to the STL list type.

Available since: 2014/07/01 version of C++ library

Constructor
LinkedList()	O(1)	Initializes a new empty list.
Methods
add(`value`)	O(1)	Adds a new value to the end of this list.
clear()	O(N)	Removes all elements from this list.
equals(`list`)	O(N)	Returns `true` if the two lists contain the same elements in the same order.
get(`index`)	O(N)	Returns the element at the specified index in this list.
insert(`index`, `value`)	O(N)	Inserts the element into this list before the specified index.
isEmpty()	O(1)	Returns `true` if this list contains no elements.
mapAll(`fn`)	O(N)	Calls the specified function on each element of the linkedlist in ascending index order.
remove(`index`)	O(N)	Removes the element at the specified index from this list.
set(`index`, `value`)	O(N)	Replaces the element at the specified index in this list with a new value.
size()	O(1)	Returns the number of elements in this list.
subList(`start`, `length`)	O(N)	Returns a new list containing elements from a sub-range of this list.
toString()	O(N)	Converts the list to a printable string representation.
Operators
`list`[`index`]	O(N)	Overloads `[]` to select elements from this list.
`list1` + `list2`	O(N)	Concatenates two lists.
`list1` += `list2`;	O(N)	Adds all of the elements from `list2` to `list1`.
`list` += `value`;	O(1)	Adds the single specified value to the list.
`list` += `a`, `b`, `c`;	O(1)	Adds multiple values to the list.
`list1` == `list1`	O(N)	Returns `true` if `list1` and `list2` contain the same elements.
`list1` != `list2`	O(N)	Returns `true` if `list1` and `list2` are different.
`ostream` << `list`	O(N)	Outputs the contents of the list to the given output stream.
`istream` >> `list`	O(N)	Reads the contents of the given input stream into the list.

Constructor detail

LinkedList();

Initializes a new list. The default constructor creates an empty list.

Usage:

LinkedList<ValueType> list;

Method detail

void add(ValueType value);
void push_back(ValueType value);

Adds a new value to the end of this list. To ensure compatibility with the list class in the Standard Template Library, this method is also called push_back.

Usage:

list.add(value);

void clear();

Removes all elements from this list.

O(N) because it must loop over the underlying list nodes to free their memory.

Usage:

list.clear();

bool equals(const LinkedList& list) const;

Returns true if the two lists contain exactly the same element values in the same order. Identical in behavior to the == operator.

Usage:

if (list.equals(list2)) ...

const ValueType& get(int index) const;

Returns the element at the specified index in this list. This method signals an error if the index is not in the array range.

O(1) at front or end of list; O(N) average/worst case.

Usage:

ValueType val = list.get(index);

void insert(int index, ValueType value);

Inserts the element into this list before the specified index. All subsequent elements are shifted one position to the right. This method signals an error if the index is outside the range from 0 up to and including the length of the list.

O(1) at front or end of list; O(N) average/worst case.

Usage:

list.insert(0, value);

bool isEmpty() const;

Returns true if this list contains no elements.

Usage:

if (list.isEmpty()) ...

void mapAll(void (*fn)(ValueType)) const;
void mapAll(void (*fn)(const ValueType&)) const;
void mapAll(FunctorType fn) const;

Calls the specified function on each element of the list in ascending index order.

Usage:

list.mapAll(fn);

void remove(int index);

Removes the element at the specified index from this list. All subsequent elements are shifted one position to the left. This method signals an error if the index is outside the array range.

O(1) at front or end of list; O(N) average/worst case.

Usage:

list.remove(index);

void set(int index, ValueType value);

Replaces the element at the specified index in this list with a new value. The previous value at that index is overwritten. This method signals an error if the index is not in the array range.

O(1) at front or end of list; O(N) average/worst case.

Usage:

list.set(index, value);

int size() const;

Returns the number of elements in this list.

Usage:

int nElems = list.size();

LinkedList subList(int start, int length) const;

Returns a new list containing elements from a sub-range of this list. For example, the call of subList(2, 4) would return a new list containing elements 2-5 of the original list in its indexes 0-3. Throws an error if the range [start, start+length) is not contained within the range [0, size()].

Usage:

LinkedList<ValueType> sub = list.subList(start, length);

Available since: 2014/10/20 version of C++ library

string toString() const;

Converts the list to a printable string representation, such as "{value1, value2, value3}".

Usage:

string str = list.toString();

Operator detail

ValueType& operator[](int index);
const ValueType& operator[](int index) const;

Overloads [] to select elements from this list. This extension enables the use of traditional array notation to get or set individual elements. This method signals an error if the index is outside the array range. The file supports two versions of this operator, one for const lists and one for mutable lists.

O(1) at front or end of list; O(N) average/worst case.

Usage:

vec[index]

LinkedList operator+(const LinkedList& v2) const;

Concatenates two lists.

Usage:

v1 + v2

LinkedList& operator+=(const LinkedList& list2);
LinkedList& operator+=(ValueType value);

Adds all of the elements from v2 (or the single specified value) to v1. As a convenience, the LinkedList package also overloads the comma operator so that it is possible to initialize a list like this:

   LinkedList<int> digits;
   digits += 0, 1, 2, 3, 4, 5, 6, 7, 8, 9;

Usage:

list1 += list2;
list1 += value;

LinkedList& operator,(ValueType value);

Adds an element to the list passed as the left-hand operatand. This form makes it easier to initialize lists in old versions of C++.

Usage:

list.mapAll(fn);