数据结构——双向链表-拓冰建站

双向链表

1.双向链表的定义

我们之前学过单链表，也就是无头单向非循环链表。那么我们今天学的是带头双向循环链表。虽然它的结构相较于单链表复杂一些，但在实际应用中具有很好的应用意义。

带头的意思就是带有一个哨兵位的头结点，此结点用来存放头结点，不存放有效数据。之前单向链表只可以指向下一个链表，双向就可以指向上一个。循环则是指可以从最后一个链表循环到第一个。

定义代码如下：

typedef int LTDataType;
typedef struct ListNode
{struct ListNode* next;struct ListNode* prev;LTDataType data;
}LTNode;

2.双向链表的基本操作

（1）双向链表建立结点

LTNode* BuyLTNode(LTDataType x)
{LTNode* node = (LTNode*)malloc(sizeof(LTNode));if (node == NULL){perror("malloc fail");exit(-1);}node->data = x;node->next = NULL;node->prev = NULL;return node;
}

（2）双向链表的初始化

LTNode* LTInit()
{LTNode* phead = BuyLTNode(0);phead->next = phead;phead->prev = phead;return phead;
}

（3）打印双向链表

这里有个很有意思的地方，注意看循环判断条件是：cur！=phead，也就是说当cur==phead的时候跳出循环。这是因为这是一个循环链表，当cur==phead的时候说明已经又到了头结点，说明已经遍历结束了。大家可以再体会一下这个思想。

void LTPrint(LTNode* phead)
{assert(phead);printf("phead<=>");LTNode* cur = phead->next;while (cur != phead){printf("%d<=>", cur->data);cur = cur->next;}printf("\n");
}

（4）双向链表的尾插

要实现尾插，我们只需要找到尾，按照双向循环链表的特点，head的prev指向尾结点，所以我们定义一个tail指针，从而实现尾插。

void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* tail = phead->prev;LTNode* newnode = BuyLTNode(x);newnode->prev = tail;tail->next = newnode;newnode->next = phead;phead->prev = newnode;/*LTInsert(phead, x);*/
}

（5）双向链表的头插


void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);/*LTNode* newnode = BuyLTNode(x);newnode->next = phead->next;phead->next->prev = newnode;phead->next = newnode;newnode->prev = phead;*/LTNode* newnode = BuyLTNode(x);LTNode* first = phead->next;// phead newnode firstphead->next = newnode;newnode->prev = phead;newnode->next = first;first->prev = newnode;/*LTInsert(phead->next, x);*/
}

（6）双向链表的尾删

尾删只需要找到尾结点，再将尾结点的前驱节点记录下来，然后释放尾结点，再将前驱和头结点之间连接起来就可以实现。

void LTPopBack(LTNode* phead)
{assert(phead);assert(phead->next != phead);LTNode* tail = phead->prev;LTNode* tailPrev = tail->prev;free(tail);tailPrev->next = phead;phead->prev = tailPrev;/*LTErase(phead->prev);*/
}

（7）双向链表的头删

大家思考一下，怎么进行头删？是不是和尾删是一样的思路，只不过这次找到的是第一个结点和第二个结点，释放第一个结点，然后改变头结点和第二个结点的指向关系。

void LTPopFront(LTNode* phead)
{assert(phead);assert(phead->next != phead);//LTNode* first = phead->next;//LTNode* second = first->next;//free(first);//phead->next = second;//second->prev = phead;LTErase(phead->next);
}

（8）获取双向链表的数据个数

int LTSize(LTNode* phead)
{assert(phead);int size = 0;LTNode* cur = phead->next;while (cur != phead){++size;cur = cur->next;}return size;
}

（9）pos位置之前进行插入

// pos之前插入
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* posPrev = pos->prev;LTNode* newnode = BuyLTNode(x);posPrev->next = newnode;newnode->prev = posPrev;newnode->next = pos;pos->prev = newnode;
}

（10）在pos位置进行删除

// 删除pos位置
void LTErase(LTNode* pos)
{assert(pos);LTNode* posPrev = pos->prev;LTNode* posNext = pos->next;free(pos);posPrev->next = posNext;posNext->prev = posPrev;
}

（11）双向链表的销毁

void LTDestroy(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){LTNode* next = cur->next;free(cur);cur = next;}free(phead);phead = NULL;
}