【C++】双向链表

每个节点有两个指针域和若干数据域，其中一个指针域指向它的前趋节点，一个指向它的后继节点。它的优点是访问、插入、删除更方便，速度也快了，但“是以空间换时间”。

* 数据结构的定义

```C
struct node
{
	int data;
	node *pre,*next;	//pre指向前趋，next指向后继
}
node *head,*p,*q,*r;
```

下面给出双向链表的插入和删除过程

[album type="photos"]

![删除p节点前后的指针变化](https://blog.fivk.cn/usr/uploads/2021/03/881009072.png)

![在p节点之前插入s节点前后的指针变化](https://blog.fivk.cn/usr/uploads/2021/03/3354079677.png)

[/album] </div>

```C
void insert(node* head, int i, int x)	//双向链表的第i个节点之前插入x
{
	int j;
	s = new node;
	s->data = x;
	p = head;
	j = 0;
	while ((p->next != NULL) && (j < i))
	{
		p = p->next;
		j = j + i;
	}									//p指向的i个节点
	if (p == NULL)
		cout << "no this position";
	else 
	{									//将节点s插入到节点p之前
		s->pre = p->pre;				//将s的前趋指向p的前趋
		p->pre = s;						//将s作为p的新前趋
		s->next = p;					//将s的后继指向p
		p->pre->next = s;				//将p的本来前趋节点的后继指向s
	}
}

void delete(node* head, int i)			//删除双节点链表的第i个节点
{
	int j;
	node* p;
	p = head;
	j = 0;
	while ((p->next != NULL) && (j < i))
	{
		p = p->next;
		j = j + 1;
	}
	if (p == NULL)
	cout<<"no this position!"
	else
	{									//将节点p删除
		p->pre->next = p->next;			//p的前趋节点的后继赋值为p的后继
		p->next->pre = p->pre;			//p的后继节点的前趋赋值为p的前趋
		free(p);
	}
}
```

最后修改：2021 年 03 月 20 日