Do you think IIT Guwahati certified course can help you in your career?
Introduction
In this blog, we will learn about the list in CPP STL. We will start with a brief introduction of the list, then we will learn about the syntax to use, we will go through an example to develop a better understanding of the whole concept. Finally, we will learn about the various methods and functions we can use with them.
So let's dive straight into the blog and start with the introduction.
Lists in c++
Lists in c++ are containers that store the elements in a linear order like arrays, but it doesn't allow contiguous memory allocation, unlike arrays.
The elements of the lists are called nodes. Each element In the list contains its value and a pointer to the next element, and another to the previous element. This whole set of values of the element and pointer to the next and previous elements is called a node.
Since these elements are connected to each other only using the pointers and stored in non-contiguous memory locations, we lose the functionality of random access of the elements using indices. Thus to access any element in the list, we will have to start with the head of the linked list then pass through each element to reach the desired element. Thus we can say that the list has slow traversals as compared to the arrays or vectors.
Normally, lists refer to the Doubly Linked List, and for singly-linked lists, we use a forward list, which we will learn in some other blog. The only major difference in both of them is that we can only travel in one direction in a singly linked list, whereas in a doubly-linked list, we can traverse in both forward and backward directions.
Implementation
Let’s see an example to learn how to use a list and the various methods related to it-
To declare a list, we use the following syntax.
list<typename> list_name;
// CPP program to depict the implementation of a list
#include <bits/stdc++.h>
using namespace std;
// function for printing the elements in a list
void printlist(list<int> l)
{
list<int>::iterator itr;
for (itr = l.begin(); itr != l.end(); ++itr)
cout << *itr<<" ";
cout<<endl;
}
// Driver Code
int main()
{
list<int> testlist;
for (int i = 0; i < 8; i++) {
testlist.push_back(i * 3);
testlist.push_front(i * 4);
}
cout << "\nList is : ";
printlist(testlist);
cout << "\nlist.front() : " << testlist.front();
cout << "\nlist.pop_front() : ";
testlist.pop_front();
printlist(testlist);
cout << "\nlist.pop_back() : ";
testlist.pop_back();
printlist(testlist);
cout << "\list.reverse() : ";
testlist.reverse();
printlist(testlist);
cout << "\nlist.sort(): ";
testlist.sort();
printlist(testlist);
return 0;
}
Can we traverse in the backward direction in the list container? Yes, we can traverse the list in a backward direction because the list is a doubly-linked list, in which all the elements have a pointer to their next and the previous element.
Do we need to specify the size of the linked list? No, since the linked list is a dynamic data structure, we don't need to specify its size in advance.
What is the difference between the singly linked list and the doubly linked list? Each node in the singly linked list contains a pointer to its next element only, whereas, in a doubly-linked list, each element contains a pointer to both its previous element and the next element.
Why can't we randomly access the elements in a list? Random accessing of the elements works on the logic that if all the elements of a container are stored sequentially in the memory in a contiguous manner, then we can directly jump to the memory location of an element and access it.
Mention different types of linked lists? There are mainly four types of linked lists- Singly-linked lists Doubly-linked lists Circular-linked lists Doubly circular linked lists.
Key takeaways-
In this article, we have extensively discussed the list container in C++ STL.’ We also saw its implementation and discussed its various member functions.
84+ registered