Designing A Linked List Class

A linked list is a data structure that consists of a sequence of nodes, x₁, ..., x_n where each node x_i contains the following information:

• Some data
• The address of the next node, x_i+1

A C++ implementation of a node is quite simple:

template <class T>
struct Node
{
	Node (const T& x, Node* y):data(x),next(y) {}
	T data;
	Node* next;
};

The main desirable property of the linked list is that the ordering is a property of the Node* data members of the list. This means that a lot of algorithms only require pointer manipulations. For example, to delete a node x₂ from a linked list, the following code suffices:

x1->next = x2->next;
delete x2;

Notice that this operation did not require a change in the memory address of other nodes in the list, and it did not require us to move data around (deleting the second element of an array on the other hand would require this.) In fact, even operations such as sorting a linked list do not invalidate pointers to elements in the list, because the ordering is a property of the values of the member variable next in each node. This is often a very useful property. For example, it is possible to maintain a linked list in a sorted state, and hold pointers to elements in the list, while adding data to the list. The pointers do not need to be updated when new elements are added.

On the other hand, linked lists do have some disadvantages. For example, they support sequential access but not random access. To locate the n_th element, one must dereference n pointers. This is in contrast to the constant time element access in an array.

Some good advice found in one textbook (which unfortunately does not appear to heed its own advice) is to pay careful attention to how an interface will be actually used, when designing it. It's instructive to write some code that uses your class before you implement it. This may seem perverse to the uninitiated, but it is in fact very useful. First, it has the benefit of making sure that the class is usable, and secondly, it serves as a kind of instant test suite.

The most difficult aspect of designing a list class is element access. While this seems very simple, it's surprisingly subtle, and textbooks do a surprisingly good job of botching it. The following are key questions:

1. How do we iterate over the elements of a list ?
2. How do we represent a position in the list ? For example, operations on list nodes such as find, insert and erase require a means of representing position.

Addressing the former issue immediately addresses the latter, because if we have a way to represent a position in the list, then we can use an operation that moves from one position to the next, to iterate.

First, we look at the first consideration.

Iterating over lists

• Some textbooks decline providing a flexible implementation, offering print as the only means to get at data in the list. This is obviously unacceptable for serious applications.
• There is an obvious generalisation of this approach that some books use -- instead of offering a print() operation, offer a way to walk a list. The walk function takes a pointer to a function as an argument, and calls that function on succesive nodes. This is an improvement, but it still suffers from inflexibility -- what if we only want to operate on a subset of the list ? What if we want to perform an operation such as add the numbers in a list ?

Accessing list elements

Clearly, the best way to flexibly address the former concern would be to provide a way to address the latter. There are a few ways to access elements in a list:

• Bad: A list class could have a notion of a current node.
• Naive (and bad) We could use integer offsets, and treat the list like an array.
• Pointer Based: We could use node pointers to represent positions in the list.
• Iterator Based: We could abstract node pointers by using objects known as iterators.

A Bad Approach to Element Access

The first approach is not acceptable. It suffers from the substantial problem that simply accessing data modifies the state of the list. Here is an example of code that will break if we use the bad approach:

	find (mylist,3); // sets current element
	print (mylist); // print() modifies current element
	cout << mylist.current();

The problem with the above code is that the print() statement needs to modify the "current" element. This has a few consequences: it means that we cannot pass a list by const reference to any useful function (since most useful functions will modify the "current" element), and the deeper problem is that seemingly innocent statements, even debugging statements, modify the state of the list. The prospect of debugging statements changing program behaviour should send shivers down the spine of any programmer. Such behaviour results in infuriating Heisenbugs -- bugs whose visibility depends on whether or not debugging is enabled.

This raises an issue -- change in the state of the "current" element should not be considered a change in the list. In other words, there is a need for a representation of "current element" in the list that is not part of the list itself. Having found our first approach unworkable, we move on to the other two alternatives.

A Naive (and bad) Approach to Element Access

An approach that appeals to beginners, and even some misguided textbook authors, is to use array notation to access elements of linked lists. This is tempting, because programmers become acquainted with arrays at an early level, and from this stems a natural desire to treat any sequence container as an array. Resist this temptation at all costs!!! There are several problems with this, but they all boil down to a very simple fact:

a linked list is not an array, and is not a random access data structure

	for (int i = 0; i < mylist.size(); ++i )
		cout << mylist[i] << endl;

