数据结构：二级指针与不含表头的单链表

【简介】

对于最基础的数据结构，单链表，通常看到的做法是在存储链表的所有元素之时，除了有一个指向链表的变量之外，往往还存在一个指向表头的元素。通常二者其实都会指向链表的第一个元素。这么做的原因是为了链表操作方便，当进行链表的插入操作时，若在某一元素后面插入新元素时没什么问题，但当要求在某一元素的前面插入新元素时就会存在问题。即，若需要在表头的前面插入新元素，会比较麻烦。所以前面存在两个变量，一个指向链表，一个指向表头时的这种操作会比较方便，但是若只有一个指向链表的变量存在的时候就不那么方便了。

在表头的前面插入新元素，因此表头的位置会发生变化，因此一个简单的做法是将指向表头的指针作为参数传入到插入函数中，返回一个新的指向表头的指针即可。但其实这种方法完全可以用另一种参数传递形式代替。若一个参数传递到函数内部，这个参数会在函数执行过后发生变化，则我们可以将该参数的地址传入到函数，函数内部操作这个地址即可。这里也一样，对于这种表头前面插入新元素，而导致表头发生变化的情况，可以很简单的将该表头指针的地址传入函数就可以了，函数传入参数就会出现二级指针。

下面给出两种方法实现，二者本质都是一样的，只不过第一种的链表内数据是一个简单的int型变量，而第二种方法的数据使用了void*指针，将数据与链表结构分离开来。这种手段也是我比较推崇的，我以后发布的数据结构算法尽量都采取void*或void**来代替简单的数据，分析代码就可以看出这种做法的灵活之处了。另外，代码中均利用了Opaque Structure的手段实现了面向对象OO的风格，虽然这种方法有些人争论它并不是完整意义上的OO，但姑且我这里就这样称呼他。所有代码采用gcc编译，可以参考我的这篇文章下载window平台下配置好的gcc(即MinGW)开发环境。

总结下两种方法的对比：

方法一：链表中的数据类型为int，新节点采用malloc分配，OO。

方法二：链表中的数据类型为void*,新节点采用静态数组分配，OO。（在嵌入式编程中我更喜欢用这种）

【方法一】

我直接将前面提到的关键函数，在某一节点的前面插入新元素的方法贴出来：

void   List_Insert_Front(Node ** pp_list, Node *p_pos, Node * p_new)
{
    Node * p_cur;
    Node ** pp_cur;
    Node * p_prev;
    if( (!pp_list) || (!p_pos)  || (!p_new)   )     // *pp_list will be assert in the while loop
        return ;


    p_new->next =  *pp_list;          // Store the list head in the p_new->next,
    p_prev      =   p_new;            // Then we can find the next p_prev simple use p_prev = p_prev->next

    pp_cur      =   pp_list;
    while(*pp_cur)
    {
        p_cur = *pp_cur;
        if(p_cur == p_pos)
        {
            p_prev->next = p_new;
            p_new->next  = p_cur;
            *pp_cur      = p_new;     // Dereference current node
            /*
            *  When insert point is head, code above will update the head pointer of the list
            *  But when insert point is not head, code above actually will do nothing,
            *  just update the nth pointer(but nothing will happen indeed)
            */
            return ;
        }
        pp_cur = &p_cur->next;
        p_prev = p_prev ->next;
    }
    return ;
}

可以看到前插入的关键就是传入表头指针的地址，在函数内部修改该指针。

我这种while循环方式的关键点在于二：

一是，第10行，初始化时将表头暂时存放在新节点p_new的next中。

二是，第21行，当插入点找到时，做一次当前节点二级指针pp_cur的取内容赋值为新节点值p_new。

对于在某一节点后面插入新元素，理论上可以不用采用二级指针，不过为了跟前插入的风格统一，同样采用二级指针传入。

void   List_Insert_Back(Node ** pp_list, Node *p_pos, Node * p_new)
{
    Node * p_cur;
    //if( (!pp_list) || (!*pp_list)  || (!p_pos)  || (!p_new)   )
    if( (!pp_list) || (!p_pos)  || (!p_new)   )     // *pp_list will be assert in the while loop
        return ;
    //find the p_position
    p_cur = * pp_list;                  // Get the head of the list

    //In the loop below, pp_list will never be dereferrenced
    while(p_cur)
    {
        if(p_cur == p_pos)
        {
            p_new->next  = p_cur->next;     // Save current next to new next
            p_cur->next  = p_new;           // Add new to current next
            return ;
        }
        p_cur = p_cur->next;                // Get the next pointer
    }
    return ;
}

完整的代码，包括测试用main函数，在文章末尾的压缩包下载中有包含。Single_linke_list_Two_Star.7zip

【方法二】

这种方法跟方法一本质上没有区别，但鉴于我是第一次在博客中介绍这种方法，还是简单说明一下。

节点的struct声明和存放地点存在于list.c的全局变量中。当然为了限制访问最好添加static修饰。

#include  "list.h"

struct _Node{
    struct _Node * next   ;       // point to next
    void         * value  ;       // point to actual value
};

static    Node    Node_Array[MAX_NODE];
static    int     Node_Entry = 0;

之后可以调用函数，返回这个Node_Array数组中的一个成员。这个数组的最大值可以通过修改MAX_NODE确定。

Node  *   Node_New(void)
{
    Node  *   p_new;
    if(Node_Entry>=MAX_NODE)
        return (Node *)0;

    p_new = &Node_Array[Node_Entry];
    p_new->value  =  (void *)0;
    p_new->next   =  (Node *)0;
    Node_Entry++;

    return p_new;
}
Node  *    Node_New_P_Value(void* value)
{
    Node  * p_new_value;
    p_new_value = Node_New();
    if(p_new_value)
        p_new_value->value = value;
    return p_new_value;
}

注意，这里的节点Node中的实际数据是void*，即指向任何类型的指针，所以若使用Node_New_P_Value新建一个节点时需要传入一个实际指向数据存储地方的指针。当然若数据指针不赋值就保持void* 0，就只能后果自负了。在我的测试主函数中，实际存储区域任然是int类型的数组：

#include  "stdio.h"
#include  "list.h"
#define  MAX_NODE_VALUE     20
static int Node_Value_Pool [MAX_NODE_VALUE];
static int Node_Value_Entry = 0;
int * Node_Value_Get(int value);




Node * p_list_1;
int main(void)
{
    Node * p_pos;
    Node * p_new;

    p_list_1 = Node_New_P_Value(Node_Value_Get(0x2));       // 0x2

这里的数据存储区Node_Value_Pool数组我任然做了一个函数叫Node_Value_Get()来进行赋初值的调用。这样的结果是，当p_list_1调用函数Node_New_P_Value()时，其得到了一个next为Null指针，数据成员void*为指向Node_Value_Pool数组中的一个的指针。

这种方法跟方法一没有本质区别，但是我跟推荐第二种方法，以后的数据结构如果可能我会尽量采用第二种方法，即，不使用malloc新建一个类型实例的方法来编写。

可以看到，一旦将Node中的数据成员使用void*带来的好处是，可以将任何数据做成链表，不管是int还是你自己typedef struct做的一个新类型，都可以用这种OO的方式，新建一个抽象的链表对象，List，来管理你自己的数据类型。这个链表中实际上并不存放任何东西，实际存放区域在其他地方，比如，我的测试程序中的一个int类型数组中。这种方法就简单的将数据类型抽象出来，与实际存储区域进行了分离。

【测试代码下载】

Single_linke_list_Two_Star.7z

Single_linked_list_No_Malloc.7z

apollius

Jul 28, 2013