双向链表

双向链表是链表变型，相比于单链表导航或者是向前和向后的两种方式。以下是重要的术语来理解双向链表的概念

• Link − 链表的每个链路存储数据称为一个元素。

• Next − 链表的每个链接包含一个链接到下一个被称为下一个(Next)。

• Prev − 链表的每个链接包含一个链接，称为上一个链接(Prev)。

• LinkedList − LinkedList包含连接链接到名为首先第一个链接，并称为最后的最后一个链接(Last)。

双向链表表示

按照如上图中所示，以下是要考虑的重要问题。

• 双向链表包含一个名为第一个（first）和最后一个链接(last)元素。
• 每个链路负责数据字段和LINK域被称为下一个(Next)。
• 每一个Link链接，其利用其下一个链接指向下一个链接。
• 每一个Link链接使用其上一个链接指向上一个链接。
• 最后一个链接带有链接的空标记列表的末尾。

基本操作

下面是一个列表支持的基本操作。

• 插入 − 在列表的开头添加的元素。

• 删除− 删除在列表开头的元素。

• 插入最后 − 在列表的末尾添加元素。

• 删除最后 − 删除列表的末尾的元素。

• 插入之后− 列表中的项目后添加元素。

• 删除 − 用键从列表中删除一个元素。

• 正向显示 − 以向前的方式显示完整列表。

• 后向显示 − 向后的方式显示完整列表。

插入操作

下面的代码演示了插入操作，从一个双向链表的开始。

//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;
}

要查看 C编程语言的实现，请点击 。