数据结构与算法中的双向链表

        链表概念在现实世界中使用得很普遍。当我们使用 Spotify 播放队列中的下一首歌曲时，我们学到的单链表的概念就开始发挥作用。但是要播放队列中的上一首歌曲到底可以做什么呢？ 

        在这篇博客中，我们将了解与数据结构相关的另一个概念，即双向链表。我们还将讨论使用 C 语言和实时应用程序的实现。

什么是双向链表？

        链表是一种线性数据结构，包含以顺序方式连接的节点。该节点包含三个字段，即存储在该参考地址处的数据和指向该参考节点左侧和右侧的后继节点的两个指针。 

        左节点指针存储序列中前一个节点的内存地址，右节点存储下一个节点的内存地址。我们在这里使用动态内存分配而不是数组，以便可以在运行时根据执行的操作分配或取消分配内存大小。 

 

        在这个例子中，头指向第一个节点。引用节点的左指针存储NULL，最后一个节点的右指针也是如此。

为了对这个例子进行操作，我们可以进一步进行相应的更改。 

双向链表的实现

1、在前面插入节点

        为了完成上述操作，首先创建一个节点并使用动态内存分配内存。将头指向新节点，并在左节点和右节点中存储 NULL 值。

void front_add(){//allocate memory using dynamic memory allocation.newnode -> data = NULL;newnode -> prev = NULL;newnode -> next = head;head= newnode;
}

2.删除最前面的节点

要从前面删除节点，我们必须将引用地址的正确节点值存储在头部并释放第一个节点。 

void front_del(){newnode=head;head= head->next ;head->prev = NULL;free(newnode);
}

3. 在末尾插入节点

要在末尾添加节点，我们必须遍历到末尾并将最后一个节点指向引用的新节点，反之亦然。

void end_add(){//allocate memory to newnodenewnode -> data= item; // temp=headwhile(temp ->next !=NULL){temp = temp->next;}temp->next= newnode;newnode -> prev = temp;newnode-> next = NULL;}

4.删除末尾节点

要删除末尾的节点，我们必须遍历链表并到达末尾。我们将使用指向最后一秒节点的指针。然后释放最后一个节点。

void rear_del(){while(temp -> next!=NULL){temp = temp->next;          //temp=head}temp ->prev-> next = NULL;free(temp);
}

现在我们已经了解了基本操作，现在我们将逐步使用 C 实现双向链表。

#include<stdio.h>
#define MAX 5struct node{int data;struct node * prev;struct node * next;
};
struct node *head;
void front_add();
void front_del();
void rear_add();
void rear_del();
void display();int main(){int choice=0;while(choice!=6){printf("enter choice:\n");printf("\n1.front_add\n2.front_Del\n3.rear_add\n4.rear_del\n5.display\n6.exit");scanf("%d\n",&choice);switch(choice){case 1:front_add();break;case 2:front_del();break;case 3:rear_add();break;case 4:rear_del();break;case 5:display();break;case 6:printf("exiting...\n");break;default:printf("unknown choice\n");}}
}
void front_add(){struct node* newnode;int item;newnode = (struct node*)malloc(sizeof(struct node));printf("enter item value:\n");scanf("%d", &item);if(head == NULL){newnode -> next = NULL;newnode -> prev = NULL;newnode -> data = item;head = newnode;}else{newnode -> data = item;newnode -> prev = NULL;newnode -> next = head;head->prev = newnode;head= newnode;}
}
void front_del(){struct node *newnode;if(head->next == NULL){head = NULL;free(head);printf("\nnode deleted\n");}else{newnode=head;head= head->next ;head->prev = NULL;free(newnode);printf("deleted\n");}
}
void rear_add(){struct node *temp,*newnode;int item;newnode = (struct node*)malloc(sizeof(struct node));printf("enter item");scanf("%d", &item);newnode -> data= item;temp = head;while(temp ->next !=NULL){temp = temp->next;}temp->next= newnode;newnode -> prev = temp;newnode-> next = NULL;printf("inserted\n");}
void rear_del(){struct node *temp;temp=head;if(head->next==NULL){head = NULL;free(head);printf("deleted\n");}else{while(temp -> next!=NULL){temp = temp->next;}temp ->prev-> next = NULL;free(temp);printf("deleted\n");}
}
void display(){struct node *temp;temp = head;if(head==NULL){printf("empty\n");}else{while(temp!=NULL){printf("%d", temp->data);temp = temp->next;}}
}

此代码将为您提供所需的输出：

 

 

        您有没有想过这些多人游戏是如何开发的，玩家可以在重复的循环中获得机会？这意味着最后一个玩家再次链接到第一个玩家以形成循环。

为了使这成为可能，我们引入了另一个与链表相关的概念。在这种情况下，循环链表很有用。

循环链表

        在循环单链表中，链表的最后一个节点包含指向链表第一个节点的指针。双链表和单链表都可以使用这个概念。

        该列表与其他两个列表的唯一区别是最后一个节点的右指针指向第一个节点，而头节点始终指向第一个节点本身。

结论

在我看来，链表的概念在解决复杂问题时非常重要和有用。在经历各种场景时，双向链表和循环单链表都是齐头并进的。我希望您喜欢阅读这个博客。请点赞并评论您对今天主题的看法。学习愉快！！