使用c语言实现双向链表_c语言多线程队列双向链表锁

使用c语言实现双向链表

最近在学习C语言，在学习中，对很多知识又有了新的认识。

我是从java开始学习编程的，现在学了一遍C以后，更坚定了我对自身学习路线的认可。 C是你必须要学的一门编程语言，但绝不是第一门。

坚定我这个想法的原因有这么几个：

1. c语言过于底层，如果上手就以C为主语言开始学习，学习、理解成本相对大，这样效率就不会那么高。
2. C语言的统治领域与别的编程语言有非常大的区别。比如java擅长web，c++擅长客户端，而C适合系统。系统开发的工作岗位门槛较高，对语言底层理解和开发能力要求较高。而我自觉难达。
3. c语言过于底层，面向过程，手动内存，语法简单。开发过程像是一点一点的去扣去实现。真正适应了C 再去转向别的语言，会觉得处处受限。语言间的歧视链就是这样产生的。

我很庆幸我在已经学习了两三门高级语言后，再回过头学习C。或许我以后不会从事直接C开发的工作，但C对我编程的思想一定定有很大影响。

之前也听很多人说，写C就是从0做起，除了简单的函数库，什么都没了。数据结构需要全部自己实现。在学习java时，我曾阅读过大多数 数据结构 的源码，并付诸实现。两年之后，用c再来一遍，应该有不同的感受。

• 头文件：

#ifndef LINKED_LIST_H
#define LINKED_LIST_H

#include <stddef.h>

typedef int ll_data_t;
struct list;

// constructs a new (empty) list
struct list *list_create(void);

// counts the items on a list
size_t list_count(const struct list *list);

// inserts item at back of a list
void list_push(struct list *list, ll_data_t item_data);

// removes item from back of a list
ll_data_t list_pop(struct list *list);

// inserts item at front of a list
void list_unshift(struct list *list, ll_data_t item_data);

// removes item from front of a list
ll_data_t list_shift(struct list *list);

// deletes a node that holds the matching data
void list_delete(struct list *list, ll_data_t data);

// destroys an entire list
// list will be a dangling pointer after calling this method on it
void list_destroy(struct list *list);

#endif

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

• 源文件

#include "linked_list.h"
#include <stdlib.h>

struct list_node
{
   struct list_node *prev, *next;
   ll_data_t data;
};

struct list
{
   struct list_node *first, *last;
};

// constructs a new (empty) list
struct list *list_create(void)
{
   struct list *res = malloc(sizeof(struct list));
   res->first = NULL;
   res->last = NULL;
   return res;
}

// counts the items on a list
size_t list_count(const struct list *list)
{
   if (!list)
      return 0;
   struct list_node *list_node = list->first;
   size_t res = 0;
   while (list_node)
   {
      res++;
      list_node = list_node->next;
   }
   return res;
}

// inserts item at back of a list
void list_push(struct list *list, ll_data_t item_data)
{
   if (!list)
   {
      return;
   }
   struct list_node *node = malloc(sizeof(struct list_node));
   node->next = NULL;
   node->data = item_data;
   node->prev = list->last;
   if (!(list->first))
   {
      list->first = node;
   }
   else
   {
      list->last->next = node;
   }
   list->last = node;
}

// removes item from back of a list
ll_data_t list_pop(struct list *list)
{
   struct list_node *prev = list->last->prev;
   ll_data_t res = list->last->data;

   if (!prev)
   {
      list->first = NULL;
   }
   else
   {
      prev->next = NULL;
   }
   free(list->last);
   list->last = prev;
   return res;
}

// inserts item at front of a list
void list_unshift(struct list *list, ll_data_t item_data)
{
   if(!list)
    { return;}
    struct list_node *new_node = malloc(sizeof(struct list_node));
    new_node->data = item_data;
    new_node->prev = NULL;
    new_node->next = (list->first) ? list->first : NULL;
    
    list->first = new_node;
}

// removes item from front of a list
ll_data_t list_shift(struct list *list)
{
   if(!list || !list->first) 
    { return 0;}
    struct list_node *first = list->first;
    ll_data_t val = first->data;
    
    if(!list->first->next) {
        // node was the only item in the list 
        list->first = NULL;
        list->last= NULL;
    } else {
        list->first = first->next;
        list->first->prev = NULL;
    }
    free(first);
    return val;
}

// deletes a node that holds the matching data
void list_delete(struct list *list, ll_data_t data)
{
   if (!list)
      return;
   struct list_node *next = list->first;
   while (next)
   {

      if (next->data == data)
      {
         if (!next->prev)
         {
            list->first = next->next;
         }
         else
         {
            next->prev->next = next->next;
         }
         if (!next->next)
         {
            list->last = next->prev;
         }
         else
         {
            next->next->prev = next->prev;
         }
         free(next);
         break;
      }
      next = next->next;
   }
}

// destroys an entire list
// list will be a dangling pointer after calling this method on it
void list_destroy(struct list *list)
{
   if (!list)
   {
      return;
   }
   struct list_node *node = list->first;
   while (node)
   {
      struct list_node *tmp = node->next;
      free(node);
      node = tmp;
   }
   free(list);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164