单链表之头插法和尾插法详解

作者：热心市民鹿先生

2024.02.19 02:52

浏览量：10

简介：本文将详细介绍单链表中头插法和尾插法的实现原理和C语言代码实现。这两种方法在链表操作中具有广泛的应用，对于理解链表数据结构以及实际编程中的链表操作非常重要。

单链表是一种常见的数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。链表中的节点可以按照顺序访问，从头节点开始或从尾节点开始。头插法和尾插法是链表操作中的两种常用方法，它们分别在链表的头部和尾部插入新的节点。

一、头插法
头插法是指在链表的头部插入新节点的方法。每次插入新节点时，新节点将成为头节点，原来的头节点将成为第二个节点。这种方法的时间复杂度为O(1)，因为只需要修改指针即可。下面是一个用C语言实现头插法的示例代码：

#include <stdio.h>
#include <stdlib.h>
struct Node {
    int data;
    struct Node* next;
};
void insertAtHead(struct Node** head, int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = *head;
    *head = newNode;
}

在这个示例中，我们定义了一个结构体Node来表示链表节点，其中包含一个整型数据data和一个指向下一个节点的指针next。insertAtHead函数用于在链表的头部插入新节点，它接受一个指向头节点的指针的指针和一个整型数据作为参数。函数首先创建一个新的节点，然后将其next指针指向原来的头节点，最后将头指针指向新节点。

二、尾插法
尾插法是指在链表的尾部插入新节点的方法。每次插入新节点时，新节点将成为尾节点，原来的尾节点将成为倒数第二个节点。与头插法不同，尾插法需要遍历整个链表来找到尾节点，因此时间复杂度为O(n)。下面是一个用C语言实现尾插法的示例代码：

#include <stdio.h>
#include <stdlib.h>
struct Node {
    int data;
    struct Node* next;
};
void insertAtTail(struct Node** head, int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = NULL;
    if (*head == NULL) {
        *head = newNode;
        return;
    }
    struct Node* current = *head;
    while (current->next != NULL) {
        current = current->next;
    }
    current->next = newNode;
}

在这个示例中，我们同样定义了一个结构体Node来表示链表节点，并定义了一个函数insertAtTail用于在链表的尾部插入新节点。该函数接受一个指向头节点的指针的指针和一个整型数据作为参数。如果链表为空（头指针为NULL），则直接将新节点设置为头节点。否则，我们遍历整个链表找到尾节点，并将新节点的指针指向尾节点的下一个节点（即NULL），然后将尾节点的下一个指针指向新节点。这样，新节点就被插入到了链表的尾部。

总结：头插法和尾插法是单链表中常用的两种插入方法。头插法时间复杂度为O(1)，而尾插法时间复杂度为O(n)。在实际应用中，可以根据具体需求选择合适的插入方法来操作链表。

单链表之头插法和尾插法详解

最热文章