单向链表和双向链表的原理及其相关实现

（一）什么是链表？

链表是线性表的一种，所谓的 线性表包含顺序线性表和链表，顺序线性表是用数组实现的，在内存中有顺序排列，通过改变数组大小实现。而链表不是用顺序实现的，用指针实现，在内存中不连 续。意思就是说，链表就是将一系列不连续的内存联系起来，将那种碎片内存进行合理的利用，解决空间的问题。

所以，链表允许插入和删除表上任意位置上的节点，但是不允许随即存取。链表有很多种不同的类型：单向链表、双向链表及循环链表。

1、那么先从单向链表着手，先看看单向链表的模拟图：

单向链表包含两个域，一个是信息域，一个是指针域。也就是单向链表的节点被分成两部分，一部分是保存或显示关于节点的信息，第二部分存储下一个节点的地址，而最后一个节点则指向一个空值。

2、双向链表：

从上图可以很清晰的看出，每 个节点有2个链接，一个是指向前一个节点（当此链接为第一个链接时，指向的是空值或空列表），另一个则指向后一个节点（当此链接为最后一个链接时，指向的 是空值或空列表）。意思就是说双向链表有2个指针，一个是指向前一个节点的指针，另一个则指向后一个节点的指针。

3、循环链表：

循环链表就是首节点和末节点被连接在一起。循环链表中第一个节点之前就是最后一个节点，反之亦然。

（二）链表有什么作用？

链表本质上就是一种数据结构，主要用来动态放置数据。也可用来构建许多数据结构，比如堆栈、队列及它们的派生。

（三）链表的实现？

1、单向链表的实现

（1）单向链表的创建过程：

第一步：定义节点的数据结构；

第二步：创建一个空表。

第三步：利用malloc（）向系统申请分配一个节点。

第四步：将新节点的指针成员赋值为空。若是空表，将新节点连接到表头；若是非空表，将新节点连接到表尾。

第五步：判断是否有后续节点，如有则转入第三步，否则结束。

（2）单向链表的输出过程：

第一步：找到表头。

第二步：若为非空表，则输出节点的值成员，是空表则退出。

第三步：跟踪链表，找到下一节点的地址。

第四步：转到第二步。

#include <stdio.h>
#include <conio.h>

struct date//申明结构体
{
    char str;
    date *prior;
    date *next;//用来指向下一个结构体指针
};

int main()
{
    date *pS,*pE,*head;//定义三个结构体指针,head用来保存链头,pE保存链尾
    date *Rhead = NULL;//定义读取结构体指针
    pE = head;//刚开始没有任何结点,指向表头
    char temp;
    scanf("%c",&temp);
    if(temp != '#')
    {
        head = new date;//新建结点
        head->str = temp;//给新结点赋值数据
        head->prior = NULL;
        head->next = NULL;
        pS = head;
    }

    scanf("%c",&temp);
    while (temp != '#')
    {
            pS = new date;//新建结点
            pS->str = temp;//给新结点赋值数据
            pS->prior = pE;
            pS->next = NULL;//让指向下一个为空(新结点,也就是新链尾)
            pE->next = pS;//把新结点连接到链尾
            pE = pS;//新结点成为了新的链尾
    }
    printf("
刚才输入的是:
");
    Rhead = head;//取得链头
    /*
        当然也可以直接用head不过这样就会改变其值,而无法再次查找链表
        切忌链头的重要性,只要找不到链头,整条链表就没用!
    */
    while (Rhead != NULL)//循环到链尾
    {
        printf("%c",Rhead->str);
        if (Rhead!=NULL)
        {
            Rhead = Rhead->next;//让其指向下一个链表
        }
    }

    printf("
");
    getch();
    return 0;
}

以上程序代码参考http://blog.csdn.net/duke56/article/details/5764614，比起其他实现，这个很直观明了。

2、双向链表的实现

#include"stdio.h"
#include"stdlib.h"

typedef int DataType;//双向链表中数据的类型
typedef struct DNode
{
    DataType element;
    struct DNode *prior,*next;
}DNode,*DoubleList;//定义双向链表中一个节点

DoubleList createDList()//创建双向链表
{
    DoubleList head,p1,p2;
    DataType data;
    scanf("%d",&data);
    if(data!=0)//初始化头结点
    {
        head=(DoubleList)malloc(sizeof(DNode));
        head->element=data;            //         head
        head->prior=NULL;      //----------------------
        head->next=NULL;       //|prior| data |  next |
        p1=head;               // -----------------------
    }                              //         p1
    else
    {
        return NULL;//如果是0的话，直接跳出去，后面的工作一律不再进行
    }
    scanf("%d",&data);
    while(data!=0)
    {                                            //        head             p2
        p2=(DoubleList)malloc(sizeof(DNode));//-----------------   -----------------
        p2->element=data;                    //|prior|data|next|-->|prior|data|next|
        p2->prior=p1;                        //-----------------    -----------------
        p2->next=NULL;                       //                           p1
        p1->next=p2;
        p1=p2;
        scanf("%d",&data);                   //其实p1的作用就是为了把后面的
    }                                            //节点依次连接到双向链表的尾部
        return head;
}

DoubleList delDList(DoubleList head,DataType data)//删除链表某个节点，该节点的值等于data
{
    DoubleList p;
    if(head==NULL)
    {
    return NULL;
    }
    if(data==0)
    {
        printf("please input the data which will be deleted!
");
        scanf("%d",&data);
    }
        p=head;//让p指向头结点，p在双向链表上移动，完成相应的操作
    while(p!=NULL&& p->element!=data)//用p->element!=data而不是p->element=data，
    {                                //是想让p在循环的控制下，在双向链表上不断移动
        p=p->next;
    }
    if(p!=NULL)
    {
    if(p==head)//如果第一次的时候就跳出来的话，p肯定指向的是head
    {
        head=p->next;//删除头结点
        head->prior=NULL;
        free(p);
    }
    else
    {
    if(p->next==NULL)//已经找到最后一个节点了才找到
    {
        (p->prior)->next=NULL;
        free(p);
    }
    else //中间某个节点上找到了要删除的节点
    {
        p->prior->next=p->next; //语句1  1和2次序很关键，绝对不能颠倒
        p->next->prior=p->prior;//语句2
        free(p);
    }
    }
    }
    else
    {
        printf("we can not find the element that you want to find!
");
    }
    return head;
}

void printDList(DoubleList head)
{
    DoubleList p=head;
    while(p!=NULL)
    {
        printf("%d	",p->element);
        p=p->next;
    }
    printf("
");
}

void freeDList(DoubleList head)
{
    DoubleList p;
    if(head==NULL)
    {
        return;
    }
    while(head!=NULL)
    {
        p=head->next;
        free(head);
        head=p;
    }
}

int main(void)
{
    DoubleList head;
    printf("please input the interge,and create the Doublelist! 
");
    head=createDList();
    printf("print the Doublelist you have created!
");
    printDList(head);
    printf("delete the Doublelist!
");
    head=delDList(head,0);//delDList()函数有返回值
    printf("print the Doublelist you have deleted!
");
    printDList(head);
    freeDList(head);
}