Accessing the n_th node takes n operations where n is the size of the list, so the loop takes 1 + 2 + 3 + ... + n = n(n+1)/2 operations. This is disasterous for large values of n, considering that we can do the same in linear time if we use the pointer based or iterator based approach.

Another fundamental problem with integer offsets is that they are invalidated by insertions and deletions. For example, consider this code:

  int pos = mylist.find ( "Thomas" );
  mylist.insert ( "William" );
  cout << mylist[pos]; // pos no longer refers to "Thomas"

Suffice it to say that we will not seriously consider implementing a linked list that uses this misguided approach as the primary means of element access.

The Pointer Approach to Element Access

The second approach is the one that is usually used in C implementations. In a C++ implementation, there are two different sub-categories of this approach.

• A linked list is the same as a list node
• A linked list is not a list node. It's a class that contains a pointer to a head node as the unique data member.

void insert_front ( Node*&  head, const element_type & x)
{
	Node* tmp = new Node(head, x);
	head = tmp;
}
// example client code
insert_front(mylist, x);

Node* insert_front ( Node*  head, const element_type & x)
{
	Node* tmp = new Node(head, x);
	return tmp;
}

// example client code
head = insert_front(mylist, x);

The linked-list-is-not-a-node approach has the advantage that encapsulation makes it possible to ensure that client code does not corrupt the list. An example of code using this approach:

void insert_front ( const element_type & x)
{
	Node* tmp = new Node(head, x);
	head = tmp;
}
// example client code
mylist.insert_front(x);

The Iterator Based Approach To Element Access

This approach uses a special iterator class that encapsulates a node pointer. One of the key advantages of this is that we can use this to provide consistent semantics to different container types. We defer further discussion of iterators.

Recall our previous Node implementation:

	struct Node
	{
		Node(const T& x, Node* y):data(x),next(y) {}
		T data;
		Node* next;
	};

Notice the constructor. This makes it simpler to write code that creates list nodes. Even if we were implementing the list in C, it would be desirable to write a function that creates a node. Notice also the fact that the node is a struct. This is intentional -- the node is a simple data aggregate.

Now we need to design the interface for the list. The first thing to consider is what operations should a linked list support. Here is a start:

• insert at front
• check for empty
• remove from front
• get element at front
• insert anywhere in list
• remove item anywhere in list
• assign one list to another list

In addition, we also need to be able to create lists. This gives rise to the following creational operations:

• Create an empty list
• Create a copy of an existing list

There are other operations that may be required, and have consequences for our design. For example, fast removal at the back of the list, and concatenation of two lists. These require us to keep track of the last node of the list. Depending on how important these operations are, it may be useful for the list class to hold a pointer to the last element of the list.

Another possible design consideration is using a sentinel node at the beginning of the list. This has the drawback of adding overhead, but is advantageous in that it makes it possible to avoid "special-casing".

In our examples, we will decline both the "sentinel" and the "tail pointer" design enhancements, while observing that these are actually quite useful in certain situations, and could be introduced to our class via a wrapper class.

So we make a first attempt at writing an interface. For now, we omit the destructor. Strictly speaking, it isn't part of the interface, it's an implementation detail specific to the C++ language.

template <class T>
class List
{

	Node* head;
public:
	struct Node
	{
		Node(const T& x, Node* y):data(x),next(y) {}
		T data;
		Node* next;
	};	
	
	void push_front(const T& x)
	{
		Node* tmp = new Node(x, head);
		head = tmp;
	}
	List(); 
	List(const List&); 
	List& operator=(const List&); 
	bool empty();
	void pop_front();
	T& front();

};

A Design Crisis

We get stuck on the last two items. To "insert anywhere in the list", we need a way to represent a place in the list. Fortunately, our previous discussion has prepared us for this.

Another problem with singly linked lists is that given a node in the list, we can not erase that node in constant time, and we can't insert a node before it in constant time. This is because these operations require manipulation of the preceding node. This is a problem with singly linked lists that detracts from their usability, and the simplest solution is to use a doubly linked list instead if you want a more flexible, general purpose class (one could write iterators that contain ordered pairs of succesive node pointers, but given this overhead, one might as well use a doubly linked list)

We address this problem by using erase_after and insert_after methods, that operate on the successor to the function argument. The ugliness of this is noted.

