线性表(List)---链式存储结构(双向链表)

双向链表设计与实现

---

双向链表的介绍

双向链表定义: 在单链表的结点中增加一个指向其前驱的pre指针。

双向链表设计意义： 方便逆序访问链表中的元素(O(n))。
单链表中的逆序访问：

len = LinkList_Length(list);
for (i = len - 1; len >= 0; i++) //O(n)
{   
LinkListNode *p = LinkList_Get(list, i); //O(n)
//访问数据元素p中的元素
}

双向链表的设计

定义一个结构体指针用来存储指针与指针之间的关系:

typedef struct DLinkListNode
{
    struct DLinkListNode *next;
    struct DLinkListNode *pre;
}DLinkListNode;

定义一个头结点用来存储链表:

typedef struct _tag_DLinkList
{
    DLinkListNode header;
    DLinkListNode *slider;//游标
    int length;
}TDLinkList;

数据元素定义实例：

typedef struct Value
{
    DLinkListNode node;
    int v;
}Value;

双向链表新增操作

• 获取当前游标指向的数据元素
• 将游标重置指向链表中的第一个数据元素
• 将游标移动指向到链表中的下一个数据元素
• 将游标移动指向到链表中的上一个数据元素
• 直接指定删除链表中的某个数据元素

双向链表重要算法

• 双向链表插入算法
  
• 双向链表删除算法
  

双向链表的优缺点

• 优点： 双向链表在单链表的基础上增加了指向前驱的指针；功能上双向链表可以完全取代单链表的使用；循环链表的Next、Pre和Current操作可以高效的遍历链表中的所有元素。
• 缺点： 代码复杂。
  

  ---

双向链表的实现

DLinkList.h

#ifndef  _DLINKLIST_H_
#define  _DLINKLIST_H_

typedef void DLinkList;
typedef struct DLinkListNode
{
    struct DLinkListNode *next;
    struct DLinkListNode *pre;
}DLinkListNode;

//创建双向链表
DLinkList *DLinkList_Create();

//销毁双向链表
void DLinkList_Destroy(DLinkList *list);

//清空双向链表
void DLinkList_Clear(DLinkList *list);

//获取双向链表长度
int DLinkList_Length(DLinkList *list);

//向第pos位置char如元素node
int DLinkList_Insert(DLinkList *list, DLinkListNode *node, int pos);

//获取第pos位置的元素
DLinkListNode *DLinkList_Get(DLinkList *list, int pos);

//删除第pos位置的元素
DLinkListNode *DLinkList_Delete(DLinkList *list, int pos);

//获取当前游标的元素
DLinkListNode *DLinkList_Current(DLinkList *list);

//将游标重置指向链表的第一个位置元素
DLinkListNode *DLinkList_Rset(DLinkList *list);

//将游标移动指向到链表下一个位置元素
DLinkListNode *DLinkList_Next(DLinkList *list);

//将游标移动指向到链表上一个位置元素
DLinkListNode *DLinkList_Pre(DLinkList *list);

//直接删除指定链表中的某个元素
DLinkListNode *DLinkList_DeleteNode(DLinkList *list, DLinkListNode *node);

#endif//DLinkList.h

DLinkList.c

#include "DLinkList.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct _tag_DLinkList
{
    DLinkListNode header;
    DLinkListNode *slider;//游标
    int length;
}TDLinkList;

//创建双向链表
DLinkList *DLinkList_Create()
{
    TDLinkList *ret = (TDLinkList *)malloc(sizeof(TDLinkList));
    if(ret==NULL)
    {
        printf("func DLinkList_Create()(ret==NULL) err\n");
        return ret;
    }
//  memset(ret, 0, sizeof(ret));
    ret->header.next = NULL;
    ret->header.pre = NULL;
    ret->slider = NULL;
    ret->length = 0;

    return ret;
}

//销毁双向链表
void DLinkList_Destroy(DLinkList *list)
{
    if (list == NULL)
    {
        return;
    }
    free(list);
    return ;
}

//清空双向链表
void DLinkList_Clear(DLinkList *list)
{
    TDLinkList *tlist=(TDLinkList *)list;
    if (list == NULL)
    {
        printf("func DLinkList_Clear() (list == NULL) err\n");
        return;
    }

    tlist->header.next = NULL;
    tlist->header.pre = NULL;
    tlist->slider = NULL;
    tlist->length = 0;
    return ;
}

