Thread: C Linked List - first attempt.

  1. #16
    Registered User
    Join Date
    Apr 2013
    Posts
    1,646
    Example where the last node pointer (called tail) is in main, and without a dummy node.

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    struct node                 /* node structure */
    {
        struct node *next;
        int data;
    };
    
    void createNewNode(struct node **head, struct node **tail, int data)
    {
        /* allocate space for new node */
        struct node *newNode = malloc(sizeof(*newNode));
        if(!newNode)            /* check the memory allocation took place */
        {
            printf("Out of memory\n");
            exit(-1);           /* exit program showing error code -1 */
        }
        newNode->next = NULL;   /* initialise the new node */
        newNode->data = data;
        if(NULL == *head)       /* set link to the new node */
            *head = newNode;
        else
            (*tail)->next = newNode;
        *tail = newNode;
    }
    
    void deleteList(struct node **head, struct node **tail)
    {
        struct node *thisNode;  /* pointers to node */
        struct node *nextNode;
        /* if null pointers or empty list return */
        if(head == NULL || tail == NULL || *head == NULL)
            return;
        thisNode = *head;       /* free nodes */
        while(thisNode)
        {
            nextNode = thisNode->next;
            free(thisNode);
            thisNode = nextNode;
        }
        *head = NULL;           /* reset head, tail */
        *tail = NULL;
    }
    
    void displayList(struct node **head)
    {
        struct node *Node;      /* pointer to node */
        /* check for null ptr or empty list */
        if(head == NULL || *head == NULL)
        {
            printf("empty list\n");
            return;
        }
        Node = *head;
        while(Node)             /* while not end of list */
        {
            /* show the element */
            printf("{addr} %p {data} %d {next} %p\n",Node,Node->data,Node->next);
            Node = Node->next;
        }
    }
    
    int main(int args, char *argv[])
    {
        struct node *head = NULL;           /* root pointer */
        struct node *tail = NULL;           /* last node pointer */
        int i;                              /* counter variable */
        
        for(i = 0 ; i < 10 ; i++)           /* add some elements to the list */
            createNewNode(&head, &tail, i);
    
        displayList(&head);                 /* display the total list */
        
        deleteList(&head, &tail);           /* delete list */
        
        displayList(&head);                 /* display empty list */
        
        return 0;
    }
    Last edited by rcgldr; 09-17-2013 at 11:39 AM.

  2. #17
    young grasshopper jwroblewski44's Avatar
    Join Date
    May 2012
    Location
    Where the sidewalk ends
    Posts
    294
    Here is a sample program using a linked list. Note that the most basic of operations have been given their own functions.

    linkedlistop.h
    Code:
    // linkedlistop.h
    
    
    struct node
    {
            int data;
            struct node * next;
    };
    
    
    void display( struct node * );
    struct node * addback( struct node * , int );
    struct node * addfront( struct node * , int );
    struct node * nalloc( int );
    struct node * find( struct node * , int );
    struct node * delnode( struct node * , struct node * );
    void freelist( struct node * );
    linkedlistop.c
    Code:
    /*
      this file contains functions for manipulating a linked list
    */
    
    
    #include <stdlib.h>
    
    
    #ifndef LLOP
    #define LLOP
    
    
    #include "linkedlistop.h"
    #include <stdio.h>
    
    
    #endif
    
    
    /*
      iterate through list and print data from each node
    */
    void display( struct node * head )
    {
        struct node * p = head;
        while( p != NULL )
        {
            printf( "%d " , p->data );
            p = p->next;
        }
        printf( "\n" );
    }
    /*
      creates node, init's data members and returns pointer to node
    */
    struct node * nalloc( int data )
    {
        struct node * p = malloc( sizeof( struct node ) );
        if( p != NULL )
        {
            p->data = data;
            p->next = NULL;
        }
        return p;
    }
    /*
      creates node and adds it to the front of list, becoming new head
    */
    struct node * addfront( struct node * head , int data )
    {
        struct node * p = nalloc( data );
        if( p == NULL )
            return head;
        p->next = head;
        return p;
    }
    /*
      creates node and adds it to back of list, returns (new) head
    */
    struct node * addback( struct node * head , int data )
    {
        struct node * curr;
        struct node * p = nalloc( data );
        if( p == NULL )
            return head;
        if( head == NULL )
            return  p;
        for( curr = head; curr->next != NULL; curr = curr->next )
            ;
        curr->next = p;
        return head;
    }
    /*
      searchs link beginning at head for target
    */
    struct node * find( struct node * head , int target )
    {
        struct node * p = head;
        if( head == NULL )
            return NULL;
        while( p != NULL )
        {
            if( p->data == target )
                return p;
            p = p->next;
        }
        return NULL;
    }
    /*
      deletes the node pointed to by np, returns updated head
    */
    struct node * delnode( struct node * head , struct node * np )
    {
        if( head == NULL || np == NULL )
            return NULL;
        struct node * p , * q = NULL;
        for( p = head; p != np && p != NULL; p = p->next )
            q = p;
        if( p == NULL ) // not found
            return head;
        if( q == NULL ) // head node
        {
            free( np );
            return p->next;
        }
        q->next = p->next;
        free( np );
        return head;
    }
    /*
      deletes every node in list using free()
    */
    void freelist( struct node * head )
    {
        struct node * p = NULL;
        while( head )
        {
            p = head;
            head = head->next;
            free( p );
        }
    }
    lltest.c
    Code:
    #include <stdlib.h>
    #include <time.h>
    
    
    #ifndef LLOP
    #define LLOP
    
    
    #include "linkedlistop.h"
    #include <stdio.h>
    
    
    #endif
    
    
    int main( void )
    {
        srand( time( NULL ) );
        struct node * head = nalloc( 10 );  // list: 10
    
    
        display( head );
    
    
        head = addback( head , rand() % 100 );  // list: 10 , (random1)
    
    
        display( head );
    
    
        head = addfront( head , rand() % 100 ); // list: (random2) , 10 , (random1)
    
    
        display( head );
    
    
        head = delnode( head , find( head , 10 ) ); // list: (random2) , (random1)
    
    
        display( head );
    
    
        freelist( head );
    
    
        return 0;
    }
    Use this to compare against your code where you are having trouble understanding.
    Last edited by jwroblewski44; 09-17-2013 at 04:06 PM.
    "Simplicity is the ultimate sophistication." - Leonardo da Vinci

  3. #18
    Registered User
    Join Date
    Apr 2013
    Posts
    1,646
    Quote Originally Posted by jwroblewski44 View Post
    Here is a sample program using a linked list.
    An issue with this style of linked list code is that appending a node to the end of a list requires scanning of the list. Post #8 is an example of generic linked list code that uses a head and tail pointer so that appending doesn't require traversing a list. Another option that avoids traversing a list for appends is a "circular" list, using a single pointer to the last node in a list, which in turn points to the first node in the list, which points to the second node in a list ... . This requires one additional dereference operation to get to the first node of a list.

  4. #19
    young grasshopper jwroblewski44's Avatar
    Join Date
    May 2012
    Location
    Where the sidewalk ends
    Posts
    294
    It's not meant to be robust, just an example. But thanks for pointing that out.
    "Simplicity is the ultimate sophistication." - Leonardo da Vinci

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Declaring linked list inside linked list
    By blueboyz in forum C Programming
    Replies: 33
    Last Post: 04-20-2012, 10:13 AM
  2. Linked lists; My first attempt
    By relyt_123 in forum C++ Programming
    Replies: 9
    Last Post: 11-05-2007, 02:54 PM
  3. Problem with my first linked list attempt.
    By SlyMaelstrom in forum C++ Programming
    Replies: 3
    Last Post: 11-09-2005, 04:33 AM
  4. singly linked list to doubly linked list
    By t48j in forum C Programming
    Replies: 3
    Last Post: 03-23-2005, 06:37 PM
  5. Replies: 6
    Last Post: 03-02-2005, 02:45 AM