Hi Everyone

In this tutorial we will talk about List.

So, what is list actually?

List is a doubly linked list container in C++ STL. List is a sequential container of STL.

Since, its underlying data structure is doubly linked list, list has a dynamic property regarding memory allocation.

Header File Inclusion for list

#include <list>

Declaration & Initialization

Empty Declaration

list<int> dbList;

Declaring with values

list<int> dbList { 1, 2, 5 };

Insertion

Insertion at the end

list<int> dbList;
dbList.push_back(5);
dbList.push_back(15);
dbList.push_back(12);

After insertion at the end, dbList will have, dbList = { 5, 15, 12 };

Insertion at the beginning

dbList.push_front(25);
dbList.push_front(17);
dbList.push_front(41);

After insertion at the beginning, dbList = { 41, 17, 25, 5, 15, 12 }

Insertion using insert() method

insert() method works differently based on parameters.  We can insert values at any position (i-th position) by giving the position and value as parameter in function call —

/**
here, 
    first parameter is the position
    second parameter is the value
dbList.insert(dbList.begin() + i, value);
**/
dbList.insert(dbList.begin() + 2, 23);

After insertion at the i-th position, dbList = { 41, 17, 23, 25, 5, 15, 12 }
We can also insert same value multiple times at i-th position —

/**
here, 
    first parameter is the position
    second parameter is the count(how many times the value will be inserted)
    third parameter is value
dbList.insert(dbList.begin() + i, count, value);
**/
dbList.insert(dbList.begin() + 1, 3, 55);

After insertion value multiple times, dbList = { 41, 55, 55, 55, 17, 23, 25, 5, 15, 12 }

Again, we can also insert range of values —

/**
here, 
    first parameter is the position
    second parameter is begin of range
    third parameter is end of range
dbList.insert(dbList.begin() + i, count, value);
**/
list <int> subList { 2, 6, 9 };
dbList.insert(dbList.begin() + 2, subList.begin(), subList.end());

After insertion range of values, dbList = { 41, 55, 2, 6, 9, 55, 55, 17, 23, 25, 5, 15, 12 }

Accessing the element

Front element

// here num will be 41
int num = dbList.front();

Last element

// here num will be 12
int num = dbList.back();

Deletion

Deletion at back

We can easily delete last element from the list using pop_back() method —

// deleting last element from the list
dbList.pop_back();

After deletion at  back, dbList = { 41, 55, 2, 6, 9, 55, 55, 17, 23, 25, 5, 15 }

Deletion at front

We can easily delete first element from the list using pop_front() method —

// deleting first element from the list
dbList.pop_front();

After deletion at  front, dbList = { 55, 2, 6, 9, 55, 55, 17, 23, 25, 5, 15 }
Using remove() method

remove() method removes all copies of given data —

// removing all copies of 5 from the list
dbList.remove(5);

Now, dbList = { 55, 2, 6, 9, 55, 55, 17, 23, 25, 15 }

Using remove_if() method

remove_if() takes a predicate to remove elements —

// here, we are using even predicate to remove elements
bool even(int& value) {
    return value % 2 == 0;
}

// removing even elements from list
dbList.remove_if(even);

Now, dbList = { 55, 9, 55, 55, 17, 23, 25, 15 }

Using erase() to remove elements

erase() method can take iterator position for deletion —

// iterator position for list
list<int>::iterator it = dbList.begin();

// advancing by 5
advance(it, 5);

// removing element from given iterator position
dbList.erase(it);

Now, dbList = { 55, 9, 55, 55, 17, 25, 15 }

erase() method also can remove a range of elements

// iterator position for list
list<int>::iterator itStart = dbList.begin();
list<int>::iterator itEnd = dbList.begin();
// advancing by 1
advance(itEnd, 1);
// removing range of element
dbList.erase(itStart, itEnd);

Now, dbList = { 55, 55, 17, 25, 15 }

Removing duplicate elements

Using unique() method, we can remove duplicate elements from list —