We first look into implementing a list, using the pointer based approach, with the linked-list-is-not-a-node model. We previously raised the importance of considering how the class is actually going to be used prior to implementing it. In this example, we could iterate over the list by using node pointers. For example, we could write a loop, and an insertion like this:

for ( Node* i = L.begin(); i!=L.end(); i=i-> next )
	cout << i->data << endl;
Node* x = L.find (3);
L.insert_after(x,4);

The notation is not that elegant, but it works.

Some Implementation Issues

There are a few issues that surface during implementation. For example, it proves useful to implement a swap() function that swaps the data of two lists. This function makes the assignment operator easier to implement (it can reuse the copy constructor) and it also offers a cheap destructive copy operation.

Another implementation issue is that copying a singly linked list requires a function to reverse the list, because the obvious strategy of iterating over the nodes and inserting them gives us a list in the wrong order. So a method that reverses the order of the list by pointer manipulation proves desirable.

Another subtle issue is const correctness. To declare a method that gives out pointers to data in the list const is dangerous, because it would allow functions that accepted a const reference to a list to use these pointers to modify the list. So we provide const versions of the methods begin() and front() that return a const pointer/reference.

The simple implementation has some positive traits that set it apart from many textbook examples. It has the following properties:

• Utility The interface is usable. In particular, it is possible to access elements of the data structure, as well as insert and delete elements. The interface is awkward, but it provides us enough access to do real work
• Safety The interface takes suitable steps to minimize circumstances where client code could corrupt a list.
• Efficiency The interface offers the same performance one would expect given a purely abstract definition of the class. For example, iterating over a list is a linear time operation, which is the best possible.

However, there is one key drawback:

• Lack of encapsulation/abstraction Strictly speaking, the Node is an implementation detail, which exposes the structure of the list. This violates encapsulation. A more abstract and ideal representation would be to have a class to represent position, and give the class similar semantics to the familiar C++ pointer: the ++ operator to advance, and the * operator to get at the data in the node. In the case of the list, it happens that Node pointers do not fare too badly as a means of representing position, because their structure closely resembles the interface we want to expose to client code. However, more advanced examples do not share this property. A good example of this is a sorted list implemented as a binary search tree. A node in such a class looks like this:

  template <class T>
  struct Node
  {
  	Node* parent;
  	Node* left;
  	Node* right;
  	T data;
  };
  

  The structure of such a node is not very helpful to client code. It is true that we could turn Node into a full-fledged class, with private data and public member functions. But we would still be stuck with explicit pointers, and we'd also be in the awkward position of using a class that serves two separate purposes (representing a node in a data structure, and a bookmark for client code)

  There are classes that are designed especially for abstracting the notion of position in a container. These classes are called iterators, and not only are they very useful, they are the focus of the next section.

Introducing Iterators

An iterator is an object that represents a position. It makes it possible to move around in a container, without exposing the structure of that container. All container iterators support a "fetch" operation that retrieves the data at a given position, as well as comparison and assignment operations. But different iterators support different operations. For example, an iterator for a singly linked list supports "forward" movement, but not "backward" movement. An iterator for an array class supports movement in both directions, and supports constant time addition (random access). There are different types of iterators, with different capabilities:

• forward iterators support forward movement.
• bidirectional iterators support forward and backward movement. Hence they are also forward iterators. Doubly linked lists, and binary trees support bidirectional iterators.
• random access iterators support forward, and backward movement, as well as constant time jumps of a given number of positions. Array classes support random access iterators. random access iterators are also bidirectional iterators.

General operations for iterators:

*it; // fetch data referenced by an iterator;
++it; it++;  // move a forward iterator forward. 
--it; it--; // move bidirectional iterator backward.
it += n; it -=n; //  increment/decrement random access iterator

i1 == i2; j1 == j2;  // comparison
i1 = x.begin();   // assignment

Iterators make for containers that are very consistent and easy to use. To get some idea of the power of iterators, here is some example code that uses iterators for vastly different STL containers:

// print out the elements of an STL set (implemented as a binary
// search tree)
for (set<double>::iterator it = x.begin(); it != x.end(); ++it )
	cout << *it << endl;

// print out the elements of an STL list  (doubly linked list)
for (list<double>::iterator it = y.begin(); it != y.end(); ++it )
	cout << *it << endl;

