链表与双向链表详解

双向链表的结构示意图

NULL ←─┐     ┌──→ ┌──→ ┌──→ NULL
       │     │    │    │
    ┌─────┬─────┬─────┐
    │ PREV│DATA1│NEXT │
    └──┼──┴──┬──┴──┼──┘
       │     │    │
       │  ┌──↓──┬─────┬──↑──┐
       └──┤PREV │DATA2│NEXT │
          └─────┴──┬──┴─────┘
                   │
                ┌──↓──┬─────┬──↑──┐
                │PREV │DATA3│NEXT │
                └─────┴─────┴─────┘

带头双向循环链表

在实际应用中，最常用的是带头双向循环链表，其特点如下：

• 拥有一个不存储有效数据的头节点
• 最后一个节点的next指针指向头节点
• 头节点的prev指针指向最后一个节点
• 形成了一个真正意义上的双向循环结构

  ┌──────────────────────────────────────────────┐
  │                                              │
  ↓                                              │
┌─────┬─────┬─────┐   ┌─────┬─────┬─────┐   ┌─────┬─────┬─────┐
│PREV │HEAD │NEXT │←──│PREV │DATA1│NEXT │←──│PREV │DATA2│NEXT │
└──┬──┴─────┴──↑──┘   └──↑──┴─────┴──┬──┘   └──↑──┴─────┴──┬──┘
   │            │        │            │        │            │
   └────────────┘        └────────────┘        └────────────┘

单链表节点定义 (C语言)

// 定义单链表节点结构
typedef struct ListNode {
    int data;              // 数据域
    struct ListNode* next; // 指针域
} ListNode;

双向链表节点定义 (C语言)

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

Java中的链表实现

// 单链表节点
class ListNode {
    int val;
    ListNode next;
    
    ListNode(int val) {
        this.val = val;
        this.next = null;
    }
}

// 双向链表节点
class DoublyListNode {
    int val;
    DoublyListNode prev;
    DoublyListNode next;
    
    DoublyListNode(int val) {
        this.val = val;
        this.prev = null;
        this.next = null;
    }
}

链表的生命周期包括创建、各种操作以及最终的销毁。以下是链表生命周期的流程图：

1. 创建空链表

// 创建一个空的单链表
ListNode* createList() {
    return NULL; // 空链表的头指针为NULL
}

2. 头插法插入节点

// 在链表头部插入节点
ListNode* insertAtHead(ListNode* head, int data) {
    // 创建新节点
    ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
    if (newNode == NULL) {
        printf("内存分配失败\n");
        return head;
    }
    
    // 初始化新节点
    newNode->data = data;
    newNode->next = head;
    
    // 返回新的头节点
    return newNode;
}

3. 尾插法插入节点

// 在链表尾部插入节点
ListNode* insertAtTail(ListNode* head, int data) {
    // 创建新节点
    ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
    if (newNode == NULL) {
        printf("内存分配失败\n");
        return head;
    }
    
    // 初始化新节点
    newNode->data = data;
    newNode->next = NULL;
    
    // 如果链表为空，直接返回新节点作为头节点
    if (head == NULL) {
        return newNode;
    }
    
    // 找到尾节点
    ListNode* current = head;
    while (current->next != NULL) {
        current = current->next;
    }
    
    // 将新节点连接到尾节点后
    current->next = newNode;
    
    return head;
}

4. 删除节点

// 删除指定值的节点
ListNode* deleteNode(ListNode* head, int data) {
    // 如果链表为空，直接返回
    if (head == NULL) {
        return NULL;
    }
    
    // 如果头节点就是要删除的节点
    if (head->data == data) {
        ListNode* temp = head;
        head = head->next;
        free(temp);
        return head;
    }
    
    // 查找要删除的节点
    ListNode* current = head;
    while (current->next != NULL && current->next->data != data) {
        current = current->next;
    }
    
    // 如果找到了要删除的节点
    if (current->next != NULL) {
        ListNode* temp = current->next;
        current->next = temp->next;
        free(temp);
    }
    
    return head;
}

5. 查找节点

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

6. 销毁链表

// 销毁链表，释放所有内存
void destroyList(ListNode* head) {
    ListNode* current = head;
    ListNode* next;
    
    // 逐个释放节点内存
    while (current != NULL) {
        next = current->next;
        free(current);
        current = next;
    }
}

1. 创建带头节点的双向循环链表

// 创建带头节点的双向循环链表
DListNode* createDList() {
    // 分配头节点内存
    DListNode* head = (DListNode*)malloc(sizeof(DListNode));
    if (head == NULL) {
        printf("内存分配失败\n");
        return NULL;
    }
    
    // 初始化头节点，形成自环
    head->data = 0;  // 头节点数据域通常不使用
    head->prev = head;
    head->next = head;
    
    return head;
}

2. 在指定节点后插入新节点

// 在pos节点后插入新节点
void insertAfter(DListNode* pos, int data) {
    if (pos == NULL) {
        return;
    }
    
    // 创建新节点
    DListNode* newNode = (DListNode*)malloc(sizeof(DListNode));
    if (newNode == NULL) {
        printf("内存分配失败\n");
        return;
    }
    
    // 初始化新节点
    newNode->data = data;
    
    // 调整指针关系，插入新节点
    newNode->next = pos->next;
    newNode->prev = pos;
    pos->next->prev = newNode;
    pos->next = newNode;
}

3. 在指定节点前插入新节点

// 在pos节点前插入新节点
void insertBefore(DListNode* pos, int data) {
    if (pos == NULL) {
        return;
    }
    
    // 复用insertAfter，在前一个节点之后插入等价于在当前节点之前插入
    insertAfter(pos->prev, data);
}

4. 删除指定节点

// 删除链表中的节点（不包括头节点）
void deleteNode(DListNode* node) {
    if (node == NULL || node->next == node) {
        // 节点为空或者是自环（可能是头节点）
        return;
    }
    
    // 调整前后节点的指针，跳过要删除的节点
    node->prev->next = node->next;
    node->next->prev = node->prev;
    
    // 释放节点内存
    free(node);
}

5. 查找节点

// 在双向链表中查找指定值的节点
DListNode* findNode(DListNode* head, int data) {
    if (head == NULL) {
        return NULL;
    }
    
    // 从头节点的下一个节点开始查找（跳过头节点）
    DListNode* current = head->next;
    
    // 遍历链表，直到回到头节点
    while (current != head) {
        if (current->data == data) {
            return current; // 找到节点
        }
        current = current->next;
    }
    
    return NULL; // 未找到节点
}

6. 销毁双向循环链表

// 销毁双向循环链表
void destroyDList(DListNode* head) {
    if (head == NULL) {
        return;
    }
    
    DListNode* current = head->next;
    DListNode* next;
    
    // 释放所有非头节点内存
    while (current != head) {
        next = current->next;
        free(current);
        current = next;
    }
    
    // 释放头节点内存
    free(head);
}