Advertisement
drankinatty

"Doubly Linked-List Using Address of List"

Apr 8th, 2021 (edited)
331
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 8.56 KB | None | 0 0
  1. /*
  2.  *  compile with -DPASSPTR2PTR to use add() with address of list.
  3.  *  for: https://stackoverflow.com/a/66997713/3422102
  4.  *
  5.  *  example inut file:
  6. John 12345
  7. Sam 54321
  8. Daivd 1000
  9. Mike 5391
  10. Lion 43222
  11. Phil 8332
  12. Bill 2853
  13.  *
  14.  *  defines:
  15.  *    PASSPTR2PTR - do add by passing address of list
  16.  *    ADDRDELETE  - do delete by passing address of list
  17.  *
  18.  */
  19.  
  20. #include <stdio.h>
  21. #include <string.h>
  22. #include <stdlib.h>
  23.  
  24. typedef struct person{
  25.   char* firstName;
  26.   char* age;
  27.   struct person* previous;
  28.   struct person* next;
  29. }Person;
  30.  
  31. void print(Person*);
  32.  
  33. // void reverseList(Person*);
  34.  
  35. // Person* add (Person*, char*, char*);
  36.  
  37. void print (Person* list) {
  38.   while(list != NULL) {
  39.     printf("%s %s\n",list->firstName,list->age);
  40.     list = list->next;
  41.   }
  42. }
  43.  
  44. void prnptrs (Person *list) {
  45.     while (list) {
  46.         printf ("%p  %p  %p\n", (void*)list->previous, (void*)list, (void*)list->next);
  47.         list = list->next;
  48.     }
  49. }
  50. #ifndef PASSPTR2PTR
  51. void reverseList (Person *list) {
  52.  
  53.   if (!list) {                  /* validate list not empty */
  54.     puts ("(list empty)");
  55.     return;
  56.   }
  57.  
  58.   while (list->next != NULL)    /* iterte to last node */
  59.     list = list->next;
  60.  
  61.   while (list) {    /* print in reverse using ->previous pointers */
  62.     printf ("%s %s\n", list->firstName, list->age);
  63.     list = list->previous;
  64.   }
  65. }
  66. #else
  67. void reverseList (Person **list) {
  68.  
  69.   Person *current = *list;
  70.   Person *last = current;
  71.  
  72.   if (!current || !current->next)
  73.     return;
  74.  
  75.   do {
  76.     Person *temp = current->previous;
  77.     current->previous = current->next;
  78.     current->next = temp;
  79.     last = current;
  80.   } while ((current = current->previous));
  81.   *list = last;
  82. }
  83. #endif
  84.  
  85. Person *createnode (const char *firstName, const char *age)
  86. {
  87.   size_t len;
  88.   Person *node = malloc (sizeof *node);   /* allocate node, use dereference ptr for size */
  89.  
  90.   if (!node) {                            /* validate EVERY allocation */
  91.     perror ("malloc-node");
  92.     return NULL;
  93.   }
  94.   node->next = node->previous = NULL;     /* initialize next and previous NULL */
  95.  
  96.   len = strlen (firstName);                         /* get length of firstName */
  97.   if (!(node->firstName = malloc (len + 1))) {      /* allocate/validate */
  98.     perror ("malloc-node->firstName");
  99.     free (node);                                    /* free node before return */
  100.     return NULL;
  101.   }
  102.   memcpy (node->firstName, firstName, len + 1);     /* copy firstName to node */
  103.  
  104.   len = strlen (age);                               /* get length of age */
  105.   if (!(node->age = malloc (len + 1))) {            /* allocate/validate */
  106.     perror ("malloc-node->age");
  107.     free (node->firstName);                         /* free node->firstName, and */
  108.     free (node);                                    /* free node before return */
  109.     return NULL;
  110.   }
  111.   memcpy (node->age, age, len + 1);                 /* copy age to node */
  112.  
  113.   return node;
  114. }
  115. #ifdef PASSPTR2PTR
  116. /* add node to list using address of list and pointer to list
  117.  * returns pointer to new node on success, NULL otherwise.
  118.  */
  119. Person *add (Person **list, const char *firstName, const char *age)
  120. {
  121.   Person **ppn = list,                            /* address of list */
  122.           *pn = *list,                            /* pointer to list */
  123.           *node = createnode (firstName, age);    /* initialize & validate new node */
  124.  
  125.   if (!node)                /* node creation failed, return list */
  126.     return NULL;
  127.  
  128.   while (pn) {  /* loop over each node */
  129.     if (strcmp (firstName, pn->firstName) <= 0) { /* compare sorts before pn->firstName */
  130.       node->previous = (*ppn)->previous;          /* if so, insert new before pn */
  131.       node->next = pn;
  132.       pn->previous = node;
  133.       *ppn = node;          /* update node at address of current node to new node */
  134.       return node;
  135.     }
  136.     if (!pn->next) {        /* if pn is last node, insert at end */
  137.       pn->next = node;
  138.       node->previous = pn;
  139.       break;
  140.     }
  141.     ppn = &pn->next;        /* advamce address to address of next node */
  142.     pn = pn->next;          /* advance pointer to next */
  143.   }
  144.  
  145.   return pn ? node : (*list = node);  /* if not 1st node, return node, else *list=node */
  146. }
  147.  
  148.  
  149. #else
  150. Person *add (Person *list, char *firstName, char *age)
  151. {
  152.   /* allocate node, use dereference ptr for size */
  153.   Person *node = createnode (firstName, age),
  154.          *iter = list,
  155.          *prev = NULL;
  156.  
  157.   if (!node)                              /* validate EVERY allocation */
  158.     return list;
  159.  
  160.   if (!list)                              /* if list empty */
  161.     return node;                          /* return node */
  162.  
  163.   /* handle new 1st node */
  164.   if (strcmp (firstName, iter->firstName) <= 0) {
  165.     list->previous = node;
  166.     node->next = list;
  167.     return node;
  168.   }
  169.  
  170.   /* iterate until firstName sorts before iter->firstName */
  171.   while (iter && strcmp (iter->firstName, firstName) <= 0) {
  172.     prev = iter;
  173.     iter = iter->next;
  174.   }
  175.  
  176.   if (!iter) {                            /* if new end node */
  177.     prev->next = node;
  178.     node->previous = prev;
  179.   }
  180.   else {                                  /* insert between nodes */
  181.     node->previous = prev;
  182.     node->next = iter;
  183.     iter->previous = node;
  184.     prev->next = node;
  185.   }
  186.  
  187.   /* if new first node, return iter, otherwise return list */
  188.   return strcmp (list->firstName, firstName) >= 0 ? node : list;
  189. }
  190.  
  191. #endif
  192.  
  193. #ifdef ADDRDELETE
  194. int delete (Person **list, const char *name)
  195. {
  196.   if (!*list) {             /* list-empty */
  197.     puts ("List Empty");
  198.     return 0;               /* return 0 - no replacement */
  199.   }
  200.  
  201.   Person **ppn = list,      /* address of node (pointer-to-pointer-to-node) */
  202.           *pn  = *list;     /* pointer to node */
  203.  
  204.   for (; pn; ppn = &pn->next, pn = pn->next) {    /* loop over all nodes */
  205.     if (strcmp (pn->firstName, name) == 0) {      /* if node with name found */
  206.       *ppn = pn->next;                    /* replace node at current address with next */
  207.       if (pn->next)                       /* if not last node (*ppn now NULL) */
  208.         (*ppn)->previous = pn->previous;  /* update node at address w/exiting previous */
  209.      
  210.       free (pn->firstName); /* free all memory for existing node */
  211.       free (pn->age);
  212.       free (pn);
  213.      
  214.       return 1;             /* return 1 - replacement made */
  215.     }
  216.   }
  217.  
  218.   fprintf (stderr, "warning: name not found '%s'.\n", name);
  219.  
  220.   return 0;
  221. }
  222. #else
  223. /** delete node with firstName from list */
  224. Person *delete (Person *list, char *name)
  225. {
  226.   if (list == NULL) {
  227.     puts("List Empty");
  228.     return list;
  229.   }
  230.  
  231.   Person *curr = list; // current node
  232.   Person *pre = NULL; // node previous to current
  233.  
  234.   // loop over the list and locate node with name
  235.   while (curr && strcmp(curr->firstName, name) != 0) {
  236.     pre = curr;
  237.     curr = curr->next;
  238.   }
  239.  
  240.   if (curr == NULL) { /* if name not found, warn & return */
  241.     fprintf (stderr, "warning: name not found '%s'.\n", name);
  242.     return list;
  243.   }
  244.  
  245.   if (pre == NULL) {                /* remove first node */
  246.     list = list->next;
  247.     list->previous = NULL;
  248.   }
  249.   else {                            /* remove later node */
  250.     pre->next = curr->next;
  251.     if (curr->next)                 /* protect when removing last */
  252.       curr->next->previous = pre;
  253.   }
  254.  
  255.   free (curr->firstName);
  256.   free (curr->age);
  257.   free (curr);
  258.  
  259.   return list;
  260. }
  261. #endif
  262.  
  263. /** delete all nodes in list */
  264. void del_list (Person *list)
  265. {
  266.   while (list) {
  267.     Person *victim = list;
  268.     list = list->next;
  269.     free (victim->firstName);
  270.     free (victim->age);
  271.     free (victim);
  272.   }
  273. }
  274.  
  275. int main (int argc, char **argv) {
  276.   FILE *in = argc > 1 ? fopen(argv[1], "r") : stdin;
  277.   char name[20];
  278.   char num[20];
  279.   Person *list=NULL;
  280.  
  281.   while (fscanf(in, "%s %s",name, num) == 2)
  282. #ifndef PASSPTR2PTR
  283.     list = add(list,name, num);
  284. #else
  285.     add (&list, name, num);
  286. #endif
  287.   fclose (in);
  288.  
  289.   printf ("Original List\n***\n");
  290.   print (list);
  291.   puts ("\nPointers\n***");
  292.   prnptrs (list);
  293.  
  294.   printf ("\nPrinting Reversed List\n***\n");
  295. #ifndef PASSPTR2PTR
  296.   reverseList(list);
  297. #else
  298.   reverseList(&list);
  299.   print (list);
  300. #endif
  301.  
  302.   puts ("\nRemoving Bill, Phil, Sam, bananas\n***");
  303. #ifdef ADDRDELETE
  304.   delete (&list, "Bill");
  305.   delete (&list, "Phil");
  306.   delete (&list, "Sam");
  307.   delete (&list, "bananas");
  308. #else
  309.   list = delete (list, "Bill");
  310.   list = delete (list, "Phil");
  311.   list = delete (list, "Sam");
  312.   list = delete (list, "bananas");
  313. #endif
  314.  
  315.   print (list);
  316.  
  317.   del_list (list);
  318.  
  319.   return 0;
  320. }
  321.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement