Thread: circular linked lists??

  1. #1
    Registered User
    Join Date
    Apr 2002
    Posts
    19

    circular linked lists??

    how do you write an implementation for the routine

    void delete_bufr( BUFR *p ){

    which deallocates all storage associated with the buffer pointed to by p and sets p to a NULL value.

    here is the header file for the above function:

    thanks
    Atif.


    /*******************
    * circbuf.1.h *
    *******************/

    /************************************************** **************
    * *
    * Prototypes for functions operating on buffer. *
    * * *
    *
    * *
    * init_bufr(n): *
    * allocates buffer, size n; returns pointer to buffer. *
    * *
    * pushout(buffer,a,b): *
    * adds a to buffer; returns true if a overwrites oldest *
    * char which is copied to *b; returns false otherwise *
    * *
    * remchars(buffer,n): *
    * removes the n oldest chars from buffer *
    * *
    * matchkey(buffer,key): *
    * returns true if the string key matches the contents of *
    * the buffer, STARTING FROM THE OLDEST CHARACTER in buffer*
    * *
    * pick_char(buffer,k,b): *
    * copies kth oldest character in buffer to *b, returning *
    * true if successful or false if there was no such char *
    * *
    * dump_bufr(buffer): *
    * for debugging: writes to stderr the current contents of *
    * buffer and its idea of how many chars; the next vacant *
    * spot and/or oldest character is marked by >>> *
    * *
    * clr_bufr(buffer): *
    * empties, but doesn't destroy buffer *
    *
    delete_bufr(bufptr): destroys buffer (== *bufptr) sets *bufptr to null
    ************************************************** **************/

    #ifndef BUFR
    #define BUFR void *
    #endif

    BUFR init_bufr(int);
    int pushout( BUFR , int, int * );
    int remchars( BUFR , int );
    int matchkey( BUFR , char * );
    int pick_char( BUFR , int, char * );
    void dump_bufr(BUFR );
    void clr_bufr(BUFR );
    void delete_bufr(BUFR *);

  2. #2
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Use a double linked list.
    Code:
    if( p->prev != p )
    {
        p->prev->next = p->next;
        p->next->prev = p->prev;
    }
    else
    {
    ... p is the only node in the whole list
    }
    Quzah.
    Hope is the first step on the road to disappointment.

  3. #3
    Registered User
    Join Date
    Apr 2002
    Posts
    19
    hey quzah, what do you mean p is the only node in the list...

    cheers,

    Atif

  4. #4
    ....
    Join Date
    Aug 2001
    Location
    Groningen (NL)
    Posts
    2,380
    If p->prev points to p, then it means that p is the only node. Remember the circularity of the list.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. singly linked circular list
    By DarkDot in forum C++ Programming
    Replies: 0
    Last Post: 04-24-2007, 08:55 PM
  2. Linked Lists 101
    By The Brain in forum C++ Programming
    Replies: 5
    Last Post: 07-24-2004, 04:32 PM
  3. Map file formats and linked lists
    By Spitball in forum Game Programming
    Replies: 2
    Last Post: 03-04-2004, 11:32 PM
  4. need help w/ linked lists
    By MKashlev in forum C++ Programming
    Replies: 11
    Last Post: 08-05-2002, 08:57 PM
  5. doubly linked lists
    By qwertiop in forum C++ Programming
    Replies: 3
    Last Post: 10-03-2001, 06:25 PM