Advertisement
drankinatty

Singly Linked List (node only, no wrapper)

Sep 24th, 2019 (edited)
578
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 4.20 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. typedef struct node_t {     /* list node */
  5.     int data;
  6.     struct node_t *next;
  7. } node_t;
  8.  
  9. /** add node at end of list, update tail to end */
  10. node_t *add (node_t **head, int v)
  11. {
  12.     node_t **ppn = head,                    /* pointer to pointer to head */
  13.             *pn = *head,                    /* pointer to head */
  14.             *node = malloc (sizeof *node);  /* allocate new node */
  15.  
  16.     if (!node) {                            /* validate allocation */
  17.         perror ("malloc-node");
  18.         return NULL;
  19.     }
  20.     node->data = v;                         /* initialize members values */
  21.     node->next = NULL;
  22.  
  23.     while (pn) {
  24.         ppn = &pn->next;
  25.         pn = pn->next;
  26.     }
  27.  
  28.     return *ppn = node;    /* add & return new node */
  29. }
  30.  
  31. /** insert nodes in linked-list in ascending order of data. */
  32. node_t *addinorder (node_t **head, int v)
  33. {
  34.     node_t **ppn = head,                    /* pointer to pointer to head */
  35.             *pn = *head,                    /* pointer to head */
  36.             *node = malloc (sizeof *node);  /* allocate new node */
  37.  
  38.     if (!node) {                            /* validate allocation */
  39.         perror ("malloc-node");
  40.         return NULL;
  41.     }
  42.    
  43.     node->data = v;                         /* initialize members values */
  44.     node->next = NULL;
  45.  
  46.     while (pn && pn->data <= node->data) {  /* loop until sort location */
  47.         ppn = &pn->next;                    /* advance pointer-to-pointer */
  48.         pn = pn->next;                      /* advance pointer */
  49.     }
  50.    
  51.     node->next = pn;            /* set node->next to pointer to current */
  52.     return *ppn = node;         /* update pointer at current addr to node */
  53. }
  54.  
  55. /** insertion sort of linked list.
  56.  *  re-orders list in sorted order.
  57.  */
  58. void insertionsort (node_t **head)
  59. {
  60.     if (!*head || !(*head)->next)   /* if list empty or 1-node, return */
  61.         return;
  62.  
  63.     node_t *sorted = *head,         /* initialize sorted list to 1st node */
  64.             *pn = (*head)->next;    /* advance original list node to next */
  65.  
  66.     sorted->next = NULL;            /* initialize sorted->next to NULL */
  67.  
  68.     while (pn) {                    /* iterate over existing from 2nd node */
  69.         node_t **pps = &sorted,     /* ptr-to-ptr to sorted list */
  70.                 *ps = *pps,         /* ptr to sorted list */
  71.                 *next = pn->next;   /* save list next as separate pointer */
  72.  
  73.         while (ps && ps->data <= pn->data) {  /* loop while sorted <= node */
  74.             pps = &ps->next;        /* get address of next node */
  75.             ps = ps->next;          /* get next node pointer */
  76.         }
  77.  
  78.         *pps = pn;          /* insert existing in sort order as current */
  79.         pn->next = ps;      /* set next as sorted next */
  80.         pn = next;          /* reinitialize existing pointer to next */
  81.     }
  82.  
  83.     *head = sorted;         /* update head to sorted head */
  84. }
  85.  
  86. /** print all nodes in list */
  87. void prn (node_t *l)
  88. {
  89.     if (!l) {
  90.         puts ("list-empty");
  91.         return;
  92.     }
  93.     for (node_t *n = l; n; n = n->next)
  94.         printf (" %d", n->data);
  95.     putchar ('\n');
  96. }
  97.  
  98. /** delete node with value v from list (for loop) */
  99. void del_node (node_t **l, int v)
  100. {
  101.     node_t **ppn = l;           /* pointer to pointer */
  102.     node_t *pn = *l;            /* pointer to node */
  103.  
  104.     for (; pn; ppn = &pn->next, pn = pn->next) {
  105.         if (pn->data == v) {
  106.             *ppn = pn->next;    /* set node at address to next */
  107.             free (pn);
  108.             break;
  109.         }
  110.     }
  111. }
  112.  
  113. /** delete all nodes in list */
  114. void del_list (node_t *l)
  115. {
  116.     node_t *n = l;
  117.     while (n) {
  118.         node_t *victim = n;
  119.         n = n->next;
  120.         free (victim);
  121.     }
  122. }
  123.  
  124. int main (void) {
  125.  
  126.     int a[] = {12, 11, 10, 7, 4, 14, 8, 16, 20, 19,
  127.                 2, 9, 1, 13, 17, 6, 15, 5, 3, 18};
  128.     size_t asz = sizeof a / sizeof *a;
  129.     node_t *list = NULL;
  130.  
  131.     for (size_t i = 0; i < asz; i++)
  132. #ifdef ADDORDER
  133.         addinorder (&list, a[i]);
  134. #else
  135.         add (&list, a[i]);
  136. #endif
  137.  
  138.     prn (list);
  139. #ifndef ADDORDER
  140.     insertionsort (&list);
  141.     prn (list);
  142. #endif
  143.     del_list (list);
  144. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement