C++ List

In C++, the std::list represents a sequential container that facilitates the storage of elements in a non-contiguous manner. It is structured as a doubly linked list, wherein each element holds references to both the preceding and succeeding list elements. This setup permits the storage of data in discontinuous memory locations, enabling efficient addition and removal operations at any specified position.

Unlike the std::vector, which stores elements in contiguous memory allowing for quick random access, a list offers sequential access where elements are accessed by traversing from the front or back.

The std::list enables bidirectional access and offers an effective method for performing insertions and deletions. Nevertheless, traversing the list can be sluggish since elements are accessed sequentially, unlike a vector that allows for random access.

Syntax

It has the following syntax:

list<type> list_name;

In this structure,

• ✅ type: It indicates the kind of elements within the list.
• ✅ list_name: It signifies the name assigned to the list.

Initialization of List

The list can be initialised in two ways.

list<int>  new_list{1,2,3,4};

list<int> new_list = {1,2,3,4};

C++ Declaration and Initialization List Example

Let's consider a scenario to demonstrate how we can define and set values for an array in C++.

Example

#include <iostream>

#include <string.h>

using namespace std;  //using standard namespace

class Test{

public:

int hno;

string city, state;

Test( int hno, string city, string state )

{ this->hno = hno;

this->city = city;

this->state = state;

}

};

class Address

{

private:

Test* addr;

public:

string name;

Address( string name, Test* addr )

{	

this->name = name;

this->addr = addr;

}

void display( )

{

cout<< " Name : " << name << " \n " << " Hno : " << addr->hno << " \n " << " City : " << addr->city << " \n " << " State : " << addr->state << endl << " ------------------------- " << endl;

}

};

int main( ) {

Test obj1= Test( 45 ,"Los Angeles","USA" );

Test obj2 = Test( 65, " London","UK" );

Address a1 = Address( "Joy",&obj1 );

Address a2 = Address( "Jack",&obj2 );

cout << " Below are the details : " << endl << " ------------------------------ " << endl;

a1.display( );

a2.display( );

return 0;

}

Output:

10 20 30

Explanation:

In this instance, we demonstrate different methods to declare and set up std::list, such as utilizing an initializer list, defining repeated values, and duplicating from a different list. Subsequently, we employ a range-based for loop to iterate through and display the elements of list2.

Basic Operations of C++ List

There are various actions carried out on std::list in C++. Some key operations include:

1) push_back and push_front

In C++, the pushback method adds an item at the end, while pushfront inserts an element at the start. These functions are commonly used for queue and deque functionalities.

C++ pushback and pushfront Function Example

Let's consider a scenario to demonstrate the pushback and pushfront methods in C++.

Example

#include <iostream>

#include <list>     // Required for std::list

#include <string>   // Required for std::string

using namespace std;   //using standard namespace

void printList(const list<int>& lst, const string& msg) {

    cout << msg;

    for (int val : lst) cout << val << " ";

    cout << "\n";

}

int main() {   //main function

    list<int> myList;

    printList(myList, "Initial list: ");

    myList.push_back(30);

    printList(myList, "After push_back(30): ");

    myList.push_front(10);

    printList(myList, "After push_front(10): ");

    myList.push_back(40);

    printList(myList, "After push_back(40): ");

    myList.push_front(5);

    printList(myList, "After push_front(5): ");

    return 0;

}

Output:

Initial list: 

After push_back(30): 30 

After push_front(10): 10 30 

After push_back(40): 10 30 40 

After push_front(5): 5 10 30 40

Explanation:

In this instance, we showcase the std::list container by adding elements to both the beginning and end through the pushfront and pushback methods. Subsequently, a printList function has been implemented to display the current list status following each insertion along with a personalized notification.

2) pop_front and pop_back

In C++, the popfront method eliminates the initial element, while the popback method removes the final element in the list. These methods are additionally employed to reduce lists from either end.

In this C++ example, we demonstrate the utilization of the popfront and popback functions with a list. These functions are used to remove elements from the front and back of the list, respectively. Let's delve into the implementation of these functions:

#include <iostream>
#include <list>

int main() {
    std::list<int> myList = {10, 20, 30, 40, 50};

    // Removing element from the front of the list
    myList.pop_front();
    
    // Removing element from the back of the list
    myList.pop_back();

    // Displaying the updated list
    for (const auto &element : myList) {
        std::cout << element << " ";
    }
    
    return 0;
}

Let's consider a scenario to demonstrate the functionalities of the popfront and popback methods in C++.

Example

#include <iostream>

#include <list>

#include <string>

using namespace std;   //using standard namespace

void printList(const list<int>& lst, const string& msg) {

    cout << msg;

    for (int val : lst) cout << val << " ";

    cout << "\n";

}

