数据结构&算法 链表



  • 链表

    链表是一系列数据结构,它们通过链接连接在一起。链接列表是包含项目的一系列链接。每个链接都包含到另一个链接的连接。链表是仅次于数组的第二大数据结构。以下是了解链接列表概念的重要术语。
    • Link —— 链表中的每个链接(Link)都可以存储一个称为元素的数据。
    • Next —— 链表中的每个链接都包含一个指向下一个链接的链接,该链接称为Next。
    • LinkedList —— 一个链表包含到第一个称为first的链接的连接链接。
  • 链表表示

    链接列表可以可视化为节点链,其中每个节点都指向下一个节点(Node)。
    根据上面的说明,以下是要考虑的重点。
    • 链表包含一个名为first的链接元素。
    • 每个链接包含一个或多个数据字段和一个称为next的链接字段。
    • 每个链接都使用其下一个链接与其下一个链接链接。
    • 最后一个链接的链接为空,以标记列表的结尾。
  • 链接列表的类型

    以下是各种类型的链表。
    • 单向链表 - 项目导航仅向前。
    • 双向链表 - 项目可以向前和向后导航。
    • 循环链表 - 最后一项包含第一个元素的链接作为下一个,而第一个元素具有到最后一个元素的链接作为上一个。
  • 基本操作

    以下是列表支持的基本操作。
    • 插入 - 在列表的开头添加一个元素。
    • 删除 - 删除列表开头的元素。
    • 显示 - 显示完整列表。
    • 搜索 - 使用给定的键搜索元素。
    • 删除 - 使用给定的键删除元素。
  • 插入操作

    在链接列表中添加新节点是一项以上的活动。我们将在这里通过图表来学习。首先,使用相同的结构创建一个节点,并找到必须将其插入的位置。
    想象一下,我们要在A(LeftNode)和C(RightNode)之间插入节点B(NewNode)。然后将B.next指向C-
    
    NewNode.next −> RightNode;
    
    
    它看起来应该像这样-
    现在,左侧的下一个节点应指向新节点。
    
    LeftNode.next −> NewNode; 
    
    
    这会将新节点置于两者的中间。新列表应如下所示-
    如果将节点插入列表的开头,则应采取类似的步骤。在末尾插入时,列表的倒数第二个节点应指向新节点,而新节点将指向NULL。
  • 删除操作

    删除也是一个多步骤的过程。我们将以图片表示形式学习。首先,通过使用搜索算法找到要删除的目标节点。
    现在,目标节点的左(上一个)节点应指向目标节点的下一个节点-
    
    LeftNode.next −> TargetNode.next;
    
    
    这将删除指向目标节点的链接。现在,使用以下代码,我们将删除目标节点指向的对象。
    
    TargetNode.next −> NULL;
    
    
    我们需要使用已删除的节点。我们可以将其保留在内存中,否则我们可以简单地重新分配内存并完全擦除目标节点。
  • 反转操作

    此操作是彻底的。我们需要使最后一个节点由头节点指向,并反转整个链表。
    首先,我们遍历列表的末尾。它应该指向NULL。现在,我们将其指向其先前的节点-
    我们必须确保最后一个节点不是最后一个节点。因此,我们将有一些临时节点,看起来像头节点指向最后一个节点。现在,我们将使所有左侧节点一个接一个地指向其先前的节点。
    除头节点指向的节点(第一个节点)外,所有节点都应指向其前任节点,使其成为新的后继节点。第一个节点将指向NULL。
    我们将使用临时节点使头节点指向新的第一个节点。
    现在,链接列表已反转。
  • 链表的C语言实现

     
    #include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    #include <stdbool.h>
    
    struct node {
       int data;
       int key;
       struct node *next;
    };
    
    struct node *head = NULL;
    struct node *current = NULL;
    
    //display the list
    void printList() {
       struct node *ptr = head;
       printf("\n[ ");
      
       //start from the beginning
       while(ptr != NULL) {
          printf("(%d,%d) ",ptr->key,ptr->data);
          ptr = ptr->next;
       }
      
       printf(" ]");
    }
    
    //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;
      
       //point it to old first node
       link->next = head;
      
       //point first to new first node
       head = link;
    }
    
    //delete first item
    struct node* deleteFirst() {
    
       //save reference to first link
       struct node *tempLink = head;
      
       //mark next to first link as first 
       head = head->next;
      
       //return the deleted link
       return tempLink;
    }
    
    //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;
    }
    
    //find a link with given key
    struct node* find(int key) {
    
       //start from the first link
       struct node* current = head;
    
       //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 {
             //go to next link
             current = current->next;
          }
       }      
      
       //if data found, return the current Link
       return current;
    }
    
    //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
          previous->next = current->next;
       }    
      
       return current;
    }
    
    void sort() {
    
       int i, j, k, tempKey, tempData;
       struct node *current;
       struct node *next;
      
       int size = length();
       k = size ;
      
       for ( i = 0 ; i < size - 1 ; i++, k-- ) {
          current = head;
          next = head->next;
        
          for ( j = 1 ; j < k ; j++ ) {   
    
             if ( current->data > next->data ) {
                tempData = current->data;
                current->data = next->data;
                next->data = tempData;
    
                tempKey = current->key;
                current->key = next->key;
                next->key = tempKey;
             }
          
             current = current->next;
             next = next->next;
          }
       }   
    }
    
    void reverse(struct node** head_ref) {
       struct node* prev   = NULL;
       struct node* current = *head_ref;
       struct node* next;
      
       while (current != NULL) {
          next  = current->next;
          current->next = prev;   
          prev = current;
          current = next;
       }
      
       *head_ref = prev;
    }
    
    void main() {
       insertFirst(1,10);
       insertFirst(2,20);
       insertFirst(3,30);
       insertFirst(4,1);
       insertFirst(5,40);
       insertFirst(6,56); 
    
       printf("Original List: "); 
      
       //print list
       printList();
    
       while(!isEmpty()) {            
          struct node *temp = deleteFirst();
          printf("\nDeleted value:");
          printf("(%d,%d) ",temp->key,temp->data);
       }  
      
       printf("\nList after deleting all items: ");
       printList();
       insertFirst(1,10);
       insertFirst(2,20);
       insertFirst(3,30);
       insertFirst(4,1);
       insertFirst(5,40);
       insertFirst(6,56);
       
       printf("\nRestored List: ");
       printList();
       printf("\n");  
    
       struct node *foundLink = find(4);
      
       if(foundLink != NULL) {
          printf("Element found: ");
          printf("(%d,%d) ",foundLink->key,foundLink->data);
          printf("\n");  
       } else {
          printf("Element not found.");
       }
    
       delete(4);
       printf("List after deleting an item: ");
       printList();
       printf("\n");
       foundLink = find(4);
      
       if(foundLink != NULL) {
          printf("Element found: ");
          printf("(%d,%d) ",foundLink->key,foundLink->data);
          printf("\n");
       } else {
          printf("Element not found.");
       }
      
       printf("\n");
       sort();
      
       printf("List after sorting the data: ");
       printList();
      
       reverse(&head);
       printf("\nList after reversing the data: ");
       printList();
    }  
    
    
    如果我们编译并运行上述程序,它将产生以下结果-
     
    Original List: 
    [ (6,56) (5,40) (4,1) (3,30) (2,20) (1,10) ]
    Deleted value:(6,56) 
    Deleted value:(5,40) 
    Deleted value:(4,1) 
    Deleted value:(3,30) 
    Deleted value:(2,20) 
    Deleted value:(1,10) 
    List after deleting all items: 
    [ ]
    Restored List: 
    [ (6,56) (5,40) (4,1) (3,30) (2,20) (1,10) ]
    Element found: (4,1) 
    List after deleting an item: 
    [ (6,56) (5,40) (3,30) (2,20) (1,10) ]
    Element not found.
    List after sorting the data: 
    [ (1,10) (2,20) (3,30) (5,40) (6,56) ]
    List after reversing the data: 
    [ (6,56) (5,40) (3,30) (2,20) (1,10) ]