Linked Lists

Introduction

The linked list is a datatype that has the following benefits:

Insertion and deletion at any point in the list is fast.
Insertion and deletion of new elements does not change the address of other elements.

The linked list is also reasonably good for storing sorted data (though it turns out that trees are more suited to this). The main liability of the list is that it's not random access, indeed the access time is linear.

How They Work

Linked lists consist of several nodes. Each node contains the following three pieces of information: data, and the address of the next node. Some lists (including those used in C++) use nodes that contain the address of the previous node. These are called doubly linked lists. One could declare a node as follows:

struct Node 
{
	node_type data;
	struct Node* next;
	struct Node* prev;

};

The only data a singly list requires is the address of its first node. A doubly linked list also stores the address of its last node. It is possible to traverse the list by following the node pointers.

Lists In C++

Lists in C++ are implemented as template classes. This means that the list class is parametrised by the type stored in the list. This parametrisation means that one can make any type of list:

	list<int> x;	// list of int
	list<double> y; // list of double
	list<string> z; // list of string

The first operations we should learn are populating a list and checking that the list is empty. We will use the symbol T to denote the data type in the list. For example, given a list of type list<int>, T would be int.

bool empty() : check if the list is empty
list::size_type size() method. Returns the size of the list. Prefer empty() to size() == 0.
void push_back(const T&) append to the end of list
void push_front(const T&) insert to the front of the list.
void remove(const T&) removes all elements whose value is the same as the parameter.

We're now in a position to do our first example:

list1.cc


#include <list>
#include <iostream>
using namespace std;
int main()
{
	list<double> x;
	x.push_back(3.2);
	x.push_back(1);
	x.push_front(2.4567);

	list<double>::const_iterator it = x.begin();
	for ( ; it != x.end(); ++it )
		cout<< *it << endl;
	return 0;
}

Note the syntax for the declaration of the iterator (what a mouthfull!) Also note the loop. Loops involving standard library iterators nearly always follow this basic format (sometimes, the declaration of the loop control iterator is placed inside the loop, but the result is equivalent.) There's an important point to be made with the iterator returned by end(). If end() returned a const_iterator referring to the last element of the list, the last element on the list would never be printed. However, since the iterator refers to a ``dummy'' node beyond the end of the list, the loop idiom above works. (Indeed, end() is deliberately designed to make this idiom work)

Iterators That Refer To Objects

If an iterator refers to an object, one could call methods on the object using the cumbersome syntax:

	(*it).method()

However, to make the notation cleaer, the arrow operator -> is provided, so that we can instead call methods and access data like this:

	it->method()

Linear Search

One can search a list using the find algorithm in the standard library. This algorithm is provided by the <algorithm> header, and it's used lite this:

	find ( start, end, search_key )

where start and end are iterators, and search_key is something we are searching for. For example,

	list<double> myList;
	// do stuff with myList
	list<double>::iterator it = find ( myList.begin(), myList.end(), 3.2);

