By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
434,882 Members | 2,460 Online
Bytes IT Community
Submit an Article
Got Smarts?
Share your bits of IT knowledge by writing an article on Bytes.

Single-Linked List in C

P: 7
SINGLE-LINKED LIST


Let's start with the simplest kind of linked list : the single-linked list which only has one link per node. That node except from the data it contains, which might be anything from a short integer value to a complex struct type, also has a pointer to
the next node in the single-linked list. That pointer will be NULL if the end of the single-linked list is encountered.
The single-linked list travels only one way; from the beginning to the end.
There is no way to go back to a previous node, unlike what can happen in double-linked lists which we will examine later.

As an example, i chose a single-linked list which is sorted increasingly and each value, which is of type int, is unique. That is, each value is greater that the previous and lower than its next.
For example: 3 -> 6 -> 10 -> 100 -> NULL.


To begin with, lets write the file slistdefs.h which will include the struct to be used as well as the prototypes of the functions for the slist. Note that slist is a short for single-linked list.

Expand|Select|Wrap|Line Numbers
  1.  /**
  2.  *
  3.  *
  4.  *    FILE: slistdefs.h
  5.  *
  6.  *
  7.  *    Description:
  8.  *
  9.  *        Function defines the structure to be used for the single-linked list,
  10.  *        as well as the prototypes for the functions to be used for the           
  11.  *              single-linked list.
  12.  *
  13.  *
  14.  */
  15.  
  16.  
  17.  
  18. #ifndef    _slistdefs_h
  19.  
  20.  
  21.  
  22. #define _slistdefs_h
  23.  
  24.  
  25.  
  26.  
  27.  
  28. #include <stdio.h>
  29.  
  30.  
  31.  
  32. #include <stdlib.h>
  33.  
  34.  
  35.  
  36.  
  37.  
  38. /**
  39.  *------------------------------------------------------------
  40.  *
  41.  *    Node for the single-linked list has two members:
  42.  *        
  43.  *        1) a integer value which is unique in the single-linked list.
  44.  *
  45.  *        2) a pointer to the next node in the list which has larger value,
  46.  *        since nodes are inserted increasingly in the single-linked list
  47.  *        and each value is unique.
  48.  *
  49.  *------------------------------------------------------------
  50.  */
  51. struct slist{
  52.  
  53.  
  54.  
  55.     int value;    
  56.  
  57.  
  58.  
  59.     struct slist *next;    
  60.  
  61.  
  62.  
  63. };
  64.  
  65.  
  66.  
  67.  
  68.  
  69. /**
  70.  *
  71.  *
  72.  *    Synopsis:
  73.  *
  74.  *        #include <stdio.h>
  75.  *        #include <stdlib.h>
  76.  *
  77.  *        void insertValue( struct slist **head, int value )
  78.  *
  79.  *
  80.  *    Description:
  81.  *
  82.  *        Function insertValue adds a new struct slist node in the 
  83.  *        single-linked list with the value specified as parameter.
  84.  *        The struct slist node is inserted increasingly according to the 
  85.  *        values of the struct slist nodes.
  86.  *
  87.  *
  88.  *    Parameters:
  89.  *
  90.  *        head: pointer to the head of the single-linked list.
  91.  *
  92.  *        value: value of the new struct slist node to be inserted.
  93.  *
  94.  *
  95.  *    Assertions:
  96.  *
  97.  *        none.
  98.  *
  99.  *
  100.  *    Returns:
  101.  *
  102.  *        Nothing.
  103.  *
  104.  *
  105.  */
  106. void insertValue( struct slist **head, int value );
  107.  
  108.  
  109.  
  110.  
  111.  
  112. /**
  113.  *
  114.  *
  115.  *    Synopsis:
  116.  *
  117.  *        #include <stdio.h>
  118.  *
  119.  *        struct slist **searchValue( struct slist **head, int value )
  120.  *
  121.  *
  122.  *    Description:
  123.  *
  124.  *        Function searchValue, traverses the single-linked list and searches
  125.  *        for a struct slist node with the value given as parameter.
  126.  *
  127.  *
  128.  *    Parameters:
  129.  *
  130.  *        head: pointer to the head of the single-linked list.
  131.  *
  132.  *        value: value to be searched for in the single-linked list.
  133.  *
  134.  *
  135.  *    Assertions:
  136.  *
  137.  *        none.
  138.  *
  139.  *
  140.  *    Returns:
  141.  *
  142.  *        Function searchValue, returns NULL if no struct slist node
  143.  *        is in the single-linked list with that value.
  144.  *
  145.  *        Otherwise, it returns the address of the pointer that points to the 
  146.  *        struct slist node with that value. That is the head of the list if the 
  147.  *        first struct slist node contains that value, or the struct slist next pointer
  148.  *        of the previous struct slist node from the one that has that value.
  149.  *
  150.  *
  151.  */
  152. struct slist **searchValue( struct slist **head, int value );
  153.  
  154.  
  155.  
  156.  
  157.  
  158. /**
  159.  *
  160.  *
  161.  *    Synopsis:
  162.  *
  163.  *        #include <stdio.h>
  164.  *        #include <stdlib.h>
  165.  *
  166.  *        void deleteValue( struct slist **head, int value )
  167.  *
  168.  *
  169.  *    Description:
  170.  *
  171.  *        Function deleteValue searches the single-linked list for 
  172.  *        a struct slist node with the value given as parameter and deletes
  173.  *        it from the single-linked list.
  174.  *
  175.  *
  176.  *    Parameters:
  177.  *
  178.  *        head: pointer to the head of the single-linked list.
  179.  *
  180.  *        value: value of the struct slist node to be deleted.
  181.  *
  182.  *
  183.  *    Assertions:
  184.  *
  185.  *        none.
  186.  *
  187.  *
  188.  *    Returns:
  189.  *
  190.  *        Nothing.
  191.  *
  192.  *
  193.  */
  194. void deleteValue( struct slist **head, int value );
  195.  
  196.  
  197.  
  198.  
  199.  
  200. /**
  201.  *
  202.  *
  203.  *    Synopsis:
  204.  *
  205.  *        #include <stdio.h>
  206.  *
  207.  *        void printValues( struct slist *head )
  208.  *
  209.  *
  210.  *    Description:
  211.  *
  212.  *        Function printValues prints on stdout the values of the
  213.  *        struct slist nodes of the single-linked list.
  214.  *
  215.  *
  216.  *    Parameters:
  217.  *
  218.  *        head: pointer to the first node in the single-linked list, or NULL
  219.  *        if list is empty.
  220.  *        Gets the value of the head pointer.
  221.  *
  222.  *
  223.  *    Assertions:
  224.  *
  225.  *        none.
  226.  *
  227.  *
  228.  *    Returns:
  229.  *
  230.  *        Nothing.
  231.  *
  232.  *
  233.  */
  234. void printValues( struct slist *head );
  235.  
  236.  
  237.  
  238.  
  239.  
  240. /**
  241.  *
  242.  *
  243.  *    Synopsis:
  244.  *
  245.  *        #include <stdio.h>
  246.  *        #include <stdlib.h>
  247.  *
  248.  *        void freeValues( struct slist **head )
  249.  *
  250.  *
  251.  *    Description:
  252.  *
  253.  *        Function freeValues frees all the struct slist nodes
  254.  *        of the single-linked list.
  255.  *
  256.  *
  257.  *    Parameters:
  258.  *
  259.  *        head: pointer to the head of the single-linked list.
  260.  *
  261.  *
  262.  *    Assertions:
  263.  *
  264.  *        none.
  265.  *
  266.  *
  267.  *    Returns:
  268.  *
  269.  *        Nothing.
  270.  *
  271.  *
  272.  */
  273. void freeValues( struct slist **head );
  274.  
  275.  
  276.  
  277.  
  278.  
  279. #endif