//获取双向链表长度
int DLinkList_Length(DLinkList *list)
{
    int ret = 0;
    TDLinkList *tlist = (TDLinkList *)list;
    if (list == NULL)
    {
        ret = -1;
        printf("func DLinkList_Length()(list == NULL) err:%d\n",ret);
        return ret;
    }
    ret = tlist->length;

    return ret;
}

//向第pos位置插入元素node
int DLinkList_Insert(DLinkList *list, DLinkListNode *node, int pos)
{
    int ret = 0, i = 0;
    TDLinkList *tlist = (TDLinkList *)list;
    DLinkListNode *Current = NULL;
    DLinkListNode *Next = NULL;
    if (list == NULL || node == NULL || pos < 0)
    {
        ret = -1;
        printf("func DLinkList_Insert() (list == NULL || node == NULL || pos < 0) err:%d", ret);
        return ret;
    }

    if (pos > tlist->length)
    {
        ret = -2;
        printf("func DLinkList_Insert() (pos > tlist->length) err:%d\n", ret);
        return ret;
    }
    Current = (DLinkListNode *)tlist;

    for (i = 0; (i < pos) && (Current->next != NULL); i++)
    {
        Current = Current->next;
    }

    Next = Current->next;
    Current->next = node;  //1
    node->next = Next;     //2

    if (Next != NULL)
    {
        Next->pre = node;  //3
    }
    node->pre = Current;   //4

    if(tlist->length==0)
    { 
        tlist->slider = node;//当链表插入第一个元素处理游标
    }
    //若在0位置插入，需要特殊处理新节点next前pre指向NULL
    if (Current == (DLinkListNode *)tlist)
    {
        node->pre = NULL;
    }
    tlist->length++;

    return ret;
}

//获取第pos位置的元素
DLinkListNode *DLinkList_Get(DLinkList *list, int pos)
{
    int i = 0;
    TDLinkList *tlist = (TDLinkList *)list;
    DLinkListNode *Current = NULL;
    DLinkListNode *ret = NULL;

    if (list == NULL || pos < 0)
    {
        printf("func DLinkList_Get() (list == NULL || pos < 0) err\n");
        return NULL;
    }
    if (pos > tlist->length)
    {
        printf("func DLinkList_Get() (pos > tlist->length) err\n");
        return  NULL;
    }
    Current = (DLinkListNode *)tlist;
    for (i = 0; (i < pos) && (Current->next != NULL); i++)
    {
        Current = Current->next;
    }
    ret = Current->next;

    return ret;
}

//删除第pos位置的元素
DLinkListNode *DLinkList_Delete(DLinkList *list, int pos)
{
    int i = 0;
    TDLinkList *tlist = (TDLinkList *)list;
    DLinkListNode *Current = NULL;
    DLinkListNode *Next = NULL;
    DLinkListNode *ret = NULL;

    if (list == NULL || pos < 0)
    {
        printf("func DLinkList_Delete() (list == NULL || pos < 0) err\n");
        return NULL;
    }

    if (pos > tlist->length)
    {
        printf("func DLinkList_Deletee() (pos > tlist->length) err\n");
        return NULL;
    }
    Current = (DLinkListNode *)tlist;
    for (i = 0; (i < pos) && (Current->next != NULL); i++)
    {
        Current = Current->next;
    }
    ret = Current->next;
    Next = ret->next;               
    Current->next = Next;           //1

    if (Next != NULL)
    {
        Next->pre = Current;
        if (Current == (DLinkListNode *)tlist)
        {
            Next->pre = NULL;
        }
    }

    if (tlist->slider == ret)
    {
        tlist->slider = Next;
    }
    tlist->length--;

    return ret;
}

//获取当前游标的元素
DLinkListNode *DLinkList_Current(DLinkList *list)
{
    TDLinkList *tlist = (TDLinkList *)list;
    DLinkListNode *ret = NULL;
    if (list == NULL)
    {
        printf("func DLinkList_Current() (list == NULL) err\n");
        return NULL;
    }
    ret = tlist->slider;

    return ret;
}

//将游标重置指向链表的第一个位置元素
DLinkListNode *DLinkList_Rset(DLinkList *list)
{
    TDLinkList *tlist = (TDLinkList *)list;
    DLinkListNode *ret = NULL;
    if (list == NULL)
    {
        printf("func DLinkList_Rset() (list == NULL) err\n");
        return NULL;
    }
    tlist->slider = tlist->header.next;
    ret = tlist->slider;

    return ret;
}

//将游标移动指向到链表下一个位置元素
DLinkListNode *DLinkList_Next(DLinkList *list)
{
    TDLinkList *tlist = (TDLinkList *)list;
    DLinkListNode *ret = NULL;
    if (list == NULL)
    {
        printf("func DLinkList_Next() (list == NULL) err\n");
        return NULL;
    }
    ret = tlist->slider;
    tlist->slider = ret->next;

    return ret;
}

