欢迎您访问 最编程 本站为您分享编程语言代码，编程技术文章！

热门搜索/Hot Search

您现在的位置是： 首页

单链接表表头插入和表尾插入代码 - Nuggets

最编程 2024-06-11 13:07:40
...

单链表是一种常用的数据结构，它由多个节点组成，每个节点包括一个数据域和一个指针域，指向下一个节点。单链表的头节点没有前驱节点，它用来记录链表的起始位置。

单链表的插入操作分为两种，分别是头插法和尾插法。它们的区别在于新节点插入到链表的哪个位置。

以下是单链表头插法和尾插法的示例代码，其中假设链表节点的数据域为整型，指针域为指向下一个节点的指针。

单链表头插法代码示例：

#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};

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

int main() {
    ListNode* head = NULL;
    head = insertAtHead(head, 3);
    head = insertAtHead(head, 2);
    head = insertAtHead(head, 1);
    // 遍历链表
    ListNode* p = head;
    while (p != NULL) {
        cout << p->val << " ";
        p = p->next;
    }
    cout << endl;
    return 0;
}

单链表尾插法代码示例：

#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};

ListNode* insertAtTail(ListNode* head, int val) {
    ListNode* node = new ListNode(val);
    if (head == NULL) {
        head = node;
    } else {
        ListNode* p = head;
        while (p->next != NULL) {
            p = p->next;
        }
        p->next = node;
    }
    return head;
}

int main() {
    ListNode* head = NULL;
    head = insertAtTail(head, 1);
    head = insertAtTail(head, 2);
    head = insertAtTail(head, 3);
    // 遍历链表
    ListNode* p = head;
    while (p != NULL) {
        cout << p->val << " ";
        p = p->next;
    }
    cout << endl;
    return 0;
}

在头插法中，新节点插入到链表头部，因此每次插入时都需要将新节点的 next 指针指向原头节点，然后将头指针指向新节点。

在尾插法中，新节点插入到链表尾部，因此需要遍历链表找到尾节点，然后将尾节点的 next 指针指向新节点。如果链表为空，则将头指针直接指向新节点。

注意在代码实现时，需要注意特殊情况，如链表为空的情况，以及遍历链表时需要判断节点指针是否为空。

上一篇： 单个链接表 - 单个链接表的定义和基本操作（头部插入、尾部插入以建立表格、查找、插入、删除等）

下一篇： 头部插入和尾部插入摘要（活动影像版）

推荐阅读