Now, lets make the other files for each of the functions:



Expand|Select|Wrap|Line Numbers
  1. /**
  2.  *
  3.  *
  4.  *    FILE:    deleteValue.c
  5.  *
  6.  *
  7.  *    Description:
  8.  *
  9.  *        File contains deleteValue function as declared in slistdefs.h file.      
  10.  *
  11.  *  
  12.  */
  13.  
  14.  
  15.  
  16. #include "slistdefs.h"
  17.  
  18.  
  19.  
  20.  
  21.  
  22. /**
  23.  *------------------------------------------------------------
  24.  *
  25.  *    Insert a struct slist node in the single-linked list.
  26.  *
  27.  *------------------------------------------------------------
  28.  */
  29. void deleteValue( struct slist **head, int value ){
  30.  
  31.  
  32.  
  33.     struct slist **deleteNode = searchValue( head, value );
  34.  
  35.  
  36.         /** node to be deleted exists                                                               */
  37.     if ( deleteNode != NULL ){                        
  38.  
  39.  
  40.                 /** keep node to be deleted to free later                                        */
  41.         struct slist *freeNode = *deleteNode;        
  42.  
  43.  
  44.  
  45.         /**
  46.          *
  47.          *    deleteNode points to the pointer that points to the
  48.          *    node to be deleted.
  49.          *    This pointer must no longer point to that node, but the node
  50.          *    after that, or NULL if no node exits. In either case, the next
  51.          *    pointer of the node to be deleted contains the answer...
  52.          *
  53.          */
  54.         *deleteNode = ( *deleteNode )->next; 
  55.  
  56.  
  57.  
  58.         free( freeNode );
  59.  
  60.  
  61.  
  62.     }
  63.  
  64.  
  65.  
  66. }    //    void deleteValue( struct slist **head, int value )


