QLinkedList

The QLinkedList class is a template class that provides linked lists. More...

 #include <QLinkedList>

Inherited by: Q3ValueList.

Note: All functions in this class are reentrant.

Public Types

class	const_iterator
class	iterator
typedef	ConstIterator
typedef	Iterator
typedef	const_pointer
typedef	const_reference
typedef	difference_type
typedef	pointer
typedef	reference
typedef	size_type
typedef	value_type

Public Functions

	QLinkedList ()
	QLinkedList ( const QLinkedList<T> & other )
	~QLinkedList ()
void	append ( const T & value )
T &	back ()
const T &	back () const
iterator	begin ()
const_iterator	begin () const
void	clear ()
const_iterator	constBegin () const
const_iterator	constEnd () const
bool	contains ( const T & value ) const
int	count ( const T & value ) const
int	count () const
bool	empty () const
iterator	end ()
const_iterator	end () const
bool	endsWith ( const T & value ) const
iterator	erase ( iterator pos )
iterator	erase ( iterator begin, iterator end )
T &	first ()
const T &	first () const
T &	front ()
const T &	front () const
iterator	insert ( iterator before, const T & value )
bool	isEmpty () const
T &	last ()
const T &	last () const
void	pop_back ()
void	pop_front ()
void	prepend ( const T & value )
void	push_back ( const T & value )
void	push_front ( const T & value )
int	removeAll ( const T & value )
void	removeFirst ()
void	removeLast ()
bool	removeOne ( const T & value )
int	size () const
bool	startsWith ( const T & value ) const
void	swap ( QLinkedList<T> & other )
T	takeFirst ()
T	takeLast ()
std::list<T>	toStdList () const
bool	operator!= ( const QLinkedList<T> & other ) const
QLinkedList<T>	operator+ ( const QLinkedList<T> & other ) const
QLinkedList<T> &	operator+= ( const QLinkedList<T> & other )
QLinkedList<T> &	operator+= ( const T & value )
QLinkedList<T> &	operator<< ( const QLinkedList<T> & other )
QLinkedList<T> &	operator<< ( const T & value )
QLinkedList<T> &	operator= ( const QLinkedList<T> & other )
bool	operator== ( const QLinkedList<T> & other ) const

Static Public Members

QLinkedList<T> fromStdList ( const std::list<T> & list )

Related Non-Members

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

Detailed Description

The QLinkedList class is a template class that provides linked lists.

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

QList<T>, QLinkedList<T>, and QVector<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 than QLinkedList's iterator-based API, and it is usually faster than QVector because of the way it stores its items in memory (see Algorithmic Complexity for details). It also expands to less code in your executable.
If you need a real linked list, with guarantees of constant time insertions in the middle of the list and iterators to items rather than indexes, use QLinkedList.
If you want the items to occupy adjacent memory positions, use QVector.

Here's an example of a QLinkedList that stores integers and a QLinkedList that stores QTime 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, use first() or last(). If you want to remove an item from either end of the list, use removeFirst() or removeLast(). If you want to remove all occurrences of a given value in the list, use removeAll().

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

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

QLinkedList's value type must be an assignable data type. This covers most data types that are commonly used, but the compiler won't let you, for example, store a QWidget as a value; instead, store a QWidget *. A few functions have additional requirements; for example, contains() and removeAll() expect the value type to support operator==(). 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 both Java-style iterators (QLinkedListIterator and QMutableLinkedListIterator) and STL-style iterators (QLinkedList::const_iterator and QLinkedList::iterator). See the documentation for these classes for details.

See also QLinkedListIterator, QMutableLinkedListIterator, QList, and QVector.

Member Function Documentation

QLinkedList::QLinkedList ()

Constructs an empty list.

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

Constructs a copy of other.

This operation occurs in constant time, because QLinkedList is implicitly shared. This makes returning a QLinkedList from a function very fast. If a shared instance is modified, it will be copied (copy-on-write), and this takes linear time.

See also operator=().

QLinkedList::~QLinkedList ()

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

void QLinkedList::append ( const T & value )

Inserts value 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 also operator<<(), prepend(), and insert().

T & QLinkedList::back ()

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