// print out the elements of an STL vector (dynamic array)
for (vector<double>::iterator it = z.begin(); it != z.end(); ++it )
	cout << *it << endl;

As you can see, the iterator lets the user get at the data, and keeps the details of the underlying data structure out of the way. While it's useful to know that the set is implemented as a binary tree, and has those performance characteristics (namely, it's maintained in sorted order, and searching takes O(log(n)) ), the complexity of the underlying data structure does not interfere with accessing data in the container. There is a good reason that the STL set is called set and not binary_search_tree -- the STL has diffused the complexity to the point that it really does behave like a "set", and iterators deserve a substantial amount of the credit for the success of this abstraction.

Iterators also have the advantage that one can use them to write generic functions that operate on pairs of iterators (ranges), and are entirely container independent (though they may be dependent on capaibilities of the iterator). For example, we could use the copy function to write some code that prints the contents of the above containers as follows:

// print out the elements of an STL set (implemented as a binary
// search tree)
copy (x.begin(),x.end(),ostream_iterator<double>(cout,"\n"));

// print out the elements of an STL list  (doubly linked list)
copy (y.begin(),y.end(),ostream_iterator<double>(cout,"\n"));

// print out the elements of an STL vector (dynamic array)
copy (z.begin(),z.end(),ostream_iterator<double>(cout,"\n"));

Implementing Iterators

An iterator that refers to a place in the list should support the following operations:

• Get data at that place:

  	T& operator*();
   

  overloading the operator gives us pointer-like semantics for lists.
• Move to next place on list. For example,

  it++; ++it 

• compare for equality and inequality, eg

  it1 == it2; it1 != it2

• Copy, assignment, and construction. eg:

   iterator i; iterator j(it); i = j; 

Some things we can't do --

• decrease to previous value. (Because this is a singly linked list)
• increase by a fixed number ( it +5 ) in constant time, because this is a linear time operation in a linked list.
• compare for inequality ( it1 < it2 ) in constant time.
• we need a means to construct an iterator from a Node pointer.

 T& operator*();

 iterator& operator++();   // ++it   
 iterator operator++(int); // it++
 bool operator==(const iterator&);  // i == j
 bool operator!=(const iterator&);  // i != j

 iterator(); // iterator i;
 iterator(Node*); 
 iterator(const iterator&); // iterator j(i)
 iterator& operator=(const iterator&); // iterator j; j = i;

Now we can add operations that depend on position to the list:

   iterator begin(); // return iterator at front of list
   iterator end(); //  return iterator at end of list
   insert_after(iterator,const T&); //  insert after iterator 
   erase_after(iterator); //  erase after iterator

You may have observed that the methods begin() and end() were not declared const. There is a reason for this -- suppose we pass our list to a function by const reference. If we declared begin() const, then this code would be legal:

void do_something(const list<int> & a )
{
	*a.begin() = 3; // modify list	
}

This is obviously a problem -- the function prototype claims to guarantee that the state of the list will remain unchanged, but does not honor this contract. To deal with this, we need a separate type for constant iterators, const_iterator. This supports the same operations as iterator, with the following differences:

• You can consruct or assign const_iterator from an iterator.
• operator*() returns a const reference.

Since there is an implicit conversion from iterator to const_iterator, there is no need to provide more comparison operators to handle mixed comparisons.

So this results in the addition of the following methods:

const_iterator begin() const;
const_iterator end() const;
const T& front() const;

The standard template library (STL) offers a number of algorithms that we can use on our list for free, provided that we make our iterators STL compatible. The main thing this requires is several typedefs. in particular, the following information is expected:

typedef T value_type; // type of element
typedef T& reference; // return type of operator*()
typedef T* pointer; // return type of operator->()
difference_type; // type used to measure distance between iterators
typedef std::forward_iterator_tag iterator_category; 

The simplest way to do this is derive iterator from std::iterator. The standard iterator class is a template that takes two parameters -- an iterator tag, and a type. For example, for a list iterator, we want to derive from

std::iterator<std::forward_iterator_tag, T >

std::iterator<std::forward_iterator_tag, const T >

The reason we use const T is that this makes the pointer and reference types const *T and const T&.

It should be noted that there is no requirement that iterators be derived from std::iterator. However, it is a useful technique.

Variations on the Theme

