Contents

• Public Types
• Public Functions
• Static Public Members
• Related Non-Members
• Detailed Description

Detailed Description

TheQLinkedList class is a template class that provides linked lists.

QLinkedList<T> is one of Qt's genericcontainer classes. It stores a list of values and provides iterator-based access as well asconstant time insertions and removals.

QList<T>,QLinkedList<T>, andQVector<T> provide similar functionality. Here's an overview:

• For most purposes,QList is the right class to use. Its index-based API is more convenient thanQLinkedList's iterator-based API, and it is usually faster thanQVector because of the way it stores its items in memory (seeAlgorithmic Complexity for details). It also expands to less code in your executable.
• If you need a real linked list, with guarantees ofconstant time insertions in the middle of the list and iterators to items rather than indexes, useQLinkedList.
• If you want the items to occupy adjacent memory positions, useQVector.

Here's an example of aQLinkedList that stores integers and aQLinkedList that storesQTime values:

QLinkedList<int> integerList;QLinkedList<QTime> timeList;

QLinkedList stores a list of items. The default constructor creates an empty list. To insert items into the list, you can use operator<<():

QLinkedList<QString> list;list<<"one"<<"two"<<"three";// list: ["one", "two", "three"]

If you want to get the first or last item in a linked list, usefirst() orlast(). If you want to remove an item from either end of the list, useremoveFirst() orremoveLast(). If you want to remove all occurrences of a given value in the list, useremoveAll().

A common requirement is to remove the first or last item in the list and do something with it. For this,QLinkedList providestakeFirst() andtakeLast(). Here's a loop that removes the items from a list one at a time and callsdelete on them:

QLinkedList<QWidget*> list;...while (!list.isEmpty())delete list.takeFirst();

QLinkedList's value type must be anassignable data type. This covers most data types that are commonly used, but the compiler won't let you, for example, store aQWidget as a value; instead, store aQWidget *. A few functions have additional requirements; for example,contains() andremoveAll() expect the value type to supportoperator==(). These requirements are documented on a per-function basis.

If you want to insert, modify, or remove items in the middle of the list, you must use an iterator.QLinkedList provides bothJava-style iterators (QLinkedListIterator andQMutableLinkedListIterator) andSTL-style iterators (QLinkedList::const_iterator andQLinkedList::iterator). See the documentation for these classes for details.

Member Type Documentation

typedef QLinkedList::ConstIterator

Qt-style synonym forQLinkedList::const_iterator.

typedef QLinkedList::Iterator

Qt-style synonym forQLinkedList::iterator.

typedef QLinkedList::const_pointer

Typedef for const T *. Provided for STL compatibility.

typedef QLinkedList::const_reference

Typedef for const T &. Provided for STL compatibility.

typedef QLinkedList::difference_type

Typedef for ptrdiff_t. Provided for STL compatibility.

typedef QLinkedList::pointer

Typedef for T *. Provided for STL compatibility.

typedef QLinkedList::reference

Typedef for T &. Provided for STL compatibility.

typedef QLinkedList::size_type

Typedef for int. Provided for STL compatibility.

typedef QLinkedList::value_type

Typedef for T. Provided for STL compatibility.

Member Function Documentation

QLinkedList::QLinkedList()

Constructs an empty list.

QLinkedList::QLinkedList(constQLinkedList<T> & other)

Constructs a copy ofother.

This operation occurs inconstant time, becauseQLinkedList isimplicitly shared. This makes returning aQLinkedList from a function very fast. If a shared instance is modified, it will be copied (copy-on-write), and this takeslinear time.

See alsooperator=().

QLinkedList::~QLinkedList()

Destroys the list. References to the values in the list, and all iterators over this list, become invalid.

void QLinkedList::append(constT & value)

Insertsvalue at the end of the list.

Example:

QLinkedList<QString> list;list.append("one");list.append("two");list.append("three");// list: ["one", "two", "three"]

This is the same as list.insert(end(),value).

See alsooperator<<(),prepend(), andinsert().

T & QLinkedList::back()

This function is provided for STL compatibility. It is equivalent tolast().

