List Built-in Functions

List Built-in Functions:

Constructor

Name	Details	Time Complexity
list<type>myList;	Construct a list with 0 elements.	O(1)
list<type>myList(N);	Construct a list with N elements and the value will be garbage.	O(N)
list<type>myList(N,V);	Construct a list with N elements and the value will be V.	O(N)
list<type>myList(list2);	Construct a list by copying another list list2.	O(N)
list<type>myList(A,A+N);	Construct a list by copying all elements from an array A of size N.	O(N)
list<type>myList(v.begin(),v.end());	Construct a list by copying all elements from a vector v.	O(N)

Capacity

Name
Details
Time Complexity
myList.size()
Returns the size of the list.
O(1)
myList.max_size()
Returns the maximum size that the list can hold.
O(1)
myList.clear()
Clears the list elements.
O(N)
myList.empty()
Return true/false if the list is empty or not.
O(1)

myList.resize()
Change the size of the list.
O(K); where K is the difference between new size and current size.

Modifiers

Name
Details
Time Complexity
myList= or myList.assign(list2.begin(),list2.end())
Assign another list.
O(N)
myList.push_back()
Add an element to the tail.
O(1)
myList.push_front()
Add an element to the head.
O(1)
myList.pop_back()
Delete the tail.
O(1)
myList.pop_front()
Delete the head.
O(1)
myList.insert()
Insert elements at a specific position.
O(N+K); where K is the number of elements to be inserted.
myList.erase()
Delete elements from a specific position.
O(N+K); where K is the number of elements to be deleted.

replace(myList.begin(),myList.end(),value,replace_value)
Replace all the value with replace_value. Not under a list STL.
O(N)
find(myList.begin(),myList.end(),V)
Find the value V. Not under a list STL.
O(N)

Operations

Name
Details
Time Complexity
myList.remove(V)
Remove the value V from the list.
O(N)
myList.sort()
Sort the list in ascending order.
O(NlogN)
myList.sort(greater<type>())
Sort the list in descending order
O(NlogN)
myList.unique()
Deletes the duplicate values from the list. You must sort the list first.
O(N), with sort O(NlogN)
myList.reverse()
Reverse the list.
O(N

Name
Details
Time Complexity
myList.begin()
Pointer to the first element.
O(1)
myList.end()
Pointer to the last element.
O(1)