Our June 2021 cohorts are filling up quickly. Join our free webinar to Uplevel your career
About usWhy usInstructorsReviewsCostFAQContactBlogRegister for Webinar

Attend our Free Webinar on How to Nail Your Next Technical Interview

WEBINAR +LIVE Q&A

How To Nail Your Next Tech Interview

Hosted By
Ryan Valles
Founder, Interview Kickstart
Our tried & tested strategy for cracking interviews
How FAANG hiring process works
The 4 areas you must prepare for
How you can accelerate your learnings

C++ STL Container Fundamentals: List

The Standard Template Library (STL) in C++ is a powerful software library that’s a set of C++ template classes. It provides built-in algorithms, functions, iterators, and containers. This article focuses on the C++ STL container List.

STL containers are objects that can store multiple elements, manage any storage required for the elements, and offer member functions that we can use to access them. A container may allow elements of either the same type or different types to be stored in it. Depending on this, and on whether it is unordered, the containers are divided into three types:

  • Sequence Containers: deque, arrays, vector, list, and forward_list
  • Associative Containers: set, multiset, map, and multimap
  • Unordered Associative Containers: unordered_set, unordered_multiset, unordered_map, and unordered_multimap

There are also Container Adapters: queue, priority_queue, and stack that are a subset of containers. These container adapters offer a different interface for sequential containers. 

To help you harness the power of STL and be a more efficient developer, we’re doing a series on C++ STL container fundamentals. This article focuses on the C++ STL container, List (check out the learn page for more).

Having trained over 10,000 software engineers, we know what it takes to crack the toughest tech interviews. Our alums consistently land offers from FAANG+ companies. The highest ever offer received by an IK alum is a whopping $1.267 Million!

At IK, you get the unique opportunity to learn from expert instructors who are hiring managers and tech leads at Google, Facebook, Apple, and other top Silicon Valley tech companies.

Want to nail your next tech interview? Sign up for our FREE Webinar.

In this article, we’ll cover:

  • C++ STL Container Fundamentals: List (std::list)
  • Use of the C++ STL Container Deque
  • Methods of std::list
  • How to Use C++ STL Container List
  • FAQs on C++ STL Container Fundamentals: List

C++ STL container Fundamentals: List (std::list)

List is a container that stores its elements in a non-contiguous manner by storing them in a linked list. Linked lists give us the freedom to add or delete elements in the container without having to declare the max size of the container. 

While the advantage of having this liberty is substantial in managing memory usage, this makes the traversal across the elements very slow. Why? Even if we know the index of an element, we can’t predict its memory location and jump to it. We will have to go to it traversing element to element.

Use of the C++ STL Container List

As discussed in the previous section, the List container is implemented using a linked list, commonly a doubly linked list. This is because lists are mainly used as stacks and queues, where we are mainly interested in optimizing the time for insertion and deletion of nodes at the beginning or the end of the list.

Methods of std::list

Here are the several methods associated with List in STL:

Let us now look at some of the most commonly used methods and how to use them.

How to Use C++ STL container List

Here, we take a look at how you can use List as a C++ STL container for a smoother coding experience:

Code Using std::list


// Usage of the methods of List in C++ STL
#include
#include 
#include 

using namespace std;

// Taking an example of an integer list

// A function to print an integer list for recurring use
void printList(list intListToPrint) {
    list ::iterator it;
    for (it = intListToPrint.begin(); it != intListToPrint.end(); ++it) {
        cout << " " << * it;
    }
    cout << "\n";
}

