准备把原来上学时候写的数据结构、算法相关的代码再重新写一遍，温习下。首先从链表说起，链表可能是我们平时用的较多的一种结构，链表操作对于删除、添加的算法时间复杂度为O(1)。

说到链表就不得不提到他的表哥数组，通过下图来看下一数据和链表在内存中的区别（此处所说的内存都是虚拟内存）。

数组在内存中的存放

注：这里addr + 1 并不是一个字节或者一个字，是一个数据单位的大小。

由上图可以看出数组是在内存中连续存放的，这就成在数据删除或者插入的时候可能要移动很多的数据，其可扩展性也不好。

链表在内存中的表示

上图中一个数据单元中除了放本单元的数据，还存放了下一个单元的地址，上图可以简化一下：

从上图可以看出，链表中的数据在内存中并不是连续存放的，而是通过index将两个数据单元关联起来，这样可以方便我们在不同的数据单元之间插入数据，例如在数据单元1和数据单元2之间插入数据如下：

数据插入

链表还可以分为单链表、双链表、循环链表，不过其原理都是大同小异，下面以单链表为例练练手，以面向对象的思路进行编程，可能在这里不是太合适，不过训练对事物进行抽象能力绝对对编程大有好处。

#include<stdio.h>#include<stdlib.h>#include<unistd.h>#include<string.h>typedefstructlist{charname[32];intage;structlist*next;/*指向下一个节点*//*在头节点之后插入新节点*/void(*insert)(structlist*head,structlist*node);int(*delete)(structlist*head,structlist*node);/*删除指定的节点*//*查找是否存在指定节点*/structlist*(*find_node)(structlist*head,structlist*node,int*ret);void(*print_list)(structlist*head);/*打印节点内容*/void(*destroy_list)(structlist*head);/*销毁整个链表*/}list_t;structinfo{char*name;intage;}person[]={{"zhangsan",18},{"lisi",20},{"xiaohong",30},{"end",0},};/**fun:头结点之后插入新节点*head：头结点指针*node:待插入节点指针*/voidlist_insert_node(structlist*head,structlist*node){if(head==NULL||node==NULL){printf("insertnodefailed!\n");return;}node->next=head->next;head->next=node;}/**fun:查找指定的节点是否存在*head：头结点指针*node:待查找节点指针*ret:查找成功失败的标志，0成功，-1失败*return:删除节点的前一个节点指针*/structlist*list_find_node(structlist*head,structlist*node,int*ret){structlist*tmp;if(head==NULL||node==NULL){printf("findnodefailed!\n");*ret=-1;returnNULL;}while(head->next){tmp=head->next;if((tmp->age==node->age)&&(strcmp(tmp->name,node->name)==0)){returnhead;}head=head->next;}*ret=-1;returnNULL;}/**fun:删除指定节点*head：头结点指针*node:待删除节点指针*return:0成功，-1失败*/intlist_del_node(structlist*head,structlist*node){intret;structlist*pre_del_node;structlist*tmp;if(head==NULL||node==NULL){printf("delnodefailed!\n");return-1;}ret=0;pre_del_node=head->find_node(head,node,&ret);if(ret==-1){returnret;}tmp=pre_del_node->next;pre_del_node->next=tmp->next;free(tmp);return0;}/**fun:显示链表内容*head：头结点指针*/voidprint_list(structlist*head){structlist*tmp;tmp=head->next;while(tmp){printf("name=%s,age=%d\n",tmp->name,tmp->age);tmp=tmp->next;}}/**fun:删除成个链表*head：头结点指针*/voiddestroy_list(structlist*head){structlist*tmp;structlist*assit;assit=head->next;while(assit){tmp=assit;assit=assit->next;free(tmp);}free(head);/*释放头节点指针*/}voidinit_head(structlist*head){head->next=NULL;head->insert=list_insert_node;head->delete=list_del_node;head->find_node=list_find_node;head->print_list=print_list;head->destroy_list=destroy_list;}intmain(intargc,char*argv[]){inti;structlist*head,*tmp;head=(structlist*)malloc(sizeof(structlist));if(head==NULL){printf("nomemory\n");exit(-1);}init_head(head);i=0;while(person[i].age){tmp=(structlist*)malloc(sizeof(structlist));if(tmp==NULL){/*此处应该释放掉已经分配的内存，防止内存泄漏，偷懒没有写*/printf("nomemory\n");exit(-1);}strcpy(tmp->name,person[i].name);tmp->age=person[i].age;tmp->next=NULL;head->insert(head,tmp);i++;}head->print_list(head);head->delete(head,tmp);printf("删除最后插入的节点之后\n");head->print_list(head);return0;}

说明：次例子仅作练习用，真正用到项目中可以找一些开源的，简洁高效的链表代码，例如我们公司项目中的链表就是修改的LINUX内核链表来用的，没有必要重复造轮子，但作为练习还是要敲一下。