[数据结构] - - - 链表

一、定义

链表：是一种常见的线性数据结构，它通过一组节点（Node）来存储数据，每个节点包含两部分：数据域和指针域。

1.1 链表的基本概念

• 节点（Node）：链表的最小单元，包含数据域（Data）与指针域（Pointer）两部分。

  • 数据域：用于存储数据，可以是任意类型（如整数、字符串、对象灯）。

  • 指针域：用于存储指向下一个节点的地址（或引用）。在某些链表（如双向链表）中，还可能包含指向前一个节点的地址。

• 头节点（Head）：链表的第一个节点，通常用一个指针（如head）来标识链表的起始位置。

• 尾节点（Tail）：链表的最后一个节点，其指针域通常指向null，表示链表的结束。

二、类型

链表可以分为以下几种类型：单链表、双向链表、循环链表、双向循环链表等。

2.1 单链表（Singly Linked List）

单链表是链表的一种最基本形式，它由一系列节点组成，每个节点包含两部分：数据域和指针域。单链表的特点是每个节点的指针域只指向下一个节点，形成一个线性的结构。

示例结构：

特点：

• 只能从头节点开始向后遍历，不能反向遍历。

// 定义单链表的节点结构体
typedef struct Node {
    int data;               // 数据域
    struct Node* next;      // 指向下一个节点的指针
} Node;

2.2 双向链表（Doubly Linked List）

双向链表（Doubly Linked List）是一种更灵活的链表结构，与单链表相比，它在每个节点中增加了指向前一个节点的指针。

示例结构：

特点：

• 1、双向遍历：可以从任意节点向前或向后遍历，操作更加灵活。

• 2、插入和删除操作高效：

  • 插入和删除节点时，只需要修改相邻节点的指针，时间复杂度为O(1)。

  • 由于有前驱指针，插入和删除操作更加直观。

• 3、存储开销较大：每个节点需要存储两个指针（prev和next），增加了存储空间的开销。

• 4、实现复杂：操作需要同时处理两个指针，代码实现相对复杂。

// 定义双向链表的节点结构体
typedef struct Node {
    int data;               // 数据域
    struct Node* prev;      // 指向前一个节点的指针
    struct Node* next;      // 指向后一个节点的指针
} Node;

2.3 循环链表（Circular Linked Lis）

循环链表是一种特殊的链表结构，其特点是尾节点的指针指向头节点，形成一个环形结构。

示例结构：

特点：

• 1、环形结构：

  • 尾节点的next指针指向头节点，而不是NULL。

  • 没有明显的“尾节点”，链表形成一个闭环。

• 2、遍历特性：

  • 从任意节点出发，可以遍历整个链表。

  • 需要特别注意循环条件，避免无限循环。

• 3、操作效率：

  • 插入和删除操作的时间复杂度为O(1)，但需要特别处理循环特性。

  • 适合需要频繁遍历或操作的场景

// 定义单向循环链表的节点结构体
typedef struct Node {
    int data;               // 数据域
    struct Node* next;      // 指向下一个节点的指针
} Node;

2.4 循环双向链表

循环双向链表是一种更复杂的链表结构，它结合了双向链表和循环链表的特点。每个节点不仅包含指向下一个节点的指针，还包含指向前一个节点的指针，同时链表的尾节点的next指针指向头节点，头节点的prev指针指向尾节点，形成一个闭环。

示例结构：

特点：

• 1、双向遍历：可以从任意节点向前或向后遍历。

• 2、循环结构：尾节点的next指针指向头节点，头节点的prev指针指向尾节点。

• 3、操作高效：插入和删除操作的时间复杂度为O(1)，且操作更直观。

• 4、灵活性高：适合需要频繁插入、删除以及双向遍历的场景。

• 5、实现复杂：需要同时处理两个指针，并且在操作时需要特别注意循环条件。

// 定义循环双向链表的节点结构体
typedef struct Node {
    int data;                      // 数据域
    struct Node* prev;             // 指向前一个节点的指针
    struct Node* next;             // 指向后一个节点的指针
} Node;

三、存储方式

链表中的节点在内存中不是连续分布的 ，而是散乱分布在内存中的某地址上，分配机制取决于操作系统的内存管理。

这个链表起始节点为2， 终止节点为7， 各个节点分布在内存的不同地址空间上，通过指针串联在一起。

四、操作

链表的操作主要包括插入、删除、查找、遍历等。

以单链表为例，以下是单链表操作的C语言实现。

4.1 定义单链表的节点结构

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

// 定义单链表的节点结构体
typedef struct Node {
    int data;               // 数据域
    struct Node* next;      // 指向下一个节点的指针
} Nod

4.2 初始化单链表

void initList(Node** head) {
    *head = NULL;  // 初始化头指针为NULL
}

4.3 创建新节点

Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));  // 动态分配内存
    if (newNode == NULL) {
        printf("内存分配失败!\n");
        exit(1);
    }
    newNode->data = data;  // 初始化数据
    newNode->next = NULL;  // 初始化指针
    return newNode;
}

4.4 插入节点

4.4.1 在链表头部插入节点

void insertAtHead(Node** head, int data) {
    Node* newNode = createNode(data);  // 创建新节点
    newNode->next = *head;
    *head = newNode;
}

4.4.2 在链表尾部插入节点

在链表尾部插入节点时，需要遍历到链表的最后一个节点，并将新节点连接到尾部。