int main() {   //main function

    list<int> myList = {10, 20, 30, 40, 50};

    printList(myList, "Original list: ");

    myList.pop_front();

    printList(myList, "After pop_front(): ");

    myList.pop_back();

    printList(myList, "After pop_back(): ");

    myList.pop_back();

    printList(myList, "After another pop_back(): ");

    return 0;

}

Output:

Original list: 10 20 30 40 50 

After pop_front(): 20 30 40 50 

After pop_back(): 20 30 40 

After another pop_back(): 20 30

Explanation:

In this illustration, we showcase the process of eliminating elements from a std::list by employing the popfront and popback methods. Subsequently, the printList function exhibits the list's contents following each operation. Initially, the list is populated with five elements, and then elements are sequentially removed from the front and back utilizing popfront and popback functions to illustrate the dynamic alterations in the list.

3) insert

In C++, elements can be inserted at any location using iterators, enabling the addition of new elements ahead of a particular position.

C++ List Example using insert function

Let's consider a scenario to demonstrate the implementation of the insert function in C++.

Example

#include <iostream>

#include <list>

#include <string>

using namespace std;  //using standard namespace

void printList(const list<int>& lst, const string& msg) {

    cout << msg;

    for (int val : lst) cout << val << " ";

    cout << "\n";

}

int main() {   //main function

    list<int> myList = {10, 20, 40};

    printList(myList, "Initial list: ");

    auto it = myList.begin();

    ++it; // points to 20

    myList.insert(it, 15);

    printList(myList, "After insert(15) before 20: ");

    it = myList.end();

    myList.insert(it, 50);

    printList(myList, "After insert(50) at end: ");

    it = myList.begin();

    myList.insert(it, 5);

    printList(myList, "After insert(5) at beginning: ");

    return 0;

}

Output:

Initial list: 10 20 40 

After insert(15) before 20: 10 15 20 40 

After insert (50) at end: 10 15 20 40 50 

After insert(5) at the beginning: 5 10 15 20 40 50

Explanation:

In this illustration, we showcase the process of adding elements to a std::list at particular positions by leveraging iterators. The process initiates with a base list {10, 20, 40} and proceeds to insert 15 before 20 utilizing an iterator. Subsequently, we add 50 at the end employing the end iterator, and include 5 at the start using the begin iterator. Ultimately, the printList function exhibits the list post each insertion, revealing the revised sequence of elements.

4) erase

In C++, the erase method is utilized to delete the element at a specified position or within a range. Subsequently, the removal based on iterators enables accurate management.

C++ List Example using erase function

Let's consider an example to demonstrate the utilization of the erase function in C++.

Example

#include <iostream>

#include <list>

#include <string>

using namespace std;  //using standard namespace

void printList(const list<int>& lst, const string& msg) {

    cout << msg;

    for (int val : lst) cout << val << " ";

    cout << "\n";

}

int main() {   //main function

    list<int> myList = {5, 10, 15, 20, 25, 30};

    printList(myList, "Original list: ");

    auto it = myList.begin();

    ++it; // points to 10

    myList.erase(it);

    printList(myList, "After erasing element at position 2 (10): ");

    it = myList.begin();

    advance(it, 2); // points to 20

    auto it2 = myList.end();

    advance(it2, -1); // points to 30

    myList.erase(it, it2);

    printList(myList, "After erasing elements from 20 up to 30: ");

    return 0;

}

Output:

Original list: 5 10 15 20 25 30 

After erasing element at position 2 (10): 5 15 20 25 30 

After erasing elements from 20 up to 30: 5 15 30

Exaplantion:

In this instance, we showcase the process of eliminating elements in C++ by applying the erase method with std::list. Initially, a list {5, 10, 15, 20, 25, 30} is set up. Subsequently, the second element (10) is eliminated using an iterator. Lastly, a series of elements ranging from 20 to 30 are deleted by utilizing erase(it, it2) alongside iterators. The function printList exhibits the list's status post each deletion.

5) size and empty

In C++, the size method is employed to retrieve the count of elements, while the empty function verifies whether the list contains no elements. These functions are valuable for condition evaluations and iterative processes.

In the following C++ example, we demonstrate the utilization of the size and empty functions with a list container:

#include <iostream>
#include <list>

int main() {
    std::list<int> numbers;

    std::cout << "Is the list empty? " << (numbers.empty() ? "Yes" : "No") << std::endl;

    numbers.push_back(10);
    numbers.push_back(20);
    numbers.push_back(30);

    std::cout << "Size of the list: " << numbers.size() << std::endl;

    return 0;
}

Let's use a scenario to demonstrate the implementation of the size and empty methods in a C++ List.

Example

#include <iostream>

#include <list>

using namespace std;  //using standard namespace

