双向链表(1) - 基本介绍以及插入节点
双向链表(doubly linked list - DLL)的操作，与单链表很大程度上有相似之处。在开始本篇文章前，可以先回顾下单链表的类似操作。
参考单链表系列中的这两篇文章：”链表(1) - 介绍“， ”链表(3) - 插入节点“。

一个双向链表包含一个额外的指针, 称之为前向指针(prev pointer)，与单链表中的后向指针(next pointer)一起来标识一个节点。


下面是使用C++代码来表示一个DLL的例子：

//双向链表中的节点元素
struct Node
{
  int data;
  Node *next; // 指向下一个节点
  Node *prev; // 指向前一个节点
};

与单链表相比，双向链表有下面的这些优点和缺点。

相比单链表的一些优势

1) DLL支持正向和逆向的遍历方式。
2) DLL中的删除操作更有效，如果提供了要删除节点的指针。
这是因为，在单链表中如果要删除一个节点，则必须要知道前一个节点。有时为了得到这前一个节点，需要遍历整个链表，而在双向链表中，使用前向指针就可以很方便的得到前一个节点。

相比单链表的一些弱势

1) DLL的每个节点，需要额外空间来保存前向指针。
其实可以使用一个指针来实现双向链表。具体可以参考"高级数据结构"系列中的下面这两篇文章：
  "高级链表 - 异或链表(1)" 以及 "高级链表 - 异或链表(2)"。
2) 所有的操作，都需要维护前向指针。例如 ，插入操作时，需要同时更改前向和后向指针。

DLL的插入操作

可以使用4种方式添加一个节点：
1) 在DLL的头部
2) 在一个指定节点的后面
3) 在DLL的尾部
4) 在一个指定节点的前面

链表头部插入一个节点: (5个步骤)

新的节点通常添加到DLL的头部前面，并且变成新的头部节点。例如，对于一个双向链表10<->15<->20<->25，在头部插入一个节点5， 则会变成了5<->10<->15<->20<->25. 假设在链表头部进行节点插入的函数称之为push()。则这个push函数需要知道头指针，因为push必须将头指针指向新的节点。
下面是具体操作的5个步骤.

// 给定链表的头指针(head)以及一个整数，插入一个新的节点至链表的头部
// 之所以传入双指针，因为函数中需要修改链表
void push(Node** head, int newData)
{
	//1. 分配新节点内存
	Node* newNode = new Node;

	//2. 赋值
	newNode->data = newData;

	//3. 将原始头节点做为新节点的后向指针，而前向指针置为NULL
	newNode->next = (*head);
	newNode->prev = NULL;

	//4. 将原始头节点的前向指针置为新的节点
	if ((*head) != NULL)
		(*head)->prev = newNode;

	//5. 将头指针置为新的节点
	(*head) = newNode;
}

上面的前4个步骤，与单链表中插入节点至头部的操作步骤是一样的。只是这里新增了一个步骤，就是改变头部的前向指针。

指定节点的后面插入新节点: (7个步骤)

假设指定的节点为 prevNode, 然后在此节点的后面插入新的节点。

//插入一个节点至指定节点的后面
void insertAfter(Node* prevNode, int newData)
{
	// 1. 检查指定节点是否为NULL
	if (prevNode == NULL)
	{
		std::cout<<"the given previous node cannot be NULL";
		return;
	}

	// 2. 分配新节点内存
	Node* newNode = new Node;

	// 3. 赋值
	newNode->data = newData;

	// 4. 将指定节点的后向指针，做为新节点的后向指针
	newNode->next = prevNode->next;

	// 5. 将新节点做为指定节点的后向指针
	prevNode->next = newNode;

	// 6. 将指定节点做为新节点的前向指针
	newNode->prev = prevNode;

	// 7. 调整新节点的后续节点的前向指针
	if (newNode->next != NULL)
		newNode->next->prev = newNode;
}

上面的前5个步骤，与单链表中插入节点至指定节点的后面的操作步骤是一样的。只是这里新增了两个步骤。即新节点的前向指针，以及新节点的后续节点的前向指针。
根据step4, step5可知，修改后向指针时，是从右到左的顺序，即先改变新节点的后向指针，再改变给定节点的后向指针。
而根据step6, step7可知，修改前向指针时，是从左到右的顺序，即先改变新节点的前向指针，再改变后续节点的前向指针。

链表的尾部插入新节点: (7个步骤)

这种情况下，新节点通常插入到最后一个节点的后面。 例如，对于双向链表5<->10<->15<->20<->25，在尾部插入新的节点30，则链表最终变成5<->10<->15<->20<->25<->30。
因为通常一个链表是用头节点来表示的，所以必须遍历整个链表，将最后一个节点的后向指针置为新节点。
下面是具体的7个实现步骤：

// 给定链表的头指针(head)以及一个整数，插入一个新的节点至链表的尾部
void append(Node** head, int newData)
{
	// 1. 分配新节点内存
	Node *newNode = new Node;
	Node *last = *head;  //链表的尾部指针，用于step5

	// 2. 赋值
	newNode->data = newData;

	// 3. 新节点将成为尾节点，所以后向指针为NULL
	newNode->next = NULL;

	// 4. 如果是空链表，则直接将新节点设置为头节点
	if (*head == NULL)
	{
		newNode->prev = NULL;
		*head = newNode;
		return;
	}

	// 5. 如果不是空链表，则遍历链表，获取尾节点
	while (last->next != NULL)
		last = last->next;

	// 6. 修改尾节点的后向指针为新节点
	last->next = newNode;

	// 7. 修改新节点的前向指针为原始尾节点
	newNode->prev = last;

	return;
}

