使用 C 的 DSA - 双向链表

更新于 2024/7/3 8:04:00

概述

双向链表是链表的一种变体，与单链表相比，双向链表可以轻松地向前和向后导航。以下是理解双向链表概念的重要术语。

链接 − 链表的每个链接都可以存储称为元素的数据。
下一个 − 链表的每个链接都包含一个指向下一个链接的链接，称为下一个。
上一个 − 链表的每个链接都包含一个指向上一个链接的链接，称为上一个。
链接列表 − LinkedList 包含指向第一个 Link（称为 First）和最后一个 Link（称为 Last）的连接链接。

双向链接列表表示

如上图所示，以下是需要考虑的重要点。

双向链接列表包含一个称为 first 和 last 的链接元素。
每个 Link 都带有一个数据字段和一个称为 next 的链接字段。
每个 Link 都使用其下一个链接与其下一个链接链接。
每个 Link 都使用其上一个链接与其上一个链接链接。
最后一个 Link 带有一个为 null 的 Link 来标记结束列表。

基本操作

以下是列表支持的基本操作。

插入− 在列表开头添加一个元素。
删除 − 删除列表开头的一个元素。
插入最后一个− 在列表末尾添加一个元素。
删除最后一个 − 从列表末尾删除一个元素。
在后面插入 − 在列表的某项后面添加一个元素。
删除 −使用键从列表中删除一个元素。
向前显示 − 以向前方式显示完整列表。
向后显示 − 以向后方式显示完整列表。

插入操作

以下代码演示了在双向链表开头的插入操作。

//在第一个位置插入链接
void insertFirst(int key, int data){
   //创建链接
   struct node *link = (struct node*) malloc(sizeof(struct node));
   link->key = key;
   link->data = data;
   if(isEmpty()){
      //make it the last link
      last = link;
   } else {
      //update first prev link
      head->prev = link;
   }
   //point it to old first link
   link->next = head;
   
   //point first to new first link
   head = link;
}

删除操作

以下代码演示了双向链表开头的删除操作。

//删除第一项
struct node* deleteFirst(){
   //保存对第一个链接的引用
   struct node *tempLink = head;
   
   //if only one link
   if(head->next == NULL){
      last = NULL;
   } else {
      head->next->prev = NULL;
   }
   head = head->next;
   
   //返回删除的链接
   return tempLink;
}

末尾插入操作

以下代码演示了在双向链表的最后一个位置插入操作。

//insert link at the last location
void insertLast(int key, int data){
   //创建链接
   struct node *link = (struct node*) malloc(sizeof(struct node));
   link->key = key;
   link->data = data;
   if(isEmpty()){
      //make it the last link
      last = link;
   } else {
      //make link a new last link
      last->next = link;     
      
      //mark old last node as prev of new link
      link->prev = last;
   }
   //point last to new last node
   last = link;
}

示例

DoublyLinkedListDemo.c

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>

struct node {
   int data;
   int key;
   struct node *next;
   struct node *prev;
};
//this link always point to first Link 
struct node *head = NULL;

//this link always point to last Link 
struct node *last = NULL;
struct node *current = NULL;

