数据结构01：单链表模板类设计

一、代码（采用C++语言）

#ifndef LINKLIST_H

#define LINKLIST_H

#include<iostream>

using namespace std; 

template<typename T> class LinkList;

template<typename T>

class Node

{

public:

//构造函数

Node():next(NULL),data(0){}

Node(const T &t):data(t),next(NULL){}

Node(const Node<T> &n):data(n.data),next(NULL){}

//析构函数

~Node(){}

friend class LinkList<T>;

private:

T data;

Node<T>* next;

};

template<typename T> class LinkList

{

public:

LinkList(); //构造函数

LinkList(int n = 0, const T *array=NULL); //转换构造

LinkList(const LinkList &list); // (深)拷贝构造函数

~LinkList(); // 析构函数

LinkList& operator=(const LinkList &list); // 重载深赋值运算符

void showlist() const; // 显示链表

void Append(const T &t); // 插入元素

//void Delete(const T &t); //删除指定元素t所在的结点

//void insert(const T &t); //按照顺序插入指定元素t

void FreeList(); //释放所有结点

void insert(const T &e) ;

void Delete(const T &e) ;

private:

Node<T>* head; //头指针

int size; //链表长度

};

  

template<typename T>

LinkList<T>::LinkList():size(0){

head = new Node<T>();

}

  

template<typename T>

LinkList<T>::LinkList(int n, const T *array) : head(new Node<T>()),size(0) {

if (array != NULL) {

for (int i = 0; i < n;i++) {

Append(array[i]);

}

}

}

  

template<typename T>

LinkList<T>::LinkList(const LinkList &list) : head(new Node<T>()) , size(0)

{

*this = list; //利用深赋值运算符重载来定深拷贝

}

  

template<typename T>

LinkList<T> & LinkList<T>::operator=(const LinkList &list)

{

if(this==&list)

return *this;

// 这是重载双目运算符函数时应该注意的问题。如果赋值表达式左、右两个对象为同一对象，贸然执行下面的语句将造成严重错误！

// 因为，尽管右边的对象list还被视为const常量对象，释放了左边对象（即本对象）的所有结点后，右边对象的所有结点也就不存在了

FreeList();

for(Node<T> *p =list.head->next;p!=NULL;p=p->next)

{

Append(p->data);

}

return *this;

}

  

template<typename T>

void LinkList<T>::Append(const T &t)

{

Node<T> *p = new Node<T>;

p->data = t;

p->next = NULL;

Node<T> *temp = head;

while (temp->next)

{

temp = temp->next;

}

temp->next = p;

size++;

}

  

template<typename T>

void LinkList<T>::FreeList() {

Node<T>* p = head->next;

while (p) {

Node<T>* temp = p; // 暂存当前节点

p = p->next; // 移动到下一个节点

delete temp; // 删除当前节点

}

head->next = NULL; // 重置头结点的指针

size = 0;

}

  

template <typename T>

LinkList<T>::~LinkList() // 析构函数

{

FreeList();

delete head ; //删除哨兵结点

}

template<typename T>

void LinkList<T>::showlist() const

{

Node<T> *p = head->next; // 跳过头结点

while (p)

{

cout << p->data << " -> ";

p = p->next;

}

cout << "NULL" << endl;

}

  

template<typename T>

void LinkList<T>::insert(const T &e) {

Node<T> *prev = head; // 前驱结点

Node<T> *curr = head->next; // 当前结点

Node<T> *newNode = new Node<T>(e); // 新结点

  

// 找到插入位置（保持有序）

while (curr != NULL && curr->data < e) {

prev = curr;

curr = curr->next;

}

// 插入新结点

prev->next = newNode;

newNode->next = curr;

size++;

}

  

template<typename T>

void LinkList<T>::Delete(const T &e) {

Node<T> *prev = head; // 前驱结点

Node<T> *curr = head->next; // 当前结点

  

// 遍历链表寻找目标结点

while (curr != NULL) {

if (curr->data == e) {

prev->next = curr->next; // 将前驱结点指向当前结点的下一个结点

delete curr; // 删除当前结点

size--;

cout << "Element " << e << " deleted successfully." << endl;

return; // 删除后直接返回

}

prev = curr;

curr = curr->next;

}

cout << "Element " << e << " not found in the list." << endl;

}

#endif

#include "LinkList.h"

  

