数据结构&算法 双向链表



  • 双向链表

    双向链表是链表的一种变体,与单链表相比,双向链表都可以轻松实现。以下是理解双向链表概念的重要术语。
    • Link —— 链表中的每个链接(Link)都可以存储一个称为元素的数据。
    • Next —— 链表中的每个链接都包含一个指向下一个链接的链接,该链接称为Next。
    • Prev —— 链表中的每个链接都包含一个指向前一个称为Prev的链接。
    • LinkedList —— 一个链表包含到第一个称为first的链接的连接链接。
  • 双向链表表示

    根据上面的说明,以下是要考虑的重点。
    • 双链表包含一个名为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;
    }
    
    
  • 双向链表的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;
    
    //is list empty
    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("\n[ ");
      
       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("\n[ ");
      
       while(ptr != NULL) {    
      
          //print data
          printf("(%d,%d) ",ptr->key,ptr->data);
        
          //move to next item
          ptr = ptr ->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;
    }
    
    //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;
    }
    
    //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;
    }
    
    //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 the deleted link
       return tempLink;
    }
    
    //delete a link with given key
    
    struct node* delete(int key) {
    
       //start from the first link
       struct node* current = head;
       struct node* previous = NULL;
      
       //if list is empty
       if(head == NULL) {
          return NULL;
       }
    
       //navigate through list
       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) {
          //change first to point to next link
          head = head->next;
       } else {
          //bypass the current link
          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 list is empty
       if(head == NULL) {
          return false;
       }
    
       //navigate through list
       while(current->key != key) {
      
          //if it is last node
          if(current->next == NULL) {
             return false;
          } else {           
             //move to next link
             current = current->next;
          }
       }
      
       //create a link
       struct node *newLink = (struct node*) malloc(sizeof(struct node));
       newLink->key = newKey;
       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; 
    }
    
    void main() {
       insertFirst(1,10);
       insertFirst(2,20);
       insertFirst(3,30);
       insertFirst(4,1);
       insertFirst(5,40);
       insertFirst(6,56); 
    
       printf("\nList (First to Last): ");  
       displayForward();
      
       printf("\n");
       printf("\nList (Last to first): "); 
       displayBackward();
    
       printf("\nList , after deleting first record: ");
       deleteFirst();        
       displayForward();
    
       printf("\nList , after deleting last record: ");  
       deleteLast();
       displayForward();
    
       printf("\nList , insert after key(4) : ");  
       insertAfter(4,7, 13);
       displayForward();
    
       printf("\nList  , 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) (7,13) (3,30) (2,20) ]
    List , after delete key(4) : 
    [ (5,40) (4,13) (3,30) (2,20) ]