链表 (Linked List)

LNode

---

Define (定义)

​ 链表 是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而顺序表相应的时间复杂度分别是O(logn)和O(1)。

Structure (类型)

• 单向链表：链表中最简单的一种是单向链表，它包含两个域，一个信息域和一个指针域。这个链接指向列表中的下一个节点，而最后一个节点则指向一个空值。

一个单向链表包含两个值: 当前节点的值和一个指向下一个节点的链接

• 双向链表：与单向链表相比，双向链表记录了两个方向的引用。双向链表的节点定义同时包含指向后继节点（下一个节点）和前驱节点（上一个节点）的引用（指针）。相较于单向链表，双向链表更具灵活性，可以朝两个方向遍历链表，但相应地也需要占用更多的内存空间。

一个双向链表有三个整数值: 数值, 向后的节点链接, 向前的节点链接

• 环形链表：如果我们令单向链表的尾节点指向头节点（首尾相接），则得到一个环形链表。在环形链表中，任意节点都可以视作头节点。

  

  用单向链表构建的循环链表

Application (应用)

单向链表通常用于实现栈、队列、哈希表和图等数据结构。

• 栈与队列：当插入和删除操作都在链表的一端进行时，它表现出先进后出的特性，对应栈；当插入操作在链表的一端进行，删除操作在链表的另一端进行，它表现出先进先出的特性，对应队列。

• 哈希表：链式地址是解决哈希冲突的主流方案之一，在该方案中，所有冲突的元素都会被放到一个链表中。

• 图：邻接表是表示图的一种常用方式，其中图的每个顶点都与一个链表相关联，链表中的每个元素都代表与该顶点相连的其他顶点。

双向链表常用于需要快速查找前一个和后一个元素的场景。

• 高级数据结构：比如在红黑树、B 树中，我们需要访问节点的父节点，这可以通过在节点中保存一个指向父节点的引用来实现，类似于双向链表。

• 浏览器历史：在网页浏览器中，当用户点击前进或后退按钮时，浏览器需要知道用户访问过的前一个和后一个网页。双向链表的特性使得这种操作变得简单。

• LRU 算法：在缓存淘汰（LRU）算法中，我们需要快速找到最近最少使用的数据，以及支持快速添加和删除节点。这时候使用双向链表就非常合适。

环形链表常用于需要周期性操作的场景，比如操作系统的资源调度。

• 时间片轮转调度算法：在操作系统中，时间片轮转调度算法是一种常见的 CPU 调度算法，它需要对一组进程进行循环。每个进程被赋予一个时间片，当时间片用完时，CPU 将切换到下一个进程。这种循环操作可以通过环形链表来实现。

• 数据缓冲区：在某些数据缓冲区的实现中，也可能会使用环形链表。比如在音频、视频播放器中，数据流可能会被分成多个缓冲块并放入一个环形链表，以便实现无缝播放。

Code Example (代码实例)

Singly linked list (单链表)

结构

typedef struct  LNode
{
	int data ; //数据域，用于存储数据
	struct LNode *next ; //指针，可以用来访问节点数据，也可以遍历，指向下一个节点
} LNode, *LinkList;
//LNode表示结点的类型，LinkList表示指向Node结点类型的指针类型

初始化

LinkedList listinit() {
    Node *L;
    L=(Node*)malloc(sizeof(Node));      //开辟空间 
    if(L==NULL){                     //判断是否开辟空间失败，这一步很有必要
        printf("申请空间失败");
        //exit(0);                  //开辟空间失败可以考虑直接结束程序
    }
    L->next=NULL;       //指针指向空
}

头插入

void insertHead(int e) {
    // 创建新节点
    struct LNode* newNode = (struct LNode*)malloc(sizeof(struct LNode));
    newNode->data = e;
    newNode->next = head;

    // 将新节点设置为头节点
    head = newNode;
}

尾插入

void insertLast(int e) {
    // 创建新节点
    struct LNode* newNode = (struct LNode*)malloc(sizeof(struct LNode));
    newNode->data = e;
    newNode->next = NULL;

    // 如果链表为空，将新节点作为头节点
    if (head == NULL) {
        head = newNode;
    } else {
        // 找到链表的最后一个节点
        struct LNode* lastNode = head;
        while (lastNode->next != NULL) {
            lastNode = lastNode->next;
        }

        // 将新节点插入到链表尾部
        lastNode->next = newNode;
    }
}

删除

bool deleteNode(struct LNode** head, int key) {
    struct LNode* temp;

    // 如果头节点的数据域等于key,需要删除头节点
    if ((*head)->data == key) {
        temp = *head;
        *head = (*head)->next;
        free(temp);
        return true;
    } else {
        // 在链表中查找并删除值为key的节点
        struct LNode* pre = *head;
        while (pre->next != NULL) {
            if (pre->next->data == key) {
                temp = pre->next;
                pre->next = pre->next->next;
                free(temp);
                return true;
            }
            pre = pre->next;
        }
    }

    // 如果没有找到值为key的节点,返回false
    return false;
}

搜索

