Advertisement
drankinatty

C singly-linked circular linked-list example

May 17th, 2015
669
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 9.22 KB | None | 0 0
  1. /* Simple example of a singly-linked circular linked list.
  2.  * This example will read any text file and store a dynamically
  3.  * allocated list of nodes containing the each line and line number.
  4.  * compile with:
  5.  *
  6.  *    gcc -Wall -Wextra -o yourprogname sourcefile.c
  7.  *
  8.  * use:
  9.  *
  10.  *    ./yourprogname somefile.txt [node2delete (default: 2, zero based)]
  11.  *
  12.  * The example reads somefile.txt into the list, prints the list to stdout,
  13.  * deletes the zero based node 'node2delete' (default 2 - (e.g. the 3rd line)),
  14.  * and prints the new list to stdout. The example then frees all memory
  15.  * allocated to the list and exits.
  16.  *
  17.  * For informational purposes, the optional DEBUG definition can be
  18.  * added to the compile string which, in addition to the information above,
  19.  * will print the list pointer addresses for each node. (e.g. node, node->next).
  20.  * Simply compile the code with:
  21.  *
  22.  *    gcc -Wall -Wextra -o yourprogname sourcefile.c -DDEBUG
  23.  */
  24. #include <stdio.h>
  25. #include <stdlib.h>
  26. #include <string.h>
  27.  
  28. /* list struct to hold line & line number */
  29. typedef struct lline {
  30.     size_t num;
  31.     char *line;
  32.     struct lline *next;
  33. } lline;
  34.  
  35. /* allocate & populate node */
  36. lline *create_node (char *s, size_t n);
  37.  
  38. /* insert node into list */
  39. lline *insert_node (lline **list, char *s, size_t n);
  40.  
  41. /* read data from file fname and add to list */
  42. lline *read_file2list (lline **list, char *fname);
  43.  
  44. /* return the number of nodes in list */
  45. size_t getszlist (lline *list);
  46.  
  47. /* print all nodes in list */
  48. void print_list (lline *list);
  49.  
  50. /* print all node pointers in list */
  51. void print_list_p (lline *list);
  52.  
  53. /* free memory allocated to lline list node */
  54. void free_node (lline *node);
  55.  
  56. /* (zero-based) delete of nth node */
  57. void delete_node (lline **list, size_t nth);
  58.  
  59. /* delete lline list & free allocated memory */
  60. void delete_list (lline *list);
  61.  
  62. int main (int argc, char **argv)
  63. {
  64.     if (argc < 2 ) {                        /* validate input / usage  */
  65.         fprintf (stderr, "error: insufficient input, usage: %s filename [node2delete]\n", argv[0]);
  66.         return 1;
  67.     }
  68.  
  69.     char *fname = argv[1];
  70.     lline *book1 = NULL;                    /* create new list pointer */
  71.  
  72.  
  73.     if (!read_file2list (&book1, fname)) {  /* read file into list      */
  74.         fprintf (stderr, "error: read of file '%s' returned no list.\n", fname);
  75.         return 1;
  76.     }
  77.  
  78.     printf ("\n Read '%zd' records from file: %s\n\n", getszlist (book1), fname);
  79.  
  80.     print_list (book1);                     /* print list (all nodes)   */
  81. #ifdef DEBUG
  82.     printf ("\n list node pointer addresses:\n\n");
  83.     print_list_p (book1);
  84. #endif
  85.     int nth = (argc > 2) ? atoi (argv[2]) : 2;
  86.     printf ("\n Deleting node: %d\n\n", nth);
  87.     delete_node (&book1, nth);
  88.  
  89.     print_list (book1);                     /* print list (confirm del) */
  90. #ifdef DEBUG
  91.     printf ("\n list node pointer addresses:\n\n");
  92.     print_list_p (book1);
  93. #endif
  94.  
  95.     delete_list (book1);                    /* free list memory in use  */
  96.  
  97.     return 0;
  98. }
  99.  
  100. /* allocate & populate node */
  101. lline *create_node (char *s, size_t n)
  102. {
  103.     lline *node = NULL;
  104.  
  105.     node = malloc (sizeof *node);
  106.     if (!node) return NULL;
  107.  
  108.     node-> line = s ? strdup (s) : strdup (""); /* allow empty line */
  109.     node-> num = n;
  110.  
  111.     return node;
  112. }
  113.  
  114. /* insert node into list */
  115. lline *insert_node (lline **list, char *s, size_t n)
  116. {
  117.     lline *node = NULL;
  118.     if (!(node = create_node (s, n))) return NULL;
  119.  
  120.  
  121.     if (!*list) {                       /* if empty, create first node  */
  122.     node-> next = node;
  123.         *list = node;                   /* insert as new first node     */
  124.     } else {
  125.         if (*list == (*list)-> next) {  /* list only contains 1 node    */
  126.             (*list)-> next = node;      /* insert as next node          */
  127.         }
  128.         else
  129.         {
  130.             lline *iter = *list;        /* second copy to iterate list  */
  131.             for (; iter->next != *list; iter = iter->next) ; /* to end  */
  132.             iter-> next = node;         /* insert at end of list        */
  133.         }
  134.         node-> next = *list;            /* circular - next is first     */
  135.     }
  136.  
  137.     return *list;                       /* return list */
  138. }
  139.  
  140. /* read list from file fname and add to list */
  141. lline *read_file2list (lline **list, char *fname)
  142. {
  143.     FILE *fp = fopen (fname, "r");
  144.     if (!fp) {
  145.         fprintf (stderr, "%s() error: file open failed for '%s'\n", __func__, fname);
  146.         return NULL;
  147.     }
  148.  
  149.     /* allocate and initialize all variables */
  150.     char *ln = NULL;            /* NULL forces getline to allocate  */
  151.     size_t n = 0;               /* max chars to read (0 - no limit) */
  152.     size_t idx = 0;             /* line number index                */
  153.     ssize_t nchr = 0;           /* number of chars actually read    */
  154.  
  155.     while ((nchr = getline (&ln, &n, fp)) != -1)    /* read file    */
  156.     {
  157.         while (nchr > 0 && (ln[nchr-1] == '\n' || ln[nchr-1] == '\r'))
  158.             ln[--nchr] = 0;     /* strip newline or carriage rtn    */
  159.  
  160.         insert_node (list, ln, idx++);      /* add line to list     */
  161.     }
  162.  
  163.     if (fp) fclose (fp);                    /* close file/free line */
  164.     if (ln) free (ln);
  165.  
  166.     return *list;
  167. }
  168.  
  169. /* return the number of nodes in list */
  170. size_t getszlist (lline *list) {
  171.  
  172.     const lline *iter = list;  /* pointer to iterate list  */
  173.     register int cnt = 0;
  174.  
  175.     if (iter ==  NULL) {
  176.     fprintf (stdout,"%s(), The list is empty\n",__func__);
  177.     return 0;
  178.     }
  179.  
  180.     for (; iter; iter = (iter->next != list ? iter->next : NULL)) {
  181.         cnt++;
  182.     }
  183.     return cnt;
  184. }
  185.  
  186. /* print all nodes in list */
  187. void print_list (lline *list) {
  188.  
  189.     const lline *iter = list;  /* pointer to iterate list  */
  190.  
  191.     if (iter ==  NULL) {
  192.     fprintf (stderr,"%s() warning: empty list.\n",__func__);
  193.     return;
  194.     }
  195.  
  196.     for (; iter; iter = (iter->next != list ? iter->next : NULL))
  197.         printf (" %5zu : %s\n", iter-> num, iter-> line);
  198. }
  199.  
  200. /* print all nodes pointers in list */
  201. void print_list_p (lline *list) {
  202.  
  203.     const lline *iter = list;  /* pointer to iterate list  */
  204.     size_t i = 0;
  205.  
  206.     if (iter ==  NULL) {
  207.     fprintf (stderr,"%s() warning: empty list.\n",__func__);
  208.     return;
  209.     }
  210.  
  211.     for (; iter; iter = (iter->next != list ? iter->next : NULL)) {
  212.         printf (" node (%3zu) : %p    node-> next (%3zu) : %p\n",
  213.                 i, iter, (iter->next == list) ? 0 : i+1, iter-> next);
  214.         i++;
  215.     }
  216. }
  217.  
  218. /* free all dynamically allocated members, then node */
  219. void free_node (lline *node)
  220. {
  221.     if (!node) return;
  222.  
  223.     if (node-> line) free (node-> line);
  224.  
  225.     free (node);
  226. }
  227.  
  228. /* (zero-based) delete of nth node */
  229. void delete_node (lline **list, size_t nth)
  230. {
  231.     /* test that list exists */
  232.     if (!*list) {
  233.     fprintf (stderr,"%s() warning: empty list.\n",__func__);
  234.     return;
  235.     }
  236.  
  237.     /* get list size */
  238.     size_t szlist = getszlist (*list);
  239.  
  240.     /* validate node to delete */
  241.     if (nth >= szlist) {
  242.     fprintf (stderr, "%s(), error: invalid node (%zu). allowed: (0 <= nth <= %zu)\n",
  243.                 __func__, nth, szlist-1);
  244.     return;
  245.     }
  246.  
  247.     /* create node pointers */
  248.     lline *victim = *list;
  249.     lline *prior = victim;
  250.  
  251.     /* if nth 0, prior is last, otherwise node before victim */
  252.     if (nth == 0) {
  253.         for (; prior->next != *list; prior = prior->next) ;
  254.     } else {
  255.         while (nth-- && victim-> next != *list) {
  256.             prior = victim;
  257.             victim = victim-> next;
  258.         }
  259.     }
  260.  
  261.     /* non-self-reference node, rewire next */
  262.     if (victim != victim->next) {
  263.     prior-> next = victim-> next;
  264.  
  265.     /* if deleting node 0, change list pointer address */
  266.     if (victim == *list)
  267.         *list = victim->next;
  268.     } else {  /* if self-referenced, last node, delete list */
  269.     *list = NULL;
  270.     }
  271.  
  272.     free_node (victim);  /* free memory associated with node */
  273. }
  274.  
  275. /* delete lline list */
  276. void delete_list (lline *list)
  277. {
  278.     if (!list) return;
  279.  
  280.     /*  Since list is being deleted, you can delete nodes beginning
  281.      *  with any node (e.g. 'list' or 'list-> next'). It is probably
  282.      *  better form to leave the beginning address as the last node
  283.      *  to delete. Both methods shown below with the code to delete
  284.      *  beginning with the first node commented with '//'.
  285.      */
  286.     // lline *iter = list;  /* pointer to iterate list  */
  287.     lline *iter = list-> next; /* pointer to iterate list  */
  288.     lline *np = NULL;          /* save next addr, to avoid invalid read */
  289.  
  290.     // while (iter->next != list)
  291.     while (iter != list)
  292.     {
  293.         np = iter-> next;
  294.         if (iter) free_node (iter);
  295.             iter = np;
  296.     }
  297.  
  298.     if (iter) free_node (iter);
  299.  
  300.     /* Additional notes on iteration techniques for delete
  301.  
  302.        for loop is fine for iteration, but when deleting list it
  303.        results in invalid read on iter = iter->next after free (iter)
  304.        unless a next pointer is used. The following will not work:
  305.  
  306.     for (; iter; iter = (iter->next != list ? iter->next : NULL))
  307.         if (iter) free_node (iter);
  308.  
  309.        But this will:
  310.  
  311.     for (; iter; iter = (iter != list ? np : NULL))
  312.     {
  313.         np = iter-> next;
  314.         if (iter) free_node (iter);
  315.     }
  316.     */
  317. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement