List in C++
FREE
Overview
Lists are one of the sequence containers available in C++ STL that store elements in a non-contiguous manner. It permits iteration in both directions. Insert and erase operations anywhere inside the sequence are completed in constant time. List containers are constructed as doubly-linked lists, which allow each of the elements, they contain to be stored in non-continuous memory locations.
What is a std::list?
std::list in C++ is a storage container. We can use the std::list to insert and remove items from any location. A doubly-linked list is used to implement the std::list. This means that list data can be retrieved in both directions. Internally, the ordering is maintained by associating each element with a connection to the element before it and a connection to the element after it.
List Syntax
The syntax of list in C++ is as follows
data_type: data type of the elements of the list list_name: variable/list name
Why use std::list?
The following are some of the benefits of using std::list:
- In comparison to other sequence containers such as array and vector, std::list performs better due to its non-contiguous storage.
- They perform better while inserting, moving, and removing items from any location. Insertion and deletion of elements from the list take time.
- The std::list also performs better with algorithms that execute a lot of these operations.
C++ List Functions
The following are some of the List functions available in C++:
| Function | Description |
|---|---|
| front() | It returns the value of the first element in the list. |
| back() | It returns the value of the last element in the list. |
| insert() | It inserts the new element before the position at which the iterator points. |
| push_front() | It inserts an element at the starting of the list. |
| push_back() | It inserts an element at the end of the list. |
| pop_front() | It removes an element from the starting of the list. |
| pop_back() | It removes an element from the end of the list. |
| begin() | It returns an iterator to the starting of the list. |
| end() | It returns an iterator to the end of the list. |
| rbegin() | It returns a reverse iterator to the end of the list |
| rend() | It returns a reverse iterator pointing to the position before the beginning of the list. |
| empty() | Check if the container is empty, returns true if it is empty, else it returns false. |
| size() | It returns the number of elements in the list |
| max_size() | It returns the maximum possible size of the list |
| reverse() | It reverses the order of elements in the list. |
| clear() | It removes all the elements in the list. |
| swap() | It swaps two lists when the type of both lists are the same. |
| sort() | It sorts the list elements in increasing order. |
| merge() | It merges the two sorted lists. |
| splice() | It inserts a new list into the invoking list. |
Example explaining List STL functions
There are various List STL functions available in C++. Let's look at the following example to understand the basic of List STL functions.
Output:
Explanation:
-
Two list variable are declared using: list<int> list1, list2;
-
list1.push_back(i); inserts an element at the end of the list1 in the range [0,4]. List1 has {0, 1, 2, 3, 4}.
-
list2.push_front(i+5); inserts an element before the starting of the list2 in the range [5,9]. List2 has {9, 8, 7, 6, 5}.
-
print(list1); is a function call to void print(list<int> lst). In this function list
::iterator it; creates an iterator of a list which will traverse throughout the list. -
list1.front(); and list1.back(); returns the value of the first element which is 0 and last element in the list1 which is 4.
-
list1.pop_front(); removes an element from the starting of the list1, that is 0 is removed, now list1 is {1, 2, 3, 4}.
-
list2.pop_back(); removes an element from the end of the list2, that is 5 is removed, now list2 is {9, 8, 7, 6}.
Lexicographically comparing Lists
Lists do not have their standard value because they are collections of elements. Thus, we compare the elements of a list or vector in their lexicographical order to compare them.
If we set list1 = 1, 2, 3 and list2 = 1, 3, 2 we may check whether list1 is bigger than list2 or not by looking at the elements of each list in the order they appear in the lists.
First, we compare the first elements of both the lists. We continue because 1 in list1 equals 1 in list2, and then 2 in list1 is smaller than 3 in list2, indicating that list2 is lexicographically greater than list1.
The operators ==, >,=, and >= can be used to compare lists lexicographically.
Conclusion
- std::list in C++ is a storage container that stores elements in a non-contiguous manner and is implemented as a doubly linked list. We can insert and remove items from any location in the std::list.
- Whenever we require more insertion and deletion operations, a list is preferred over vectors and arrays.
- There are various list STL functions, such as push_front() to insert an element at the start, push_back() to insert an element at the end, size() to check the size of the list, etc.
- We compare the elements of a list or vector in their lexicographical order to compare them.