my linked list code - comments please

This is a discussion on my linked list code - comments please within the C Programming forums, part of the General Programming Boards category; Would some of you experienced programmers please comment on my double linked lists code? Many thanks! (Special thanks to Dave_Sinkula ...

  1. #1
    Registered User
    Join Date
    Sep 2004
    Posts
    57

    my linked list code - comments please

    Would some of you experienced programmers please comment on my double linked lists code? Many thanks!

    (Special thanks to Dave_Sinkula for getting me past a mental block!)

    I am expecially concerned about possible "gotcha's", things I have not taken into consideration.

    Code:
    #include <stdio.h>
    
    typedef struct node NODE;
    struct node {
        NODE *pNext;
        NODE *pPrev;
        char *pLine;
    };
    NODE *head;
    NODE *tail;
    
    int initList();  // init with NULL head/tail
    void insertAtBeginning(NODE *);
    void insertAtEnd(NODE *);
    void insertBefore(NODE *, NODE *);
    void insertAfter(NODE *, NODE *);
    void removeNode(NODE *);
    
    void traverseForward(NODE *);
    void traverseBackward(NODE *);
    
    void doSomething(NODE *pNode);
    NODE * getNode();
    
    int main(int argc, char *argv[]) {
        char buf1[] = "this is buf 1.";
        char buf2[] = "this is buf 2.";
        char buf3[] = "this is buf 3.";
        NODE *ppp;
    
        if ( initList() == 0 )
            printf("initList malloc failed.\n");
    
        ppp = getNode();  // for simplicity here, error checking is done in getNode()
        ppp->pLine = buf1;
        insertAtEnd(ppp);          // 1
    
        ppp = getNode();
        ppp->pLine = buf2;
        insertAtBeginning(ppp);    // 2 1
    
        NODE *ppp2 = getNode();
        ppp2->pLine = buf3;
        insertAfter(ppp, ppp2);   // 2 3 1
    
        traverseForward(head);    // print list
        traverseBackward(tail);
    
        removeNode(ppp2);         // 2 1
        free(ppp2);
    
        traverseForward(head);
    }
    
    
    int initList() {
    
        head = (NODE *) malloc(sizeof(NODE));
        if (head == NULL)
            return 0;
    
        tail = (NODE *) malloc(sizeof(NODE));
        if (tail == NULL)
            return 0;
    
        head->pNext = tail;
        head->pPrev = NULL;
        head->pLine = NULL;
    
        tail->pNext = NULL;
        tail->pPrev = head;
        tail->pLine = NULL;
    
        return 1;
    }
    
    void insertAtBeginning(NODE *pNewNode) {
        insertAfter(head, pNewNode);
    }
    
    void insertAtEnd(NODE *pNewNode) {
        insertBefore(tail, pNewNode);
    }
    
    void insertBefore(NODE *pNode, NODE *pNewNode) {
        pNewNode->pPrev = pNode->pPrev;
        pNewNode->pNext = pNode;
        pNode->pPrev->pNext = pNewNode;
        pNode->pPrev = pNewNode;
    }
    
    void insertAfter(NODE *pNode, NODE *pNewNode) {
        pNewNode->pPrev = pNode;
        pNewNode->pNext = pNode->pNext;
        pNode->pNext->pPrev = pNewNode;
        pNode->pNext = pNewNode;
    }
    
    void removeNode(NODE *pNode) {
        pNode->pPrev->pNext = pNode->pNext;
        pNode->pNext->pPrev = pNode->pPrev;
    
        //free(pNode);  // should be done by caller, if finished with this node
    }
    
    void traverseForward(NODE *pNode) {
        NODE *ppp = pNode;
        if (ppp == head)
            ppp = head->pNext;
        while (ppp != tail) {
            doSomething(ppp);   // do whatever... with this node
            ppp = ppp->pNext;
        }
    }
    
    void traverseBackward(NODE *pNode) {
        NODE *ppp = pNode;
        if (ppp == tail)
            ppp = tail->pPrev;
        while (ppp != head) {
            doSomething(ppp);   // do whatever... with this node
            ppp = ppp->pPrev;
        }
    }
    
    void doSomething(NODE *pNode) {
        printf("%s\n",pNode->pLine);
    }
    
    NODE *getNode() {
        NODE *ppp;
        ppp = (NODE *) malloc(sizeof(NODE));
        if ( ppp == NULL ) {
            printf("malloc failed.\n");
            exit(0);
        }
        return ppp;
    }
    Last edited by cdave; 04-26-2005 at 11:25 PM.

  2. #2
    Registered User
    Join Date
    Mar 2005
    Posts
    37
    hi,

    I wanne to know as to what you want us to do ? send you review comments on ur code on the way its writen.. or try to find bug in ur code .. ??

  3. #3
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,006
    Since you call malloc, free, and exit, you should add this.
    Code:
    #include <stdlib.h>
    Here you are either using C99 or C++. Declarations may not follow statements in older C.
    Code:
        NODE *ppp2 = getNode();
    Similarly, these are not necessarily prototypes for functions taking no arguments in C.
    Code:
    int initList();  // init with NULL head/tail
    NODE * getNode();
    http://david.tribble.com/text/cdiffs.htm#C99-empty-parm

    The following cast is not necessary in C.
    Code:
    ppp = (NODE *) malloc(sizeof(NODE));
    FAQ > Explanations of... > Casting malloc
    Last edited by Dave_Sinkula; 04-27-2005 at 07:34 AM.
    7. It is easier to write an incorrect program than understand a correct one.
    40. There are two ways to write error-free programs; only the third one works.*

  4. #4
    Registered User
    Join Date
    Sep 2004
    Posts
    57
    Thank you Dave! Really good stuff!

    I:
    - bookmarked those 2 links you gave. (I'm still absorbing them)
    - took off the cast to malloc.
    - put in the "#include <stdlib.h>" (I had wondered about that)
    - fixed my prototypes for my 2 functions with no arguments
    - put my ppp2 declaration before all statements (not C99)

    ok, I'm off to my next task.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Following CTools
    By EstateMatt in forum C Programming
    Replies: 5
    Last Post: 06-26-2008, 10:10 AM
  2. Replies: 5
    Last Post: 11-04-2006, 05:39 PM
  3. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM
  4. How can I traverse a huffman tree
    By carrja99 in forum C++ Programming
    Replies: 3
    Last Post: 04-28-2003, 05:46 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21