Re: [newbie] linked lists

From: Daniel Koepke (
Date: 01/14/97

On Tue, 14 Jan 1997, Cyber Reaper wrote:

> ok... I feel that I have reached the point where I will need linked lists...
> but I dont know how to make them... can anyone give me a quick rundown on
> makeing linked list.. it would be much apreataded<sp?> 

Linked lists are good things.  Dynamic storage is always fun.  But,
before I explain how and why, know that linked lists are not always
the best solution.  A large linked list being traversed takes time
and creating a doubly linked list (one with a 'prev' link) takes up
a bit more memory (although it works better for larger lists).

On with the good stuff.  A linked list is essentially a pointer that
contains data and another pointer (that points to another pointer),
thus creating a list of pointers all linked together by a 'next' type
structure.  For instance:

  struct data_entry_s {
     int data_x, data_y;
     char *data_z;
     struct data_entry_s *next;

The 'next' element will point to the next entry in our list.  Now
that we have the structure, we create it's top element (the start of
the list):

  struct data_entry_s *DataEntries = NULL;

To begin to add to the list it needs to be 'malloc()'d.  In CircleMUD,
you can accomplish this with the CREATE() macro.  Here's some code to
make use of the above structure and CircleMUD's CREATE() macro:

  struct data_entry_s *add_data_to_list(int x, int y, char *z) {
    struct data_entry_s *new;
    CREATE(new, struct data_entry_s, 1);

    new->x = x;
    new->y = y;
    new->z = str_dup(z);

    // Now we prepend to the linked list since it's fastest.  To
    // append we'd need to get to the end of the list somehow.  If
    // you have an 'EndOfList' pointer, that will be useful for
    // this.  Cycling all the way to the end is too wasteful,
    // otherwise.
    new->next = DataEntries; // set next to first element
    DataEntries = new; // make this the new first element
    return (new);

To remove elements, CircleMUD includes the REMOVE_FROM_LIST() macro
[the below code is not a "complete" selection]:

  // Find the entry with X==1 and Y==1 and remove it
  // We cycle through the list, setting 'ent' to the first one and
  // each time through that we don't satisfy our condition, setting
  // it to 'next' until 'ent' is NULL (eg., we have hit the end of
  // the list).
  for (ent = DataEntries; ent; ent = ent->next)
    if (ent->x == 1 && ent->y == 1)
  REMOVE_FROM_LIST(ent, DataEntries, next);

Anyway, that should demonstrate the basics.  If you need more help,
I'll offer it.

Daniel Koepke
Forgive me father, for I am sin.

| Ensure that you have read the CircleMUD Mailing List FAQ: |
|   |

This archive was generated by hypermail 2b30 : 12/18/00 PST