Re my request for help with dynamic lists
Russell Smithers
R.Smithers at ee.surrey.ac.uk
Tue May 21 00:18:16 AEST 1991
Well its been a little while now and since there seems no more replys being mailed to me I shall make a summery well this was my initial question :
___________________________________________________________________-_
Subject: Doubly Linked Lists
Keywords:
Hi every one, I thought that I would tap into all this knowladge. My que
stions is this.
Q. I have been programing in C for about a year in my own spare time wit
hout any one saying to me learn c or any one helping me that much, but I realy l
ike the language I have bought some books on the subject "Data Structures Using
C" being one of them and I know that the book just mentioned contains enough for me to learn doubly linked lists I also know that if I had the time to sit down
and spend some proper time doing it that id be able to do it my self(ive tried t
his though, but I dont have enough time), so my question(finaly) is this could s
ome kind soul mail me and help me out it wont take me long just about three e-ma
ils if that.
Thanks any one!
P.S. I realy need and would appreciate this as im working on a program and doubl
y linked lists are its heart!
______________________________________________________________________
I think that I missed telling every one that I actualy do know what ll,dll and all that is I just wanted some C code, but I god a lot of realy good replys with lots of source so here it all is im leaving out the headers/footers.
_______________________________________________________________________
typedef struct snode {
int data; /* There can be as many data fields as
you desire. */
struct snode *front;
struct snode *rear;
} node;
Nice start... Now write a routine that creates a new node and adds it to
the list.
node *list = NULL;
node *newNode(data)
int data;
{ node *new;
if (new = (node *)malloc(sizeof(node))) {
new->data = data;
new->front = new->rear = NULL;
}
return (new);
}
node *addToList(data)
int data;
{ node *new;
new = newNode(data);
if (list) {
new->front = list;
list->rear = new;
}
list = new;
return (list);
}
Now a routine to delete a data item from the list.
node *deleteFromList(data)
int data;
{ node *tracer = list;
while (tracer) {
if (tracer->data == data) {
if (tracer->front) tracer->front->rear = tracer->rear;
if (tracer->rear) tracer->rear->front = tracer->front;
if (list == tracer) list = tracer->front;
free(tracer);
tracer = NULL;
}
else tracer = tracer->front;
}
return (list);
}
Those routines should be enough to keep the mind bouncing for awhile. Just
keep remembering that pointers will act as boolean FALSE if they are NULL,
and functions are a similar manner.
************************************************************************************
Here's what we use -- the C source and the associated .h file follow.
Duane Morse e-mail: duane at anasaz (or ... asuvax!anasaz!duane)
(602) 861-7609
------------------------------C source follows
/*TITLE llist.c - Anasazi Linked List Utility Routines - 1.15 */
/*SUBTTL Preface, includes, defines, and declarations */
/* (]$[) llist.c:1.15 | CDATE=3/8/90 16:22:38 */
/*
** Copyright (C) 1987,1989 Anasazi, Inc.
** All Rights Reserved
*/
#include <stdio.h>
#include <llist.h>
#include <dbug.h>
static char LNK_NULL_ERR[] = "link is null";
static char CUR_NULL_ERR[] = "current is null";
static char NEW_NULL_ERR[] = "new is null";
static char CUR_BAD_ERR[] = "llist.current fwd or bwd pointer messed up";
static char LNK_BAD_ERR[] = "l_llist link fwd or bwd pointer messed up";
extern void l_abort();
/*SUBTTL l_linit - Initialize a link list header */
/*
** void l_linit(link)
**
** Parameters:
** link - a pointer to a l_list data structure
**
** Returns:
** Nothing.
*/
void l_linit(link)
register l_list *link;
{
DBUG_ENTER("l_linit");
DBUG_3("llist", "l_linit(%#lx)", (long)link);
if(link == LNULL)
l_abort(LNK_NULL_ERR, 1);
link->forward = link->backward = link;
DBUG_VOID_RETURN;
}
/*SUBTTL l_lafter - Link new item after current item */
/*
** void l_lafter(current,new)
**
** Parameters:
** current - l_list structure which points to current item.
** new - l_list structure which points to item to be put into list.
** Returns:
** Nothing.
*/
void l_lafter(current,new)
register l_list *current, *new;
{
DBUG_ENTER("l_lafter");
DBUG_4("llist", "l_lafter(%#lx, %#lx)", (long)current, (long)new);
if(current == LNULL)
l_abort(CUR_NULL_ERR, 1);
if(new == LNULL)
l_abort(NEW_NULL_ERR, 1);
if ((current->forward == LNULL) || (current->backward == LNULL))
l_abort(CUR_BAD_ERR, 1);
new->forward = current->forward;
new->backward = current;
current->forward->backward = new;
current->forward = new;
DBUG_VOID_RETURN;
}
/*SUBTTL l_lbefore - Link new item before current item */
/*
** void l_lbefore(current,new)
**
** Parameters:
** new - l_list structure pointing to item tp be put into list.
** current - l_list structure pointing to current item in list.
**
** Returns:
** Nothing.
*/
void l_lbefore(current,new) /* Link "old" before "new" */
register l_list *current, *new;
{
DBUG_ENTER("l_lbefore");
DBUG_4("llist", "l_lbefore(%#lx, %#lx)", (long)current, (long)new);
if(current == LNULL)
l_abort(CUR_NULL_ERR, 1);
if(new == LNULL)
l_abort(NEW_NULL_ERR, 1);
if ((current->forward == LNULL) || (current->backward == LNULL))
l_abort(CUR_BAD_ERR, 1);
new->forward = current;
new->backward = current->backward;
current->backward->forward = new;
current->backward = new;
DBUG_VOID_RETURN;
}
/*SUBTTL l_unlink - Unlink specified item */
/*
** void l_unlink(link)
**
** Parameters:
** link - pointer to link to be removed from list.
**
** Returns:
** Nothing.
**
*/
void l_unlink(link)
register l_list *link;
{
DBUG_ENTER("l_unlink");
DBUG_3("llist", "l_unlink(%#lx)", (long)link);
if(link == LNULL)
l_abort(LNK_NULL_ERR, 1);
if ((link->forward == LNULL) || (link->backward == LNULL))
l_abort(LNK_BAD_ERR, 1);
link->forward->backward = link->backward;
link->backward->forward = link->forward;
DBUG_VOID_RETURN;
}
/*SUBTTL l_unlbef - Unlink the item before the current item */
/*
** l_list *l_unlbef(link)
**
** Unlink the item before link and return a pointer to it.
**
** Parameters:
** link = A pointer to the current item in the list.
**
** Returns:
** A pointer to the item which was unlinked.
*/
l_list *l_unlbef(link)
register l_list *link;
{
l_list *rlink;
DBUG_ENTER("l_unlbef");
DBUG_3("llist", "l_unlbef(%#lx)", (long)link);
if(link == LNULL)
l_abort(LNK_NULL_ERR, 1);
if ((link->forward == LNULL) || (link->backward == LNULL))
l_abort(LNK_BAD_ERR, 1);
rlink = link->backward;
if (rlink == link)
return LNULL;
link->backward->backward->forward = link;
link->backward = link->backward->backward;
DBUG_RETURN(rlink);
}
/*SUBTTL l_unlaft - Return unlinked item after link */
/*
** l_list *l_unlaft(link)
**
** Removes the item which linked after the item pointed to by link and
** returns a pointer to it.
**
** Parameters:
** link = A pointer to the current item in the list.
**
** Returns:
** Returns a pointer to the item removed from the list.
**
*/
l_list *l_unlaft(link)
register l_list *link;
{
l_list *rlink;
DBUG_ENTER("l_unlaft");
DBUG_3("llist", "l_unlaft(%#lx)", (long)link);
if(link == LNULL)
l_abort(LNK_NULL_ERR, 1);
if ((link->forward == LNULL) || (link->backward == LNULL))
l_abort(LNK_BAD_ERR, 1);
rlink = link->forward;
if (rlink == link)
return LNULL;
link->forward->forward->backward = link;
link->forward = link->forward->forward;
DBUG_RETURN(rlink);
}
/*SUBTTL l_nextl - Return a pointer to the next item in the list. */
/*
** l_list *l_nextl(link)
**
** Return a pointer to the next item in the list.
**
** Parameters:
** link - A pointer to the current item in the list.
**
** Returns:
** Return a pointer to the next item in the list.
*/
l_list *l_nextl(link)
register l_list *link;
{
#ifdef XTRADBUG
DBUG_ENTER("l_nextl");
DBUG_3("llist", "l_nextl(%#lx)", (long)link);
#endif
if(link == LNULL)
l_abort(LNK_NULL_ERR, 1);
#ifdef XTRADBUG
DBUG_RETURN(link->forward);
#else
return link->forward;
#endif
}
/*SUBTTL l_prevl - Return a pointer to the previous item in the list. */
/*
** l_list *l_prevl(link)
**
** Return a pointer to the previous item in the list.
**
** Parameters:
** link - A pointer to the current item in the list.
**
** Returns:
** Return a pointer to the previous item in the list.
*/
l_list *l_prevl(link)
register l_list *link;
{
#ifdef XTRADBUG
DBUG_ENTER("l_prevl");
DBUG_3("llist", "l_prevl(%#lx)", (long)link);
#endif
if(link == LNULL)
l_abort(LNK_NULL_ERR, 1);
#ifdef XTRADBUG
DBUG_RETURN(link->backward);
#else
return link->backward;
#endif
}
/*SUBTTL l_lcount - count number of elements in a linked list */
/*
** int l_lcount(head)
**
** This routine runs through a linked list, merely counting
** counting the number of members.
**
** Parameters:
** head = points to the head of the list.
**
** Returns:
** Number of elements in the list.
*/
int l_lcount(head)
register l_list *head;
{
register l_list *link;
register int n;
for (n = 0, link = l_nextl(head); head != link; link = l_nextl(link))
n++;
return n;
}
------------------------------Include file follows
/*TITLE llist.h - Header File for Anasazi list utilities - 1.3 */
/* (]$[) llist.h:1.3 | CDATE=3/16/88 11:25:13 */
#ifndef l_llist_h
#define l_llist_h
/*
** Copyright (C) 1986,1987 Anasazi, Inc.
** All Right Reserved
**
** Contains the structure definitions and defines as well as the
** forward declarations for the linked list routines.
**
*/
#define LLIST 1
typedef struct s_list { /* Definition of a list header */
struct s_list *forward;
struct s_list *backward;
} l_list;
#define LNULL ((l_list *) 0) /* Null list pointer */
#define v_lempty(link) ((link)->forward == (struct s_list *) &((link)->forward))
/* References to link list routines */
l_list *l_unlbef();
l_list *l_unlaft();
l_list *l_nextl();
l_list *l_prevl();
void l_linit();
void l_lafter();
void l_lbefore();
void l_unlink();
#define l_lempty(link) ((link)->forward == (struct s_list *) &((link)->forward))
#endif
*************************************************************************
No problem. For a little spice in life you should work on writing a generic
double-link-list library routine. C++ would be perfect for the job, but if
you want to do it in C here's a few suggestions:
typdef struct {
void *head;
int (*compare)(void *x,void *y);
} listdata;
listdata *createlist(int (*compfunc)(void *x,void *y));
int addtolist(listdata *list,void *data);
int delfromlist(listdata *list,void *data);
int listcontains(listdata *list,void *data);
void destroylist(listdata *list);
void foreach(listdata *list,void (*dofunc)(void *data));
A small set of roiutines lis this will go along way, since you can reuse them
over and over again. The compare function is used to sort the list. The
foreach() function can be used to interate ofer the entire list ad do something
with each data item. Like I said, this stuff is best handled in C++ :)
*******************************************************************
History of my double-linked list package.
-----------------------------------------
After many iterations, mostly concerned with the end of the list, and also the
problems of empty lists: I decided that the end of a list would be denoted by
a pointer back to the root (pair) of the list, using an (almost) circular list
with the side effect that NULL would not be used under any circumstances. This
would allow lists to be checked, for validity, for debug purposes, with a high
probability of discovering invalid lists. The first (abstract) attempt was:
typedef struct links {struct links *next, *prev;} LINKS;
#define end(list) &list
#define init(list) list.next=list.prev=end(list)
LINKS *add_after(LINKS *place, LINKS *item)
{item->prev=place;
item->next=place->next;
item->next->prev=item;
place->next=item;
return(item);}
LINKS *add_before(LINKS *place, LINKS *item)
{item->next=place;
item->prev=place->prev;
item->prev->next=item;
place->prev=item;
return(item);}
LINKS *remove(LINKS *item)
{item->prev->next=item->next;
item->next->prev=item->prev;
return(item);}
These worked quite satisfactorily; but with a lot of casting where LINKS was
incorporated into larger (practical) structures. [Unless you are an _expert_
pointer juggler, LINKS _must_ be the first object in the structure]. The next
step was to use the power of C to reduce the number of expressions to one!
LINKS *add_after(LINKS *p, LINKS *q)
{return((q->prev=p)->next=(q->next=p->next)->prev=q);}
LINKS *add_before(LINKS *p, LINKS *q)
{return((q->next=p)->prev=(q->prev=p->prev)->next=q);}
Note the satisfying symmetry in the two functions; but the problem of the casts
still arose. As the above forms should expand to about seven instructions or
less, depending on your compiler, an inline form was on the cards as a macro.
#define add_before(P,Q)((void*)(((LINKS*)(Q))->next=((LINKS*)(P)))->prev= \
(((LINKS*)(Q))->prev=((LINKS*)(P))->prev)->next\
=((LINKS*)(Q)))
#define add_after(P,Q) ((void*)(((LINKS*)(Q))->prev=((LINKS*)(P)))->next= \
(((LINKS*)(Q))->next=((LINKS*)(P))->next)->prev\
=((LINKS*)(Q)))
#define remove(Q) (((LINKS*)(Q))->prev->next=((LINKS*)(Q))->next, \
((LINKS*)(Q))->next->prev=((LINKS*)(Q))->prev, \
((void*) (Q)))
With the auxiliary definitions, which avoid undue brain-strain:
#define end(R) ((void*)&(R).next)
#define init(R) ((void*)((R).next=(R).prev=end(R)))
The root of a list may be a simple structure containing a pair of pointers, or
it may be an entry in another list. In these cases the two pointer fields may
be identified as "first" and "last", which is felt to be more explanatory. This
involves changing the macros for end and init to:
#define end(R) ((void*)&(R).first)
#define init(R) ((void*)((R).last=(R).first=end(R)))
Where the root of the list is in static storage, the list may be initialised
statically, as below. Whether this is a good idea or not depends on the program
operation. (H&S[e2p73]"not all compilers accept casts in constant expressions")
static struct {LINKS *first, *last;} root={end(root), end(root)};
If it is desired to add elements to either the head or the tail of a list, the
operations may be defined in terms of the previous functions or macros:
#define add_head(R, Q) (add_after (end(R), Q))
#define add_tail(R, Q) (add_before(end(R), Q))
Similarly, functions/macros can be defined to (destructively) remove list items
#define get_head(R) (R.first==end(R)? NULL: remove(R.first))
#define get_tail(R) (R.last ==end(R)? NULL: remove(R.last ))
Where the list would be dismantled by: while(p=get_head(R)) {action}
Of course: the same effect could be obtained by using ANSI C void pointers for
the parameters (and return value) of the xxx_* functions. By incorporating the
casts into the macros, the need for casts in the user's program is zero, _if_
the user declares suitable structures. An example of an outline program for a
random poet is given below.
Scanning lists is a simple matter as demonstrated below. Provided that the list
root has been initialised, the following are safe, even with empty lists:
for(p=list.first; p!=end(list); p=p->next) {action} /* scan list forwards */
for(p=list.last; p!=end(list); p=p->prev) {action} /* scan list backwards */
The real beauty of the scheme is that: empty lists do not need to be treated as
special cases, and "guard" elements are not needed as they might be in PASCAL.
Even if special cases need to be treated differently the power of C macros will
allow conditional expressions to be used, if needed. However no special actions
are neccessary for empty lists with this package.
The next step is: to see which would be the most efficient way of sorting lists
of variable-length records. Would the use of a double linked list be more
efficient than sorting an array of pointers to records? [watch this space]
------------------------------------cut here-----------------------------------
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/**** application independent definitions for double-linked list package. ****/
typedef struct links {struct links *next, *prev;} LINKS;
#define end(R) ((void*)&(R).first)
#define init(R) ((void*)((R).last=(R).first=end(R)))
#define add_before(P,Q)((void*)(((LINKS*)(Q))->next=((LINKS*)(P)))->prev= \
(((LINKS*)(Q))->prev=((LINKS*)(P))->prev)->next\
=((LINKS*)(Q)))
/********************* application dependent definitions *********************/
typedef struct verse {struct {struct verse *next, *prev;} link;
int verse_no;
char stanza[1];} VERSE;
typedef struct chapter {struct {struct chapter *next, *prev;} link;
struct {struct verse *first, *last;} verses;
int chapter_no;} CHAPTER;
typedef struct {struct chapter *first, *last;} BOOK;
/** demo of 2d double-linked list, input chap# verse# stanza, finish with Q **/
void main(void)
{int new_verse_no, new_chapter_no; /* for input info */
CHAPTER *cc; VERSE *vv; /* pointers to current position in book */
BOOK chapters; init(chapters); /* book initially empty */
while(scanf("%d%d", &new_chapter_no, &new_verse_no)==2)/* stop if not nn */
{char stanza[80]; int test=-1; /* any non-zero value will suffice */
fgets(stanza, 79, stdin);/* read rest of line and \n, can't overflow */
for(cc=chapters.first; cc!=end(chapters); cc=cc->link.next)
{if((test=new_chapter_no-cc->chapter_no)<=0) break;} /* found? */
if(test!=0) /* then chapter does not exist, make one */
{CHAPTER *new=malloc(sizeof(CHAPTER)); /* fixed size */
init(new->verses); new->chapter_no=new_chapter_no; /* fill */
cc=add_before(cc, new);} /* and link into list of chapters */
for(vv=cc->verses.first; vv!=end(cc->verses); vv=vv->link.next)
{if(new_verse_no<vv->verse_no) break;} /* bigger verse # found */
{VERSE *new=malloc(sizeof(VERSE)+strlen(stanza)); /* size varies! */
new->verse_no=new_verse_no; strcpy(new->stanza, stanza); /* fill */
add_before(vv, new);} /* and link into list of verses */
continue;} /* noise word, for fortran lovers */
for(cc=chapters.first; cc!=end(chapters); cc=cc->link.next)
for(vv=cc->verses.first; vv!=end(cc->verses); vv=vv->link.next)
{printf("%4d%4d:%s", cc->chapter_no, vv->verse_no, vv->stanza);}
return;} /* more noise, for fortran lovers */
/* header file: linkpack.h - definitions for double-linked lists 4jan90 */
#ifndef NULL
#define NULL (void*) 0
#endif
typedef struct links {struct links *next, *prev;} LINKS;
typedef struct root {struct links *first, *last;} ROOT;
/*n.b. P=Position (in list). Q=item in Question. R=Root of list */
#define add_before(P,Q)((void*)(((LINKS*)(Q))->next=((LINKS*)(P)))->prev= \
(((LINKS*)(Q))->prev=((LINKS*)(P))->prev)->next\
=((LINKS*)(Q)))
#define add_after(P,Q) ((void*)(((LINKS*)(Q))->prev=((LINKS*)(P)))->next= \
(((LINKS*)(Q))->next=((LINKS*)(P))->next)->prev\
=((LINKS*)(Q)))
#define remove(Q) (((LINKS*)(Q))->prev->next=((LINKS*)(Q))->next, \
((LINKS*)(Q))->next->prev=((LINKS*)(Q))->prev, \
((void*) (Q)))
#define end(R) ((void*)&(R).first)
#define init(R) ((void*)((R).last=(R).first=end(R)))
#define add_head(R, Q) (add_after (end(R), Q))
#define add_tail(R, Q) (add_before(end(R), Q))
#define get_head(R) (R.first==end(R)? NULL: remove(R.first))
#define get_tail(R) (R.last ==end(R)? NULL: remove(R.last ))
***************************************************************
struct dummy {
int x;
int y;
struct dummy *next;
}
where next points to the next element in the list and a NULL value
for next indicates the last element in the list. A similar doubly
linked list would have elements defined:
struct dummy {
int x;
int y;
struct dummy *next;
struct dummy *prev;
}
where next points to the next element in the list and prev points
to the previous element in the list. A NULL value for next indicates
the last element in the list; a NULL value for prev indicates the
first element.
What good is it? Typically for maintaining an ordered list that can be
traversed in both directions. The code to insert a new element on an
ordered list would look something like this:
struct dummy *first; /* a pointer to the first list element */
struct dummy *last; /* a pointer to the last list element */
insert_list_element(new)
struct dummy *new;
{
struct dummy *dum = first;
/* sort on struct element x, or add new element at end of list */
while ((dum->x < new->x) && (dum->next != NULL))
dum = dum->next;
/* set up new element's links */
new->next = dum->next;
new->prev = dum;
/* link new element into the list */
if (dum->next != NULL)
(dum->next)->prev = new;
dum->next = new;
break;
}
A real world example of a use of such a list would be a Unix disk driver.
Requests to read blocks from the disk would be sorted by track number
(the "x" of the example). The driver would begin operations on the
element pointed to by "first" and continue to the end (i.e. moving the
read head across the disk in one direction). It would then start with
the element pointed to by "last" and continue to the beginning (i.e.
moving the head back across the disk).
*******************************************************************************
Well thats it!
More information about the Comp.lang.c
mailing list