The linklist library version 1.1

Contents

• Introduction
• General notes
• List format
• Typical usage
• Reference

  ---

  Introduction

  The linklist library is a collection of C routines to manipulate doubly linked lists. The number of lists and the number of nodes per list is limited only by the available memory on the computer. Routines are available to create new lists, insert and delete nodes, go to the head or tail of the list, and to step from node to node in either direction.

  ---

  General notes

  • An ANSI C compiler, such as gcc is required. The regular K&R compiler won't work.
  • Include the following header file, found in /usr/local/include

        #include <linklist.h>
    

  • Use -llinklist on the command line to tell the compiler to use the linklist library. For example:

        gcc -o foo foo.c -L/usr/local/lib -llinklist
    

  ---

  List format

  The diagram below shows a representation of a linked list with three elements. Each node consists of three pointers: to the previous node, to the next node, and to the user's data. Two nodes, the head and the tail, are only there to mark the beginning and end of the list and contain no user data. The library keeps track of a ``current'' node for each list. The current pointer may be pointing at any of the nodes containing user data and is the focal point for any actions such as deleting, inserting, or stepping from node to node.

   
             head                cur                 tail
             |                   |                   |
             |                   |                   |
             v                   v                   v
   
   NULL <--- prev <--- prev <--- prev <--- prev <--- prev
             NULL      data      data      data      NULL
             next ---> next ---> next ---> next ---> next ---> NULL
  

  An empty list looks like this. It consists of head and tail nodes only and contains no user data.

             head      tail
             |         |
             |         |
             v         v
   
   NULL <--- prev <--- prev
             NULL      NULL
             next ---> next ---> NULL
  

  ---

  Typical usage

  This code fragment illustrates the typical use of the library routines.

  #include <stdio.h>
  #include <linklist.h>
  ...
  struct datum {
      char first[20];
      char last[20];
      int id;
  };
  
  struct datum *d;
  struct datum **dd;
  int ret;
  int id[MAX];
  ...
  /* create a bunch of lists */
  for (i=0; i<MAX; i++) {
      id[i] = ll_new_list();
      if (id[i] == NULL) {
  	fprintf(stderr,"can't make list %d\n", i);
  	exit(1);
      }
  ...
  /* insert data into one of the lists */
  id = 5;
  d = malloc(sizeof(struct datum);
  while (get_next_datum(d)) {
      ret = ll_insert_after(id, d);
      if (ret) {
  	fprintf(stderr,"ll_insert_after error\n");
  	exit(1);
      }
      d = malloc(sizeof(struct datum);
  }
  
  /* access each element of the list */
  (void)ll_first(id);
  d = ll_val(id);
  if (d == NULL) {
      fprintf(stderr,"NULL val!\n");
  }
  print_data(d);
  while(ll_next(id) > 0) {
      d = ll_val(id);
      if (d == NULL) {
  	fprintf(stderr,"NULL val!\n");
  	continue;
      }
      print_data(d);
  }
  
  /* destroy the list */
  count = ll_destroy_list(id, dd);
  for (i=0; i<count; i++) {
      free(dd[i]);
  }
  

  ---

  Reference

  • int ll_new_list(void)
    

    
    Create a new, empty linked list. If all went well, a non-negative list ID is returned. This ID is used in all subsequent functions that access this particular list. In case of an error, a negative value is returned.

    
    

  • int ll_insert_after(int id, void *p)
    

    • id is the ID of the list
    • p is a pointer to the data item

    
    Add a node to the list specified by id after the current node. The node will point to the data pointed to by p. The application programmer is responsible for allocating (and freeing, if necessary) these data pointers, which may point to any sort of data structure. The new node then becomes the current node. If all went well, 0 is returned, else some negative value.

    
    

  • int ll_insert_before(int id, void *p)
    

    • id is the ID of the list
    • p is a pointer to the data item

    
    Add a node to the list specified by id before the current node. The node will point to the data pointed to by p. The application programmer is responsible for allocating (and freeing, if necessary) these data pointers, which may point to any sort of data structure. The new node then becomes the current node. If all went well, 0 is returned, else some negative value.

    
    

  • void *ll_delete(int id)
    

    • id is the ID of the list

    
    Delete the current node in the specified list. The node before it then becomes the current node, unless this was the first node, in which case the following node becomes the current node. If all goes well, a pointer to the data item of the node is returned, so that the application can free() it, if necessary. A NULL pointer is returned in the case of an error. Note that it is possible that the data pointer itself was NULL, so this isn't a foolproof method of detecting an error.

    
    

  • void *ll_val(int id)
    

    • id is the ID of the list

    
    Returns a pointer to the data item of the current node A NULL pointer is returned in the case of an error, such as an empty list. Note that it is possible that the data pointer itself was NULL, so this isn't a foolproof method of detecting an error. The current node remains the same.

    
    

  • int ll_next(int id)
    

    • id is the ID of the list

    
    The current node moves the next node of the list. Returns 1 if all went well, 0 if we were already at the tail of the list, or a negative value if there was an error.

    
    

  • int ll_prev(int id)
    

    • id is the ID of the list

    
    The current node moves the previous node of the list. Returns 1 if all went well, 0 if we were already at the head of the list, or a negative value if there was an error.

    
    

  • int ll_first(int id)
    

    • id is the ID of the list

    
    The current node moves to the first node of the list that contains user data. Returns 0 if all went well, else some negative value if there was an error.

    
    

  • int ll_last(int id)
    

    • id is the ID of the list

    
    The current node moves to the last node of the list that contains user data. Returns 0 if all went well, else some negative value if there was an error.

    
    

  • int ll_destroy_list(int id, void **p)
    

    • id is the ID of the list
    • p is a pointer to an array of pointers (see below)

    
    The specified list is destroyed. That is, all of the nodes allocated for the list are freed, and any state for the list is ``forgotten''. A negative value is returned if there was an error. If all went well, a non-negative integer is returned, which specifies the number of nodes (containing user data) that were deleted. The pointer p will then point to an array of data pointers of the list which can then be freed by the application.