constT & QLinkedList::back() const

This is an overloaded function.

iterator QLinkedList::begin()

Returns an STL-style iterator pointing to the first item in the list.

See alsoconstBegin() andend().

const_iterator QLinkedList::begin() const

This is an overloaded function.

void QLinkedList::clear()

Removes all the items in the list.

See alsoremoveAll().

const_iterator QLinkedList::constBegin() const

Returns a const STL-style iterator pointing to the first item in the list.

See alsobegin() andconstEnd().

const_iterator QLinkedList::constEnd() const

Returns a const STL-style iterator pointing to the imaginary item after the last item in the list.

See alsoconstBegin() andend().

bool QLinkedList::contains(constT & value) const

Returns true if the list contains an occurrence ofvalue; otherwise returns false.

This function requires the value type to have an implementation ofoperator==().

See alsoQLinkedListIterator::findNext() andQLinkedListIterator::findPrevious().

int QLinkedList::count(constT & value) const

Returns the number of occurrences ofvalue in the list.

This function requires the value type to have an implementation ofoperator==().

See alsocontains().

int QLinkedList::count() const

Same assize().

bool QLinkedList::empty() const

This function is provided for STL compatibility. It is equivalent toisEmpty() and returns true if the list is empty.

iterator QLinkedList::end()

Returns an STL-style iterator pointing to the imaginary item after the last item in the list.

See alsobegin() andconstEnd().

const_iterator QLinkedList::end() const

This is an overloaded function.

bool QLinkedList::endsWith(constT & value) const

Returns true if the list is not empty and its last item is equal tovalue; otherwise returns false.

This function was introduced in Qt 4.5.

See alsoisEmpty() andlast().

iterator QLinkedList::erase(iterator pos)

Removes the item pointed to by the iteratorpos from the list, and returns an iterator to the next item in the list (which may beend()).

See alsoinsert().

iterator QLinkedList::erase(iterator begin,iterator end)

This is an overloaded function.

Removes all the items frombegin up to (but not including)end.

T & QLinkedList::first()

Returns a reference to the first item in the list. This function assumes that the list isn't empty.

See alsolast() andisEmpty().

constT & QLinkedList::first() const

This is an overloaded function.

[static]QLinkedList<T> QLinkedList::fromStdList(conststd::list<T> & list)

Returns aQLinkedList object with the data contained inlist. The order of the elements in theQLinkedList is the same as inlist.

Example:

std::list<double> stdlist;list.push_back(1.2);list.push_back(0.5);list.push_back(3.14);QLinkedList<double> list=QLinkedList<double>::fromStdList(stdlist);

This function was introduced in Qt 4.1.

See alsotoStdList().

T & QLinkedList::front()

This function is provided for STL compatibility. It is equivalent tofirst().

constT & QLinkedList::front() const

This is an overloaded function.

iterator QLinkedList::insert(iterator before, constT & value)

Insertsvalue in front of the item pointed to by the iteratorbefore. Returns an iterator pointing at the inserted item.

See alsoerase().

bool QLinkedList::isEmpty() const

Returns true if the list contains no items; otherwise returns false.

See alsosize().

T & QLinkedList::last()

Returns a reference to the last item in the list. This function assumes that the list isn't empty.

See alsofirst() andisEmpty().

constT & QLinkedList::last() const

This is an overloaded function.

void QLinkedList::pop_back()

This function is provided for STL compatibility. It is equivalent toremoveLast().

void QLinkedList::pop_front()

This function is provided for STL compatibility. It is equivalent toremoveFirst().

void QLinkedList::prepend(constT & value)

Insertsvalue at the beginning of the list.

Example:

QLinkedList<QString> list;list.prepend("one");list.prepend("two");list.prepend("three");// list: ["three", "two", "one"]

This is the same as list.insert(begin(),value).

See alsoappend() andinsert().

void QLinkedList::push_back(constT & value)

This function is provided for STL compatibility. It is equivalent to append(value).

void QLinkedList::push_front(constT & value)

This function is provided for STL compatibility. It is equivalent to prepend(value).

