数据结构-双向链表-阿里云开发者社区

1.头文件中的声明：

首先我们需要写一个结构体，双向带头链表的话需要一个前驱指针prev和一个后驱指针next，前驱指针的作用是方便找尾节点，因为头节点的prev指向的就是最后一个节点，后驱指针next的作用是方便插入和找头节点。

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int LTDataType;
typedef struct Listnode
{
  struct ListNode* prev;
  struct ListNode* next;
  LTDataType data;
}LTNode;
LTNode* BuyLTNode(LTDataType x);//创建节点
LTNode* LTInit();//初始化
void LTPrint(LTNode* phead);//打印
void LTPushBack(LTNode* phead, LTDataType x);//尾插
void LTPopBack(LTNode* phead);//尾删
void LTPushFront(LTNode* phead, LTDataType x);//头插
void LTPopFront(LTNode* phead);//头删
int LTSize(LTNode* phead);//求有效数据
LTNode* LTFind(LTNode* phead, LTDataType x);
void LTInsert(LTNode* pos ,LTDataType x);//在pos位置之前插入x
void LTErase(LTNode* pos);//在pos位置删除
void LTDestroy(LTNode* phead);

2.带头双向链表的实现

2.1创建新节点

创建一个节点比较简单，首先malloc一块空间出来，然后将这个结构体的数据data设置成需要的数据，再将前驱指针和后驱指针全部置空就行，方便后续链接。

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.2链表初始化

双向带头链表的初始化肯定需要一个头节点，所以使用BuyLTNode创建一个头节点phead，然后将phead的next指向自己，prev也指向自己。

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

2.3打印链表

打印链表也很简单，只需要创建一个结构体指针cur来遍历链表就可以了，循环的结束条件是cur为phead，为什么呢？因为尾节点的next不为NULL，而是头指针，如果条件设置为NULL的话，就会陷入死循环，所以当cur走到头节点的话就代表已经遍历完一遍了。

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

2.4尾插

假设当前节点是这样的情况，我们要插入一个newnode，怎么尾插呢？这个时候我们就通过头节点phead找到尾节点n3，然后再尾插就可以了。首先定义一个结构体指针tail来找n3，然后将newnode进行链接，首先将newnode与tail进行链接，newnode->prev=tail,tail->next=newnode,再将newnode与phead进行链接，phead->prev=newnode,newnode->next=phead,然后newnode就在这个链表上完成尾插了。

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;
}

2.5尾删

尾删的话不仅要找到尾节点，还需要找到尾节点的前一个节点,所以创建一个尾节点tail,尾节点的前一个节点tailprev(tailprev=tail->prev)，然后将tailprev与头节点进行链接，phead->prev=tailprev,tailprev->next=phead。

void LTPopBack(LTNode* phead)
{
  assert(phead);
  assert(phead->next != phead);
  LTNode* tail = phead->prev;
  LTNode* pretail = tail->prev;
  phead->prev = pretail;
  pretail->next = phead;
}

2.6头插

头插需要找到第一个节点，所以创建一个结构体指针tail指向第一个节点(tail=phead->next)，然后将newnode与phead进行链接，phead->nedxt=newnode,newndoe->prev=phead,再将newnode与tail进行链接,newndoe->next=tail,tail->prev=newnode.

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

2.7头删

头删需要找到第一个和第二个节点，所以定义一个结构体指针first来指向第一个节点，second指向第二个节点(second=first->next)，然后将第二个节点和phead进行链接，phead->next=second,second->prev=phead,然后释放第一个节点的空间，free(first)。

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

2.8有效数据

求出链表的有效数据个数就比较简单了，遍历的时候size++就行了。

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

2.9寻找节点

寻找节点也比较简单，在遍历链表的时候判断当前节点的data是否等于x即可。

LTNode* LTFind(LTNode* phead, LTDataType x)
{
  assert(phead);
  LTNode* cur = phead->next;
  while (cur != phead)
  {
    if (cur->data = x)
    {
      return cur;
    }
    cur = cur->next;
  }
  return NULL;
}

2.10在pos位置之前插入x

这里需找到pos和pos前一个节点，所以创建一个结构体指针posprev指向pos的前一个节点(posprev=pos->prev)，然后将newnode与posprev进行链接，posprev->next=newnode,newnoe->prev=posprev,再将newnode与pos进行链接，pos->prev=newnode,newnode->next=pos。

void LTInsert(LTNode* pos, LTDataType x)
{
  assert(pos);
  LTNode* newnode = BuyLTNode(x);
  LTNode* prepos = pos->prev;
  newnode->next = pos;
  pos->prev = newnode;
  newnode->prev = prepos;
  prepos->next = newnode;
}

将这个函数完成之后就可以对头插与尾插进行简化了。

尾插：

这里大家需要了解一下为什么第一个参数是phead，因为LTInsert这个函数是实现pos位置之前的插入，当我们需要尾插，那么尾巴的后一个节点是什么呢?不就是头节点吗！！

void LTPushBack(LTNode* phead, LTDataType x)
{
  assert(phead);
  LTInsert(phead, x);
}

头插：

头插就比较好理解了，第一个参数就是头节点的下一个节点。

1. void LTPushFront(LTNode* phead, LTDataType x)
2. {
3.  assert(phead);
4. 
5.  LTInsert(phead->next, x);
6. }

2.11删除pos位置的节点

删除pos位置需要找到pos的前一个节点和后一个节点，所以创建一个结构体指针posprev保存pos的前一个节点(posprev=pos->prev)，再创建一个结构体指针保存pos的后一个节点(posnext=pos->next)，然后将posprev与posnext进行链接，posprev->next=posnext,posnext->prev=posprev，然后free掉pos。

void LTErase(LTNode* pos)
{
  assert(pos);
  LTNode* posNext = pos->next;
  LTNode* posPrev = pos->prev;
  free(pos);
  posNext->prev = posPrev;
  posPrev->next = posNext;
}

将这个函数完成之后就可以对头删与尾删进行简化了。

头删：

1. void LTPopFront(LTNode* phead)
2. {
3.  assert(phead);
4.  assert(phead->next!=phead);
5. 
6.  LTErase(phead->next);
7. }

尾删：

尾节点通过头节点phead的前驱指针来找就好了。

1. void LTPopBack(LTNode* phead)
2. {
3.  assert(phead);
4.  assert(phead->next != phead);
5. 
6.  LTErase(phead->prev);
7. }

2.12销毁

销毁链表还是和单链表一样，区别就是循环结束条件是cur走到头节点，还有就是保存cur的后一个节点，最后还要free掉头节点，因为没有走到头节点。

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