上面的前7个步骤，与单链表中进行相应操作的前6个步骤相同。新增的1个步骤是修改新节点的前向指针。

指定节点的前面插入新节点：(7个步骤)

假设指定的节点为 nextNode, 然后在此节点的前面插入新的节点。

void insertBefore(Node* nextNode, int newData)
{
	// 1. 检查指定节点是否为NULL
	if (nextNode == NULL)
	{
		printf("the given previous node cannot be NULL");
		return;
	}

	// 2. 分配新节点内存
	Node* newNode = new Node;

	// 3. 赋值
	newNode->data = newData;

	// 4. 将指定节点的前向指针，做为新节点的前向指针
	newNode->prev = nextNode->prev;

	// 5. 将新节点做为指定节点的前向指针
	nextNode->prev = newNode;

	// 6. 将指定节点做为新节点的后向指针
	newNode->next = nextNode;

	// 7. 调整新节点的前面节点的后向指针
	if (newNode->prev != NULL)
		newNode->prev->next = newNode;
}

实现所有插入操作的完整程序

#include <iostream>

struct Node
{
	int data;
	Node *next; // 指向下一个节点
	Node *prev; // 指向前一个节点
};

// 给定链表的头指针(head)以及一个整数，插入一个新的节点至链表的头部
// 之所以传入双指针，因为函数中需要修改链表
void push(Node** head, int newData)
{
	//1. 分配新节点内存
	Node* newNode = new Node;

	//2. 赋值
	newNode->data = newData;

	//3. 将原始头节点做为新节点的后向指针，而前向指针置为NULL
	newNode->next = (*head);
	newNode->prev = NULL;

	//4. 将原始头节点的前向指针置为新的节点
	if ((*head) != NULL)
		(*head)->prev = newNode;

	//5. 将头指针置为新的节点
	(*head) = newNode;
}

//插入一个节点至指定节点的后面
void insertAfter(Node* prevNode, int newData)
{
	// 1. 检查指定节点是否为NULL
	if (prevNode == NULL)
	{
		std::cout<<"the given previous node cannot be NULL";
		return;
	}

	// 2. 分配新节点内存
	Node* newNode = new Node;

	// 3. 赋值
	newNode->data = newData;

	// 4. 将指定节点的后向指针，做为新节点的后向指针
	newNode->next = prevNode->next;

	// 5. 将新节点做为指定节点的后向指针
	prevNode->next = newNode;

	// 6. 将指定节点做为新节点的前向指针
	newNode->prev = prevNode;

	// 7. 调整新节点的后续节点的前向指针
	if (newNode->next != NULL)
		newNode->next->prev = newNode;
}

// 给定链表的头指针(head)以及一个整数，插入一个新的节点至链表的尾部
void append(Node** head, int newData)
{
	// 1. 分配新节点内存
	Node *newNode = new Node;
	Node *last = *head;  //链表的尾部指针，用于step5

	// 2. 赋值
	newNode->data = newData;

	// 3. 新节点将成为尾节点，所以后向指针为NULL
	newNode->next = NULL;

	// 4. 如果是空链表，则直接将新节点设置为头节点
	if (*head == NULL)
	{
		newNode->prev = NULL;
		*head = newNode;
		return;
	}

	// 5. 如果不是空链表，则遍历链表，获取尾节点
	while (last->next != NULL)
		last = last->next;

	// 6. 修改尾节点的后向指针为新节点
	last->next = newNode;

	// 7. 修改新节点的前向指针为原始尾节点
	newNode->prev = last;

	return;
}

//插入一个节点至指定节点的前面
void insertBefore(Node* nextNode, int newData)
{
	// 1. 检查指定节点是否为NULL
	if (nextNode == NULL)
	{
		printf("the given previous node cannot be NULL");
		return;
	}

	// 2. 分配新节点内存
	Node* newNode = new Node;

	// 3. 赋值
	newNode->data = newData;

	// 4. 将指定节点的前向指针，做为新节点的前向指针
	newNode->prev = nextNode->prev;

	// 5. 将新节点做为指定节点的前向指针
	nextNode->prev = newNode;

	// 6. 将指定节点做为新节点的后向指针
	newNode->next = nextNode;

	// 7. 调整新节点的前面节点的后向指针
	if (newNode->prev != NULL)
		newNode->prev->next = newNode;
}

void printList(Node *head)
{
	Node *last = NULL;
	std::cout<<"\nTraversal in forward direction \n";
	while (head != NULL)
	{
		std::cout<<" "<<head->data<<" ";
		last = head;
		head = head->next;
	}

	std::cout<<"\nTraversal in reverse direction \n";
	while (last != NULL)
	{
		std::cout << " " << last->data << " ";
		last = last->prev;
	}
	std::cout << std::endl;
}


int main()
{
	//初始化为空链表
	Node* head = NULL;

	// 插入节点6.  链表变为：6->NULL
	append(&head, 6);

	// 插入节点7，链表变为：7->6->NULL
	push(&head, 7);

	// 头部插入节点1，链表变为：1->7->6->NULL
	push(&head, 1);

	// 尾部插入节点4，链表变为：1->7->6->4->NULL
	append(&head, 4);

	// 在节点7后面插入节点8，链表变为：1->7->8->6->4->NULL
	insertAfter(head->next, 8); 
	// 节点8之前插入节点9，链表变为：1->7->9->8->6->4->NULL
	insertBefore(head->next->next, 9);

	std::cout<<"Created DLL is: ";
	printList(head);

	return 0;
}

输出：
Created DLL is:
Traversal in forward direction
1 7 9 8 6 4
Traversal in reverse direction
4 6 8 9 7 1