L5_04 链表

一、链表概述

链表是一种线性数据结构，它通过指针将一系列节点连接起来。与数组不同，链表的元素在内存中不需要连续存储，每个节点包含数据和指向下一个节点的指针。

1.1 链表的特点

• 优点：

  • 插入和删除操作效率高（O(1)）
  • 不需要预先分配内存空间
  • 动态扩展方便

• 缺点：

  • 访问元素需要遍历（O(n)）
  • 需要额外的内存空间存储指针

1.2 链表的类型

• 单链表：每个节点只有一个指向下一个节点的指针
• 双链表：每个节点有两个指针，分别指向前一个和后一个节点
• 循环链表：最后一个节点的指针指向头节点，形成一个环

---

二、单链表的实现

2.1 节点结构定义

struct Node {
    int data;
    Node* next;
    
    Node(int val) : data(val), next(nullptr) {}
};

2.2 创建单链表

Node* createList(const vector<int>& arr) {
    if (arr.empty()) return nullptr;
    
    Node* head = new Node(arr[0]);
    Node* current = head;
    
    for (size_t i = 1; i < arr.size(); ++i) {
        current->next = new Node(arr[i]);
        current = current->next;
    }
    
    return head;
}

2.3 遍历单链表

void traverseList(Node* head) {
    Node* current = head;
    while (current != nullptr) {
        cout << current->data << " ";
        current = current->next;
    }
    cout << endl;
}

2.4 插入节点

Node* insertAtHead(Node* head, int val) {
    Node* newNode = new Node(val);
    newNode->next = head;
    return newNode;
}

Node* insertAtTail(Node* head, int val) {
    Node* newNode = new Node(val);
    
    if (head == nullptr) {
        return newNode;
    }
    
    Node* current = head;
    while (current->next != nullptr) {
        current = current->next;
    }
    current->next = newNode;
    
    return head;
}

Node* insertAtPosition(Node* head, int val, int pos) {
    if (pos == 0) {
        return insertAtHead(head, val);
    }
    
    Node* newNode = new Node(val);
    Node* current = head;
    int currentPos = 0;
    
    while (current != nullptr && currentPos < pos - 1) {
        current = current->next;
        currentPos++;
    }
    
    if (current != nullptr) {
        newNode->next = current->next;
        current->next = newNode;
    }
    
    return head;
}

2.5 删除节点

Node* deleteAtHead(Node* head) {
    if (head == nullptr) return nullptr;
    
    Node* temp = head;
    head = head->next;
    delete temp;
    return head;
}

Node* deleteAtTail(Node* head) {
    if (head == nullptr) return nullptr;
    if (head->next == nullptr) {
        delete head;
        return nullptr;
    }
    
    Node* current = head;
    while (current->next->next != nullptr) {
        current = current->next;
    }
    
    delete current->next;
    current->next = nullptr;
    return head;
}

Node* deleteByValue(Node* head, int val) {
    if (head == nullptr) return nullptr;
    
    if (head->data == val) {
        Node* temp = head;
        head = head->next;
        delete temp;
        return head;
    }
    
    Node* current = head;
    while (current->next != nullptr && current->next->data != val) {
        current = current->next;
    }
    
    if (current->next != nullptr) {
        Node* temp = current->next;
        current->next = current->next->next;
        delete temp;
    }
    
    return head;
}

2.6 查找节点

Node* search(Node* head, int val) {
    Node* current = head;
    while (current != nullptr) {
        if (current->data == val) {
            return current;
        }
        current = current->next;
    }
    return nullptr;
}

---

三、双链表的实现

3.1 双链表节点结构

struct DoubleNode {
    int data;
    DoubleNode* prev;
    DoubleNode* next;
    
    DoubleNode(int val) : data(val), prev(nullptr), next(nullptr) {}
};

3.2 双链表的插入操作

DoubleNode* insertAtHead(DoubleNode* head, int val) {
    DoubleNode* newNode = new DoubleNode(val);
    
    if (head != nullptr) {
        head->prev = newNode;
        newNode->next = head;
    }
    
    return newNode;
}

DoubleNode* insertAtTail(DoubleNode* head, int val) {
    DoubleNode* newNode = new DoubleNode(val);
    
    if (head == nullptr) {
        return newNode;
    }
    
    DoubleNode* current = head;
    while (current->next != nullptr) {
        current = current->next;
    }
    
    current->next = newNode;
    newNode->prev = current;
    
    return head;
}

3.3 双链表的删除操作

DoubleNode* deleteNode(DoubleNode* head, DoubleNode* node) {
    if (head == nullptr || node == nullptr) return head;
    
    if (head == node) {
        head = node->next;
    }
    
    if (node->prev != nullptr) {
        node->prev->next = node->next;
    }
    
    if (node->next != nullptr) {
        node->next->prev = node->prev;
    }
    
    delete node;
    return head;
}

---

四、循环链表

4.1 创建循环链表

Node* createCircularList(const vector<int>& arr) {
    if (arr.empty()) return nullptr;
    
    Node* head = new Node(arr[0]);
    Node* current = head;
    
    for (size_t i = 1; i < arr.size(); ++i) {
        current->next = new Node(arr[i]);
        current = current->next;
    }
    
    current->next = head;  // 形成循环
    return head;
}

4.2 遍历循环链表

void traverseCircularList(Node* head) {
    if (head == nullptr) return;
    
    Node* current = head;
    do {
        cout << current->data << " ";
        current = current->next;
    } while (current != head);
    cout << endl;
}

---

五、链表的应用场景

1. 实现栈和队列
2. 动态内存管理
3. 图的邻接表表示
4. 操作系统中的进程调度
5. 浏览器的前进后退功能

---

六、总结

链表是一种灵活的数据结构，适用于频繁插入和删除操作的场景。理解链表的基本操作是学习更复杂数据结构的基础。