双向链表的实现与操作(C语言实现)

新闻链接：http://blog.csdn.net/u010590318/article/details/29210607#

新闻时间：2014-06-07

新闻正文：

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。

单链表的局限

1，单链表的结点都只有一个指向下一个结点的指针

2，单链表的数据元素无法直接访问其前驱元素

3，逆序访问单链表中的元素是极其耗时的操作

双向链表的操作

双向链表的新操作

1,获取当前游标指向的数据元素

2,将游标重置指向链表中的第一个数据元素

3,将游标移动指向到链表中的下一个数据元素

4,将游标移动指向到链表中的上一个数据元素

5,直接指定删除链表中的某个数据元素

DLinkListNode*DLinkList_DeleteNode(DLinkList* list, DLinkListNode* node);

DLinkListNode*DLinkList_Reset(DLinkList* list);

DLinkListNode*DLinkList_Current(DLinkList* list);

DLinkListNode*DLinkList_Next(DLinkList* list);

DLinkListNode*DLinkList_Pre(DLinkList* list);

头文件：
#ifndef _DDLinkList_H_
#define _DDLinkList_H_
typedef void DLinkList;
typedef struct DLinkListNode   //声明指针域
{
        DLinkListNode * pre;
        DLinkListNode * next;
}DLinkListNode;

DLinkList * DLinkList_Create();

void DLinkList_DesTroy(DLinkList * list);

void DLinkList_Clear(DLinkList* list);

int DLinkList_Length(DLinkList* list);

int DLinkList_Insert(DLinkList* list, DLinkListNode* node, int pos);

DLinkListNode* DLinkList_Get(DLinkList* list, int pos);

DLinkListNode* DLinkList_Delete(DLinkList* list, int pos);

DLinkListNode* DLinkList_DeleteNode(DLinkList* list, DLinkListNode* node);

DLinkListNode* DLinkList_Reset(DLinkList* list);

DLinkListNode* DLinkList_Current(DLinkList* list);

DLinkListNode* DLinkList_Next(DLinkList* list);

DLinkListNode* DLinkList_Pre(DLinkList* list);

#endif

源文件：

// 双向链表.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include "DLinkList.h"
#include <stdlib.h>
#include <malloc.h>

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

struct Value
{
    DLinkListNode header; //指针域
    int v; //数据域
};

int _tmain(int argc, _TCHAR* argv[])
{
         int i = 0;
    DLinkList* list = DLinkList_Create();//创建链表
    struct Value* pv = NULL;
    struct Value v1;
    struct Value v2;
    struct Value v3;
    struct Value v4;
    struct Value v5;
   
    v1.v = 1;
    v2.v = 2;
    v3.v = 3;
    v4.v = 4;
    v5.v = 5;
    //插入5个数
    DLinkList_Insert(list, (DLinkListNode*)&v1, DLinkList_Length(list));
    DLinkList_Insert(list, (DLinkListNode*)&v2, DLinkList_Length(list));
    DLinkList_Insert(list, (DLinkListNode*)&v3, DLinkList_Length(list));
    DLinkList_Insert(list, (DLinkListNode*)&v4, DLinkList_Length(list));
    DLinkList_Insert(list, (DLinkListNode*)&v5, DLinkList_Length(list));
   
    for(i=0; i<DLinkList_Length(list); i++)
    {
        pv = (struct Value*)DLinkList_Get(list, i);
        
        printf("插入了：%d\n", pv->v);
    }
   
    printf("\n");
    //删除头尾
    DLinkList_Delete(list, DLinkList_Length(list)-1);
    DLinkList_Delete(list, 0);
    printf("删除头尾结点后：\n");
    for(i=0; i<DLinkList_Length(list); i++)
    {
                pv = (struct Value*)DLinkList_Next(list);
        
        printf("%d\n", pv->v);
    }
   
    printf("\n");
   
    DLinkList_Reset(list);//游标指向第一个结点   2
    DLinkList_Next(list);//游标指向第二个结点    3
   
    pv = (struct Value*)DLinkList_Current(list);
   
    printf("游标移到第二个结点后的值： %d\n", pv->v);
   
    DLinkList_DeleteNode(list, (DLinkListNode*)pv);//删除第二个结点
   
    pv = (struct Value*)DLinkList_Current(list);
   
    printf("游标删除第二个结点后的值： %d\n", pv->v);
   
    DLinkList_Pre(list); //将游标向前移动一位
   
    pv = (struct Value*)DLinkList_Current(list);
   
    printf("游标向前移了一位后的值：%d\n", pv->v);
   
    printf("Length: %d\n", DLinkList_Length(list));
   
    DLinkList_DesTroy(list);
        system("pause");
        return 0;
}

//创建
DLinkList * DLinkList_Create()
{
        TDLinkList* list = NULL;
        list = (TDLinkList*)malloc(sizeof(TDLinkList));
        if(NULL != list)
        {
                list->len = 0;
                list->header.next = NULL;
                list->header.pre = NULL;
                list->slider = NULL;
        }
        return list;
}

