数据结构：C语言实现----带头双向链表总结

双向链表结构体声明

typedef struct DNode
{int data;struct DNode *prior;struct DNode *next;
} DNode, *DLinkList;

（1)初始化

void InitDulList(DLinkList plist)
{assert(plist != NULL);if(plist == NULL)return;plist->prior=plist->next=NULL;
}

（2）静态函数：申请节点内存

static DLinkList ApplyNode(DLinkList next, DLinkList prior, int val)
{DLinkList s=(DNode *) malloc (sizeof (DNode));assert(s != NULL);if(s == NULL)return NULL;s->data=val;s->next=next;s->prior=prior;return s;
}

（3）求链表长度

int Listlength(DLinkList plist)
{assert(plist != NULL);if(plist == NULL)return -1;int count = 0;DLinkList p=plist->next; //p指向头的下一个，即第一个有效结点while(p != NULL){count++;p=p->next;}return count;
}

（4）得到某个结点，函数返回该结点

DLinkList GetNode(DLinkList plist, int pos)
{assert(plist != NULL);if(plist == NULL)return NULL;if(pos < 0)return NULL;DLinkList p=plist;while(pos && p != NULL){p=p->next;pos--;}return p;
}

（5）插入

void Insert(DLinkList plist, int pos, int val)
{assert(plist != NULL);if(plist == NULL)return;DLinkList p = GetNode(plist, pos); //要插入其后的结点的位置DLinkList s = ApplyNode(p->next, p, val); //要插入的结点if(p->next != NULL) //尾插单独考虑{p->next->prior=s;	}p->next = s;
}

（6）头插

void InsertHead(DLinkList plist, int val)
{assert(plist != NULL);if(plist == NULL)return; DLinkList s=ApplyNode(plist->next, plist, val);if(plist->next != NULL) //若此时链表内没有有效数据，为空链{plist->next->prior = s;}plist->next = s;
}

（7）尾插

void InsertTail(DLinkList plist, int val)
{assert(plist != NULL);if(plist == NULL)return;Insert(plist, Listlength(plist), val);
}

（8）删除

void Delete(DLinkList plist, int pos)
{assert(plist != NULL);if(plist == NULL)return;if(pos<0 || pos>Listlength(plist)){return;}DLinkList p=GetNode(plist,pos); //要删除的结点if(p == NULL || p == plist) return;p->prior->next=p->next; if(p->next != NULL) //尾删无next{p->next->prior=p->prior;}free(p);
}

（9）头删

void DeleteHead(DLinkList plist)
{assert(plist != NULL);if(plist == NULL)return;Delete(plist,1);
}

（10）尾删

void DeleteTail(DLinkList plist)
{assert(plist != NULL);if(plist == NULL)return;Delete(plist,Listlength(plist));
}

（11）判空

int ListEmpty(DLinkList plist)
{assert(plist != NULL);if(plist == NULL)return -1;if(plist->next == NULL)return -1;return 0;
}

（12）清空链表 

void ClearList(DLinkList plist)
{assert(plist != NULL);if(plist == NULL)return;while(!ListEmpty(plist)){DeleteHead(plist);}
}

（13）输出

void Show(DLinkList plist)
{assert(plist != NULL);if(plist == NULL)return;DLinkList p=plist->next;while(p != NULL){printf("%d -->",p->data);p=p->next;}printf("NULL\n");
}