const T & 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 also constBegin() and end().

const_iterator QLinkedList::begin () const

This is an overloaded function.

void QLinkedList::clear ()

Removes all the items in the list.

See also removeAll().

const_iterator QLinkedList::constBegin () const

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

See also begin() and constEnd().

const_iterator QLinkedList::constEnd () const

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

See also constBegin() and end().

bool QLinkedList::contains ( const T & value ) const

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

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

See also QLinkedListIterator::findNext() and QLinkedListIterator::findPrevious().

int QLinkedList::count ( const T & value ) const

Returns the number of occurrences of value in the list.

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

See also contains().

int QLinkedList::count () const

Same as size().

bool QLinkedList::empty () const

This function is provided for STL compatibility. It is equivalent to isEmpty() 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 also begin() and constEnd().

const_iterator QLinkedList::end () const

This is an overloaded function.

bool QLinkedList::endsWith ( const T & value ) const

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

This function was introduced in Qt 4.5.

See also isEmpty() and last().

iterator QLinkedList::erase ( iterator pos )

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

See also insert().

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

This is an overloaded function.

Removes all the items from begin 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 also last() and isEmpty().

const T & QLinkedList::first () const

This is an overloaded function.

QLinkedList<T> QLinkedList::fromStdList ( const std::list<T> & list ) `[static]`

Returns a QLinkedList object with the data contained in list. The order of the elements in the QLinkedList is the same as in list.

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 also toStdList().

T & QLinkedList::front ()

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

const T & QLinkedList::front () const

This is an overloaded function.

iterator QLinkedList::insert ( iterator before, const T & value )

Inserts value in front of the item pointed to by the iterator before. Returns an iterator pointing at the inserted item.

See also erase().

bool QLinkedList::isEmpty () const

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

See also size().

T & QLinkedList::last ()

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

See also first() and isEmpty().

const T & QLinkedList::last () const

This is an overloaded function.

void QLinkedList::pop_back ()

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

void QLinkedList::pop_front ()

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

void QLinkedList::prepend ( const T & value )

Inserts value 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 also append() and insert().

void QLinkedList::push_back ( const T & value )

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

void QLinkedList::push_front ( const T & value )

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

int QLinkedList::removeAll ( const T & value )

Removes all occurrences of value 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 of operator==().

See also insert().

void QLinkedList::removeFirst ()

Removes the first item in the list.

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

See also removeLast() and erase().

void QLinkedList::removeLast ()

Removes the last item in the list.

See also removeFirst() and erase().

bool QLinkedList::removeOne ( const T & value )

Removes the first occurrences of value 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 of operator==().

This function was introduced in Qt 4.4.

See also insert().

int QLinkedList::size () const

Returns the number of items in the list.

See also isEmpty() and count().

bool QLinkedList::startsWith ( const T & value ) const

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

This function was introduced in Qt 4.5.

See also isEmpty() and first().

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

Swaps list other 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 also takeLast() and removeFirst().

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 also takeFirst() and removeLast().

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

Returns a std::list object with the data contained in this QLinkedList. 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 also fromStdList().

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

Returns true if other 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 implement operator==().

See also operator==().

This function requires the value type to implement operator==().

See also operator!=().

Related Non-Members

QDataStream & operator<< ( QDataStream & out, const QLinkedList<T> & list )

Writes the linked list list to stream out.

This function requires the value type to implement operator<<().

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

Reads a linked list from stream in into list.

This function requires the value type to implement operator>>().

The documentation provided herein is licensed under the terms of the GNU Free Documentation License version 1.3 as published by the Free Software Foundation.

Documentation sources may be obtained from www.qt-project.org.

Nokia, Qt and their respective logos are trademarks of Nokia Corporation in Finland and/or other countries worldwide. All other trademarks are property of their respective owners. Privacy Policy

QLinkedList

Public Types

Public Functions

Static Public Members

Related Non-Members

Detailed Description

Member Type Documentation

Member Function Documentation

Related Non-Members

QDataStream & operator<< ( QDataStream & out, const QLinkedList<T> & list )

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

1. Choose your focus

2. Download the tools

3. Try the sample apps

4. Educate yourself

5. Start developing