// removing duplicate elements
dbList.unique();

Now, dbList = { 17, 25, 15 }

clear() method

// removing all elements from list
dbList.clear();

Now, dbList = {  }

Assign

Assigning values to list using assign() method is similar to assigning values to a variable. assign() method first removes all elements from the list then assign new values —

// declaring a list with values
list <int> dbList { 5, 2,7};

// assigning values to the list
// first parameter - count of the values
// second parameter - value we wanna put
dbList.assign(5, 25);

Now, dbList = { 25, 25, 25, 25, 25 }

Using assign() method we can also copy the elements from —

// declaring an empty list
list <int> copyList;

// assigning values to the list
// first parameter - begin iterator of other list
// second parameter - end iterator of other list
dbList.copy(dbList.begin(), dbList.end());

Now, copyList also holds the same element, copyList =  { 25, 25, 25, 25, 25 }

Reversing the element

We can easily reverse the elements of list using reverse() method —

// declaring a list with values
list <int> dbList { 5, 2, 7, 15, 26, 12 };

// reversing the elements of list
dbList.reverse();

Now, dbList = { 12, 26, 15, 7, 2, 5 }

Sorting the list elements

We can easily sort list elements using sort() method —

// sorting the elements of list
dbList.sort();

Now, dbList = { 2, 5, 7, 12, 15, 26 }

Swapping elements between two lists

We can easily swap elements between two lists using swap() method —

// declaring lists with values
list <int> listOne { 1, 3, 5, 7, 9 };
list <int> listTwo { 2, 4, 6, 8 };

// swapping elements
listOne.swap(listTwo);

Now, listOne = { 2, 4, 6, 8 }
listTwo = { 1, 3, 5, 7, 9 }

Merging sorted elements of two lists

For merging sorted elements of two lists, first we need sort elements of two lists. Then, we can merge elements of two lists using merge() method —

// declaring lists with values
list <int> listOne { 1, 5, 12, 9 };
list <int> listTwo { 11, 2, 9, 6};

// sorting
listOne.sort();
listTwo.sort();

// merging elements
listOne.merge(listTwo);
// now listOne will hold all elements of two lists in sorted manner

Now, listOne = { 1, 2, 5, 6, 9, 9, 11, 12 }

Time Complexity

Operation	Description	Time Complexity
begin()	It returns an iterator pointing to the first element in list	O(1)
end()	Returns the iterator pointing next to the last element of vector	O(1)
front()	Accessing front element	O(1)
back()	Accessing back element	O(1)
push_back()	Insert value at end	O(1)
push_front()	Insert value at begin	O(1)
pop_back()	Remove value at end	O(1)
pop_front()	Remove value at begin	O(1)
empty()	Returns a bool value False if vector is not empty True if vector is empty	O(1)
size()	Returns the number of elements present in the list	O(1)
insert()	Insert new elements in the list	O(n)
assign()	It assigns new elements to the list By replacing its current elements	O(n + m) n - elements that deleted m - elements that inserted
emplace()	Insert new elements in the list	O(n)
erase()	It removes a single element or the range of element from the list	O(n)
remove()	Remove given values from the list	O(n)
remove_if()	Remove values using a predicate	O(n)
reverse()	Reversing the whole list	O(n)
unique()	Removes duplicate elements	O(n)
swap()	Swap elements between two lists	O(n)
merge()	Merge sorted elements of two list	O(n)

Applications

Adjacency List

Adjacency list is a form of graph representation where adjacency describes a particular node’s neighbors in a graph. We can create adjacency list easily by using array of list.

Let’s say, we have V vertices. Then adjacency list will be —

// If the nodes are denoted by integer and starts from 0
list <int> adja[v];

// If the nodes are denoted by integer and starts from 0
list <int> adja[v + 1];

// If the nodes are denoted by char
list <char> adja[v];

// If the nodes are denoted by string
list <string> adja[v];

For now, that’s all from list

See you next time. 

Happy Coding