In
CS102, you learned how
std::vector works. I'm not sure if you knew at the
time, but that was your introduction to data structures. A vector
is a dynamically resizable "array" where the memory is contiguous.
You may access one with
operator[] just like a normal
array too. You get the idea (I hope).
Well, now let's talk about a new data structure...
std::list. This is C++'s implementation of a
doubly-linked list, complete with similar syntax to
std::vector that you're used to coding with. This
means, however, that you have to deal with the properties of a
linked list as well.
The basics
Let's take a look at a simple program with
std::list:
C++ Code (list_sample1.cpp)
#include <iostream>
#include <string>
#include <list>
using namespace std;
int main() {
//Declare our list to be a list of integers (similar to vector)
list<int> int_list;
//Insert some elements at the end
int_list.push_back(1);
int_list.push_back(2);
int_list.push_back(3);
int_list.push_back(4);
//Unlike vectors, we can push to the front as well (efficiently)!
int_list.push_front(0);
//Print out first and last elements
cout << int_list.front() << " "
<< int_list.back () << endl;
//Lists also let us pop from both the front and the back
int_list.pop_front();
int_list.pop_back();
//Print out new first and last elements
cout << int_list.front() << " "
<< int_list.back () << endl;
return 0;
}
If we run this, we get the following output:
Output Text
0 4
1 3
Cool right? We can insert into both ends of the list, and also get
the front and back values. Furthermore, we can even pop off the
list in both directions.
"But Clara! I can push to the front in a vector and erase!"
Sure, it's possible with
insert and
erase,
but is that efficient with a vector? if you insert into the
front of a vector, you are having to copy all elements in the
vector over by 1, which is costly. The same applies for deleting.
You have to copy all elements over and then resize.
For
list, we don't have such a penalty since it's
node-based. We have pointers to the front and back of the list, and
those nodes point to the next and previous ones, allowing us to
insert and delete in the front and back without having to do any
copying.
Educational rants aside, let's move on.
Traversing through linked lists: The iterator subclass
In that previous example, I only demonstrated two ways to grab
values from
std::list, being
front and
back. What about elements in the middle? Well, we must
go through every element in the list until we reach the one we want.
This is one of the tradeoffs of linked lists. Let's demo it.
C++ Code (list_sample2.cpp)
#include <iostream>
#include <string>
#include <list>
using namespace std;
int main() {
//Declare our list to be a list of integers (similar to vector)
list<int> int_list;
//Insert {0..4}
int_list.push_back(0);
int_list.push_back(1);
int_list.push_back(2);
int_list.push_back(3);
int_list.push_back(4);
//Create an "iterator" to go through the list.
list<int>::iterator it;
for (it = int_list.begin(); it != int_list.end(); it++) {
cout << *it << endl;
}
return 0;
}
Running this gives us this output:
Output Text
0
1
2
3
4
Confused? Let's break it down.
C++ Fragment
list<int>::iterator it;
This will create an iterator
it that can traverse a
list<int>. That's it. It's just a normal variable
with a slightly longer name than you might've liked.
C++ Fragment
for (it = int_list.begin(); it != int_list.end(); it++) {
This isn't the same as your average for-loop. Iterators allow for a
operator++ to proceed to the next element, kind of like
doing
i++ on an integer. They are bi-directional, which
means you can also do
it-- to go backwards.
int_list.begin() returns an iterator pointing
to the very first element in the list.
int_list.end() is a little more confusing. It points to
the very last element in the list...
plus 1. For
consistency with the lecture notes, the element beyond the last one
and the element before the first one is known as the
sentinel
node. To
visualise this,
[S][0][1][2][3][4][S]
^ ^
| |
.begin() .end()
That misalignment is intentional. It literally points to the element
past the last one in the list. Take a look at that loop again, it's
going until
it == int_list.end(). If it pointed to the
last element, we'd end up going through every element except for
the last one. That's not what we want do we?
C++ Fragment
cout << *it << endl;
Most iterators can be dereferenced (more on that later in the
course). If we do
*it, it'll return the element in the
list that the iterator is pointing to.
"So I can't use operator[]?"
Nope. And you wouldn't want to. It'll just start at
list.begin() and go until the
n-th element,
which is painfully slow.