If the search is unsuccesful, the ``end'' argument is returned (in the above example, myList.end().

An Example: Student Records

The following is a simple example of how a list can be used as a data structure for storing student records. We comment on the code:

Class Student

This is the class responsible for keeping student data. As usual, we've made data members private, though it's true that the class does not provide a great deal of encapsulation. We explain the code:

	Student(){}

This is just a default constructor.

	Student (string Name) : Name(Name) {}

This constructor takes a string as an argument. We will need this for searching the list. Note that the parameter and the data member are allowed to have the same name if the parameter is only used in the initialisation list.

	istream& read ( istream& s = cin )

We make this method take a stream argument to keep it general. It returns the stream so that it can be used idiomatically inside tests. For example, one could write code that looks like this:

	if ( stu.read() )
		doSomething(); // the read was succesful, so we can do something
	else
		errorFunction();	// bad data

	bool operator==(const Student& s )

We write the comparison operator so that it returns true if the names of the students are the same. We need this for the find() algorithm to work properly, since it uses == to compare the search key with each element in the list.

	string& name ()

We have accessor methods that provide indirect read and write access to our data members. This pretty much blows away any encapsulation Student offers. In other words, Student is more like a record type than it is a class.

Functions

	void printMenu()

Straightforward. Displays the menu options.

	void errmsg()

Prints an error message. This is called when bad input is entered, so it also clears cin, so that subsequent extractions will work. It also reads the line (using the getline() call) that caused the problem, so that one line does not cause several error messages, and more importantly, that the program does not unsuccesfully attempt to extract (for example) an integer when there isn't an integer to extract.

	void add(list<Student> students)

Reads in data and adds it to the list. Note the idiomatic use of read(). If stu.read() evaluates to false, it's because cin is in an error state and needs to be cleaned up, hence we call errmsg().

	void del(list<Student> students)

Read in and delete a student. The one expression here that deserves attention is this:

	( it = find(students.begin(),students.end(),stu ) ) != students.end()

First, it runs find. Since we redefined the comparison operator to only compare names, comparison returns true if a student with the same name as that entered by the student. So find() will return a valid iterator if it succeeds, or end() if it fails. Note that end() refers to one point past the list, and is not a valid iterator!. So we compare the return of find() with end() to see if find() was succesful or not. If the find is unsuccesful, we report it to the user.

Note that the remove() method again uses the comparison operator -- so it removes students whose name matches the search term.

	
	void show(list<Student> & );

Displays a list of all the students. Note the loop idiom. Also, note that methods in Student can be accessed via arrow notation it->name() instead of the cumbersome notation (*it).name()

 int main()

The logic of the main loop is difficult to do both correctly and elegantly. To get it right, without ``cheating'' by using gotos or by using redundant statements, it helps to write out the sequence of events. Note that we must print the menu, then extract the choice, then test the choice over and over. Since the exit condition is that the choice is 4, which cannot be realised until the end of the loop, we use a do {} while(); loop. Note that if the extraction fails, we clean up instead of bailing out.

list2.cc


#include <string>
#include <list>
#include <iostream>
#include <algorithm>
using namespace std;

class Student
{
public:
	Student(){}
	Student(string Name):Name(Name){}
	istream& read (istream& s = cin) {
		s >> Name >> Phone >> Gpa;
	}

	ostream& print(ostream& s = cout ) const {
		s << "Name: " << Name << "\nTel: " << Phone << "\nGPA: " << Gpa << "\n\n";
	}

	bool operator==(const Student& s) const {
		return s.Name == Name;
	}

	string& name() { return Name; }
	long& phone() { return Phone; }
	double& gpa() { return Gpa; }
private:
	string Name;
	long Phone;
	double Gpa;
};

void printMenu()
{
	cout 	<<	"1: add record\n"
			<<  "2: delete record\n"
			<<  "3: show all records\n"
			<<  "4: quit\n"
			<< endl;
}

void errmsg()
{
	cin.clear();
	std::string dummy;
	getline(cin,dummy);
	cout << "Bad input" << endl;
}

void add(list<Student>& students)
{
	cout << "Enter last name, phone and GPA" << endl;
	Student stu;
	if (stu.read())
		students.push_back(stu);
	else
		errmsg();
}

void del(list<Student>& students)
{
	string s;
	Student stu;
	list<Student>::iterator it;
	cout << "enter the student to delete" << endl;
	cin >> s;
	stu = Student(s);

	if (  (it = find(students.begin(), students.end(),stu)) != students.end() )
	{
		students.remove(stu);
		cout << "Deleted" << endl;
	}
	else
		cout << it->name() << " : not found" << endl;
}

void show(const list<Student>& students)
{
	list<Student>::const_iterator it;
	for (  it = students.begin(); it != students.end(); ++it )
		it->print();
}

int main()
{
    int choice;
    std::list<Student> students;
    do 
    {
        printMenu();
        if ( cin >> choice )
            switch (choice)
            {
                case 1:
                    add(students); break;
                case 2:
                    del(students); break;
                case 3:
                    show(students); break;
                case 4:
                    break;
                default:
                    errmsg();
            }
        else
            errmsg();
    }
    while ( choice != 4 );
}

A Critique

Having finished the example, it's worth thinking about the design, and how it could be improved. For example, a linear search is rather slow, so if we needed to search the list frequently, a different data structure may prove more efficient. To sort, we'd need some kind of sorting cirterion, but this would be fairly easy. However, the vector data type is not a terribly good choice, because inserting data in the middle of a vector is very slow, and maintaining sorted data is inconvenient. There is in fact a data structure that works, called a binary search tree. In C++, this is implemented as a map. We discuss this in the next section. Another important point is that we could have been more careful in our reading of the data. While there is some error checking, it would be better to read data in one line at a time, and break up each line, since this is how we expect users to enter the data. To find out how to do this, read the tutorial on stringstream.