Double-Linked Lists

Before STL we had to write our own versions of linked-lists. This is mine.

See:

A small test program is contained within the definition file (tag.cpp).

`tag.h`

/* tag.h
*
*   tags are used to maintain double-linked lists
*
*/
#if !defined(__TAG_H)
#define __TAG_H

class List;

class Node {
public:
	Node *next;
	Node *prev;
	Node(): next(0), prev(0) { }
	virtual ~Node() { }
	virtual void show() { }
	virtual long size() { return sizeof( Node); }
	friend List;
};

class List {
	Node *top;
	Node *bottom;
	int length;
public:
	List(): top(0), bottom(0), length(0) { }
	~List() { clear(); }

	Node *first() { return top; }
	Node *last()  { return bottom; }
	int count() const { return length; }

	void append(Node *np);
	void prepend(Node *np);
	void clear();
	int index(Node *np);
	void insert(Node *np, int n);
	void after(Node *np, Node *after);
	int extract(Node *np);
	void remove(Node *np);
	void show();
	long size();

	Node *operator [](int n);
};

#endif

`tag.cpp`

/*** tag.cpp  $Revision:   1.1  $  $Date:   23 Jan 1991 21:10:20  $
*
*  Maintain double-linked lists
*
***/
#include "stdio.h"
#include <string>
#include "tag.h"
using namespace std;

#if defined(TAG_TEST)

class Label: public Node {
public:
	string item;
	Label(char *name) { item = name; }
	~Label() { printf("Deleting node: %s\n",item.c_str()); }
	void show();
};

List labels;

#define MAXC 128
char text[MAXC];
void print(const char *text);
void show_list(List &lp);

void main()
{
	int i,ntag=0;
	Node *np;

	for (i=0; i<6; i++) {
		sprintf_s(text,MAXC-1,"tag %d",++ntag);
		np = new Label(text);
		labels.append(np);
	}
	show_list(labels);

	np = labels[5];
	printf("testing index function (offset 5): %d\n",labels.index(np));
	if (np) {
		print("\nnode at position 5 is ");
		np->show();
		print("\n\n");
	}

	ntag = 3;
	printf("\n Remove node %d\n\n",ntag);
	labels.remove(labels[ntag-1]);
	show_list(labels);
}

void print(const char *text)
{
	fputs(text,stdout);
}

void Label::show()
{
	sprintf_s(text,MAXC-1,"%8x %8x %8x  ",this,next,prev);
	print(text);
	print(item.c_str());
	print("\n");
}

void show_list(List &lp)
{
	sprintf_s(text,MAXC-1,"\n%8s %8s %8s %8s\n","list","first","last","length");
	print(text);
	sprintf_s(text,MAXC-1,"%8x %8x %8x ",&lp,lp.first(),lp.last());
	print(text);
	sprintf_s(text,MAXC-1,"%8d\n\n",lp.count());
	print(text);
	sprintf_s(text,MAXC-1,"%8s %8s %8s\n","node","next","prev");
	print(text);
	lp.show();
	print("\n\n");
}

#endif

void List::show()
{
	Node *np;
	for (np=first(); np; np=np->next) np->show();
}

long List::size()
{
	Node *np;
	long sum = sizeof(List);
	for (np=first(); np; np=np->next) sum += np->size();
	return sum;
}

/* remove
*
*  Cut specified node from list and return it
*  to the list of available nodes.
*
*/
void List::remove(Node *np)
{
	if (extract(np)) delete np;
}

/*
*
*  Clear all nodes from list
*
*/

void List::clear()
{
	while (length) remove(top);
}


/* append
*
*  Add node to bottom of list
*
*/
void List::append(Node *np)
{
	Node *c;
	if (!np) return;
	c = bottom;
	np->next = 0;
	np->prev = c;
	bottom = np;
	if (c) c->next = np;
	else top = np;
	length++;
}

/* prepend
*
*  Add node to top of list
*
*/
void List::prepend(Node *np)
{
	Node *c;
	if (!np) return;
	c = top;
	np->prev = 0;
	np->next = c;
	top = np;
	if (c) c->prev = np;
	else bottom = np;
	length++;
}

//  Extract specified node from list

int List::extract(Node *np)
{
	Node *next, *prev;
	int n = index(np);
	if (!n) return 0;
	next = np->next;
	prev = np->prev;
	if (prev) prev->next = next;
	else top = next;
	if (next) next->prev = prev;
	else bottom = prev;
	np->next = np->prev = 0;
	length--;
	return 1;
}

// returns position if node is in list and 0 otherwise.

int List::index(Node *np)
{
	Node *tp;
	int position;
	position = 0;
	for (tp=top; tp; tp=tp->next) {
		position++;
		if (tp==np) return position;
	}
	return 0;
}
	

//  returns node from specified offset (index-1) in list

Node *List::operator [](int n)
{
	int i;
	Node *np;
	if (n<0) return 0;
	np = top;
	for (i=0; i<n; i++) {
		if (np) np = np->next;
		else break;
	}
	return np;
}


//   add node after specified position in list

void List::insert(Node *np, int n)
{
	Node *cur, *pre;
	if (!np) return;
	cur = (*this)[n];
	if (cur) {
		pre = cur->prev;
		if (pre) {
			np->prev = cur->prev;
			np->next = cur;
			pre->next = np;
			cur->prev = np;
			length++;
		}
		else prepend(np);
	}
	else append(np);
}

// add node after specified node (which should be in the list)

void List::after(Node *np, Node *aft)
{
	Node *post;
	if (!aft) prepend(np);
	else if (index(aft) > 0) {
		post = aft->next;
		aft->next = np;
		np->prev = aft;
		np->next = post;
		post->prev = np;
		length++;
	}
}

Results


    list    first     last   length
  411100   323f18   322dc0        6

    node     next     prev
  323f18   323f48        0  tag 1
  323f48   323f78   323f18  tag 2
  323f78   323fa8   323f48  tag 3
  323fa8   323fd8   323f78  tag 4
  323fd8   322dc0   323fa8  tag 5
  322dc0        0   323fd8  tag 6


testing index function (offset 5): 6

node at position 5 is   322dc0        0   323fd8  tag 6



 Remove node 3

Deleting node: tag 3

    list    first     last   length
  411100   323f18   322dc0        5

    node     next     prev
  323f18   323f48        0  tag 1
  323f48   323fa8   323f18  tag 2
  323fa8   323fd8   323f48  tag 4
  323fd8   322dc0   323fa8  tag 5
  322dc0        0   323fd8  tag 6


Deleting node: tag 1
Deleting node: tag 2
Deleting node: tag 4
Deleting node: tag 5
Deleting node: tag 6

Maintained by John Loomis, updated Tue Feb 13 00:30:28 2007