int main() {   //main function

    list<int> myList;

    cout << "Initially: Size = " << myList.size() << ", Is empty? " 

              << (myList.empty() ? "Yes" : "No") << "\n";

    myList.push_back(100);

    myList.push_back(200);

    cout << "After adding elements: Size = " << myList.size() << ", Is empty? " 

              << (myList.empty() ? "Yes" : "No") << "\n";

    return 0;

}

Output:

Initially: Size = 0. Is empty? Yes

After adding elements: Size = 2, Is empty? No

Explanation

In this illustration, we showcase the utilization of the size and empty member methods within the list container. Initially, an empty list is instantiated, and subsequently, we present its size and whether it is empty. Following this, two integer values (100 and 200) are appended using the push_back operation.

6) clear

In C++, the clear function is primarily utilized to eliminate all elements from the list, effectively emptying it. This is beneficial for repurposing the list without the need for reallocation.

C++ List Example using clear function

Let's consider an example to demonstrate the clear method in a C++ List.

Example

#include <iostream>

#include <list>

using namespace std;   //using standard namespace

int main() {   //main function

    list<int> myList = {1, 2, 3, 4, 5};

    cout << "Before clear(), size = " << myList.size() << "\n";

    myList.clear();

    cout << "After clear(), size = " << myList.size() << "\n";

    return 0;

}

Output:

Before clear(), size = 5

After clear(), size = 0

Explanation:

In this instance, we showcase the clear method of the std::list container. Initially, a list is created containing 5 integers. Subsequently, the list's size is displayed both before and after invoking the clear method, which eliminates all elements from the list. Following the clear operation, the list is devoid of elements, resulting in a size of 0.

7) sort

In C++, the sort function is primarily utilized for arranging the list in ascending order. Furthermore, it is specifically designed for sortable data types.

C++ List Example using the sort Function

Let's consider a demonstration to explain the sort operation in a C++ List.

Example

#include <iostream>

#include <list>

#include <string>

using namespace std;  //using standard namespace

void printList(const list<int>& lst, const string& msg) {

    cout << msg;

    for (int val : lst) cout << val << " ";

    cout << "\n";

}

int main() {   //main function

    list<int> myList = {40, 10, 50, 20, 30};

    printList(myList, "Before sort: ");

    myList.sort();

    printList(myList, "After sort: ");

    return 0;

}

Output:

Before sort: 40 10 50 20 30 

After sort: 10 20 30 40 50

Explanation:

In this instance, we showcase the process of organizing a std::list by employing the sort member function. Initially, the list contains unordered elements {40, 10, 50, 20, 30}. Subsequent to invoking the myList.sort method, the list undergoes reorganization into ascending sequence as {10, 20, 30, 40, 50} and is then exhibited.

9) reverse

In C++, the reverse method is employed to invert the sequence of items within the list. This method does not have a return value; instead, it directly alters the elements within the list.

C++ List Example using reverse function

Let's consider a scenario to demonstrate the functionality of the reverse method in C++.

Example

#include <iostream>

#include <list>

#include <string>

using namespace std;   //using standard namespace

void printList(const list<int>& lst, const string& msg) {

    cout << msg;

    for (int val : lst) cout << val << " ";

    cout << "\n";

}

int main() {    //main function

    list<int> myList = {10, 20, 30, 40};

    printList(myList, "Before reverse: ");

    myList.reverse();

    printList(myList, "After reverse: ");

    return 0;

}

Output:

Before reverse: 10 20 30 40 

After reverse: 40 30 20 10

Explanation:

In this illustration, we showcase the process of reversing the order of elements in a list by employing the reverse method. Initially, the list is populated with {10, 20, 30, 40} elements. Subsequently, upon invoking the myList.reverse method, the sequence within the list transforms to {40, 30, 20, 10} prior to being exhibited.

9) remove(value)

In C++, the remove(value) method is utilized for eliminating all elements that match the given value. This function proves to be a proficient approach for eliminating duplicates or undesired values.

C++ List Example using remove (Value) function

Let's consider a scenario to demonstrate the erase (value) operation in a C++ List.

Example

#include <iostream>

#include <list>

#include <string>

using namespace std;   //using standard namespace

void printList(const list<int>& lst, const string& msg) {

    cout << msg;

    for (int val : lst) cout << val << " ";

    cout << "\n";

}

int main() {   //main function

    list<int> myList = {10, 20, 10, 30, 10, 40};

    printList(myList, "Original list: ");

    myList.remove(10);

    printList(myList, "After removing all 10s: ");

    return 0;

}

Output:

Original list: 10 20 10 30 10 40 

After removing all 10s: 20 30 40

Explanation:

In this instance, we showcase the process of eliminating every instance of a particular value from a list. At the beginning, the list comprises elements {10, 20, 10, 30, 10, 40}. Subsequently, upon invoking the remove(10) function, all occurrences of 10 are removed from the list, leading to {20, 30, 40}, which is then exhibited.