//销毁
void DLinkList_DesTroy(DLinkList * list)
{
        free(list);
}

//清空
void DLinkList_Clear(DLinkList* list)
{
        TDLinkList* sList = (TDLinkList*)list;
        if(NULL != sList)
        {
                sList->len = 0;
                sList->header.next = NULL;
                sList->header.pre = NULL;
                sList->slider = NULL;
        }
}

//获得长度
int DLinkList_Length(DLinkList* list)
{
        TDLinkList* sList = (TDLinkList*)list;
        int len = -1;
        if(NULL != sList)
        {
                len = sList->len;
        }
        return len;
}

//插入
int DLinkList_Insert(DLinkList* list, DLinkListNode* node, int pos)
{
        TDLinkList* sList = (TDLinkList*)list;
       
        int i = 0;
        int ret = 0;
        if((NULL != sList) && (pos >= 0) && (NULL != node))
        {
                DLinkListNode* current = (DLinkListNode*)sList;
                DLinkListNode* next = NULL;
                for( i=0; (i<pos) && (current->next != NULL); i++)
                {
                        current = current->next;
                }
                next = current->next;
                current->next = node;
                node->next = next;
                if(NULL != next)
                {
                        next->pre = node;
                }
                node->pre = current;

                if(sList->len == 0)
                {
                        node->pre = NULL;
                        sList->slider = node;
                }
                sList->len++;
                ret = 1;
        }
        return ret;
}

//获得结点
DLinkListNode* DLinkList_Get(DLinkList* list, int pos)
{
        TDLinkList* sList = (TDLinkList*)list;
        int i = 0;
        DLinkListNode * resnode  = NULL;
        if((pos >= 0) && (pos < sList->len) && (NULL != sList))
        {
                DLinkListNode * current = (DLinkListNode*)sList;
                for ( i=0; i<pos; i++)
                {
                        current = current->next;
                }
                resnode = current->next;
        }
        return resnode;
}

//删除
DLinkListNode* DLinkList_Delete(DLinkList* list, int pos)
{
        TDLinkList* sList = (TDLinkList*)list;
        int i = 0;
        DLinkListNode* ret = NULL;
        if((NULL != sList) && (pos >= 0) && (pos < sList->len))
        {
                DLinkListNode* current = (DLinkListNode*)sList;
                DLinkListNode* next = NULL;
                for ( i=0; i<pos; i++)
                {
                        current = current->next;
                }
                ret = current->next;
                next = ret->next;

                current->next = next;
                if(NULL != next)
                {
                        next->pre = current;
                        //当删除的结点是第一个结点的时候
                        if(current == (DLinkListNode*)sList)
                        {
                                //前驱指针为空
                                next->pre = NULL;       
                        }
                }
                if(sList->slider == ret)
                {
                        sList->slider = next;
                }
                sList->len--;
        }
        return ret;
}

//通过指定结点删除
DLinkListNode* DLinkList_DeleteNode(DLinkList* list, DLinkListNode* node)
{
        TDLinkList* sList = (TDLinkList*)list;
        DLinkListNode* ret = NULL;
        int i = 0;
        if((NULL != sList) && (NULL != node))
        {
                DLinkListNode* current = (DLinkListNode*)sList;
                for ( i=0; i<sList->len; i++)
                {
                        if(current->next == node)
                        {
                                ret = current->next;
                                break;
                        }
                        current = current->next;
                }
                if( ret != NULL )
        {
            DLinkList_Delete(sList, i);
        }
        }
        return ret;
       
}

//重置游标，使其到第一个结点处
DLinkListNode* DLinkList_Reset(DLinkList* list)
{
        TDLinkList* sList = (TDLinkList*)list;
        DLinkListNode* ret = NULL;
        if((NULL != sList))
        {
                sList->slider = sList->header.next;
                ret = sList->slider;
        }
        return ret;
}

//将游标移至当前结点处
DLinkListNode* DLinkList_Current(DLinkList* list)
{
        TDLinkList* sList = (TDLinkList*)list;
        DLinkListNode* ret = NULL;
        if(NULL != sList)
        {
                ret = sList->slider;
        }
        return ret;
}

//
DLinkListNode* DLinkList_Next(DLinkList* list)
{
        TDLinkList* sList = (TDLinkList*)list;
        DLinkListNode* ret = NULL;
        if((NULL != sList) && (NULL != sList->slider ))
        {
                ret = sList->slider;
                sList->slider = ret->next;
        }
        return ret;
}

DLinkListNode* DLinkList_Pre(DLinkList* list)
{
        TDLinkList* sList = (TDLinkList*)list;
        DLinkListNode* ret = NULL;
        if((NULL != sList) && (NULL != sList->slider ))
        {
                ret = sList->slider;
                sList->slider = ret->pre;
        }
        return ret;
}

运行结果：

插入了：1
插入了：2
插入了：3
插入了：4
插入了：5

删除头尾结点后：
2
3
4

游标移到第二个结点后的值： 3
游标删除第二个结点后的值： 4
游标向前移了一位后的值：2
Length: 2
请按任意键继续. . .

[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课