书上并没有详细的实现所有代码，考试也不侧重于详细考这部分的细节，不过为了善始善终，本帖还是来写一下吧。基于之前的单链表改装一下就行~

---

一.定义和初始化

和单链表几乎一样，只不过加了一个指向前驱的指针：

typedef struct DoubleLinkNode{//定义一个双链表的节点类型 
	int data;
	DoubleLinkNode *next,*prior;
}DNode,*DoubleList;

这里仍然用带头节点的指针，初始化的时候其前驱和后继均为NULL即可，物理意义上也满足头结点没有前驱的逻辑：

void InitList(DoubleList &D){
	D=(DoubleList)malloc(sizeof(DNode));
	D->next=NULL;
	D->prior=NULL;
	return;
}

二.求表长和遍历

求表长和单链表几乎相等，同样注意即便头结点不存储数据，但依然记作链表的一员：

int CountLength(DoubleList &D){
	int length=0;
	DNode *p=D;//注意，长度是要包含头结点的！
	while(p!=NULL){
		p=p->next;
		length++;
	} 
	return length;
}

然后是打印链表：

void PrintList(DoubleList &D){
	DNode *p=D->next;//从头结点的后一位开始遍历
	while(p!=NULL)
	{
		cout<<p->data<<" ";
		p=p->next;	
	} 
}

由于双链表具有双向指针，那么我们也可以逆序遍历，实现逆序打印如下：

void ReversePrint(DoubleList &D) { 
    // 先找到最后一个节点
    DNode *p = D->next;
    while (p->next != NULL) {
        p = p->next;
    }
    // 从后向前遍历
    while (p != D) {  // 直到头节点停止
        cout << p->data << " ";
        p = p->prior;
    }
    cout << endl;
}

三.增加元素

重中之重，可以说如果考试考双链表，近乎99%的概率考的就是插入节点后修改指针的那4个顺序，各位直接按照教材上的那种模式即可，这里我写的可能不尽相同。首先单独实现一个每次将节点插入到表头——即头结点后面的操作：

void InsertHead(DoubleList &D, int value) {
    DNode *newNode = (DNode*)malloc(sizeof(DNode));
    newNode->data = value;
    newNode->next = NULL;
    newNode->prior = NULL;
    
    // 插入到链表头部,也即每次都插在头结点后面！ 
    if (D->next != NULL) {
        D->next->prior = newNode;
    }
    newNode->next = D->next;
    newNode->prior = D;
    D->next = newNode;
}

然后是在指定Loc插入节点——这里面涉及到那个经典的修改4指针的操作：

void Insert(DoubleList &D, int loc, int value) {
    DNode *s = (DNode*)malloc(sizeof(DNode));
    s->data = value;
    s->next = NULL;
    s->prior = NULL;
    // 找到插入位置的前一个节点
    DNode *p = D;
    int i = 0;
    while (p->next!=NULL&&i<=loc-2) {//位序为loc实际上是下标loc-1，因此我们要找到前一个下标loc-2 
        p = p->next;
        i++;
    }
    // 插入新节点
    s->next = p->next;
    s->prior= p;
    if (p->next != NULL) {//如果p原来的后继不是空节点，则其前驱应该是新插入进来的s！ 这样写的作用不用额外处理头结点~ 
        p->next->prior = s;
    }
    p->next = s;
}

我这里还添加了边界值判断条件，实际考试不会这么复杂，选择题大概率是在链表中间插入，而大题实际上也对边界值判断要求没那么严格，毕竟不是某些自命题考察程序设计。

四.删除元素

单链表需要我们找到被删节点的前一个节点，但双链表可以直接找到某一个节点的前驱，因此我们直接定位到删除为止即可。这里使用的是按位序删除，各位也可以实现按值删除，非常easy：

void  Delete(DoubleList &D, int loc){
	//由于是双链表，因此我们直接定位到该点处即可 
    DNode *p = D;
    int i = 0;
    while (p->next!=NULL&&i<=loc-1) {
        p = p->next;
        i++;
    }
    if (p == NULL) return; // 位置超出范围
    p->prior->next=p->next;
    if (p->next != NULL)
    	p->next->prior=p->prior;
    free(p);   
} 

五.修改元素

修改就更加简单了，找到以后直接修改数据域就行：

void Alter(DoubleList &D, int loc,int value){
	DNode *p = D;
    int i = 0;
    while (p->next!=NULL&&i<=loc-1) {
        p = p->next;
        i++;
    }
    if (p == NULL) return; // 位置超出范围
    p->data=value;
}

六.查询元素

同样简单，这里实现了查指定位序的值，也可以根据值查找位序：

int Search(DoubleList &D, int loc){
	DNode *p = D;
    int i = 0;
    while (p->next!=NULL&&i<=loc-1) {
        p = p->next;
        i++;
    }
    if (p == NULL) 
		return -999; // 位置超出范围
    return p->data; 
}

---

最后给一下测试用例，该带的头文件各位心里清楚，这里不再赘述~

int main(int argc, char** argv) {
	DoubleList D; 
	InitList(D);
    InsertHead(D, 111);
    InsertHead(D, 222);
    InsertHead(D, 333);
    Insert(D,2,1325);
	Insert(D,2,1325);
    Delete(D,2);
    Alter(D,2,2513);
    cout<<Search(D,4)<<endl;
    PrintList(D);  
	cout<<endl;
	ReversePrint(D);
	return 0;
}