# 数据结构 链表_单链表的实现与分析

2017-11-18 12:50:28来源:cnblogs.com作者:IDreamo人点击

## 单链表的实现与分析

`    /*list.h*/      #ifndef LIST_H      #define LIST_H            #include <stdio.h>      /*Define a structure for linked list elements.*/      typedef struct ListElmt_      {          void *data;          struct ListElmt_ *next;      } ListElmt;            /*Define a structure for linked lists.*/      typedef struct List_      {          int size;          int (*match)(const void *key1,const void *key2);          void (*destroy)(void *data);          ListElmt *head;          ListElmt *tail;      } List;            /*Public Interface*/      void list_init(List *list,void(*destroy)(void *data));      void list_destroy(List *list);      int list_ins_next(List *list,ListElmt *element,const void *data);      int list_rem_next(List *list,listElmt *element,void **data);      #define list_size(list)((list)->size)            #define list_head(list)((list)->head)      #define list_tail(list)((list)->tail)      #define list_is_head(list,element)(element==(list)->head ? 1 : 0)      #define list_is_tail(element)((element)->next==NULL ? 1 : 0)      #define list_data(element)((element)->data)      #define list_next(element)((element)->next)            #endif // LIST_H  `

## list_init

list_init用来初始化一个链表以便能够执行其他操作（见示例2）。

list_init的复杂度为O(1)，因为初始化过程中的所有步骤都能在一段恒定的时间内完成。

`    /*list.c*/      #include <stdio.h>      #include <string.h>            #include "lish.h"            /*list_init*/      void list_init(List *list,void(*destroy)(void *data))      {          list->size = 0;          list->destroy = destroy;          list->head = NULL;          list->tail = NULL;                return;      }            /*list_destroy*/      void list_destroy(List *list)      {          void *data;          /*Remove each element*/          while(list_size(list)>0)          {              if(list_rem_next(list,NULL,(void **)&data)==0 && list->destroy!=NULL)              {                  /*Call a user-defined function to free dynamically allocated data.*/                  list->destroy(data);              }          }          memset(list,0,sizeof(list));          return;      }            /*list_ins_next*/      int list_ins_next(List *list,ListElmt *element,const void *data)      {          ListElmt *new_element;                    /*Allocate storage for the element*/          if((new_element=(ListElmt *)malloc(sizeof(ListElmt)))==NULL)              return -1;          /*insert the element into the list*/          new_element->data=(void *)data;          if(element == NULL)          {              /*Handle insertion at the head of the list. */              if(list_size(list)==0)                  list_tail = new_element;                                new_element->next = list->head;              list->head = new_element          }          else           {              /*Handle insertion somewhere other than at the head*/              if(element->next==NULL)                  list->tail = new_element;                            new_element->next = element->next;              element->next = new_element;          }          /*Adjust the size of the list of account for the inserted element. */          list->size++;                    return 0;      }            /*list_rem_next*/      int list_rem_next(List *list,ListElmt *element,void **data)      {          ListElmt *old_element;                    /*Do not allow removal from an empty list. */          if(list_size(list) == 0)              return -1;                    /*Remove the element from the list. */          if(element == NULL)          {              /*Handle removal from the head of the list. */              *data = list->head->data;              old_element = list->head;              list->head = list->head->next;                            if(list_size(list) == 1)                  list->tail = NULL;          }          else           {              /*Handle removal from somewhere other than the head. */              if(element->next == NULL)                  return -1;                            *data = element->next->data;              old_element = element->next;              element->next = element->next->next;                            if(element->next == NULL)                  list->tail = element;          }          /*Free the storage allocated by the abstract datatype.*/          free(old_element);          /*Adjust the size of the list account for the removed element. */          list->size--;          return 0;      }  `

## list_destroy

list_destroy用来销毁链表（见示例2），其意义就是移除链表中的所有的元素。

list_destroy的运行时复杂度为O(n)，n代表链表中的元素个数，这是因为list_rem_next的复杂度为O,而移除每个元素时都将调用list_rem_next一次。

## list_ins_next

list_ins_next将一个元素插入由element参数所指定的元素之后（见示例2）。该调用将新元素的数据指向由用户传递进来的数据。向链表中插入新元素的处理步骤很简单，但需要特别小心。有两种情况需要考虑：插入链表头部和插入其他位置。

## list_rem_next

list_rem_next从链表中移除由element所指定的元素之后的那个结点（见示例2）。移除的是element之后的那个结点而不是移除element本身。这个调用也需要考虑两个因素，移除的是头结点以及移除其余位置上的结点。

list_rem_next的复杂度为O(1)，因为所有的移除步骤都在恒定的时间内完成。