6.1 Double linked lists

This is a generic double linked list which does not allocate memory for its nodes. It is supposed that nodes have been allocated previously.

A list node keeps pointers to previous and next list elements. The data type for the element contained in the list must derive from it.

<Double linked node. >= (U->)
// A double linked node.
//
class DLinkedNode {
public:
  DLinkedNode *l_next;
  DLinkedNode *l_prev;
  DLinkedNode(void) : l_next(NULL),l_prev(NULL) {;}
};

Defines DLinkedNode (links are to index).

The l_next link is used to guess if a node is linked in a DLinkedList. We assume that the node is linked when such field is non-null.

<Other public methods of DLinkedList. >+= (U->) [<-D->]
  // Return non-zero if the nd seems to be linked.
  // Depend on nd->l_next be UNUSED when the node is not linked. 
  // 
  int is_linked(const DLinkedNode *nd) const {
    assert(nd);return nd->l_next!=NULL;
  }

<Double linked list dependencies. >= (U->) [D->]
#include <flux/types.h>         // for NULL et al.
#include <assert.h>             // for assert

The double linked list contains a pointer to the head element and another one to the tail of the list. Except for node insertion or removal (where users are responsible of node allocation and deallocation), users should employ a list iterator to refer to list nodes.

<Double linked list. >= (U->)
// A double linked list which does not allocate nodes.
//
class DLinkedList {
protected:
  friend class DLinkedListItr;
  DLinkedNode *l_head;       // First element.
  DLinkedNode *l_tail;       // Last element.
public:
  // Creates an empty DLinkedList.
  DLinkedList(void){ l_head = l_tail= NULL; }

  // Returns non-zero if the list is empty.
  int is_empty(void) { return l_head==NULL; }

  // Does it look fine?
  int valid(void);

  <Other public methods of DLinkedList. > 

};

Defines DLinkedList (links are to index).

A valid linked list must satisfy this integrity check.

<DLinkedList::valid implementation. >= (U->)
// Is this list valid?
// Do its pointers look fine?
int DLinkedList::valid(void){
  int is_valid=((l_head && l_tail) || (!l_tail && !l_tail));
  if (!is_empty()){
    DLinkedNode *n=l_head;
    do {
      is_valid |= (n->l_next->l_prev == n);
      is_valid |= (n->l_prev->l_next == n);
      n=n->l_next;
    } while(is_valid && n != l_head);
  }
  return is_valid;
}

Node insertion at the head of the list is easy. The list will be double linked and the tail node will be considered to be the predecessor of the head node.

<Other public methods of DLinkedList. >+= (<-U) [<-D->]
// Links nd at the head of the list. 
void link_first(DLinkedNode *nd);

<DLinkedList::link_first implementation. >= (U->)
// Links nd at the head of the list. 
void DLinkedList::link_first(DLinkedNode *nd)
{
  assert(valid());  
  if (is_empty()){
    l_head=l_tail=nd->l_prev=nd->l_next=nd;
  }
  else {
    nd->l_next=l_head;
    nd->l_prev=l_tail;
    l_tail->l_next=nd;
    l_head->l_prev=nd;
    l_head=nd;
  }
  assert(valid());  
}

A more generic insertion method provides insertion at an arbitrary point. The ``arbitrary point'' will be indeed a list iterator (to be discussed below).

<Other public methods of DLinkedList. >+= (<-U) [<-D->]
// Link node before/after the given one. 
void link_before(DLinkedNode *nd, const DLinkedListItr &at);
void link_after(DLinkedNode *nd, const DLinkedListItr &at);

<DLinkedList::link_after implementation. >= (U->)
// Links node after the given one. 
void DLinkedList::link_after(DLinkedNode *nd, 
                             const DLinkedListItr &at)
{
  assert(valid());  

  nd->l_prev=at.i_now;
  nd->l_next=at.i_now->l_next;
  at.i_now->l_next=nd;
  nd->l_next->l_prev=nd;

  l_tail=l_head->l_prev;

  assert(valid());  
}

<DLinkedList::link_before implementation. >= (U->)
// Links node before the given one. 
void DLinkedList::link_before(DLinkedNode *nd, 
                             const DLinkedListItr &at)
{
  assert(valid());  

  nd->l_next=at.i_now;
  nd->l_prev=at.i_now->l_prev;
  at.i_now->l_prev=nd;
  nd->l_prev->l_next=nd;

  l_head=l_tail->l_next;

  assert(valid());  
}

These methods remove arbitrary nodes from the list.

<Other public methods of DLinkedList. >+= (<-U) [<-D->]
// Unlinks nd.
void unlink(DLinkedNode *at);

// Unlinks pointed node. 
void unlink(DLinkedListItr &it);

<DLinkedList::unlink implementation. >= (U->)
// Unlinks pointed node. 
void DLinkedList::unlink(DLinkedListItr &it)
{
   unlink(it.i_now);
}

