数据结构头插法尾插法区别

数据结构中的头插法和尾插法是两种常见的插入元素的方式，它们的区别如下：

1. 头插法：
头插法是将新元素插入到链表或者队列的头部。具体步骤如下：
- 创建一个新节点，并将新节点的值设置为待插入的元素。
- 将新节点的指针指向原链表或队列的头节点。
- 更新链表或队列的头节点为新节点。

2. 尾插法：
尾插法是将新元素插入到链表或者队列的尾部。具体步骤如下：
- 创建一个新节点，并将新节点的值设置为待插入的元素。
- 将新节点的指针指向空（对于链表）或者下一个节点（对于队列）。
- 更新链表或队列的尾节点为新节点。

区别：
- 插入顺序：头插法在链表或队列的头部插入元素，而尾插法在链表或队列的尾部插入元素。
- 时间复杂度：头插法和尾插法的时间复杂度都是O(1)，因为只需要修改少量指针即可完成插入操作。
- 元素顺序：使用头插法插入的元素会逆序排列，而使用尾插法插入的元素会保持原有顺序。

相关问题

c++ 语言链表头插法

链表的头插法是指将新的节点插入到链表的头部，使其成为新的头节点。C++语言实现链表头插法的代码如下：

#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* newNode = new ListNode(val);
    newNode->next = head;
    return newNode;
}

void printList(ListNode* head) {
    ListNode* curr = head;
    while (curr) {
        cout << curr->val << " ";
        curr = curr->next;
    }
    cout << endl;
}

int main() {
    ListNode* head = NULL;

    // 插入元素
    head = insertAtHead(head, 3);
    head = insertAtHead(head, 2);
    head = insertAtHead(head, 1);

    // 打印链表
    printList(head);

    return 0;
}

在上面的代码中，我们定义了一个链表节点结构体 `ListNode`，其中包含一个整型变量 `val` 和一个指向下一个节点的指针 `next`。我们还定义了两个函数，一个用于在链表头插入新的节点 `insertAtHead`，另一个用于打印链表的所有节点 `printList`。

在 `insertAtHead` 函数中，我们首先创建一个新的节点 `newNode`，并将它的值设置为 `val`。然后将新节点的 `next` 指向当前链表头节点 `head`，最后将新节点作为新的头节点返回。

在 `main` 函数中，我们先初始化头节点 `head` 为空指针。然后使用 `insertAtHead` 函数向链表中插入三个元素。最后使用 `printList` 函数打印链表中的所有元素。

链表头插法是链表常用的一种操作，它的时间复杂度为 $O(1)$，非常高效。

c 语言单链表头插法

单链表头插法是将新节点插入到链表的头部，使其成为新的第一个节点，代码实现如下：

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

struct ListNode {
    int val;
    struct ListNode *next;
};

struct ListNode* createNode(int val) {
    struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));
    node->val = val;
    node->next = NULL;
    return node;
}

struct ListNode* addNode(struct ListNode* head, int val) {
    struct ListNode* node = createNode(val);
    node->next = head;
    return node;
}

int main() {
    struct ListNode* head = NULL; // 初始化链表为空
    head = addNode(head, 1);
    head = addNode(head, 2);
    head = addNode(head, 3);

    // 遍历链表
    struct ListNode* p = head;
    while (p != NULL) {
        printf("%d ", p->val);
        p = p->next;
    }

    return 0;
}

上述代码中，`createNode` 函数用于创建新节点，`addNode` 函数用于将新节点插入到链表头部，`head` 指针指向链表的头节点，初始化为 `NULL`，表示链表为空。在 `main` 函数中，我们使用 `addNode` 函数向链表中插入新节点，并且遍历链表输出节点的值。