// 函数用于在链表中搜索给定的元素
struct Node* search(struct Node* head, int key) {
    struct Node* temp = head;
    while (temp != NULL) {
        if (temp->data == key) {
            return temp;
        }
        temp = temp->next;
    }
    return NULL;
}

完整代码

#include<stdio.h>
#include<stdlib.h>

// 定义链表节点
struct Node {
    int data;
    struct Node* next;
};

// 函数用于创建新的节点
struct Node* createNewNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// 函数用于将新节点添加到链表的末尾
struct Node* addNode(struct Node* head, int data) {
    struct Node* newNode = createNewNode(data);
    if (head == NULL) {
        head = newNode;
    } else {
        struct Node* temp = head;
        while (temp->next != NULL) {
            temp = temp->next;
        }
        temp->next = newNode;
    }
    return head;
}

// 函数用于在链表中搜索给定的元素
struct Node* search(struct Node* head, int key) {
    struct Node* temp = head;
    while (temp != NULL) {
        if (temp->data == key) {
            return temp;
        }
        temp = temp->next;
    }
    return NULL;
}

int main() {
    struct Node* head = NULL;

    // 添加节点到链表
    head = addNode(head, 10);
    head = addNode(head, 20);
    head = addNode(head, 30);
    head = addNode(head, 40);

    // 在链表中搜索元素
    int key = 30;
    struct Node* found = search(head, key);
    if (found != NULL) {
        printf("Element %d found in the list\n", key);
    } else {
        printf("Element %d not found in the list\n", key);
    }

    return 0;
}

Double linked list (双向链表)

在单链表的基础上，双链表（Double linked list）是其扩展形式。区别在于双链表的节点不仅仅含有指向下一个节点的指针，同时还含有指向上一个节点的指针。这使得双链表可以从两个方向遍历：向前和向后。

结构定义

struct DoubleNode {
    int data;
    struct DoubleNode* prev;
    struct DoubleNode* next;
};

创建新节点

创建新节点时，需要初始化其数据部分，以及前后指针部分。

struct DoubleNode* createNewDoubleNode(int data) {
    struct DoubleNode* newNode = (struct DoubleNode*)malloc(sizeof(struct DoubleNode));
    newNode->data = data;
    newNode->prev = NULL;
    newNode->next = NULL;
    return newNode;
}

添加节点

在双链表中添加节点稍微复杂一些，因为除了要处理新节点的next指针，还要处理prev指针。

void addNodeToEnd(struct DoubleNode** head, int data) {
    struct DoubleNode* newNode = createNewDoubleNode(data);
    if (*head == NULL) {
        *head = newNode;
    } else {
        struct DoubleNode* temp = *head;
        while (temp->next != NULL) {
            temp = temp->next;
        }
        temp->next = newNode;
        newNode->prev = temp;
    }
}

遍历

双链表既可以向前遍历也可以向后遍历，提供更多的灵活性。

// 向前遍历
void printListForward(struct DoubleNode* head) {
    struct DoubleNode* temp = head;
    while (temp != NULL) {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}

// 向后遍历
void printListBackward(struct DoubleNode* head) {
    struct DoubleNode* temp = head;
    // 先到达链表的最后一个节点
    while (temp->next != NULL) {
        temp = temp->next;
    }
    // 从后向前遍历
    while (temp != NULL) {
        printf("%d ", temp->data);
        temp = temp->prev;
    }
    printf("\n");
}

通过以上定义和函数，我们可以灵活地管理和使用双链表数据结构，轻松地进行节点的添加、删除和遍历操作。

Circular linked list (循环链表)

循环链表是链表的一种，其中最后一个节点指向链表的第一个节点，形成一个环。与单链表和双链表相比，循环链表的优点是从链表的任何一个节点都可以访问到链表中的所有其他节点。这种类型的链表在需要周期性访问各个节点的场合（如轮转调度算法）中特别有用。

循环链表的实现可以基于单链表或双链表的结构进行扩展，主要的区别在于链表的尾节点指向链表的头节点，形成一个闭环。

完整代码:

// Some codec
#include <stdio.h>
#include <stdlib.h>

// 定义节点结构体
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// 创建新节点
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// 插入节点
void insertNode(Node** head, int data) {
    Node* newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
        newNode->next = newNode;
    } else {
        Node* last = (*head)->next;
        while (last->next != *head) {
            last = last->next;
        }
        last->next = newNode;
        newNode->next = *head;
    }
}

// 遍历链表
void traverseList(Node* head) {
    if (head == NULL) {
        printf("List is empty.\n");
        return;
    }
    Node* current = head;
    do {
        printf("%d ", current->data);
        current = current->next;
    } while (current != head);
    printf("\n");
}

int main() {
    Node* head = NULL;

    // 插入节点
    insertNode(&head, 1);
    insertNode(&head, 2);
    insertNode(&head, 3);
    insertNode(&head, 4);

    // 遍历链表
    printf("Circular List: ");
    traverseList(head);

    return 0;
}

Citing (引用)

• Hello-算法

• Wikipedia

• 图码

• 课程平台