How to Iterate Through a List in C++

1. List in C++
2. Iterate Through a List in C++

This brief programming tutorial will discuss a widely used data structure in C++, i.e., List. In C++ Standard Template Library (STL), we have a class list available for this data structure.

There is a bundle of functions packaged with it that can be used to perform multiple operations on the list. Later in this article, we will discuss how we can traverse the list and view or edit a list.

List in C++

List, or Linked List, is a linear data structure that can serve as a data container and store the data in the memory. Unlike vectors and arrays, data in the list is not stored in contiguous memory locations.

Instead, data is saved in random memory locations. Each element inserted in the list is called a node.

Each node in a list contains a pointer pointing to the next element of the list. This is why elements of the list are not saved in contiguous locations; hence, it is also called Linked List.

Lists can be categorized into two types:

1. Singly Linked List
2. Doubly Linked List

Singly Linked List

In this type of link list, all nodes have 2 parts, one is for data, and one is for storing the pointer pointing to the next node. The second part stores the address of the next node of the list.

Doubly Linked List

In this type of link list, all nodes have 3 parts, the first part is for the pointer to the previous node, the second is for storing data, and the third one contains the pointer referencing the next element of the list.

The list class in STL contains a doubly linked list. Like arrays, the insertion and deletion in this list type take linear time.

However, lists do not require contagious memory blocks. Moreover, growing a list by attaching a single list node at a time is easier and more rational than re-allocating the whole dynamic array (as done by the vectors).

Therefore, it is considered a more flexible data structure than other data structures like arrays and vectors.

Another data structure, forward_list, can iterate through only one direction and is a singly linked list. Compared to other data structures, the major disadvantage of lists and forward lists is that we cannot directly access any list element by giving its position like in arrays.

For example, to access the 5th element in a list, one has to start from some endpoint, either beginning or end to that position, and it takes a linear amount of time. Lists also use additional RAM to store the connecting information for each element.

Iterate Through a List in C++

We can use the iterator class of Standard Template Library C++ to traverse the list elements. The syntax for this is as follows:

std::list<int>::iterator itr;

There are different methods for iteration in the list:

Let’s look at the code below that uses different functions of the list class.

#include <cstdlib>
#include <iostream>
#include <iterator>
#include <list>
using namespace std;

void displaylist(list<int> l)  // print function to show list
{
  list<int>::iterator myitr;
  for (myitr = l.begin(); myitr != l.end(); ++myitr) cout << "  " << *myitr;
  cout << endl;
}
int main() {
  list<int> mylist1;
  for (int a = 0; a < 10; ++a) {
    int r = 1 + (rand() % 50);
    mylist1.push_back(r);
  }
  cout << "\nData of List 1 : ";
  displaylist(mylist1);
  cout << "\nList first element : " << mylist1.front();
  cout << "\nAfter we pop first element: ";
  mylist1.pop_front();
  displaylist(mylist1);

  cout << "\nWhen we sort the list: ";
  mylist1.sort();
  displaylist(mylist1);

  return 0;
}

Output:

Data of List 1 :   34  37  28  16  44  36  37  43  50  22

List first element : 34
After we pop first element:   37  28  16  44  36  37  43  50  22

When we sort the list:   16  22  28  36  37  37  43  44  50