c印记(十一)：单向链表 list原理与实现

注：

文中的定义，是指这样规定或者说就长这样，并非c语言当中的定义和声明

本文所说，比较偏向于实用性，不是大而全的链表各种操作的实现

一、简而言之

在百度百科里面摘取了一段关于链表的介绍：

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。

也无需多言，不管是c语言相关的基础教材，又或者数据结构相关教材均有讲述，这里就不在赘言。简而言之，一个线性单向链表的结构如下图所示：

c印记(十一)：单向链表 list原理与实现

二、一般而言

这里是对就一般而言，链表的结构，操作方法等的表述。

2.1 基本结构

使用c语言实现单向链表，大概有两种情况：专用，通用

2.1.1 实现专用链表

比如，需要实现一个链表来管理学生信息(这里不去管这种实现的效率或者可行性，只是举例而已)，当新生入学的时候，可以在链表中插入新生信息，
当有学生毕业的时候，可以从链表中删除信息。
那么，可能的链表节点结构定义如下：

typedef struct student_node_s
{
int num; /**< 学号 */
char* name; /**< 名字 */
/** ... 根据具体需求，可能还有更多其他信息 */
struct student_node_s* next; /**< 指向下一个节点 */
}student_node_t;

链表结构定义如下：

typedef struct student_list_s
{
int count; /**< 总共有多少学生 */
    student_node_t* head; /**< 表头 */
}student_list_t;

2.1.2 通用链表

如上述这样的链表，虽然可以方便学生信息管理这个功能使用，但它也有一些缺点，比如从字面意思可知，所谓专用，就是专门为学生信息管理这个功能定制的，不能或者说很难用在其他功能中，比如需要添加教师信息管理功能，就会遇到麻烦，按专用的逻辑，就需要为教师信息管理功能定制一个链表，其功能和学生管理的链表几乎相同，只是节点数据信息不一样而已。

因此，通用链表实现就此登场了，其节点和链表的数据结构定义如下：

/**@brief 节点数据结构定义 */
typedef struct list_node_s 
{
void* data; /**< 节点数据 */
struct list_node_s* next; /**< 指向下一个节点 */
}list_node_t;

/**@brief 链表数据结构定义 */
typedef struct list_s
{
int length;/**< 表示链表中有多少个元素或者节点 */
    list_node_t* head; /**< 表头 */
}list_t;

这样定义之后，不管是学生信息管理，还是教师信息管理都可以分别定义各自的数据信息结构，存放在list_node_t::data 成员当中。

注：上面不管是通用，还是专用链表，都是专门定义了一个表示链表的结构体，并在其中添加了表示链表中有多少节点的数据成员，而不是纯粹的直接使用像list_node_t这样的节点结构作为链表头来表示一个链表，是因为，如果是纯粹的list_node_t，那么每当要获取链表中有多少个节点的时候，都需要遍历一次链表，如果节点较多时，消耗的时间就会比较大。

2.2 基本操作

说到数据结构，不管是链表，队列或者树等等的时候，基本操作都是增、删，查，改。

增：向链表当中插入一个节点
删：从链表中删除一个节点
查：在链表中遍历查找目标节点
改：找到并修改目标节点

这几个操作当中有一个共同的操作，就是找到目标节点。对于单向链表来说，要查找目标节点，其方法就是遍历，并比较。

这里以通用链表为例来说明这个查找的过程。

通常情况下，通用链表要查找目标节点的话，都会需要使用者提供一个比较函数，其过程的伪代码如下：

node = list->head;
while(node)
{
if (compare(node, target))
    {/** 对比返回 真，表示找到目标节点 */
/**todo somethings */
break; 
    }

    node = node->next; /** 获取下一个节点 */
}

三、门户之见

这里就说说，我的想法以及我的实现。

3.1 数据结构

在数据结构方面，我的实现也是走通用链表的方式，但却和他的结构基本上截然相反。上面描述的通用链表的实现是将用户数据嵌套至链表节点当中，而我的实现是将链表节点嵌套至用户数据当中。其大概形式如下：

/**@brief 链表节点数据结构定义 */
typedef struct list_node_s
{
struct list_node_s* next; /**< 指向下一个节点 */
}list_node_t;