C++ List Functions

There are multiple functions available in the C++ List. These include:

C++ Example Program to display various functions on List

Let's consider an example to demonstrate the various operations on the C++ List.

Example

#include <iostream>

#include <list>

using namespace std;   //using standard namespace

int main() {   //main function

    list<int> list1 = {3, 1, 4, 1, 5};

    list<int> list2 = {2, 7, 1};

    // push_back and push_front

    list1.push_back(9);

    list1.push_front(0);

    // insert at 2nd position

    auto it = list1.begin();

    advance(it, 2);

    list1.insert(it, 8);

    // emplace and emplace_front

    list1.emplace(it, 6);         // Inserts before iterator

    list1.emplace_front(-1);      // Inserts at front

    // pop operations

    list1.pop_back();

    list1.pop_front();

    // front and back

    cout << "Front: " << list1.front() << ", Back: " << list1.back() << endl;

    // size, max_size, empty

    cout << "Size: " << list1.size() << ", Max Size: " << list1.max_size() << endl;

    cout << "Is Empty: " << (list1.empty() ? "Yes" : "No") << endl;

    // sort and unique

    list1.sort();

    list1.unique();

    // reverse

    list1.reverse();

    // assign new values

    list2.assign(3, 10);  // 10 10 10

    // resize

    list2.resize(5, 99);  // fills with 99

    // merge list2 into list1 (both must be sorted)

    list1.sort();

    list2.sort();

    list1.merge(list2);

    // splice (move elements from one list to another)

    list<int> list3 = {50, 60};

    list1.splice(list1.begin(), list3);  // moves list3 to front of list1

    // swap

    list<int> list4 = {100, 200};

    list1.swap(list4);

    // Final Output

    cout << "Final list4 after swap (was list1): ";

    for (int x : list4) cout << x << " ";

    cout << endl;

    cout << "Final list1 after swap (was list4): ";

    for (int x : list1) cout << x << " ";

    cout << endl;

    return 0;

}

Output:

Front: 0, Back: 5

Size: 8, Max Size: 384307168202282325

Is Empty: No

Final list4 after swap (was list1): 50 60 0 1 3 4 5 6 8 10 10 10 99 99 

Final list1 after swap (was list4): 100 200

Explanation:

In this instance, we showcase the manipulation of a std::list through various functions like insert, emplace, splice, sort, merge, and others. Each function illustrates a distinct list operation like adding, removing, updating, or combining lists. Subsequently, the swap function switches the contents of two lists, showcasing the comprehensive alterations and data transfer between them.

C++ List MCQs

1) Which of the following statements matches the functionality of std::list's splice function in C++?

• ✅ It tests each item in the list against a condition and removes those that fit.
• ✅ It copies each element from one list and puts them into the other list.
• ✅ It can quickly move elements from one list to another without the need to copy or move them.
• ✅ It deletes a specified range of elements, saves them as a separate list and returns the new list.

c) Elements can be efficiently transferred from one list to another without the necessity of duplicating or relocating them.

2) When we apply unique function to a list where the duplicates are not next to each other, what does it return?

• ✅ It deletes all occurrences of the same element, no matter where it originally appeared in the list.
• ✅ This algorithm only takes out the first match of a repeated element within the list.
• ✅ After sorting, the code removes all items that appear more than once in the list.
• ✅ It deletes just those duplicate elements that are next to each other.

Option d) Removes only consecutive duplicate elements.

3) When two std::list containers are used with the merge function, what does the function do?

• ✅ Adds the second list to the end of the first list, regardless of how the lists are arranged.
• ✅ Combines two sorted lists into another single sorted list with the data already in order.
• ✅ Arrange both lists in order before merging them without intervention.
• ✅ Produces a new list containing elements arranged in descending order from both the original lists.

Answers: b) Merges two sorted lists to create a new sorted list with the existing data arranged in a sequential order.

4) When should we consider std::vector over std::list while selecting a container in C++?

• ✅ If the code must frequently insert and delete items right at the ends of the container.
• ✅ If we need to organize the elements more than once.
• ✅ When we need to access the elements in an array by using an index number.
• ✅ When we need the collection to expand or shrink based on its contents.

When there is a requirement to retrieve elements from an array based on an index value.

5) What is the result if we sort a list of custom objects without declaring any comparison function?

• ✅ The program will organize the objects by the memory address assigned to them.
• ✅ A compile-time error is produced when there is no operator (<) present in the program.
• ✅ The list will not be sorted and will remain unchanged.
• ✅ An error will be raised during runtime because we forgot to include a comparison check.

Option b) An error occurs during compilation if the program lacks the (<) operator.