//列表是否为空
bool isEmpty(){
   return head == NULL;
}
int length(){
   int length = 0;
   struct node *current;
   for(current = head; current!=NULL;
      current = current->next){
      length++;
   }
   return length;
}
//display the list in from first to last
void displayForward(){
   //start from the beginning
   struct node *ptr = head;
   
   //navigate till the end of the list
   printf("
[ ");
   while(ptr != NULL){        
      printf("(%d,%d) ",ptr->key,ptr->data);
      ptr = ptr->next;
   }
   printf(" ]");
}
//display the list from last to first
void displayBackward(){
   //start from the last
   struct node *ptr = last;
   
   //navigate till the start of the list
   printf("
[ ");
   while(ptr != NULL){    
      //print data
      printf("(%d,%d) ",ptr->key,ptr->data);
      
      //move to next item
      ptr = ptr ->prev;
      printf(" ");
   }
   printf(" ]");
}
//在第一个位置插入链接
void insertFirst(int key, int data){
   //创建链接
   struct node *link = (struct node*) malloc(sizeof(struct node));
   link->key = key;
   link->data = data;
   if(isEmpty()){
      //make it the last link
      last = link;
   } else {
      //update first prev link
      head->prev = link;
   }
   //point it to old first link
   link->next = head;
   
   //point first to new first link
   head = link;
}
//insert link at the last location
void insertLast(int key, int data){
   //创建链接
   struct node *link = (struct node*) malloc(sizeof(struct node));
   link->key = key;
   link->data = data;
   if(isEmpty()){
      //make it the last link
      last = link;
   } else {
      //make link a new last link
      last->next = link;     
      
      //mark old last node as prev of new link
      link->prev = last;
   }
   //point last to new last node
   last = link;
}
//删除第一项
struct node* deleteFirst(){
   //保存对第一个链接的引用
   struct node *tempLink = head;
   
   //if only one link
   if(head->next == NULL){
      last = NULL;
   } else {
      head->next->prev = NULL;
   }
   head = head->next;
   //返回删除的链接
   return tempLink;
}
//delete link at the last location
struct node* deleteLast(){
   //save reference to last link
   struct node *tempLink = last;
   
   //if only one link
   if(head->next == NULL){
      head = NULL;
   } else {
      last->prev->next = NULL;
   }
   last = last->prev;
   //返回删除的链接
   return tempLink;
}
//删除指定键的链接
struct node* delete(int key){
   //start from the first link
   struct node* current = head;
   struct node* previous = NULL;
   
   //如果列表为空
   if(head == NULL){
      return NULL;
   }
   //浏览列表
   while(current->key != key){
      //if it is last node
      if(current->next == NULL){
         return NULL;
      } else {
         //store reference to current link
         previous = current;
         
         //move to next link
         current = current->next;             
      }
   }
   //found a match, update the link
   if(current == head) {
      //将 first 改为指向 next 链接
      head = head->next;
   } else {
      //绕过当前链接
      current->prev->next = current->next;
   }    
   if(current == last){
      //change last to point to prev link
      last = current->prev;
   } else {
      current->next->prev = current->prev;
   }
   return current;
}
bool insertAfter(int key, int newKey, int data){
   //start from the first link
   struct node *current = head;      
   
   //如果列表为空
   if(head == NULL){
      return false;
   }
   //浏览列表
   while(current->key != key){
      //if it is last node
      if(current->next == NULL){
         return false;
      } else {           
         //move to next link
         current = current->next;             
      }
   }
   //创建链接
   struct node *newLink = (struct node*) malloc(sizeof(struct node));
   newLink->key = key;
   newLink->data = data;

   if(current==last) {
      newLink->next = NULL; 
      last = newLink; 
   } else {
      newLink->next = current->next;         
      current->next->prev = newLink;
   }
   newLink->prev = current; 
   current->next = newLink; 
   return true; 
}
main() {
   insertFirst(1,10);
   insertFirst(2,20);
   insertFirst(3,30);
   insertFirst(4,1);
   insertFirst(5,40);
   insertFirst(6,56); 

   printf("
List (First to Last): ");  
   displayForward();
   printf("
");
   printf("
List (Last to first): "); 
   displayBackward();

   printf("
List , after deleting first record: ");
   deleteFirst();        
   displayForward();

   printf("
List , after deleting last record: ");  
   deleteLast();
   displayForward();

   printf("
List , insert after key(4) : ");  
   insertAfter(4,7, 13);
   displayForward();

   printf("
List  , after delete key(4) : ");  
   delete(4);
   displayForward();
}

输出

如果我们编译并运行上述程序，则会产生以下输出 −

List (First to Last): 
[ (6,56) (5,40) (4,1) (3,30) (2,20) (1,10) ]

List (Last to first): 
[ (1,10) (2,20) (3,30) (4,1) (5,40) (6,56) ]
List , after deleting first record: 
[ (5,40) (4,1) (3,30) (2,20) (1,10) ]
List , after deleting last record: 
[ (5,40) (4,1) (3,30) (2,20) ]
List , insert after key(4) : 
[ (5,40) (4,1) (4,13) (3,30) (2,20) ]
List , after delete key(4) : 
[ (5,40) (4,13) (3,30) (2,20) ]

❮ 使用 C 的 DSA 链接列表使用 C 的 DSA 循环链接列表 ❯

使用 C 的 DSA 教程

使用 C 的 DSA 有用资源

使用 C 的 DSA - 双向链表

概述

双向链接列表表示

基本操作

插入操作

删除操作

末尾插入操作

示例

输出

颜色选择器

读后有收获微信请站长喝咖啡

错误报告

您的建议:

感谢您的帮助！