/**@brief 用户链表节点数据结构定义 */
typedef struct usr_node_s
{
    list_node_t node; /**< 链表节点，必须放在结构体的第一个成员位置 */
/** xxx 用户自己的数据定义 */
int num;
char* name;
}usr_node_t;

相对于第二章中提到的结构体形式，这里的结构体形式是有一定优势的，比如，链表的实现里面只需要关心增，删，查，改等操作就可以了，不需要需分配节点实例。又比如，节点的内存是连续，不像前面的那样，链表节点和用户数据需要分别分配内存。还比如，可以留给用户更大的*度，比如客户在获取到head节点之后，可以自己在外面实现链表遍历，期间可以进行各种用户想要的操作。

然后链表结构定义和前面的提到的数据结构类似，这里就不在重复了。

3.2 操作接口

这里说说我的实现和2.2节当中提到的链表操作的基本接口有何差异。

3.2.1 增、删、查、改

在2.2节当中，说到了几个基本的操作增、删、查、改。并提到了，他们都有一个共同的动作，就是找到目标节点。但在某些情况下，这些基本操作虽然能满足操作需求，但在性能上却大有问题。

比如，要使用链表实现一个FIFO（先进先出）的queue（队列），也就是说，每次插入，都是发生在链表的末尾，按照2.2节中提到的寻找目标节点的方式实现的话，就意味着，每次添加新节点都需要将整个链表遍历一遍，这样效率就太低了。

因此，在我的实现当中，会单独开一个API负责处理这种情况，并在链表数据结构中添加一个数据成员来表示链表尾部节点，在尾部添加新节点的时候，只需要将其添加到这个数据成员表示的尾部节点之后，并将数据成员指向新的尾部节点，其大致意思如下：

typedef struct list_s
{
/** xxx 其他数据成员 */
    list_node_t* head; /**< 表头 */
    list_node_t* tail;   /**< 表尾 */
}list_t;

/** 在尾部插入新节点的操作示意 */
if (list->tail)
{/** 如果tail节点存在，只需要将新节点接入tail节点的next指针中 */
list->tail->next = new_node;
}
else
{/**如果tail节点为NULL，就是说整个链表中一个节点都没有， 这是需要将新节点赋给head节点 */
list->head = new_node;
}
list->tail = new_node; /** 将tail 指向新的尾节点 */

3.2.2 关于compare函数

在2.2节中寻找目标节点的过程中需要由用户提供一个compare函数来作为节点对比依据。在我的实现中，链表遍历，并比较的动作，将会有用户来完成。链表只会提供，获取head 节点以及插入或删除的接口（因为查和改用户在找到目标节点时就已经可以进行了）。

这里就以插入新节点为例来说明（其数据部分还是前面提到的学生信息）：

/** 链表的API */
/**
 * l [in] 链表handle
 * prev [in] 新节点将插入该节点之后
 * new_node [in] 要插入的新节点
 */
void insert(list_t* l,  list_node_t* prev, list_node_t* new_node);

list_node_t* front(list_t* l); /** 获取head 节点 */


/** 用户需要实现的插入节点的函数 */

/**
 * l [in] 链表handle
 * num [in] 在学号为‘num’的学生节点之后插入新节点
 * new_node [in] 需要插入的新学生节点
 */
void usrInsert(list_t* l,  int num, list_node_t* new_node)
{
    list_node_t* node = front(l); /** 获取head 节点 */

while（node）
    {
        student_node_t* sn = (student_node_t*)node; /** 转换为学生节点 */
if (sn->num == num)
        {/** 找到目标节点 */
            insert(l, node, new_node);
break;
        }
    }
}

同样，删除节点也是和上面类似的操作，这里也就不再赘言。

四、和盘托出

这里就将我的实现全部贴出来。

注：其中general_xxx.h 就是全面章节中提到的通用头文件

头文件如下：

#ifndef __TINY_LIST_H__
#define __TINY_LIST_H__


#include "general_type.h"