//将游标移动指向到链表上一个位置元素
DLinkListNode *DLinkList_Pre(DLinkList *list)
{
    TDLinkList *tlist = (TDLinkList *)list;
    DLinkListNode *ret = NULL;
    if (list == NULL)
    {
        printf("func DLinkList_Pre() (list == NULL) err\n");
        return NULL;
    }
    ret = tlist->slider;
    tlist->slider = ret->pre;

    return ret;

}

//直接删除指定链表中的某个元素
DLinkListNode *DLinkList_DeleteNode(DLinkList *list, DLinkListNode *node)
{
    int i = 0;
    TDLinkList *tlist = (TDLinkList *)list;
    DLinkListNode *ret = NULL;
    DLinkListNode *Current = NULL;
    if (list == NULL || node)
    {
        printf("func DLinkList_DeleteNode() (list == NULL || node) err\n");
        return NULL;
    }

    Current = (DLinkListNode *)tlist;
    for (i = 0; i < tlist->length; i++)
    {
        if (Current->next == node)
        {
            ret = Current->next;
            break;
        }
    }
    if (ret != NULL)
    {
        DLinkList_Delete(tlist, i);
    }
    if (ret == tlist->slider)
    {
        tlist->slider = ret->next;
    }

    return ret;
}

双向链表集成测试框架

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "DLinkList.h"

typedef struct Value
{
    DLinkListNode node;
    int v;
}Value;

void main()
{
    int i = 0, ret = 0;
    Value v1, v2, v3, v4, v5;
    Value *tmp = NULL;

    DLinkList *list = DLinkList_Create();
    if (list == NULL)
    {
        printf("func DLinkList_Create()(list == NULL) err\n");
        return;
    }

    v1.v = 1;
    v2.v = 2;
    v3.v = 3;
    v4.v = 4;
    v5.v = 5;

    ret = DLinkList_Insert(list, (DLinkListNode *)&v1, DLinkList_Length(list));
    if (ret != 0)
    {
        printf("func DLinkList_Insert() (ret != 0) err:%d\n", ret);
        return;
    }

    ret = DLinkList_Insert(list, (DLinkListNode *)&v2, DLinkList_Length(list));
    if (ret != 0)
    {
        printf("func DLinkList_Insert() (ret != 0) err:%d\n", ret);
        return;
    }

    ret = DLinkList_Insert(list, (DLinkListNode *)&v3, DLinkList_Length(list));
    if (ret != 0)
    {
        printf("func DLinkList_Insert() (ret != 0) err:%d\n", ret);
        return;
    }

    ret = DLinkList_Insert(list, (DLinkListNode *)&v4, DLinkList_Length(list));
    if (ret != 0)
    {
        printf("func DLinkList_Insert() (ret != 0) err:%d\n", ret);
        return;
    }

    ret = DLinkList_Insert(list, (DLinkListNode *)&v5, DLinkList_Length(list));
    if (ret != 0)
    {
        printf("func DLinkList_Insert() (ret != 0) err:%d\n", ret);
        return;
    }

    printf("Get Elements:\n");
    for (i = 0; i < DLinkList_Length(list); i++)
    {
        tmp = (Value *)DLinkList_Get(list, i);
        printf("tmp->v:%d\n", tmp->v);
    }
    printf("\n");
    printf("\n");


    DLinkList_Delete(list, DLinkList_Length(list) - 1); //删除最后一个元素
    DLinkList_Delete(list, 0);                           //删除第一个元素

    printf("Delete first element and last element:\n");
    for (i = 0; i < DLinkList_Length(list); i++)
    {
        tmp = (Value *)DLinkList_Next(list);
        printf("tmp->v:%d\n", tmp->v);
    }

    printf("\n");
    DLinkList_Rset(list);   //游标重置
    DLinkList_Next(list);   //游标后移一个  3

    printf("reset slider,and move slider to next: \n");
    tmp = (Value *)DLinkList_Current(list);
    printf("tmp->v:%d\n", tmp->v);


    DLinkList_Pre(list);     //游标前移一个 2
    printf("mov slider to pre:\n");
    tmp = (Value *)DLinkList_Current(list);
    printf("tmp->v:%d\n", tmp->v);

    printf("Length:%d\n", DLinkList_Length(list));  

    DLinkList_Destroy(list);

    system("pause");
    return;
}

结果截图