使用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

• 源文件

#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);
}