void insertAtTail(Node** head, int data) {
    Node* newNode = createNode(data);  // 创建新节点
    if (*head == NULL) {  // 如果链表为空
        *head = newNode;  // 新节点成为头节点
    } else {
        Node* current = *head;
        while (current->next != NULL) {  // 遍历到链表尾部
            current = current->next;
        }
        current->next = newNode;  // 将新节点连接到尾部
    }
}

4.4.3 在指定位置插入节点

在指定位置插入节点时，需要找到插入位置的前一个节点，并将新节点插入。

void insertAtPosition(Node** head,  int data， int position) {
	if(position < 0) {
		printf("无效的位置\n");
		return;
	}
    Node* newNode = createNode(data);  // 创建新节点
    if (position == 0) {  // 在头部插入
        newNode->next = *head;
        *head = newNode;
    } else {
        Node* current = *head;
        int count = 0;
        while (current != NULL && count < position - 1) {  // 找到插入位置的前一个节点
            current = current->next;
            count++;
        }
        if (current == NULL) {
            printf("位置超出范围!\n");
            free(newNode);
            return;
        }
        newNode->next = current->next;
        current->next = newNode;
    }
}

4.5 删除节点

要想删除C节点，只要将B节点的next指针指向D节点就可以了。

4.5.1 删除头节点

void deleteHead(Node** head) {
    if (*head == NULL) {
        printf("链表为空\n");
        return;
    }
    Node* temp = *head;
    *head = (*head)->next;
    free(temp);
}

4.5.2 删除尾节点

void deleteTail(Node** head) {
    if (*head == NULL) {
        printf("链表为空\n");
        return;
    }
    if ((*head)->next == NULL) {
        free(*head);
        *head = NULL;
        return;
    }
    Node* temp = *head;
    while (temp->next->next != NULL) {
        temp = temp->next;
    }
    free(temp->next);
    temp->next = NULL;
}

4.5.3 删除指定位置的节点

void deleteAtPosition(Node** head, int position) {
    if (*head == NULL) {
        printf("链表为空\n");
        return;
    }
    if (position < 0) {
        printf("无效的位置\n");
        return;
    }
    if (position == 0) {
        Node* temp = *head;
        *head = (*head)->next;
        free(temp);
        return;
    }
    Node* temp = *head;
    for (int i = 0; i < position - 1 && temp->next != NULL; i++) {
        temp = temp->next;
    }
    if (temp->next == NULL) {
        printf("位置超出范围\n");
        return;
    }
    Node* nodeToDelete = temp->next;
    temp->next = temp->next->next;
    free(nodeToDelete);
}

4.6 查找指定值的节点

查找指定值的节点时，需要遍历链表并返回节点的指针。

Node* searchNode(Node* head, int data) {
    Node* current = head;
    while (current != NULL) {  // 遍历链表查找目标节点
        if (current->data == data) {
            return current;  // 找到节点，返回指针
        }
        current = current->next;
    }
    return NULL;  // 未找到节点，返回NULL
}

查找节点，返回节点位置（位置从0开始），未找到返回-1。

int searchNode(Node* head, int key) {
    int position = 0;
    Node* temp = head;
    while (temp != NULL) {
        if (temp->data == key) {
            return position;
        }
        temp = temp->next;
        position++;
    }
    return -1;
}

4.7 遍历并打印链表

void printList(Node* head) {
    Node* current = head;
    while (current != NULL) {  // 遍历链表
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}

五、性能分析

链表与数组的区别：

1、存储方式：

• 数组：

  • 连续存储：数组的元素在内存中是连续存储的，每个元素的地址可以通过起始地址和偏移量直接计算。

  • 固定大小：数组的大小在声明时通常需要固定，虽然动态数组可以动态扩展，但底层仍然需要重新分配内存并复制数据。

• 链表：

  • 离散存储：链表的节点可以分散在内存的任意位置，每个节点通过指针连接。

  • 动态大小：链表的大小可以动态变化，插入或删除节点时不需要移动其他元素，只需修改指针。

2、访问效率：

• 数组：随机访问：数组支持通过索引直接访问任意位置的元素，时间复杂度为O(1)。

• 链表：顺序访问：链表不支持随机访问，访问某个节点需要从头节点开始逐个遍历，时间复杂度为O(n)。

3、插入和删除操作

• 数组：插入和删除：在数组中插入或删除元素时，通常需要移动大量元素以保持连续性，时间复杂度为O(n)。例如，在数组头部插入元素时，需要将所有元素向后移动一位。

• 链表：插入和删除：链表的插入和删除操作只需修改相邻节点的指针，时间复杂度为O(1)（如果已知插入或删除位置的指针）。例如，在链表头部插入或删除节点时，只需修改头指针。

4、内存使用

• 数组：

  • 内存分配：数组需要预先分配固定大小的内存，即使某些位置未使用，也会占用内存。

  • 内存碎片：数组需要连续内存空间，可能导致内存碎片化问题，尤其是在频繁动态分配和释放时。

• 链表：

  • 动态分配：链表的节点是动态分配的，每个节点只占用实际需要的内存，内存使用更灵活。

  • 额外开销：链表的每个节点需要额外存储指针（单链表需要一个指针，双向链表需要两个指针），增加了内存开销。

5、扩展性和灵活性

• 数组：

  • 固定大小：数组的大小在声明时固定，扩展数组需要重新分配内存并复制数据。

  • 适用场景：适合存储大小固定且需要频繁随机访问的数据。

• 链表：

  • 动态大小：链表的大小可以动态变化，适合存储大小不确定或频繁变化的数据。

  • 适用场景：适合需要频繁插入和删除操作的场景，如实现队列、栈、动态集合等。