Lists are sequences of elements stored in a linked list. Compared to vectors, they allow fast insertions and deletions, but slower random access as we need to traverse all the elements to finding any element. List container's are implemented using double linked list.
Lists Operators
- assign - assign an element to list
- back - returns a reference to the last element of a list
- begin - returns a reference iterator to the beginning of the list
- clear - deletes all elements from the list
- empty - returns true(1) if the list has no elements else return false(0).
- end - return a reference iterator just past the last element of a list
- erase - deletes elements from a list
- front - returns a reference iterator to the first element of a list
- insert - inserts elements into the list
- max_size - outputs the number of the maximum number of elements that the list can hold
- merge - merge two list
- pop_back - removes the last element from the list
- pop_front - removers the first element from the list
- push_back - add an element to the end of the list
- push_front - add an element to the front of the list
- rbegin - returns a reverse_iterator to the end of the list
- remove - removes elements from a list
- remove_if - removes element if the given condition is fulfilled.
- rend - returns a reverse_iterator to the beginning of the list
- resize - used to change the size of the list
- reverse - reverse the list.
- size - outputs the number of items in the list
- sort - sorts a list into ascending order
- splice - merge two lists in constant time
- swap - swap the contents of this list with another list.
- unique - removes the consecution duplicate element.
assign()
- This function assign value(s) to the list having some count of value(s). for eg: assign 3 elements with value 10 will be like 10 10 10.
- This can also be used to copy an element from one vector to another.
#include<bits/stdc++.h>
using namespace std;
void print_list(list<int> l){
for(auto l1 : l){
cout<<l1<<" ";
}
cout<<endl;
}
int main(){
list<int> list1;
cout<<"assigning 5 elements with value 10\n";
list1.assign(5,10);
print_list(list1);cout<<endl;
list<int> list2;
list2.assign(list1.begin(),list1.end());
cout<<"using assign to copy from one list1 to
another list2\n";
print_list(list2);cout<<endl;
cout<<"list1 after destroying previous contents\n";
list1.assign(3,100);
print_list(list1);
return 0;
}
Sponsered
back()
- The back() function returns a reference(not an iterator) to the last element in the list.
- The function begin() returns an iterator to the first element of the list.
- It runs in constant time.
- The function clear() deletes all of the elements in the list.
- It runs in linear time.
- The empty() function returns true if the list has no elements, false otherwise.
- The end() function returns an iterator just past the end of the list.
- Note that before you can access the last element of the list using an iterator that you get from a call to end(), you'll have to decrement the iterator first.
#include<bits/stdc++.h>
using namespace std;
void print_list(list<int> l){
for(auto l1 : l) cout<<l1<<" ";
cout<<endl;
}
int main(){
list<int> list1 = {10,20,30,40,50};
print_list(list1);
list<int>::iterator it1=list1.end();
//decrementing the iterator
it1--;
cout<<"end() : "<<*it1<<endl;
return 0;
}
erase()
- The erase() function either deletes the element at given location , or deletes the elements between start and end (including start but not including end). The return value is the element after the last element erased.
- The first version of erase (the version that deletes a single element at given location) runs in constant time for lists and linear time for vectors, dequeues, and strings. The multiple element version of erase always takes linear time.
#include<bits/stdc++.h>
using namespace std;
void print_list(list<int> l){
for(auto l1 : l) cout<<l1<<" ";
cout<<endl;
}
int main(){
list<int> list1 = {10,20,30,40,50,60};
cout<<"list before erasing any element\n";
print_list(list1);
list<int> ::iterator it1=list1.begin();
it1++;
list1.erase(it1);
cout<<"list after erasing element at position 2\n";
print_list(list1);
cout<<"list after erasing element from position 2 to
position 4\n";
auto it2=list1.begin();
it2++;//2nd position
auto it3=list1.begin();
advance(it3,4);//5th position
list1.erase(it2,it3);
print_list(list1);
return 0;
}
front()
- The front() function returns a reference(not an iterator) to the first element of the list.
- It runs in constant time.
The insert function either:
- inserts value before location, returning an iterator to the element inserted,
- inserts num copies of value before location, or
- inserts the elements from start to end before location
#include<bits/stdc++.h>
using namespace std;
void print_list(list<int> l){
for(auto l1 : l) cout<<l1<<" ";
cout<<endl;
}
int main(){
list<int> list1 = {10,20,30,40,50};
cout<<"original list\n";
print_list(list1);
auto it1=list1.begin();
advance(it1,2);//moved to 3rd position
list1.insert(it1,100);
cout<<"list1 after inserting 100 before 3rd positioned element\n";
print_list(list1);cout<<endl;
auto it2=list1.begin();
advance(it2,2);//3rd position
cout<<"inserting 3 occurence of 5 at 3rd position\n";
list1.insert(it2,3,5);
print_list(list1);
return 0;
}
max_size()
- The max_size() function returns the maximum number of elements that the list can hold. The max_size() function should not be confused with the size() or (C++ Strings) capacity() functions, which return the number of elements currently in the list and the the number of elements that the list will be able to hold before more memory will have to be allocated, respectively.
Sponsered
- The function merge() merges the list with lst, producing a combined list that is ordered with respect to the < operator. If compare function is specified, then it is used as the comparison function for the lists instead of <.
- merge() runs in linear time.
- Note that the list which is merged will become empty after merging
#include<bits/stdc++.h>
using namespace std;
void print_list(list<int> l){
for(auto l1 : l) cout<<l1<<" ";
cout<<endl;
}
bool compare(int first,int second){
return first < second;
}
int main(){
list<int> list1 = {20,10,30};
list<int> list2 = {3,2,1};
cout<<"list1 : ";
print_list(list1);
cout<<"list2 : ";
print_list(list2);cout<<endl;
list1.merge(list2);
cout<<"list1 after merging list1 and list2 in it\n";
print_list(list1);
// print_list(list2);
if(list2.empty()){
cout<<"list2 is empty\n";
}
cout<<endl;
list<int> list3 = {1,5,8};
list<int> list4 = {2,3,9};
cout<<"list3 : ";
print_list(list3);
cout<<"list4 : ";
print_list(list4);
list3.merge(list4,compare);
cout<<"list3 after merging list3 and list3 in it using compare function\n";
print_list(list3);
return 0;
}
pop_back()
- The pop_back() function removes the last element of the list
- pop_back() runs in constant time
- The function pop_front() removes the first element of the list.
- The pop_front() function runs in constant time.
- The push_back() function appends value to the end of the list
- The push_back() function runs in constant time.
- The push_front() function inserts val at the beginning of list.
- push_front() runs in constant time.
- The rbegin() function returns a reverse_iterator to the end of the current list.
- rbegin() runs in constant time.
- The function remove() removes all elements that are equal to val from the list.
- remove() runs in linear time.
- The remove_if() function removes all elements from the list for which the unary predicate is true.
- remove_if() runs in linear time .
#include<bits/stdc++.h>
using namespace std;
void print_list(list<int> l){
for(auto l1 : l) cout<<l1<<" ";
cout<<endl;
}
bool divisible_by_20(int value){
return (value%20)==0;
}
int main(){
list<int> list1 = {10,20,30,40,50,60};
cout<<"original list\n";
print_list(list1);
list1.remove_if(divisible_by_20);
cout<<"removing element from original list which are divisible by 20\n";
print_list(list1);
return 0;
}
rend()
- The function rend() returns a reverse_iterator to the beginning of the current list.
- rend() runs in constant time
resize()
- The function resize() changes the size of the list to size. If val is specified then any newly created elements will be initialized to have a value of val.
- This function runs in linear time.
reverse()
- The function reverse() reverses the list, and takes linear time
size()
- The size() function returns the number of elements in the current list.
sort()
- The sort() function is used to sort lists into ascending order. Ordering is done via the < operator, unless p is specified, in which case it is used to determine if an element is less than another.
- Sorting takes N log N time.
splice()
- The splice() function inserts lst at location pos. If specified, the element(s) at del or from start to end are removed.
- splice() simply moves elements from one list to another, and doesn't actually do any copying ordeleting. Because of this, splice() runs in constant time
#include<bits/stdc++.h>
using namespace std;
void print_list(list<int> l){
for(auto l1 : l) cout<<l1<<" ";
cout<<endl;
}
int main(){
list<int> list1 = {10,20,30,40};
list<int> list2 = {50,60,70};
cout<<"moving list2 elements in the begining of list1\n";
list1.splice(list1.begin(),list2);
cout<<"list1 : ";
print_list(list1);
cout<<"list2 is empty since all of its element have
been moved to list1\n";
cout<<endl;
list<int> list3 = {10,20,30,40};
list<int> list4 = {50,60,70};
auto it2 = list4.begin();
advance(it2,1);
list3.splice(list3.end(),list2,it2);
cout<<"moving a single element of list4 at the end of
list3\n";
cout<<"list3 : ";
print_list(list3);
cout<<"list4 : ";
print_list(list4);cout<<endl;
list<int> list5 = {10,20,30,40};
list<int> list6 = {50,60,70,80,90,100};
auto it3=list5.begin();
advance(it3,2);
auto it4=list6.begin();
auto it5=list6.begin();
advance(it4,1);
advance(it5,4);
cout<<"moving a range of element from list6 into list5\n";
list5.splice(it3,list6,it4,it5);
cout<<"list5 : ";
print_list(list5);
cout<<"list6 : ";
print_list(list6);
return 0;
}
swap()
The swap() function exchanges the elements of the current list with those of other. This
function operates in constant time
- Note that 2 lists to be swapped should be of same size and having same data type.
#include<bits/stdc++.h>
using namespace std;
void print_list(list<int> l){
for(auto l1 : l) cout<<l1<<" ";
cout<<endl;
}
int main(){
list<int> list1;
list<int> list2;
list<string> list3;
list3.assign(3,"amar");
list1.assign(3,10);
list2.assign(3,20);
cout<<"list1 : ";
print_list(list1);
cout<<"list2 : ";
print_list(list2);cout<<endl;
cout<<"after swapping\n";
list1.swap(list2);
cout<<"list1 : ";
print_list(list1);
cout<<"list2 : ";
print_list(list2);
return 0;
}
unique()
- The function unique() removes all consecutive duplicate elements from the list.
- Note that only consecutive duplicates are removed, which may require that you sort() the list first.
- unique() runs in linear time.
#include<bits/stdc++.h>
using namespace std;
void print_list(list<int> l){
for(auto l1 : l) cout<<l1<<" ";
cout<<endl;
}
int main(){
list<int> list1 = {20,10,10,10,30,40,10,20};
cout<<"original list\n";
print_list(list1);
list<int> list2;
list2.assign(list1.begin(),list1.end());
list1.sort();
cout<<"finding unique element of original list after using
sort() function\n";
list1.unique();
print_list(list1);
list2.unique();
cout<<"finding unique element of original list without
using sort() funciton\n";
print_list(list2);
return 0;
}
If you have some content OR material OR something is missing related to this then do share them through the comment section for which we will be thankful to you.
Thank You
With 💙 by Learn DSA
Tags:
C++ STL