// Driver Code
int main() {
    list listExampleNum;

    for (int i = 0; i < 5; ++i) {
        listExampleNum.push_front(i);
    }

    // Adding extra elements at the back and front
    listExampleNum.push_back(100);
    listExampleNum.push_front(50);

    cout << "\nlistExampleNum contains:";
    printList(listExampleNum);

    // Getting the front-most element
    cout << "\nlistExampleNum.front(): " << listExampleNum.front();

    // Getting the back-most element
    cout << "\nlistExampleNum.back(): " << listExampleNum.back();

    // Pop the front-most element
    cout << "\nlistExampleNum.pop_front():";
    listExampleNum.pop_front();
    printList(listExampleNum);

    // Pop the back-most element
    cout << "listExampleNum.pop_back():";
    listExampleNum.pop_back();
    printList(listExampleNum);

    // Reverse the list
    cout << "listExampleNum.reverse():";
    listExampleNum.reverse();
    printList(listExampleNum);

    // Get the size of the list
    cout << "listExampleNum.size(): " << listExampleNum.size();

    // Sort the list
    cout << "\nlistExampleNum.sort():";
    listExampleNum.sort();
    printList(listExampleNum);

    // Creating a new list and sorting it (merge requires two sorted lists to be merged)
    cout << "\nCreating one more list and sorting it to use with merge later along with the sorted list above.";

    list listExampleSquare;

    for (int i = 0; i < 5; ++i) {
        listExampleSquare.push_front(i * i);
    }

    listExampleSquare.push_front(-1);
    listExampleSquare.push_back(36);
    cout << "\nAfter push_front(-1) and push_back(36):";
    printList(listExampleSquare);

    cout << "listExampleSquare.sort():";
    listExampleSquare.sort();
    printList(listExampleSquare);

    // Merging the two sorted lists
    cout << "Merging sorted lists listExampleNum and listExampleSquare:";
    listExampleNum.merge(listExampleSquare);
    printList(listExampleNum);

    // Assign three elements of value 20 (assign replaces the existing elements)
    cout << "\nlistExampleNum.assign(3, 20):";
    listExampleNum.assign(3, 20);
    printList(listExampleNum);
    cout << "\nAfter pushing 60 to the front:";
    listExampleNum.push_front(60);
    printList(listExampleNum);

    // Removing all the elements of value 20 in the list
    cout << "listExampleNum.remove(20):";
    listExampleNum.remove(20);
    printList(listExampleNum);

    return 0;
}

Output


listExampleNum contains:  50 4 3 2 1 0 100

listExampleNum.front(): 50
listExampleNum.back(): 100
listExampleNum.pop_front():  4 3 2 1 0 100
listExampleNum.pop_back():  4 3 2 1 0
listExampleNum.reverse():  0 1 2 3 4
listExampleNum.size(): 5
listExampleNum.sort():  0 1 2 3 4

Creating one more list and sorting it to use with merge later along with the sorted list above.
After push_front(-1) and push_back(36):  -1 16 9 4 1 0 36
listExampleSquare.sort():  -1 0 1 4 9 16 36
Merging sorted lists listExampleNum and listExampleSquare:  -1 0 0 1 1 2 3 4 4 9 16 36

listExampleNum.assign(3, 20):  20 20 20

After pushing 60 to the front:  60 20 20 20
listExampleNum.remove(20):  60

Want to learn more? Check out other posts on C++ STL container fundamentals in our learn folder!

FAQs on C++ STL Container Fundamentals: List

Q1. What is a list in STL?

A list is a sequence container that allows non-contiguous memory allocation. Compared to a vector, a list has a slower traversal. It optimizes the insertion/deletion time at the beginning or end of the list. The list in STL is usually implemented as a doubly-linked list. 

Q2. Is there any STL container for a linked list in C++?

Yes. In C++, we have the container list that implements a linked list in the Standard Template Library or STL. 

Q3. Is C++ list a linked list or a doubly-linked list?

C++ list in STL is a linked list implementation as a doubly-linked list.

Q4. Is STL allowed in coding interviews?

Yes! Unless they want to see you implement a specific algorithm by scratch, you can go for it. STL is allowed in coding interviews.

Q5. Which is a better choice: an array or a linked list?

A linked list is better in terms of memory and insertion/deletion time. In terms of search time, an array is better.

Ready to Nail Your Next Coding Interview?

Whether you’re a coding engineer gunning for a software developer or software engineer role, a tech lead, or you’re targeting management positions at top companies, IK offers courses specifically designed for your needs to help you with your technical interview preparation!

If you’re looking for guidance and help with getting started, sign up for our FREE webinar. As pioneers in technical interview preparation, we have trained thousands of software engineers to crack the most challenging coding interviews and land jobs at their dream companies, such as Google, Facebook, Apple, Netflix, Amazon, and more!

Sign up now!

Attend our Free Webinar on How to Nail Your Next Technical Interview

WEBINAR +LIVE Q&A

How To Nail Your Next Tech Interview

Hosted By
Ryan Valles
Founder, Interview Kickstart
Our tried & tested strategy for cracking interviews
How FAANG hiring process works
The 4 areas you must prepare for
How you can accelerate your learnings

Recommended Posts

All Posts