#ifdef __cplusplus
extern "C" {
#endif

/***************************************************************************
 *
 * macro declaration
 *
 ***************************************************************************/

/***************************************************************************
 *
 * data structure declaration
 *
 ***************************************************************************/
/**@brief list node, 
 *@note sub node need put the flow structure in the start position of sub node. 
 */
typedef struct tiny_list_node_s
{
struct tiny_list_node_s* next; /**< pointer to next node */
}tiny_list_node_t;

/** callback function for free list node */
typedef void (*TinyListNodeFreeFunc_t)(void* node);

/** the data structure of list */
typedef struct tiny_list_s 
{
    GU32 node_count; /**< how many node in current list */
    TinyListNodeFreeFunc_t node_free; /**< callback function for free list node */
    tiny_list_node_t* head; /**< list header node */
    tiny_list_node_t* tail; /**< list tail node */
}tiny_list_t;

/***************************************************************************
 *
 * API declaration
 *
 ***************************************************************************/

/**
 *@brief initialize list
 *
 *@param tl [io] pointer to the structure of tiny_list_t
 *@param node_free [in] the callback function for free list node.
 *
 *@return none.
 *@see
 *
 */
G_API void tfListInitialize(tiny_list_t* tl, TinyListNodeFreeFunc_t node_free);

/**
 *@brief get first node
 *
 *@param tl [in] pointer to the structure of tiny_list_t
 *
 *@return success: first node in list, fail: NULL.
 *@see
 *
 */
G_API tiny_list_node_t* tfListFront(tiny_list_t* tl);

/**
 *@brief pop first node from list
 *
 *@param tl [in] pointer to the structure of tiny_list_t
 *
 *@return none
 *@see
 *@note if node_free != NULL, then this operation will free the popped node.
 *
 */
G_API void tfListPopFront(tiny_list_t* tl);

/**
 *@brief push a node to the front of list
 *
 *@param tl [in] pointer to the structure of tiny_list_t
 *@param node [in] pointer to new node
 *
 *@return none.
 *@see
 *
 */
G_API void tfListPushFront(tiny_list_t* tl, tiny_list_node_t* node);

/**
 *@brief push a node to the back of list
 *
 *@param tl [in] pointer to the structure of tiny_list_t
 *@param node [in] pointer to new node
 *
 *@return none.
 *@see
 *
 */
G_API void tfListPushBack(tiny_list_t* tl, tiny_list_node_t* node);

/**
 *@brief remove a node from list(with prev node)
 *
 *@param tl [in] pointer to the structure of tiny_list_t
 *@param prev [in] pointer to the prev node of current node.
 *@param node [in] pointer to the node which need to removed
 *
 *@return none.
 *@see
 *@note prev will not removed. prev cann't be NULL. 
 *
 */
G_API void tfListRemoveFast(tiny_list_t* tl,tiny_list_node_t* prev, tiny_list_node_t* node);

/**
 *@brief insert a node to list(with prev node)
 *
 *@param tl [in] pointer to the structure of tiny_list_t
 *@param prev [in] pointer to the prev node of current node.
 *@param node [in] pointer to the node which need to insert
 *
 *@return none.
 *@see
 *@note if prev == NULL, then insert node to the head of list. 
 *
 */
G_API void tfListInsertFast(tiny_list_t* tl,tiny_list_node_t* prev, tiny_list_node_t* node);

/**
 *@brief clear(remove and free) all of node in list 
 *
 *@param tl [in] pointer to the structure of tiny_list_t
 *
 *@return none.
 *@see
 *@note if node_free != NULL, then this operation will free all node
 *
 */
G_API void tfListClear(tiny_list_t* tl);

/**
 *@brief how many node in list
 *
 *@param tl [in] pointer to the structure of tiny_list_t
 *
 *@return the count of node in current list.
 *@see
 *
 */
G_API GU32 tfListCount(tiny_list_t* tl);

/**
 *@brief check is current empty?
 *
 *@param tl [in] pointer to the structure of tiny_list_t
 *
 *@return empty: GTRUE, not: GFALSE
 *@see
 *
 */
G_API GBOL tfListIsEmpty(tiny_list_t* tl);


#ifdef __cplusplus
}
#endif

#endif //end of __TINY_LIST_H__

源文件如下：

#include <string.h>

#include "tiny_list.h"



/***************************************************************************
*
* macro define
*
***************************************************************************/
#define LOGE printf
#define LOGD printf
#define LOGW printf
/***************************************************************************
*
* data structure define
*
***************************************************************************/

