|
| |
Linked Lists
What is a Linked List?
Linked lists are among the most useful data structures in
Computer Science, and are therefore very heavily used in lots
of different applications. For this assignment, we will
concentrate on the doubly-linked list, which is
perhaps the most useful of all linked lists. Here's what a
doubly-linked list looks like:
As you can see, the linked list consists of a number of list
items linked together in both the forward direction and
the reverse direction. The links are typically pointers, and
that is what we will use to implement this kind of list.
Why are Linked Lists so Useful?
Linked lists are useful because they are very flexible.
You can use a linked list as a collection mechanism;
that is, the linked list can collect together items which
have something in common with each other. For example,
perhaps you wish to collect together all the people who work
in your office. Or all the people who work for a particular
boss.
Sometimes the order of items in a list is important, and
sometimes it isn't. It all depends on what your needs might
be. Perhaps you don't care about the order at all, in which
case you could treat the items in a list as a set of
items (in the Mathematical sense), or a multi-set of
items (where the value of an item can be duplicated within
the list).
Alternatively, you might wish to maintain the items in the
list in a particular order -- perhaps alphabetically, or by
employee number, or by salary.
Linked List Operations
There are obviously a number of useful operations that a
linked list should support. For example:
- Adding an item to a list
- Removing an item from a list
- Determining whether an item is currently in the list
or not.
- Determining how many items are currently in the list
- Navigating through the list in order to access the
items in a list
Depending on how you are using the list, you may need only
the ability to add or remove an item at the end of a list, or
at the front of a list, or to add or remove an item anywhere
in the list. Similarly, you may need only to navigate the
list from the start to the end, or you may need to move both
in the forward direction or in the reverse direction. You may
wish to start at the beginning of the list, at its end, or
anywhere in between.
Doubly-Linked Lists
The doubly-linked list is very flexible in its ability to
support the above features. Doubly-linked lists allow you to:
- Add an item anywhere in the list
- Remove an item from anywhere in the list
- Navigate in any direction, from any starting point in
the list
The doubly-linked list supports these features by using
two pointers in each list item:
- A next pointer
- A previous pointer
In addition, it is very useful to add one more pointer in
each list item:
- A list pointer -- a pointer to the
list in which the list item currently resides
The next pointer, as its name suggests, points to
the next list item in the list. The previous pointer
similarly points to the previous list item in the list. If a
list item is the first one in the list, then its previous
pointer is NULL. If a list item is the last one in the list,
then its next pointer is NULL. In this way, we can
navigate through the list and have a way of ensuring that we
don't "fall off" at either end of the list.
The list pointer serves two purposes:
- A flag indicating whether the list item is currently
in a list (we assume that a list item is either in a
single list, or it is in no list). If the list item
is not currently in a list, then its list
pointer is NULL. If the list item is currently in a
list, then the list pointer points to the owning
list.
- If the list item is in a list, then the list pointer
provides convenient access to the owning list's
context, which the list item code will need for its
purposes.
Class Design
To implement such a doubly-linked list, we will be
implementing three classes:
- A List
class, each instance of which represents a
doubly-linked list
- A ListItem
class, each instance of which represents an item that
can exist in a List
- A ListIterator
class, which encapsulates the necessary context to
allow multiple concurrent iterations (navigations)
through a List
What must each class provide to support the necessary
features? Well, let's cut to the chase, and give you some
code to start with:
class List
{
public:
List(); // Constructor
~List(); // Destructor
// Access
ListItem *First() const; // Returns ptr to first item in list
ListItem *Last() const; // Returns ptr to last item in list
int Count() const; // Returns count of items in list
// Operations
void Append(ListItem &item); // Appends an item to the end of the list
void Purge(); // Removes all items from the list
private:
// Data members
ListItem *m_first; // Pointer to the first list item
ListItem *m_last; // Pointer to the last list item
int m_count; // Count of list items currently in list
};
|
class ListItem
{
public:
ListItem(void *data);// Constructor (associates with data)
~ListItem(); // Destructor
// Operations
void Add(List &list, ListItem *prevItem);
// Add this ListItem to the specified list
// following the specified prevItem
// (if prevItem is NULL, place at front of list)
void Remove(); // Remove this list item from the list it is in
// Access methods
ListItem *Next() const; // Return ptr to next item in list
ListItem *Previous() const; // Return ptr to previous item in list
void *Data(); // Returns ptr to data for item
private:
// Data members
ListItem *m_next; // Pointer to next item in the list
ListItem *m_prev; // Pointer to previous item in the list
List *m_list; // Pointer to the list the item currently is in
void *m_data; // Pointer to data
};
|
class ListIterator
{
public:
ListIterator(List &list); // Constructor
~ListIterator(); // Destructor
// Access
ListItem *Current() const;// Return ptr to current list item
ListItem *Next(); // Move to next item and return ptr to it
ListItem *Previous(); // Move to previous item and return ptr to it
bool AtFirst() const; // return true if current item is first item
bool AtLast() const; // return true if current item is last item
private:
// Data
List *m_list; // The list we are iterating through
ListItem *m_current; // Points to the current item in the list
};
|
Note:
The above classes are incomplete, and show no
implementation details. That's your job!
Note:
If your C++ compiler doesn't implement the primitive
type bool, you can substitute int.
NOTE:
Do not
change any of these class members, their signatures,
or their access (public or private). Furthermore, do not
add any other data members or member functions. These
classes will be used and modified in later
assignments, and if you change them here, you will
have difficulty following the instructions in the
later assignments. YOU HAVE BEEN WARNED!
The List Class
As you might guess, a doubly-linked list is represented by
an instance of class List.
Its primary purpose is to provide the necessary state of the
list -- specifically, to point at the first item in the list,
and the last item in the list, so that we can start
navigation at the appropriate places. It also keeps track of
the number of items currently in the list.
Aside from the obvious access methods, the List class
supports two operations:
- Append()
-- adds an item to the end of the List
- Purge()
-- removes all items from the List.
[Hint: Where, in particular,
would you think the Purge() operation would be useful within the List class?]
The ListItem Class
Not surprisingly, an item in a doubly-linked list is
represented by an instance of class ListItem.
Its primary purpose is to hold the three pointers we talked
about above, and to support the basic operations on a ListItem:
- ListItem()--
the constructor associates data with the list item.
Since we don't know what you might want to put in a
list, this is a void *
pointer, which must be cast appriopriately, once you
retrieve the data from a list item.
- Add()
-- adds the item to a specified List,
following the specified previous item. [Hint:
What should this do if the item is already in a List?]
- Remove()
-- removes the item from the List
it is in. [Hint: What should this do if
the item is not in any List
?]
- Data()--
this returns a void *
pointer to the data the list item represents.
Typically, this must be typecast to the proper type
before you can use the pointer to access the data
structure; this implies that you must know what is
being held in the list item.
[Hint: What should the ListItem
destructor do? ]
The ListIterator Class
Whenever you wish to navigate through a doubly-linked
list, you need to maintain some context -- where you are
currently positioned within the list. We could have
maintained that context within the List
class itself, but that would mean that we could only have a
single navigation active against a specific list at a time.
That is often quite restrictive, so instead we invent a
class, ListIterator,
which serves to maintain the necessary context, and in
general encapsulates the necessary support for iterating
(navigating) through a specific list.
ListIterator
supports the following operations:
- ListIterator()
-- the constructor is responsible for associating the
ListIterator
with the specified List,
and for setting its starting position at the first
item in that List.
- Next()
-- Moves the current position to the next item in the
List.
If there is no next item, does not change the current
position, and returns NULL.
- Previous()
-- Moves the current position to the previous item in
the List.
If there is no previous item, does not change the
current position, and returns NULL.
- AtFirst()
-- returns a Boolean value indicating whether the
current position is at the first item in the List
- AtLast()
-- returns a Boolean value indicating whether the
current position is at the last item in the List.
- Current()
-- This is merely an access method, and returns a
pointer to the current item for the ListIterator.
There should always be a current item for a ListIterator
(i.e. it should never become NULL, nor should it
point at anything other than a list item that is in
the List
being navigated by the ListIterator.)
The Assignment
Your task is to implement the three classes, List, ListItem and ListIterator. Place
the class declarations all in a single file, list.h,
and their implementations in a single file, list.cpp.
Here are some hints you will need to pay attention to:
- You will need to protect against including the list.h file more than once.
This should by now be standard practice for every
header file you write (It's not? WOW!). Take a look
at the wine.h and person.h files below for
examples of how to do this. Of course, you'll have to
come up with a unique macro name for each header
file.
- Since these classes refer to each other, you will
need to use one or more forward references
so that the classes will compile. For example, if you
wish to have the List
class compile successfully, you may need to specify
the following line before the List class
declaration:
class ListItem;
This will forward declare the ListItem
class so that the List
class can refer to ListItem
without the compiler complaining. Note that, since a
forward declaration does not provide any information
about a class other than its name, if you have code that
refers to information about that class, such as its size
or its members, your compiler will complain -- sometimes
with some very strange error messages!
- These three classes work together as a family of
classes to support a single piece of
functionality. It will be probably be necessary to
declare appropriate friendship
relationships among the classes. However, try to keep
these to a minimum -- do not
make every class a friend of every other class.
- Since all of these classes contain data members which
are pointers, you should pay particular attention to
disabling their copy constructors and assignment
operators -- just place the appropriate member
function signatures in the private
part of the class declaration, and do not implement
those member functions.
- Initially, place all your implementation code in the
list.cpp file, and don't worry about efficiency. It's
much better to get the code working first, and then
worry about how to make it fast -- not the other way
around. Later, if you have time, you can consider
making the appropriate modifications to speed up the
code -- mostly making essential member functions inline.
Using Your Implementation
To give you an idea how you might use these classes in a
real situation, here's an example:
#ifndef _WINE
#define _WINE
//
// wine.h
//
class Wine
{
public:
Wine(char *name, int year);
Wine(const Wine &wine); // Must implement explicitly
~Wine();
const char *Name() const { return m_name; }
int Year() const { return m_year; }
void Print();
private:
// Data members
char *m_name;
int m_year;
};
#endif
|
//
// wine.cpp
//
#include <iostream.h>
#include <string.h>
#include "wine.h"
Wine::Wine(char *name, int year)
: m_name(new char[strlen(name)+1]), m_year(year)
{
strcpy(m_name, name);
}
Wine::Wine(const Wine &wine) // >>>You must implement this<<<
Wine::~Wine()
{
delete [] m_name;
}
void Wine::Print()
{
cout << m_name << ", " << m_year << endl;
}
|
//
// test.cpp
//
#include "list.h"
#include "wine.h"
static void ListWines()
{
List list;
Wine wine[] = { Wine("Beaujolais", 1970), Wine("Amontillado", 1964),
Wine("Reisling", 1980), Wine("Gewurztraminer", 1993) };
ListItem items[] = { &wine[0], &wine[1], &wine[2], &wine[3] };
for (int i = 0; i < sizeof(items)/sizeof(items[0]); i++)
{
list.Append(items[i]);
}
ListIterator iter(list);
for (ListItem *item = iter.Current();
item != 0;
item = iter.Next()
)
{
Wine *wine = (Wine *)(item->Data());
wine->Print();
}
}
int main()
{
ListWines();
return 0;
}
|
Note:
You must implement the copy constructor for
the Wine class.
You may notice that it's a little clumsy to separate a ListItem from the
data it represents. Here's another, slightly different,
approach that makes things a little easier:
#ifndef _PERSON
#define _PERSON
// person.h
#include <string.h>
#include "list.h"
class Person
{
public:
Person(char *name);
Person(const Person &person); // Must implement explicitly
~Person();
const char *Name() const { return m_name; }
void Add(List &list, Person *prevPerson);
void Remove();
void Print();
operator ListItem &() { return m_item; }
private:
ListItem m_item;
char *m_name;
};
#endif
|
// person.cpp
#include <iostream.h>
#include "person.h"
Person::Person(char *name)
: m_item(this), m_name(new char[strlen(name)+1])
{
strcpy(m_name, name);
}
Person::Person(const Person &person) // >>>You must implement this<<<
Person::~Person() { delete [] m_name; }
void Person::Add(List &list, Person *prevPerson)
{
m_item.Add(list, &(prevPerson->m_item));
}
void Person::Remove()
{
m_item.Remove();
}
void Person::Print()
{
cout << "Person: " << m_name << endl;
}
|
// test.cpp
#include "list.h"
#include "person.h"
static void ListPersons()
{
List list;
Person person[] = { "Fred", "Mary", "Joe" };
for (int i = 0; i < sizeof(person)/sizeof(person[0]); i++)
{
list.Append(person[i]);
}
ListIterator iter(list);
for (ListItem *item = iter.Current(); item != 0; item = iter.Next())
{
Person *person = (Person *)(item->Data());
person->Print();
}
}
int main()
{
ListPersons();
return 0;
}
|
Note:
You must implement the copy constructor for
the Person class.
Testing Your Implementation
You will need to do a reasonable amount of testing to
ensure that your implementation of these classes actually
works correctly. I strongly suggest that you freely instrument
your code so that you can turn on tracing and debugging
information when convenient and/or necessary. Adding a line
like:
cout << "Adding item at " << this << " after item at " << prevItem
<< " and before item at " << nextItem << endl;
at the appropriate place in your code can really help you
figure out what's going on.
Use the two test programs shown above to test your
implementation. However, they do not constitute
exhaustive tests. I expect you to augment the
above two (Wine and Person) programs with your own, more
thorough, set of tests, to ensure that each function in each
class works as specified.
I expect
you to provide me with evidence (hard copy output
would be best) that you have tested the program
sufficiently. Since you will be using and enhancing
these classes in later assignments, it's to your
advantage to make sure that they work, now!
|
