双向链表(Doubly Linked List)

双向链表介绍

双向链表的结构如下：

struct Node{
    int data;
    struct Node* prev;
    struct Node* next;
};

可以看到双向链表的节点是由两个结构体指针及相关数据构成的，因此可以更方便地对链表中的节点进行访问和数据的修改。

双向链表的实现

进行几个基本操作：头部插入(InsertAtHead)、尾部插入(InsertAtTail)、打印(Print)、反向打印(ReversePrint)。

头部插入(InsertAtHead)

插入时要先在堆区开辟一块动态内存，为了避免代码重复，我们设计一个函数GetNewNode(int x)，可以在堆区新建一个节点，存储数据x，同时返回堆区内存的地址。

struct Node* GetNewNode(int x){
	struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
	newNode->data = x;
	newNode->next = NULL;
	newNode->prev = NULL;
	return newNode;
}

再进行头部插入

void InsertAtHead(int x){
	struct Node* newNode = GetNewNode(x);
	if(head == NULL){
		head = newNode;
		return;
	}
	head->prev = newNode;
	newNode->next = head;
	head = newNode;
}

尾部插入(InsertAtTail)

只需要先遍历到最后一个节点，再进行插入操作即可。

void InsertAtTail(int x){
	struct Node* newNode = GetNewNode(x);
	if(head == NULL){
		head = newNode;
		return;
	}
	struct Node* temp = head;
	while(temp->next != NULL){
		temp = temp->next;
	}
	temp->next = newNode;
	newNode->prev = temp;
}

打印(Print)

void Print(){
	struct Node* temp = head;
	printf("Forward: ");
	while(temp != NULL){
		printf("%d ",temp->data);
		temp = temp->next;
	}
	printf("\n");
}

反向打印(ReversePrint)

同样需要先遍历到最后一个节点。

void ReversePrint(){
	struct Node* temp = head;
	while(temp->next != NULL){
		temp = temp->next;
	}
	printf("Reverse: ");
	while(temp != NULL){
		printf("%d ",temp->data);
		temp = temp->prev;
	}
	printf("\n");
}

完整实现如下：

#include<stdio.h>
#include<stdlib.h>
struct Node{
	int data;
	struct Node* prev;
	struct Node* next;
};
struct Node* head = NULL;
struct Node* GetNewNode(int x){
	struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
	newNode->data = x;
	newNode->next = NULL;
	newNode->prev = NULL;
	return newNode;
}
void InsertAtHead(int x){
	struct Node* newNode = GetNewNode(x);
	if(head == NULL){
		head = newNode;
		return;
	}
	head->prev = newNode;
	newNode->next = head;
	head = newNode;
}
void InsertAtTail(int x){
	struct Node* newNode = GetNewNode(x);
	if(head == NULL){
		head = newNode;
		return;
	}
	struct Node* temp = head;
	while(temp->next != NULL){
		temp = temp->next;
	}
	temp->next = newNode;
	newNode->prev = temp;
}
void Print(){
	struct Node* temp = head;
	printf("Forward: ");
	while(temp != NULL){
		printf("%d ",temp->data);
		temp = temp->next;
	}
	printf("\n");
}
void ReversePrint(){
	struct Node* temp = head;
	while(temp->next != NULL){
		temp = temp->next;
	}
	printf("Reverse: ");
	while(temp != NULL){
		printf("%d ",temp->data);
		temp = temp->prev;
	}
	printf("\n");
}
int main(){
	InsertAtTail(1);Print();
	InsertAtHead(3);Print();
	InsertAtHead(2);Print();
	InsertAtHead(4);Print();
	InsertAtTail(5);Print();
	ReversePrint();
	return 0;
}

输出结果：

Forward: 1
Forward: 3 1
Forward: 2 3 1
Forward: 4 2 3 1
Forward: 4 2 3 1 5
Reverse: 5 1 3 2 4