int QLinkedList::removeAll(constT & value)

Removes all occurrences ofvalue in the list.

Example:

QList<QString> list;list<<"sun"<<"cloud"<<"sun"<<"rain";list.removeAll("sun");// list: ["cloud", "rain"]

This function requires the value type to have an implementation ofoperator==().

See alsoinsert().

void QLinkedList::removeFirst()

Removes the first item in the list.

This is the same as erase(begin()).

See alsoremoveLast() anderase().

void QLinkedList::removeLast()

Removes the last item in the list.

See alsoremoveFirst() anderase().

bool QLinkedList::removeOne(constT & value)

Removes the first occurrences ofvalue in the list. Returns true on success; otherwise returns false.

Example:

QList<QString> list;list<<"sun"<<"cloud"<<"sun"<<"rain";list.removeOne("sun");// list: ["cloud", "sun", "rain"]

This function requires the value type to have an implementation ofoperator==().

This function was introduced in Qt 4.4.

See alsoinsert().

int QLinkedList::size() const

Returns the number of items in the list.

See alsoisEmpty() andcount().

bool QLinkedList::startsWith(constT & value) const

Returns true if the list is not empty and its first item is equal tovalue; otherwise returns false.

This function was introduced in Qt 4.5.

See alsoisEmpty() andfirst().

void QLinkedList::swap(QLinkedList<T> & other)

Swaps listother with this list. This operation is very fast and never fails.

This function was introduced in Qt 4.8.

T QLinkedList::takeFirst()

Removes the first item in the list and returns it.

If you don't use the return value,removeFirst() is more efficient.

See alsotakeLast() andremoveFirst().

T QLinkedList::takeLast()

Removes the last item in the list and returns it.

If you don't use the return value,removeLast() is more efficient.

See alsotakeFirst() andremoveLast().

std::list<T> QLinkedList::toStdList() const

Returns a std::list object with the data contained in thisQLinkedList. Example:

QLinkedList<double> list;list<<1.2<<0.5<<3.14;std::list<double> stdlist= list.toStdList();

This function was introduced in Qt 4.1.

See alsofromStdList().

bool QLinkedList::operator!=(constQLinkedList<T> & other) const

Returns true ifother is not equal to this list; otherwise returns false.

Two lists are considered equal if they contain the same values in the same order.

This function requires the value type to implementoperator==().

See alsooperator==().

QLinkedList<T> QLinkedList::operator+(constQLinkedList<T> & other) const

Returns a list that contains all the items in this list followed by all the items in theother list.

See alsooperator+=().

QLinkedList<T> & QLinkedList::operator+=(constQLinkedList<T> & other)

Appends the items of theother list to this list and returns a reference to this list.

See alsooperator+() andappend().

QLinkedList<T> & QLinkedList::operator+=(constT & value)

This is an overloaded function.

Appendsvalue to the list.

QLinkedList<T> & QLinkedList::operator<<(constQLinkedList<T> & other)

Appends the items of theother list to this list and returns a reference to this list.

See alsooperator+=() andappend().

QLinkedList<T> & QLinkedList::operator<<(constT & value)

This is an overloaded function.

Appendsvalue to the list.

QLinkedList<T> & QLinkedList::operator=(constQLinkedList<T> & other)

Assignsother to this list and returns a reference to this list.

QLinkedList<T> & QLinkedList::operator=(QLinkedList<T> && other)

bool QLinkedList::operator==(constQLinkedList<T> & other) const

Returns true ifother is equal to this list; otherwise returns false.

Two lists are considered equal if they contain the same values in the same order.

This function requires the value type to implementoperator==().

See alsooperator!=().

Related Non-Members

QDataStream &operator<<(QDataStream & out, constQLinkedList<T> & list)

Writes the linked listlist to streamout.

This function requires the value type to implementoperator<<().

See alsoFormat of the QDataStream operators.

QDataStream &operator>>(QDataStream & in,QLinkedList<T> & list)

Reads a linked list from streamin intolist.

This function requires the value type to implementoperator>>().

See alsoFormat of the QDataStream operators.