// Unlinks nd.
void DLinkedList::unlink(DLinkedNode *at)
{ 
  assert(at && valid());  

  at->l_prev->l_next=at->l_next;
  at->l_next->l_prev=at->l_prev;

  if (at==l_tail && at==l_head)
    l_head=l_tail=NULL;
  else if (at==l_tail)
    l_tail=at->l_prev;
  else if (at==l_head)
    l_head=at->l_next;

  at->l_next=NULL;
  assert(valid());  
}
 

A more specific one removes (and returns) the head node.

<Other public methods of DLinkedList. >+= (<-U) [<-D->]
// Unlinks head nd.
DLinkedNode *unlink_head(void);

<DLinkedList::unlink_head implementation. >= (U->)
// Unlinks head nd.
DLinkedNode *DLinkedList::unlink_head(void)
{
  DLinkedNode *n=l_head;
  assert(valid());  
  n->l_prev->l_next=n->l_next;
  n->l_next->l_prev=n->l_prev;

  if (n==l_tail)
    l_head=l_tail=NULL;
  else
    l_head=n->l_next;
  n->l_next=NULL;
  assert(valid());  
  return n;
}

And yet another specific one removes the tail node.

<Other public methods of DLinkedList. >+= (<-U) [<-D->]
// Unlinks tail nd.
DLinkedNode *unlink_tail(void);

<DLinkedList::unlink_tail implementation. >= (U->)
// Unlinks tail nd.
DLinkedNode *DLinkedList::unlink_tail(void)
{
  DLinkedNode *n=l_tail;
  assert(valid());  
  n->l_prev->l_next=n->l_next;
  n->l_next->l_prev=n->l_prev;

  if (n==l_head)
    l_head=l_tail=NULL;
  else
    l_tail=n->l_prev;
  n->l_next=NULL;
  assert(valid());  
  return n;
}

Discussing now iterators over the list, they can be obtained from the list head and tail.

<Other public methods of DLinkedList. >+= (<-U) [<-D]
// Return first and last elements.
DLinkedListItr get_head(void);
DLinkedListItr get_tail(void);
// Return first and last elements.

<DLinkedList::get_head and get_tail implementation. >= (U->)
DLinkedListItr DLinkedList::get_head(void)
{ 
  DLinkedListItr itr;
  assert(valid()); itr.i_now=l_head; return itr; 
}
DLinkedListItr DLinkedList::get_tail(void) 
{  
  DLinkedListItr itr;
  assert(valid()); itr.i_now=l_tail; return itr;
}

The iterator class is a simple one. We provide common comparison and movement operators. We do not try to hide completely the list internals from its users; indeed, users will usually know how is the list stored because they are responsible for list node allocation. Remember that we are inside a tiny kernel.

<Double linked list iterator. >= (U->)
// An iterator for DLinkedLists.
//
class DLinkedListItr {
protected:
  friend class DLinkedList;
  DLinkedNode *i_now;           // Current postition.
public:
  // Creates a DLinkedListItr
  DLinkedListItr(void) : i_now(NULL) {; }
  DLinkedListItr(const DLinkedList &list) : i_now(list.l_head) {;}

  // Compare iterator positions. 
  int operator==(const DLinkedListItr nd) const {return i_now == nd.i_now; }
  int operator!=(const DLinkedListItr nd) const {return i_now != nd.i_now; }
  int is_null(void) const { return i_now == NULL; }

  // get a reference to the element pointed by the iterator. 
  DLinkedNode *get_element(void){ return i_now; }

  // Advance iterator.
  DLinkedListItr &operator++(){ 
    assert(i_now); i_now=i_now->l_next; return *this;
  }
  DLinkedListItr &operator--(){ 
    assert(i_now); i_now=i_now->l_prev; return *this;
  }
};

Defines DLinkedListItr (links are to index).

As the list used iterators, and iterators use the list we must break the cyclic dependency.

<Double linked list dependencies. >+= (U->) [<-D]
class DLinkedListItr;

\subsection{Double linked lists \cpp{} source files}

All the code we have seen is kept in klib/dlist.h and klib/dlist.C.

<dlist.h*>=
<Read the literate code instead warning. >
#ifndef __D_LINKED_LIST_H
#define __D_LINKED_LIST_H

<Double linked list dependencies. >

<Double linked node. >
<Double linked list. >
<Double linked list iterator. >
#endif // __D_LINKED_LIST_H

<dlist.C*>=
<Read the literate code instead warning. >

#include <klib/dlist.h>         // Exported interface

<Double linked list implementation dependencies. >

<DLinkedList::get_head and get_tail implementation. >
<DLinkedList::valid implementation. >
<DLinkedList::link_first implementation. >
<DLinkedList::link_after implementation. >
<DLinkedList::link_before implementation. >
<DLinkedList::unlink implementation. >
<DLinkedList::unlink_head implementation. >
<DLinkedList::unlink_tail implementation. >
<Implementation of other public methods of DLinkedList. >