Expand|Select|Wrap|Line Numbers
  1. /**
  2.  *
  3.  *
  4.  *    FILE:    insertValue.c
  5.  *
  6.  *
  7.  *    Description:
  8.  *
  9.  *        File contains insertValue function as declared in slistdefs.h file.
  10.  *   
  11.  *
  12.  */
  13.  
  14.  
  15.  
  16. #include "slistdefs.h"
  17.  
  18.  
  19.  
  20.  
  21.  
  22. /**
  23.  *------------------------------------------------------------
  24.  *
  25.  *    Insert a struct slist node in the single-linked list.
  26.  *
  27.  *------------------------------------------------------------
  28.  */
  29. void insertValue( struct slist **head, int value ){
  30.  
  31.  
  32.     /** pointer to the new struct slist node                        */
  33.     struct slist *add;                                
  34.  
  35.  
  36.  
  37.     /**
  38.      *
  39.      *    struct slist **p : *p is the pointer that points to the node
  40.      *    that has value larger than the value of the new node to be inserted.
  41.      *    That pointer must be made to point to the new node, and the next                      
  42.          *      pointer of the new node must be made to point to whatever *p points   
  43.          *      at.Note, that *p might be the head of the single-linked list if the list is
  44.          *      empty,or the next pointer of the last node, if the new one has the
  45.          *      largest value.
  46.      *    
  47.      */
  48.     struct slist **p;
  49.  
  50.  
  51.  
  52.     if ( ( add = ( struct slist * )malloc( sizeof( struct slist ) ) ) == NULL ){
  53.  
  54.  
  55.  
  56.         ( void )fprintf( stderr, "\nerror allocating memory%c", '\0' );
  57.  
  58.  
  59.  
  60.         exit( EXIT_FAILURE );
  61.  
  62.  
  63.  
  64.     }
  65.  
  66.  
  67.  
  68.     for ( p = head ; *p != NULL && ( *p )->value <= value ; p = &( ( *p )->next ) ){
  69.  
  70.  
  71.  
  72.         if ( ( *p )->value == value ){
  73.  
  74.  
  75.                         /** do nothing; value already in list                             */
  76.             return ;                                
  77.  
  78.  
  79.  
  80.         }
  81.  
  82.  
  83.  
  84.     }
  85.  
  86.  
  87.  
  88.     add->value = value;
  89.  
  90.  
  91.          /** add points to the node with > value ; NULL if in the end or start          */
  92.     add->next = *p;                                    
  93.  
  94.  
  95.  
  96.          /** head, or next pointer of previous node points to the new node          */
  97.     *p = add;                                        
  98.  
  99.  
  100.  
  101. }    //    void insertValue( struct slist **head, int value )


Expand|Select|Wrap|Line Numbers
  1. /**
  2.  *
  3.  *
  4.  *    FILE:    searchValue.c
  5.  *
  6.  *
  7.  *    Description:
  8.  *
  9.  *        File contains searchValue function as declared in slistdefs.h file.
  10.  *        
  11.  *
  12.  */
  13.  
  14.  
  15.  
  16. #include "slistdefs.h"
  17.  
  18.  
  19.  
  20.  
  21.  
  22. /**
  23.  *------------------------------------------------------------
  24.  *
  25.  *    Insert a struct slist node in the single-linked list.
  26.  *
  27.  *------------------------------------------------------------
  28.  */
  29. struct slist **searchValue( struct slist **head, int value ){
  30.  
  31.  
  32.  
  33.     for ( ; *head != NULL && ( *head )->value <= value ; head = &( ( *head )->next ) ){
  34.  
  35.  
  36.  
  37.         if ( ( *head )->value == value ){
  38.  
  39.  
  40.  
  41.                         /** value found in slist                            */
  42.             return ( head );                        
  43.  
  44.  
  45.  
  46.         }
  47.  
  48.  
  49.  
  50.     }
  51.  
  52.  
  53.  
  54.        /** value not found in slist                                    */
  55.     return ( NULL );                                
  56.  
  57.  
  58.  
  59. }    //    struct slist **searchValue( struct slist **head, int value )



