- DSA 使用 C 教程
- 使用 C 的 DSA - 主页
- 使用 C 语言的 DSA - 概述
- 使用 C 语言的 DSA - 环境
- 使用 C 算法的 DSA
- 使用 C 的 DSA - 概念
- 使用 C 数组的 DSA
- 使用 C 链表的 DSA
- 使用 C 的 DSA - 双向链表
- 使用 C 的 DSA - 循环链表
- 使用 C 的 DSA - 堆栈内存溢出
- 使用 C 的 DSA - 解析表达式
- 使用 C 队列的 DSA
- 使用 C 的 DSA - 优先级队列
- 使用 C 树的 DSA
- 使用 C 哈希表的 DSA
- 使用 C 堆的 DSA
- 使用 C - Graph 的 DSA
- 使用 C 搜索技术的 DSA
- 使用 C 排序技术的 DSA
- 使用 C 的 DSA - 递归
- 使用 C 语言的 DSA 有用资源
- 使用 C 的 DSA - 快速指南
- 使用 C 的 DSA - 有用资源
- 使用 C 的 DSA - 讨论
使用 C 的 DSA - 双向链表
概述
双链表是链表的一种变体，与单链表相比，双链表可以轻松地向前和向后两种方式进行导航。以下是理解双向链表概念的重要术语。
链接- 链表的每个链接都可以存储称为元素的数据。
Next - 链接列表的每个链接都包含一个指向下一个链接的链接，称为“Next”。
Prev - 链接列表的每个链接都包含一个指向称为 Prev 的上一个链接的链接。
LinkedList - LinkedList 包含指向名为 First 的第一个链接和名为 Last 的最后一个链接的连接链接。
双向链表表示
根据上图所示，以下是需要考虑的要点。
双向链表包含一个名为first 和last 的链接元素。
每个链接携带一个数据字段和一个接下来调用的链接字段。
每个链接都使用其下一个链接与其下一个链接进行链接。
每个链接都使用其上一个链接与其前一个链接进行链接。
Last Link 带有一个为 null 的 Link 来标记列表的结尾。
基本操作
以下是列表支持的基本操作。
插入- 在列表的开头添加一个元素。
删除- 删除列表开头的元素。
Insert Last - 在列表末尾添加一个元素。
删除最后一个- 从列表末尾删除一个元素。
Insert After - 在列表的项目之后添加一个元素。
删除- 使用 key 从列表中删除一个元素。
向前显示- 以向前方式显示完整列表。
向后显示- 以向后方式显示完整列表。
插入操作
以下代码演示了双向链表开头的插入操作。
//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;
}
例子
双链表Demo.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;
printf(" ");
}
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;
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 = key;
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;
}
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) (4,13) (3,30) (2,20) ] List , after delete key(4) : [ (5,40) (4,13) (3,30) (2,20) ]