int main() {

int arr[] = {1, 2, 3, 4, 5};

LinkList<int> list1(5, arr); // 使用数组初始化链表

list1.showlist(); // 输出: 1 -> 2 -> 3 -> 4 -> 5 -> NULL


list1.Append(6); // 追加元素

list1.showlist(); // 输出: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> NULL

  

LinkList<int> list2(list1); // 拷贝构造

list2.showlist(); // 输出: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> NULL

  

list1.FreeList(); // 清空链表

list1.showlist(); // 输出: NULL

  

list2.Append(7); // 添加新元素到 list2

list2.showlist(); // 输出: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> NULL

  

// **测试插入功能**

list2.insert(0); // 插入 0 到头部

list2.showlist(); // 输出: 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> NULL

  

list2.insert(4); // 插入 4 到中间

list2.showlist(); // 输出: 0 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6 -> 7 -> NULL

  

list2.insert(8); // 插入 8 到尾部

list2.showlist(); // 输出: 0 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6 -> 7 -> 8 -> NULL

  

// **测试删除功能**

list2.Delete(4); // 删除第一个值为 4 的节点

list2.showlist(); // 输出: 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> NULL

  

list2.Delete(0); // 删除头部的 0

list2.showlist(); // 输出: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> NULL

  

list2.Delete(8); // 删除尾部的 8

list2.showlist(); // 输出: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> NULL

  

list2.Delete(10); // 尝试删除不存在的元素 10

list2.showlist(); // 输出: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> NULL

return 0;

}

#输出结果：
1 -> 2 -> 3 -> 4 -> 5 -> NULL
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> NULL
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> NULL
NULL
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> NULL
0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> NULL
0 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6 -> 7 -> NULL
0 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6 -> 7 -> 8 -> NULL
Element 4 deleted successfully.
0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> NULL
Element 0 deleted successfully.
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> NULL
Element 8 deleted successfully.
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> NULL
Element 10 not found in the list.
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> NULL

二、关键问题和设计细节：

在数据结构中链表是一种重要的线性表，但在链表类设计中可能会存在各种需要注意的细节，下面是🦐🌼🥚总结的在实践过程中遇到的几种问题（持续更新……）

1.区分有头结点和没有头结点的链表

首先，我们区分清楚两者的概念。带头结点和不带头结点的链表主要区别在于结构和操作方式。带头结点的链表在起点增加了一个额外的头结点，通常不存储有效数据，仅用于标识链表的起点和简化操作，统一了对链表中所有节点的插入与删除操作逻辑，而无需特殊处理第一个节点；此外，即使链表为空，头结点依然存在。而不带头结点的链表没有这个额外的头结点，第一个节点直接存储有效数据，操作时需要对头节点进行特殊处理，空链表时直接为 null。

带头结点的链表通过引入一个额外的头结点，消除了对头节点的特殊处理需求，使插入、删除操作逻辑一致，尤其在需要频繁调整链表结构时，可以减少对头指针更新的复杂性，同时方便统一管理和遍历链表。其结构对边界条件的鲁棒性较强，例如空链表和单节点链表的处理更加简洁。相比之下，不带头结点的链表尤其在对第一个节点进行插入、删除操作时，必须频繁检查和更新头指针，增加了逻辑的繁琐性。

Exemple：实现单链表的插入操作

A.带头结点的链表

带头结点的链表有一个额外的头结点（不存储有效数据），插入逻辑无需考虑是否在链表的第一个位置插入。假设要在链表的第 i 个位置插入一个新节点：

struct Node {
    int data;
    Node* next;
};

void insert(Node* head, int position, int value) {
    Node* current = head; // 从头结点开始
    for (int i = 0; i < position && current != nullptr; ++i) {
        current = current->next;
    }
    if (current == nullptr) return; // 插入位置非法

    Node* newNode = new Node{value, current->next};
    current->next = newNode; // 插入新节点
}

在此实现中，无论插入到链表的何处（包括第一个位置），头结点始终存在，因此逻辑无需特殊处理。

B.不带头结点的链表

不带头结点的链表直接从第一个节点存储有效数据。如果要在链表的第 i 个位置插入一个新节点，则需要特别处理在第一个位置插入的情况：

struct Node {
    int data;
    Node* next;
};

void insert(Node*& head, int position, int value) {
    if (position == 0) { 
        // 在头部插入新节点
        head = new Node{value, head};
        return;
    }
    
    Node* current = head; // 从第一个节点开始
    for (int i = 1; i < position && current != nullptr; ++i) {
        current = current->next;
    }
    if (current == nullptr) return; // 插入位置非法

    Node* newNode = new Node{value, current->next};
    current->next = newNode; // 插入新节点
}

在此实现中，需要单独处理插入到第一个位置的逻辑，因为直接修改了头指针的指向。

如果在不带头结点的链表中插入、删除或其他操作时不正确处理特殊情况（例如头节点的操作），可能会导致以下问题：

1. 插入操作中未处理头节点

如果在第一个位置插入节点时未正确处理头节点的特殊性（例如直接修改头指针），新节点可能无法正确链接到链表中：

