1.链表算法
链表是一系列数据结构，通过链接连接在一起。
链接列表是包含项目的一系列链接。每个链接都包含与另一个链接的连接。链表是数组后第二常用的数据结构。以下是理解链表的概念的重要术语。
- 链接 - 链接列表的每个链接都可以存储称为元素的数据。
- Next - 链接列表的每个链接都包含指向下一个名为Next的链接的链接。
- LinkedList - 链接列表包含指向名为First的第一个链接的连接链接。
链表清单表示
链表可以显示为节点链，其中每个节点指向下一个节点。
根据以上说明，以下是要考虑的重点。
- 链接列表包含一个名为first的链接元素。
- 每个链路都带有一个数据字段和一个名为next的链接字段。
- 每个链接使用其下一个链接与其下一个链接链接。
- 最后一个链接带有一个null链接以标记列表的结尾。
链表的类型
以下是各种类型的链表。
- 简单链接列表 - 项目导航仅向前。
- 双向链接列表 - 可以向前和向后导航项目。
- 循环链接列表 - 最后一项包含第一个元素的链接作为下一个，第一个元素具有前一个元素的链接。
基本操作
以下是列表支持的基本操作。
- 插入 - 在列表的开头添加元素。
- 删除 - 删除列表开头的元素。
- 显示 - 显示完整列表。
- 搜索 - 使用给定键搜索元素。
- 删除 - 使用给定键删除元素。
插入操作
在链表中添加新节点是一个以上的步骤活动。我们将在这里用图表来学习。首先，使用相同的结构创建一个节点，并找到它必须插入的位置。
想象一下，我们在 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。
我们将使用temp节点使头节点指向新的第一个节点。
2.双链表算法
双向链接列表是链接列表的变体，与单链接列表相比，可以以两种方式轻松地向前和向后导航。以下是理解双向链表概念的重要术语。
- 链接 - 链接列表的每个链接都可以存储称为元素的数据。
- Next - 链接列表的每个链接都包含指向下一个名为Next的链接的链接。
- 上一页 - 链表的每个链接都包含一个名为Prev的上一个链接的链接。
- LinkedList - 链接列表包含指向名为First的第一个链接和名为Last的最后一个链接的连接链接。
双重链表清单表示
根据以上说明，以下是要考虑的重点。
- 双链表包含一个名为first和last的链接元素。
- 每个链路都带有一个数据字段和两个名为next和prev的链接字段。
- 每个链接使用其下一个链接与其下一个链接链接。
- 每个链接使用其先前的链接与其先前的链接链接。
- 最后一个链接带有一个null链接以标记列表的结尾。
基本操作
以下是列表支持的基本操作。
- 插入 - 在列表的开头添加元素。
- 删除 - 删除列表开头的元素。
- Insert Last - 在列表末尾添加元素。
- 最后 删除 - 从列表末尾删除元素。
- Insert After - 在列表项 之后 添加元素。
- 删除 - 使用键从列表中删除元素。
- 显示转发 - 以转发方式显示完整列表。
- 向后 显示 - 以向后方式显示完整列表。
插入操作
下面的代码演示了双向链表开头的插入操作。
实例
//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; }
3.循环链表算法
圆形链接列表是链接列表的变体，其中第一个元素指向最后一个元素，最后一个元素指向第一个元素。单链表和双链表都可以制成循环链表。
单链表作为通函
在单链表中，最后一个节点的下一个指针指向第一个节点。
双重挂钩清单为通函
在双向链表中，最后一个节点的下一个指针指向第一个节点，第一个节点的前一个指针指向最后一个节点，在两个方向上形成圆形。
根据以上说明，以下是要考虑的重点。
- 最后一个链接的下一个链接指向列表的第一个链接，无论是单链还是双链表。
- 在双链表的情况下，第一个链接的前一个指向列表的最后一个。
基本操作
以下是循环列表支持的重要操作。
- insert - 在列表的开头插入一个元素。
- delete - 从列表的开头删除元素。
- display - 显示列表。
插入操作
下面的代码演示了基于单个链表的循环链表中的插入操作。
实例
//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()) { head = link; head->next = head; } else { //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; if(head->next == head) { head = NULL; return tempLink; } //mark next to first link as first head = head->next; //return the deleted link return tempLink; }
显示列表操作
以下代码演示了循环链表中的显示列表操作。
//display the list void printList() { struct node *ptr = head; printf("\n[ "); //start from the beginning if(head != NULL) { while(ptr->next != ptr) { printf("(%d,%d) ",ptr->key,ptr->data); ptr = ptr->next; } } printf(" ]"); }
