Realization of bidirectional linked list in c

1. I learned how to use C language to realize the knowledge of two-way linked list in the training company before, and now I have time to write it again. First define the header file list.h.

  1 #ifndef __LIST_H__
  2 #define __LIST_H__
  3
  4 #include <stdio.h>
  5 #include <stdlib.h>
  6 #include <string.h>
  7
  8 //Two way loop list
  9 struct list
 10 {
 11         struct list *prev, *next;
 12         void *dat;
 13         int size;
 14 };
 15
 16 //Compare function types
 17 typedef int (*cmp_t)(void *dat1, void *dat2);
 18
 19 //Print function type
 20 typedef void (*print_t)(void *dat);
 21
 22 struct list *list_create(int size);
 23 int list_addtail(struct list *head, void *dat);
 24 int list_addhead(struct list *head, void *dat);
 25 struct list *list_find(struct list *head, void *dat, cmp_t cmp);
 26 void list_delnode(struct list *head, void *dat, cmp_t cmp);
 27 void list_print(struct list *head, print_t print);
 28 void list_destroy(struct list **entry);
 29
 30 #endif /* __LIST_H__ */

In the header file, it mainly defines a list of structures, which defines the next pointer after the previous prev, as well as the variable dat and size size to save data. Everything else is a function declaration.

2. Let's take a look at the function implementation of list.c.

1 #include "list.h"
  2
  3 //Assign a header node
  4 struct list *list_create(int size)
  5 {
  6         struct list *head = NULL;
  7         head = calloc(1, sizeof(*head));
  8         if (NULL == head)
  9         {
 10                 perror("calloc head");
 11                 return NULL;
 12         }
 13         head->prev = head->next = head;
 14         head->size = size;
 15         return head;
 16 }
 17
 18 //Add a node to the end of the list
 19 int list_addtail(struct list *head, void *dat)
 20 {
 21         struct list *tmp, *new;
 22
 23         //Assign new nodes
 24         new = calloc(1, sizeof(*new));
 25         if(new == NULL)
 26         {
 27                 perror("calloc new");
 28                 return -1;
 29         }
 30
 31         //Allocate data space for nodes
 32         new->dat = calloc(1, head->size);
 33         if(new->dat == NULL)
 34         {
 35                 perror("calloc dat");
 36                 free(new);
 37                 return -1;
 38         }
 39         memcpy(new->dat, dat, head->size);
 40
 41         //Add a new node to the list
 42         new->next = head;
 43         new->prev = head->prev;
 44         head->prev->next = new;
 45         head->prev = new;
 46         return 0;
 47 }
 48
 49
 50 //Add a node to the chain header
 51 int list_addhead(struct list *head, void *dat)
 52 {
 53         struct list *tmp, *new;
 54
 55         //Assign new nodes
 56         new = calloc(1, sizeof(*new));
 57         if(new == NULL)
 58         {
 59                 perror("calloc new");
 60                 return -1;
 61         }
 62
 63         //Allocate data space for nodes
 64         new->dat = calloc(1, head->size);
 65         if(new->dat == NULL)
 66         {
 67                 perror("calloc dat");
 68                 free(new);
 69                 return -1;
 70         }
 71         memcpy(new->dat, dat, head->size);
 72
 73         //Add a new node to the list
 74         new->prev = head;
 75         new->next = head->next;
 76         head->next->prev = new;
 77         head->next = new;
 78         return 0;
 79 }
 80
 81 //Find a node in the linked list
 82 struct list *list_find(struct list *head, void *dat, cmp_t cmp)
 83 {
 84         struct list *tmp;
 85         for (tmp = head->next; tmp != head; tmp = tmp->next)
 86         {
 87                 if (!cmp(tmp->dat, dat))
 88                 {
 89                         return tmp;
 90                 }
 91         }
 92         return NULL;
 93 }
 94
 95 //Delete a specified node
 96 void list_delnode(struct list *head, void *dat, cmp_t cmp)
 97 {
 98         struct list *tmp;
 99         tmp = list_find(head, dat, cmp);
100         if (tmp != NULL)
101         {
102                 tmp->prev->next = tmp->next;
103                 tmp->next->prev = tmp->prev;
104                 free(tmp->dat);
105                 free(tmp);
106         }
107 }
108
109 //Print contents of linked list
110 void list_print(struct list *head, print_t print)
111 {
112         struct list *tmp;
113         for (tmp = head->next; tmp != head; tmp = tmp->next)
114         {
115                 print(tmp->dat);
116         }
117         printf("\n");
118 }
119
120 //Destroy the list, release all the space occupied by the list
121 void list_destroy(struct list **entry)
122 {
123         struct list *head, *tmp, *next;
124
125         if (entry != NULL)
126         {
127                 head = *entry;
128                 for (tmp = head->next; tmp != head; tmp = next)
129                 {
130                         next = tmp->next;
131                         free(tmp->dat);
132                         free(tmp);
133                 }
134                 free(head);
135                 *entry = NULL;
136         }
137
138 }

First, define the header node * list_create(int size). In this function, memory space will be allocated and the front and back pointers will point to the header.

3. Test the bidirectional linked list just written by testing test.c.

1 #include <stdio.h>
  2 #include "list.h"
  3
  4 //This program is used to test the bidirectional circular list
  5 int ar[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
  6 void print_int(void *dat);
  7 int cmp_int(void *dat1, void *dat2);
  8
  9 int main(void)
 10 {
 11         int i = 0;
 12         struct list *tmp;
 13         struct list *head = list_create(sizeof(int));
 14         if (NULL == head)
 15         {
 16                 return -1;
 17         }
 18
 19         for (i; i < 10; i++)
 20         {
 21                 list_addtail(head, &ar[i]);
 22         }
 23
 24         list_print(head, print_int);
 25         tmp = list_find(head, &ar[3], cmp_int);
 26         if (tmp != NULL)
 27         {
 28                 print_int(tmp->dat);
 29                 printf("\n");
 30         }
 31
 32         list_delnode(head, &ar[4], cmp_int);
 33         list_print(head, print_int);
 34
 35         ar[4] = 100;
 36         list_delnode(head, &ar[4], cmp_int);
 37         list_print(head, print_int);
 38
 39         list_destroy(&head);
 40         return 0;
 41
 42
 43 }
 44
 45 void print_int(void *dat)
 46 {
 47         printf("%d ", *(int *)dat);
 48 }
 49
 50 int cmp_int(void *dat1, void *dat2)
 51 {
 52         return *(int *)dat1 - *(int *)dat2;
 53 }

Results of running the program:

 

 

 

 

Tags: C

Posted on Sun, 05 Jan 2020 23:08:44 -0800 by eazyGen