写在前面
书接上文，上次我在闵老和各位大佬的引导下学习了单链表，这次触类旁通，开始学习双链表的相关知识。这里为了方便期末考前的复习，先做一个对比。
单链表：
轻松的到达下一个节点,艰难的回到前一个结点；轻松的单向便利，困难(基本不可能）双向便利
双链表
1.操作稍复杂(because:每次在插入或删除某个节点时, 需要处理四个节点的引用, 而不是两个)
2.占用内存空间更大一些.
3.轻松从头遍历到尾, 轻松从尾遍历到头
再接下来是一个小小的概念引入(搬运自百度）
双链表也叫双向链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。
双链表中各节点包含以下 3 部分信息：
指针域：用于指向当前节点的直接前驱节点；
数据域：用于存储数据元素。
指针域：用于指向当前节点的直接后继节点；
接下来，废话不多说，上代码(闵版）
#include
#include
typedef struct DoubleLinkedNode{
char data;
struct DoubleLinkedNode *previous;
struct DoubleLinkedNode *next;
} DLNode, *DLNodePtr;
DLNodePtr initLinkList(){
DLNodePtr tempHeader = (DLNodePtr)malloc(sizeof(struct DoubleLinkedNode));
tempHeader->data = ‘\0’;
tempHeader->previous = NULL;
tempHeader->next = NULL;
return tempHeader;
}
void printList(DLNodePtr paraHeader){
DLNodePtr p = paraHeader->next;
while (p != NULL) {
printf(“%c”, p->data);
p = p->next;
}
printf(“\r\n”);
}
void insertElement(DLNodePtr paraHeader, char paraChar, int paraPosition){
DLNodePtr p, q, r;
p = paraHeader;
for (int i = 0; i < paraPosition; i ++) {
p = p->next;
if (p == NULL) {
printf(“The position %d is beyond the scope of the list.”, paraPosition);
return;
}
}
q = (DLNodePtr)malloc(sizeof(struct DoubleLinkedNode));
q->data = paraChar;
r = p->next;
q->next = p->next;
q->previous = p;
p->next = q;
if (r != NULL) {
r->previous = q;
}
}
void deleteElement(DLNodePtr paraHeader, char paraChar){
DLNodePtr p, q, r;
p = paraHeader;
while ((p->next != NULL) && (p->next->data != paraChar)){
p = p->next;
}
if (p->next == NULL) {
printf(“The char ‘%c’ does not exist.\r\n”, paraChar);
return;
}
q = p->next;
r = q->next;
p->next = r;
if (r != NULL) {
r->previous = p;
}
free(q);
}
void insertDeleteTest(){
DLNodePtr tempList = initLinkList();
printList(tempList);
insertElement(tempList, ‘H’, 0);
insertElement(tempList, ‘e’, 1);
insertElement(tempList, ‘l’, 2);
insertElement(tempList, ‘l’, 3);
insertElement(tempList, ‘o’, 4);
insertElement(tempList, ‘!’, 5);
printList(tempList);
deleteElement(tempList, ‘e’);
deleteElement(tempList, ‘a’);
deleteElement(tempList, ‘o’);
printList(tempList);
insertElement(tempList, ‘o’, 1);
printList(tempList);
}
void basicAddressTest(){
DLNode tempNode1, tempNode2;
tempNode1.data = 4;
tempNode1.next = NULL;
tempNode2.data = 6;
tempNode2.next = NULL;
printf(“The first node: %d, %d, %d\r\n”,
&tempNode1, &tempNode1.data, &tempNode1.next);
printf(“The second node: %d, %d, %d\r\n”,
&tempNode2, &tempNode2.data, &tempNode2.next);
tempNode1.next = &tempNode2;
}
int main(){
insertDeleteTest();
basicAddressTest();
return 0;
}
几点说明：
1.可能是我自己dev的问题，在调用dev时只允许以int main()的形式调用，不然会报错。有鉴于此，我将闵老代码末尾的void main()进行了修改。
2.在我的电脑上运行时，地址显示的结果与闵老在csdn中的地址有所不同，不过据我推测，可能不同电脑、不同操作系统对内存的分配可能会有所不同，因此应该是正常的现象，所以没有进行修改。(本人知识水平有限，观点仅供参考）
————————————华丽的分割线——————————
（特别说明，以下内容，出于本人对int类型的热爱，链表中元素均以Int类呈现）
一些小小的原理剖析
1.对删除函数的理解，分析
先上图
删除是双链表中一个比较无脑的操作，为啥呢，因为你只需遍历链表找到要删除的结点，然后将该节点从表中直接”删了”(不是字面意思！！)即可
代码
Node * DeleteList(Node * head,int data)
{
Node * temp=head;
/*遍历链表*/
while (temp)
{
if (temp->data==data)
{
/*判断是否是头结点*/
if(temp->pre == NULL)
{
head=temp->next;
temp->next = NULL;
free(temp);
return head;
}
/*判断是否是尾节点*/
else if(temp->next == NULL)
{
temp->pre->next=NULL;
free(temp);
return head;
}
else
{
temp->pre->next=temp->next;
temp->next->pre=temp->pre;
free(temp);
return head;
}
}
temp=temp->next;
}
printf(“找不到，请重输！！！%d!\r\n”,data);//当然，作为一个合格的文明人，这里可以用一些文明的语句替换
return head;
}
2.对插入函数的理解，分析
插入函数的实现并不简单，所以我把它放到最后来讲。当然了，这只是相对于删除函数而言的，本质其实也和单链表差不多。也是那么两步：新节点先与其直接后继节点建立双层逻辑关系；
新节点的直接前驱节点与之建立双层逻辑关系；
之所以说它比删除函数复杂，主要体现在情况的多变，插到头，中，尾代码上是有比较大的去别的。
头、尾
这两种情况本质上是一样的，图示如下
头
尾
中
其操作的核心，其实已经在上文点出来了(即上文，双链表插入函数构建的核心思想部分),这里不再多说
代码实现如下：
/*在第add位置的前面插入data节点*/
Node * InsertListHead(Node * head,int add,int data)
{
/*新建数据域为data的结点*/
Node * temp=(Node*)malloc(sizeof(Node));
if(temp== NULL)
{
printf(“malloc error!\r\n”);
return NULL;
}
else
{
temp->data=data;
temp->pre=NULL;
temp->next=NULL;
}
/*插入到链表头，要特殊考虑*/
if (add==1)
{
temp->next=head;
head->pre=temp;
head=temp;
}
else
{
Node * body=head;
/*找到要插入位置的前一个结点*/
for (int i=1; i {
body=body->next;
}
/*判断条件为真，说明插入位置为链表尾*/
if (body->next==NULL)
{
body->next=temp;
temp->pre=body;
}
else
{
body->next->pre=temp;
temp->next=body->next;
body->next=temp;
temp->pre=body;
}
}
return head;
}
/*在第add位置的后面插入data节点*/
Node * InsertListEnd(Node * head,int add,int data)
{
int i = 1;
/*新建数据域为data的结点*/
Node * temp=(Node*)malloc(sizeof(Node));
temp->data=data;
temp->pre=NULL;
temp->next=NULL;
Node * body=head;
while ((body->next)&&(i {
body=body->next;
i++;
}
/*判断条件为真，说明插入位置为链表尾*/
if (body->next==NULL)
{
body->next=temp;
temp->pre=body;
temp->next=NULL;
}
else
{
temp->next=body->pre->next;
temp->pre=body->pre;
body->next->pre=temp;
body->pre->next=temp;
}
return head;
}
我的一些小小的升级
增设查找函数
通常，双向链表同单链表一样，都仅有一个头指针。因此，双链表查找指定元素的实现同单链表类似，都是从表头依次遍历表中元素。(但是，由前文可知，双链表可以轻松的双向遍历，所以这应该这是一种约定俗成，理论上，我觉得从后往前遍历，一样是可以实现的）
代码实现：
/*head为原双链表，elem表示被查找元素*/
int FindList(Node * head,int elem)
{
/*新建一个指针t，初始化为头指针 head*/
Node * temp=head;
int i=1;
while (temp)
{
if (temp->data==elem)
{
return i;
}
i++;
temp=temp->next;
}
/*失败情形*/
return -1;
}
增设更改节点函数
更改双链表中指定结点数据域的操作是在查找的基础上完成的。通过遍历找到存储有该数据元素的结点，直接更改其数据域即可。
代码：
/*说明：add 表示更改结点在双链表中的位置，newElem 为新数据的值*/
Node *ModifyList(Node * p,int add,int newElem)
{
Node * temp=p;
/*遍历到被删除结点*/
for (int i=1; i {
temp=temp->next;
}
temp->data=newElem;
return p;
}