C/C++ 双向链表实现----Harsha Suryanarayana

（来自印度的顶级程序员。一些添加，c++部分为个人理解）

关于Harsha Suryanarayana：
https://www.freecodecamp.org/chinese/news/mycodeschool-youtube-channel-history/
B站视频：
【【强烈推荐】深入浅出数据结构 - 顶尖程序员图文讲解 - UP主翻译校对 (已完结)】https://www.bilibili.com/video/BV1Fv4y1f7T1?vd_source=2cb4b275b46b9a0bd5d3d0e3d51588e6
油管：
https://www.youtube.com/watch?v=92S4zgXN17o&list=PL2_aWCzGMAwI3W_JlcBbtYTwiQSsOTa6P
仓库：
GitHub：https://github.com/LIangZH-RT/data_structure_code
gitee：https://gitcode.com/LangZH_RT/data_structure_code/tree/main

注意：此篇为链表的续，你必须看完链表后再来学习。

双向链表的节点

双向即两个方向，之前的链表，每一个节点只能指向下一个节点。但双向链表还看看可以指向上一个节点，这时就需要两个指针，prve 和 next 。一个双向链表：

在之前链表的节点基础上再加一个指针：

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

在双向链表中插入你的第一个节点

与单链表一样同样写一个函数来获取节点。

Node * createNode(int data){
    Node * temp = (Node *)malloc(sizeof(Node));
    temp->prev = NULL;
    temp->next = NULL;
    temp->data = data;
    return temp;
}

一开始双向链表为空直接设置head为获取的节点：

void insertAtHead(Node **head, int data){
    Node * newNode = createNode(data);
    if(*head == NULL){
        *head = newNode;
    }
}

但是还需要考虑非空双向链表情况。这时不仅需要修改head，还要修改原第一个节点的prev指针，指向新插入节点。

    newNode->next = *head; 
    (*head)->prev = newNode;
    *head = newNode;

与单向链表头插写法一致，你可以复制单向链表的头插函数，再加入修改prev的代码即可。完整插入：

void insertHead(Node ** head,int data){
	Node * newNode = createNode(data);
	newNode->next = *head;
	(*head)->prev = newNode;  // 修改prev
	*head = newNode;
}

push_back 操作

同样直接复制单链表push_back函数再加入修改prev即可。双向链表的push_back:

void push_Back(Node ** head, int data) {
	Node * newNode = createNode(data);
	Node * temp = *head;
	//添加判断头部情况
	if(*head == NULL) {
		*head = newNode;
		return;
	}
	while(temp->next != NULL){
		temp = temp->next;	
	}
	newNode->prev = temp;
	temp->next = newNode;
}

在任意位置插入

注意：在pos = 1时，需要判断head是否空，若空则它的prev没有。不是NULL，是不存在。

同样复制单向链表操作：

void insert(Node ** head,int data,int pos){
	Node * newNode = createNode(data);
	if(pos < 1) return;
	if(pos == 1) {
	newNode->next = *head;
	if(*head !=NULL)
	(*head)->prev = newNode;  // 修改prev
	*head = newNode;		
	return;
	}
	Node * temp = *head;
	for(int i=0; i<pos-2; i++){
	//超出链表判断
		if(temp->next == NULL) return;  
		temp = temp->next;
	}
	newNode->next = temp->next;
	newNode->prev = temp; // 修改prev指向
	temp->next = newNode;
} 

删除节点

在删除的时候注意：
1.修改后一节点的prev，不然会出现野指针。
2.若删除最后一节点，temp2->next是NULL，没有prev，需要判断。

复制单链表操作：

void removef(Node **head,int pos){
	Node * temp1 = *head;
	//判断pos
	if(pos == 1){
		*head = temp1->next;
		//这里需要注意修改第二个节点的prev，它成为第一节点。
		if(*head != NULL) { 
            (*head)->prev = NULL; 
        }
		free(temp1);
		return;
	}
	int i;
	for(i = 0;i < pos-2;i++){
		temp1 = temp1->next; 
	}
	Node * temp2 = temp1->next; 
	//这里修改 要删除的节点的下一节点的prev指向 
	//begin
	if(temp2->next != NULL) 
	temp2->next->prev = temp1;
	//end
	temp1->next = temp2->next;
	free(temp2);  
}

剩下的反转操作可只按照上述内容自行练习。
感谢Harsha Suryanarayana的视频。
如果您发现内容存在疑问或错误，欢迎私信或评论，个人邮箱：aa2961363680@outlook.com。

下一篇数据结构 stack