logo图片
数据结构与算法

双链表

双链表是链表的一种变体,与单链表相比,双链表可以双向导航,向前和向后都更容易。以下是理解双向链表概念的重要术语。
Link-链表的每个链接都可以存储一个称为元素的数据。 Next-链表的每个链接都包含一个指向名为 Next 的下一个链接的链接。 Prev-链表的每个链接都包含一个指向上一个链接的链接,称为 Prev。 LinkedList-链接列表包含指向名为 First 的第一个链接和名为 Last 的最后一个链接的连接链接。

双向链表表示

双向链表
根据上图,以下是需要考虑的重点。
双向链表包含一个名为 first 和 last 的链接元素。 每个链接都带有一个数据字段和两个称为 next 和 prev 的链接字段。 每个链接都使用其下一个链接与其下一个链接相链接。 每个链接都使用其上一个链接与其上一个链接相链接。 最后一个链接带有一个为空的链接,以标记列表的结尾。

基本操作

以下是列表支持的基本操作。
插入-在列表的开头添加一个元素。 删除-删除列表开头的元素。 末尾添加-在列表末尾添加一个元素。 删除最后一个-从列表末尾删除一个元素。 项后添加-在列表项之后添加一个元素。 删除-使用键从列表中删除一个元素。 向前显示-向前显示完整列表。 向后显示-向后显示完整列表。

插入操作

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

示例

//insert link at the first location
void insertFirst(int key, int data) {
   //create a link
   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;
}

删除操作

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

示例

//delete first item
struct node* deleteFirst() {
   //save reference to first link
   struct node *tempLink = head;
    
   //if only one link
   if(head->next == null) {
      last = null;
   } else {
      head->next->prev = null;
   }
    
   head = head->next;
    
   //return the deleted link
   return tempLink;
}

在操作结束时插入

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

示例

//insert link at the last location
void insertLast(int key, int data) {
   //create a link
   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;
}
昵称: 邮箱:
Copyright © 2020 立地货 All Rights Reserved.
备案号:京ICP备14037608号-4