There are several other possible variations on the linked list theme. We discuss some of them:

• Doubly Linked Lists: Doubly linked list classes are similar to singly linked lists, but have the additional property that each node contains the address of its predecessor and its successor. An implementation of a node in a doubly linked list class looks like this:

  template < class T> 
  struct Node
  {
  	Node( const T& data, Node* prev, Node* next):data(data),prev(prev),next(next) {}
  	T data;
  	Node* next;
  	Node* prev;
  };
  

  An iterator in a doubly linked list is bidirectional -- we can move backwards or forwards in a doubly linked list. Doubly linked lists do not suffer from the awkward special-casing issues associated with singly linked lists. As such, they are useful as general purpose classes, which is why the STL includes a class with similar performance characteristics (the C++ standards document tends to beat around the bush -- it doesn't specifically mandate a linked list, but rather, enumerates the properties of a linked list, and mandates a class with those properties)
• Sentinel nodes: To avoid special-casing in operations such as inserting at the front of the list, some list classes use sentinel nodes. These are dummy nodes that serve the sole purpose of acting as the (seemingly paradoxical) predecessor to the first node in the list. If we combine this with iterators, we can avoid the awkward insert_after / erase_after syntax. However, this creates some extra overhead, because each list must contain at least one node. This is problematic in cases where we may have a lot of empty lists. (for example, a hash table implementation) It is also very difficult to correctly implement "off-by-one" iterators.
• Circular lists: A circular list is a linked list that has the property that the last node in the list contains the address of the first node. There are a couple of possible advantages to this approach:
  • Instead of keeping a pointer to the head of the list, we can keep a pointer to the tail. This makes it possible to find either end of the list very quickly, and do constant time insertions at the end or at the start of the list, without having to store two pointers (one to the head, one to the tail)
  • It makes it very easy to rotate the list. A rotation is a cyclic permutation:

    (x₀ , x₂ , ... , x_n ) -> (x_{i mod n} , x_{(i+2) mod n} , ... , x_{(i-1+n) mode n} )

    This becomes a constant time operation.
  Note that it may not be necessary to expose the circular structure to client code. If the client wants to traverse the list in "rotated" order, they can call a constant-time rotate, and traverse it like an ordinary list. The only disadvantage of this is that is inconvenient in that it involves modifying the data in the list. It's interesting to note that the SGI implementation of the std::list class uses a sentinel node and a circular list. Note that they do not use the same trick for their singly linked slist class (which is very similar to the previous example), because while list is a general use class, slist is intended to provide maximum speed, and minimum size overhead.

  The main possible advantage of exposing the circular structure to client code is that it could make use ranges of iterators that spanned the "end" of the list. But there is also an obvious problem -- if we use the obvious implementation, we have begin() == end(). We can circumvent this problem by using a sentinel, but using a sentinel is a problem, in that the sentinel will get in the way if we want to use ranges that span the "end" of the list. Another alternative is to linearise iterators by storing state information -- an initial node, and a count of how many "laps" the iterator has done. This results in iterators that are larger, and more fragile (since the state depends on two node pointers, deleting either pointer will invalidate the iterator) But it offers the following benefits:

  • no special-casing in client code,
  • iterator ranges may span head/end node on list
  • no sentinel node overhead.

Implementing A Circular Linked List with a Sentinel

We implement a circular linked list, with the following properties:

• The list is circular (as stated above)
• The list contains a sentinel node (as stated above)
• The list contains a pointer to the end of the list, but no pointer to the start of the list.
• Inserting at the front of the list is a constant time operation.
• Appending to the list is a constant time operation.
• Finding the last element of the list, and the front of the list is a constant time operation.
• Appending at the end of the list is a constant time operation.
• Deleting the last element is a slow (linear time) operation.
• Inserting and erasing do not require the messy syntax required for the other list implementation. In particular, if we have an iterator, we are allowed to do any of the following:
  • Remove the element the iterator references from the list
  • Insert an element in from of that reference by the iterator

The bottom line is that we trade a slight amount of overhead (a sentinel node) for a fair degree of flexibility. At a first glance, it doesn't appear obvious that this design helps us write code that inserts before a given iterator. The trick here is to use "off-by-one" iterators. In particular, dereferencing an iterator produces the element at the next node:

		inline T& operator*() { return m_rep->m_next->m_data; }

The main change in this list with respect to the non-circular list is the fact that we don't keep track of the head node, we keep track of a pointer m_node that points to the last element in the list. Hence m_node->next points to the dummy sentinel node, and m_node->next->next points to the first node in the list.

We dicuss the important changes:

• void reverse()
  

  This function is tricky to implement, because looping in a circular list is not that easy. The problem is that when iterating over a circular list, the termination condition is the same as the initial condition. One gets around this problem by terminating on an empty list, then using a do-while loop to perform the first step without a check. There is another subtle issue -- recall that the data member m_node points to the last member of the list. So we need to reassign this to a pointer to the first node, which is m_node->m_next>m_next. (Note that m_node->m_next is the dummy sentinel node).

• inline void push_front(const T&x); { insert (begin(),x); }
  inline void push_back(const T& x) { insert (end(),x); }
  inline void pop_front() { erase(begin()); }
  inline bool empty() { return m_node == m_node->m_next; }
  

  Push and pop functions admit trivial implementations, because of the lack of a need for special-casing in our new setting. Note that even though end() is "one past the end of the list", it is still a valid iterator, and we can use it in a call to insert(). Note also that empty() checks that the sentinel is its own successor.

• void erase (iterator x)
  

  The implementation of the erase() method suffers some awkwardness, but it's not that much worse than the dreaded "erase_after" method. First, it checks that we're not trying to erase the sentinel node.

  	if (x==end())
  		return;
  

  Then it checks to see if the last node on the list is being erased.

  	if (x.m_rep->m_next == m_node)
  		m_node = x.m_rep;
  

  Since m_node needs to point to the last node on the list, this variable needs to be reassigned if the last element of the list is removed. If the iterator does reference the last element on the list, its corresponding pointer, m_rep points to the element before that, thanks to our off-by-one iterator implementation. So in this case, we assign the value of x.m_rep to m_node. The last few lines simply cut out the node referenced by the iterator :

  	Node* tmp = x.m_rep->m_next;
  	x.m_rep->m_next = x.m_rep->m_next->m_next;
  	delete tmp;
  

• void insert (iterator x, const T& y)
  

  This is similar to our old insert_after function, except it requires a check for the case where we insert before end(). In the case where we insert before end(), the newly inserted node becomes the last node in the list, so it's necessary to assign the value m_node accordingly.

• void rotate(iterator)
  

  This rotates the list so that the iterator argument is at the front of the list. Rotation may seem like an operation that is "natural" for a circular list, but the only requirement for a constant time implementation is that both ends of the list be quickly accesible.

Implementing A Circular Linked List without a Sentinel

Here, we compare three list implementations -- the circular, and basic lists implemented above, and the SGI implementation of the STL list class. The SGI list is a doubly linked list. This list has a characteristic that sets it apart from singly linked lists -- it supports bidirectional iteration. Support for bidirectional iteration is an STL requirement, so a linked list that meets the requirements for the STL list must be doubly linked. As we will see, there is a pattern emerging in the comparison -- there is an escalating tradeoff between minimising overhead and maximising flexibility. The STL class aims to offer as much flexibility as possible.

While we've covered a lot of issues, there are more issues that the reader should be aware of. Think of this section as an invitation to further exploration.

Exception Safety

is an important consideration in library design, especially where templates are involved. There are three possible guarantees a class can make for a given method:

• Weak guarantee The method will not leak resources or leave the object in an invalid state as a result of exceptions.
• Strong guarantee The method will either return succesfully or have no effect
• Nothrow guarantee In addition to the weak guarantee, no exceptions will leave the method. Note that this implies the strong guarantee.

Appendix: A Quick Lit Review

There are many textbooks that cover linked lists, and they reflect different approaches. Unfortunately, the vast majority of them do a fairly poor job at it. Of these titles, the only one that provides much insight to beginners on the topic of implementing data structures is the Weiss book. The Koenig/Moo book is also good, but it addresses a more advanced audience.

Of these books, I'd enthusiastically recommend Cormen et al as a pure theory book for Data Structures. I believe theory should be studied separately from implementation, it is complex and rich enough in its own right to deserve special attention. On the other hand, sticky implementation details are important, and this is where the books by Weiss prove valuable. The Koenig and Moo book also does a good job at addressing many library implementation and generic programming issues, but it is not a data structures book (the main theme is the related topic of library design)