/***************************************************************************
*
* inner API define
*
***************************************************************************/
static inline void tlFreeNode(tiny_list_t* tl, tiny_list_node_t* node)
{
    tl->node_count--;

if (tl->node_free)
    {
        tl->node_free(node);
    }

if (tl->head == NULL)
    {
        tl->tail = NULL;
    }
}
/***************************************************************************
*
* API define
*
***************************************************************************/

void tfListInitialize(tiny_list_t* tl, TinyListNodeFreeFunc_t node_free)
{
memset(tl, 0, sizeof(*(tl)));
    tl->node_free = node_free;
}

tiny_list_node_t* tfListFront(tiny_list_t* tl)
{
return tl->head;
}

void tfListPopFront(tiny_list_t* tl)
{
if (tl->head)
    {
        tiny_list_node_t* temp = tl->head;

        tl->head = tl->head->next;
        tlFreeNode(tl, temp);
    }
}

void tfListPushFront(tiny_list_t* tl, tiny_list_node_t* node)
{
    tfListInsertFast(tl, NULL, node);
}

void tfListPushBack(tiny_list_t* tl, tiny_list_node_t* node)
{
    tfListInsertFast(tl, tl->tail, node);
}

void tfListRemoveFast(tiny_list_t* tl,tiny_list_node_t* prev, tiny_list_node_t* node)
{
if (prev && node)
    {
if (prev == node)
        {
if (tl->head == prev)/**mean that remove head node */
            {
                tl->head = node->next;
            }
else
            {
                LOGW("prev == node, but prev != head, this case is illegal,"
"so here will be remove nothing\n");
return ;
            }
        }
else
        {
            prev->next = node->next;
        }

        tlFreeNode(tl, node);
    }
}

void tfListInsertFast(tiny_list_t* tl,tiny_list_node_t* prev, tiny_list_node_t* node)
{
if (node)
    {
if (prev)
        {
if (tl->tail == prev)
            {
                tl->tail = node;
            }
            node->next = prev->next;
            prev->next = node;
        }
else
        {
if (tl->head == NULL)
            {
                tl->tail = node;
            }

            node->next = tl->head;
            tl->head = node;
        }

        tl->node_count++;
    }
else
    {
        LOGE(" node is NULL \n");
    }

}

void tfListClear(tiny_list_t* tl)
{
    tiny_list_node_t* head = tl->head;

while (head)
    {
        tiny_list_node_t* node = head;
        head = head->next;

if (tl->node_free)
        {
            tl->node_free(node);
        }
    }

    tl->head = NULL;
    tl->tail = NULL;
    tl->node_count = 0;
}

GU32 tfListCount(tiny_list_t* tl)
{
return tl->node_count;
}

GBOL tfListIsEmpty(tiny_list_t* tl)
{
return tl->head ? GFALSE : GTRUE;
}

五、扪心自问

以上是目前想法的实现，只能算是初版，应对目前需求尚可，但不排除其内有Bug存在。后续还可继续优化或改进，比如：

对于node_free这个回调函数，不一定在create的时候传入，可以改为在需要使用到node_free的接口的参数中传入(如，clear，destroy，popfront等)。
对于接口，还可以增加一些常规链表的基本接口，比如，增加一个remove接口，传入 compare回调函数来对比节点找到目标节点，而不需要用户自己去实现函数来找到它的前一个节点。
…

秒客网

c印记(十一)：单向链表 list原理与实现

一、简而言之

二、一般而言

2.1 基本结构

2.1.1 实现专用链表

2.1.2 通用链表

2.2 基本操作

三、门户之见

3.1 数据结构

3.2 操作接口

3.2.1 增、删、查、改

3.2.2 关于compare函数

四、和盘托出

五、扪心自问

相关文章

c印记(十一)： 单向链表 list原理与实现

一、简而言之

二、一般而言

2.1 基本结构

2.1.1 实现专用链表

2.1.2 通用链表

2.2 基本操作

三、门户之见

3.1 数据结构

3.2 操作接口

3.2.1 增、删、查、改

3.2.2 关于compare函数

四、和盘托出

五、扪心自问

相关文章

c印记(十一)：单向链表 list原理与实现