Expand|Select|Wrap|Line Numbers
  1. /**
  2.  *
  3.  *
  4.  *    FILE:    printValues.c
  5.  *
  6.  *
  7.  *    Description:
  8.  *
  9.  *        File contains printValues function as declared in slistdefs.h file.
  10.  *        
  11.  *
  12.  */
  13.  
  14.  
  15.  
  16. #include "slistdefs.h"
  17.  
  18.  
  19.  
  20.  
  21.  
  22. /**
  23.  *------------------------------------------------------------
  24.  *
  25.  *    Print values from the struct slist nodes in the single-linked list.
  26.  *
  27.  *------------------------------------------------------------
  28.  */
  29. void printValues( struct slist *head ){
  30.  
  31.  
  32.  
  33.     for ( ; head != NULL ; head = head->next ){
  34.  
  35.  
  36.  
  37.         printf( "\nValue:\t%d\n", head->value );
  38.  
  39.  
  40.  
  41.     }
  42.  
  43.  
  44.  
  45. }    // void printValues( struct slist *head )



Expand|Select|Wrap|Line Numbers
  1. /**
  2.  *
  3.  *
  4.  *    FILE:    freeValues.c
  5.  *
  6.  *
  7.  *    Description:
  8.  *
  9.  *        File contains freeValues function as declared in slistdefs.h file.
  10.  *   
  11.  *
  12.  */
  13.  
  14.  
  15.  
  16. #include "slistdefs.h"
  17.  
  18.  
  19.  
  20.  
  21.  
  22. /**
  23.  *------------------------------------------------------------
  24.  *
  25.  *    Free all the struct slist nodes in the single-linked list.
  26.  *
  27.  *------------------------------------------------------------
  28.  */
  29. void freeValues( struct slist **head ){
  30.  
  31.  
  32.  
  33.     /**
  34.      *
  35.      *    previousNode: points to the node to be freed.
  36.      *
  37.      *    nextNode: points to the next node from the one to be freed. Keep the
  38.          *      single-linked list
  39.      *    in this way.
  40.      *
  41.      */
  42.     struct slist *previousNode, *nextNode;
  43.  
  44.  
  45.  
  46.     /**
  47.      *
  48.      *    previousNode points to the node to be freed.
  49.      *    Before it gets freed, however, nextNode must be made to point to the
  50.          *      next node from the one
  51.      *    that previousNode points at. Note that in each step, previousNode 
  52.          *       must be made to point to nextNode
  53.      *    so as nextNode will always point to the struct slist node that is the 
  54.          *       next from the the
  55.      *    one that previousNode points at.
  56.      *
  57.      */
  58.     for ( previousNode = nextNode= *head ; previousNode != NULL ; previousNode = nextNode ){
  59.  
  60.  
  61.  
  62.         nextNode = previousNode->next;
  63.  
  64.  
  65.  
  66.         free( previousNode );
  67.  
  68.  
  69.  
  70.     }
  71.  
  72.  
  73.  
  74.     /**
  75.      *
  76.      *    Safely, make the head of the single-linked list NULL.
  77.      *    If this is not made, any attempt to insert, delete, search or print
  78.      *    will fail.
  79.      *
  80.      */
  81.     *head = NULL;
  82.  
  83.  
  84.  
  85. }    //    void freeValues( struct slist **head )



The code is ready to copy and paste so as you can immediately run test and modify the functions so as to cover your needs.
You can add messages when for example a value does not exist when deleting; you might want to inform user that no deletion was made. You can add prints in many other places too. Add assertions to check that each value is unique.

You can add more functions to practise a bit on single-linked list, or change entirely the concept of the code i present.
You can write a function int getLength( struct slist *head ) that returns the number of nodes in the list.
Write functions to return nodes with the lower and greater value, and for more challenging ones function to copy a list to another or a function to reverse the list. Try to write recursive versions of some of the functions as well.
Except to see more data types and code for them, like double-linked list and binary search tree.
Jun 15 '08 #1
Share this Article
Share on Google+