假设有一条链表 head -> [10] -> [20] -> [30] -> null，我们希望在第一个位置插入节点 [5]。

错误代码：

void insert(Node* head, int position, int value) {
    Node* current = head;
    for (int i = 1; i < position && current != nullptr; ++i) {
        current = current->next;
    }
    if (current == nullptr) return;

    Node* newNode = new Node{value, current->next};
    current->next = newNode;
}

当 position = 0 时，current 并不会指向 head 的前一个位置，导致无法正确插入新节点。

结果

新节点无法替换原来的头节点，链表的头指针仍指向旧的头节点，插入操作失败或链表结构紊乱。

2. 删除操作中未处理头节点

在删除第一个节点时，必须修改头指针指向链表的下一个节点。如果未处理，链表的头指针仍然指向已被删除的节点，导致链表断裂。

问题示例

假设链表为 head -> [10] -> [20] -> [30] -> null，我们希望删除第一个节点 [10]。

错误代码：

  void remove(Node* head, int position) {
    Node* current = head;
    for (int i = 1; i < position && current != nullptr; ++i) {
        current = current->next;
    }
    if (current == nullptr || current->next == nullptr) return;

    Node* toDelete = current->next;
    current->next = toDelete->next;
    delete toDelete;
}

当 position = 0 时，上述代码不会修改头指针 head。

结果

头指针仍指向已被删除的节点，访问链表时可能导致：

• 悬空指针：继续访问已被释放的内存，导致程序崩溃或异常行为。

• 链表断裂：后续节点无法被访问，整个链表逻辑错误。

3. 遍历时未处理头节点为空的情况

在不带头结点的链表中，空链表直接表示为 head == nullptr。如果在操作中未检查头指针是否为空，可能导致访问空指针。

问题示例

假设链表为空，我们尝试遍历链表：

错误代码：

void traverse(Node* head) {
    Node* current = head;
    while (current->next != nullptr) { // 未检查 head 是否为 nullptr
        std::cout << current->data << " ";
        current = current->next;
    }
}

如果链表为空，则 current == nullptr，访问 current->next 会导致程序崩溃。

结果

• 运行时错误：访问空指针引发段错误（Segmentation Fault）。

• 代码鲁棒性差：程序无法安全处理空链表情况。

总的来说不带头结点的链表在未正确处理头节点的情况下，可能会导致以下严重后果：

1. 插入操作失败，导致链表结构紊乱。

2. 删除操作导致悬空指针或链表断裂。

3. 遍历操作可能引发程序崩溃。

因此，在不带头结点的链表中，头节点的操作必须被精确处理，特别是对于插入、删除以及空链表的判断，务必加以特殊逻辑处理。

2.链表类内部函数细节

(1).构造函数相关：

 构造函数可以分为有参数的构造函数和无参数的构造函数
 
 a.无参（默认）构造函数：
     在用户不定义的的时候，系统会自动分配一个默认构造函数来实现。
     注意在构造的时候，不能和有参数的构造函数冲突，即当有参数的构造函数的所有参数都有默认值的时候，创建新对象是就会有ambiguous报错，因为编译器不知道调用哪个函数来构造新对象
     
 b.有参数的构造函数：
     本质上是一种函数的重载，因为构造函数可以有不同的参数，所以可以认为是函数重载，这一点与析构函数形成对比，析构函数是不能有参数的，因而是不可以重载的。
     当构造函数有多个参数的时候，构造对象调用该构造函数的时候并不一定要给出所有的参数的值，系统会按照参数的顺序分配，没有实例化的参数会被赋予默认值。
     
 c.拷贝构造函数：
     通常为了方便我们都会利用重载深赋值运算符来定义拷贝构造函数，比如：`this = list; //利用深赋值运算符重载来定深拷贝`,但是这里要注意！！！：
     拷贝构造函数也是构造函数，在函数内部并没有构造head，size等数据成员，深赋值运算函数中会有很多涉及到head的地方，，如果没有定义就会导致程序崩溃，所以这里要使用冒号语法显式的初始化head等数据成员。

(2).template模版相关：

 C++ 中主要有两种模板：
 
1.  函数模板（Function Template）
    • template <typename T> 表示声明一个模板，其中 T 是一个占位符，代表数据类型。可以使用 typename 或 class，两者作用相同。调用时，可以显式指定类型，如 add<int>，也可以由编译器自动推导。
    

2.   类模版（Class Template）
        
    • template <typename T> 定义了一个类模板。创建类对象时，必须显式指定类型，例如 Box<int>。这一点是与函数模版最大的不同，**即类模版必须要显式的指定类型才能创建实例对象