Computer Science II -- Week 8
Introduction
Note that the links from this page are to handouts that will be distributed the night of class. Only print out those handouts if you could not attend class.
Main topics this week:
A linked list is a data structure, so that means it can hold a collection of items.
Describe the layout of a simple linked list.
Where can items be inserted into the list?
Where can items be deleted from the list?
The last node in a linked list typically points to 0.
Basic list operations are:
insert (data, node *)
node *find (data)
remove (node *)
node *first ()
node *next (node *)
Work through example of each operation on a sample linked list.
What are the advantages of a linked list over an array?
If we were to write the class declarations for a node and list class, they might look like this:
struct Node
{
int data;
Node *next;
};class List
{
public:
List ();
~List ();Node *first () const;
Node *next (Node *) const;
Node *find (int) const;
void insert (int, Node *);
void remove (Node *);private:
};
As we look at the implementation of these operations, we'll come up with private data that needs stored in the List class.
What do we need to know in order to be able to return the first Node in the List?
How do we return the next Node in a List?
How can we find a specific value in a List? What is the big Oh rating of finding something in a List?
Look at the logic of inserting into a List again. The Node * we pass into insert is the Node after which we should insert the new data. What is the big Oh of inserting into the List?
What if we want to insert something at the beginning of the List?
Show code for insert as we currently understand it.
Note that we have a special case in this code, where we check to see if we're inserting at the front of the List or not. We'd like to avoid special cases in our code as much as possible (Why?).
We can avoid the special case in inserting by adding a dummy first node. That way there is always a node we can insert after, even if we're inserting at the front of the list. The dummy first node is not considered part of the List from the user's perspective.
Show code for insert with dummy first node. Also update the first and find methods.
Look at the logic of removing from a List again. The Node * we pass in is the Node we want removed. What is the big Oh of removing from the list as we currently understand it?
Show code for removing from a List.
We can do better than that if we alter our List again. Instead of each Node knowing where the next Node is (a singly linked list), we can make each Node know about the next Node and the previous Node (a doubly linked list).
Change the Node struct to be doubly linked.
Since we have a doubly linked list, we could also add a previous option, like:
Node *previous (Node *);
Now we need to update our insert method. Show the new code for that.
Now we've put a special case back into our insert (for when the next pointer is null, at the end of the list). It'd be nice if we could get rid of that special cases.
We can do that by making our List a circular linked list. A circular linked list is one where the last Node points to the first Node, and the first Node points to the last Node.
Show a picture of this.
Now, since the next and previous pointers will never be null, we can remove the last of our special cases from the insert method.
Now we can see what the remove method looks like for a doubly-linked circular list.
One problem still exists with our List class.We are relying on a programmer using the class to pass in valid Node pointers. If they pass in garbage, our List class will crash.
Ideally our List class would protect itself against that sort of thing.
One option is for the List class to keep track of the current Node by adding a private data member to the List class.
Big disadvantage to this option.
A better option is to create a separate class that acts like a pointer to a Node, but that prevents a programmer from passing in bad data.
The people who came up with this idea called the separate class an Iterator.
What we do is to take the List operations that deal with a current location out of the List, and put them into an Iterator class.
Iterator Operations List Operations
next () Iterator find (value)
previous () Iterator begin ()
value getData ()
We have to use the List to get an Iterator, and then we have to use Iterator methods to move to the next or previous item. There is never an opportunity for a programmer to pass a garbage pointer..
This is the same concept as the C++ standard template library iterators, which we talked about a little on week 6.
The C++ standard template library iterators have a way to get to the next (++) and previous (--) items, and a way to get the data pointed to by the iterator (*).
So the whole idea behind C++ iterators is to allow the collection class to protect itself from a programmer passing in bad pointers.
Standard Template Library List
The standard template library provides a linked list class. (Section 8.7 in your book describes the standard template library list class.)
Usage:
#include <list>
void main ()
{
list<int> x;x.push_back (5);
x.push_front (10);list<int>::iterator iter = x.begin ();
while (iter != x.end ())
{
cout << (*iter) << endl;
iter++;
}
}
Note that C++ iterators work the same whether you have a list or a vector as the collection class.