目录

一、顺序表

1.1 静态顺序表

SeqList.h

1.2 动态顺序表

1.2.1 主要特点

1.2.2 主要操作

1.2.3 代码实现

二、链表

2.1 概念

2.2 主要特点

2.3 常见类型

2.4 优缺点

优点

缺点

2.5 代码实现

LinkList.h

LinkList.cpp

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使 用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串...

线性表在逻辑结构上是线性结构，也就说是连续的一条直线。

但是在物理结构上（实际存储）并不一定是连续的， 线性表在物理上存储时，通常以数组（顺序表）和链式结构（链表）的形式存。

一、顺序表

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。

注意：此处使用数组，不能在其内部跳跃存储，需连续存储。

注意：注意数组下标的使用（从0开始），图中的内容是元素示例，即存储的内容！

1.1 静态顺序表

静态顺序表的特点是固定长度，一旦创建后，其长度就不会改变。

优点是访问元素快速，可以通过索引直接访问元素，时间复杂度为O(1)。

缺点是插入和删除元素的操作较慢，需要进行元素的移动，时间复杂度为O(n)。

注意：在使用静态顺序表时，要合理估计元素个数，避免出现溢出或浪费过多的空间。

SeqList.h

#pragma one //预处理指令，用于确保头文件在编译过程中只被包含一次，防止重复定义和潜在的编译错误
constexpr int MAX_SIZE = 100; //声明一个编译时常量用于确定数组长度
typedef int SqDataType;//便于对数据类型的更改（后续可使用模板优化）
 
class SeqList{
private:
SqDataType _data[MAX_SIZE];//静态数组
   size_t _size;//数据元素数量
}

注意：此处仅对静态顺序表进行定义不进行实现，因为较为简单且使用频率低。

1.2 动态顺序表

与静态顺序表不同，动态顺序表的长度可以在运行时动态地进行调整，以适应元素的插入、删除等操作。

在动态顺序表中，通常使用动态内存分配来管理顺序表的存储空间

1.2.1 主要特点

1. 可变长度：动态顺序表的长度可以根据需要进行动态扩展或收缩。当元素数量超过当前容量时，可以自动扩展内存以容纳更多元素。

2. 动态内存管理：使用动态内存分配来动态管理顺序表的存储空间。通过申请和释放内存，动态顺序表可以根据需求调整容量。

3. 灵活性：由于长度可变，动态顺序表可以灵活地进行插入、删除和修改等操作，而不需要移动其他元素。

1.2.2 主要操作

1. 创建顺序表：动态分配一定的内存空间，并初始化顺序表的相关属性。

2. 插入元素：在指定位置插入一个元素，如果当前容量不足，需要扩展内存空间。

3. 删除元素：删除指定位置的元素，如果删除后容量过大，可以收缩内存空间。

4. 查找元素：按照索引位置或元素值进行查找，并返回对应的元素。

5. 修改元素：根据索引位置或元素值，修改指定位置的元素值。

6. 获取长度：返回顺序表中元素的个数。

7. 遍历顺序表：按照顺序输出顺序表中的所有元素。

1.2.3 代码实现

SeqList.h

#pragma one
#include<iostream>
 
typedef int SqDataType;
class SeqList {
private:
    SqDataType* _array;  // 存储数据的数组指针
    size_t _size;    // 当前元素个数
    size_t _capacity;  // 当前容量
public:
    SqList();//构造函数
    ~SqList();//析构函数
    void checkCapacity();//检查容量
    void push_back(SqDataType value);//尾部插入
    void push_front(SqDataType value);//头部插入
    void pop_back();//尾部删除
    void pop_front();//头部删除
    SqDataType get(size_t index); //按索引位置查找
    size_t getSize();//获取长度
    void print();//遍历顺序表
}

SeqList.cpp

#include"SeqList.h"
 
SeqList::SeqList()
{
        _array = nullptr;//对成员属性进行初始化
        _size = 0;
        _capacity = 0;
}
 
SeqList::~SeqList()
{
    if(_array != nullptr)
    delete[] _array;
}
 
//由于头插尾插都需要检查容量，便提取出此函数用于检查容量
void checkCapacity()
{
    //对初次插入和后续插入进行扩容处理
    //因为初次进入_size和_capacity都为0，判断为满，进行扩容
    if (_size == _capacity) {
        if (_capacity == 0)
            _capacity = 1;
        else
            _capacity *= 2;
 
        //开辟新空间并进行数据移动
        int* newArray = new SqDataType[_capacity];
        for (int i = 0; i < _size; i++) {
            newArray[i] = _array[i];
        }
 
        //将旧空间进行释放，避免内存泄漏
        delete[] _array;
        _array = newArray;
    }    
}
 
//尾部插入数据
void push_back(int value) {
checkCapacity();
 
    //此处使用_size++需要读者结合数组下标特性进行理解
    _array[_size++] = value;
}
 
//尾部删除
void pop_back()
{
    //只有在有容量的情况下才能进行删除
    if (_size > 0)
        _size--;
}
 
//头部插入
void push_front(SqDataType value)
{
checkCapacity();
    
    //在头部插入数据需要将后续数据全部向后挪动
    for(size_t index = size; index > 0; index--)
    _array[index] = _array[index - 1];
    
    //挪动数据后将数据插入头部更新size
    _array[0] = value;
    _size++;
}
 
//头部删除
void pop_front()
{
    if(_size != 0)
    {
        for(size_t index = 0; index < _size - 1; index++)
            _array[index] = _array[index + 1];
        
        _size--;
    }
}
 
//按索引查找
SqDataType get(size_t index)
{
    if(index >= 0 && index < _size)
        return _array[index];
    else
        throw std::out_of_range("Index out of range.");
}
 
//获取容量
size_t getSize()
{
    return _size;
}
 
//便利打印顺序表
void Print()
{
    for(size_t index = 0; index < _size; index++)
        std::cout << _array[index] << " ";
    std::cout << std::endl;
}

二、链表

2.1 概念

链表（Linked List）是一种物理结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

链表是一种常见的线性数据结构，它由一系列节点组成，每个节点包含数据元素和一个指向下一个节点的指针。

相邻节点之间通过指针连接，而不是像数组那样在内存中连续存储。

2.2 主要特点

1. 动态性：链表的长度可以动态增长或缩小，不需要预先分配固定的内存空间。
2. 灵活性：由于节点之间使用指针连接，可以轻松地插入、删除和修改节点，不需要移动其他节点。
3. 存储效率：相对于数组，链表的存储空间利用率较低，因为每个节点需要额外的指针来指向下一个节点。

2.3 常见类型

单向链表（Singly Linked List）：每个节点只有一个指针，指向下一个节点。最后一个节点的指针为nullptr，表示链表的结束。

单向链表
 

双向链表（Doubly Linked List）：每个节点有两个指针，一个指向前一个节点，一个指向后一个节点。这样可以双向遍历链表，但相对于单向链表，双向链表需要更多的内存空间来存储额外的指针。

双向链表
​​

2.4 优缺点

优点

1. 动态性：链表长度可以动态增长或缩小，适用于需要频繁插入和删除节点的场景。
2. 灵活性：链表的节点可以轻松地插入、删除和修改，不需要移动其他节点，操作更加灵活。

缺点

1. 随机访问效率低：链表中的元素不能像数组那样通过索引进行快速访问，需要从头节点开始遍历链表，时间复杂度为O(n)。
2. 额外的内存开销：每个节点都需要额外的指针来连接其他节点，增加了一定的内存开销。

2.5 代码实现

此处实现的是入门的不带头节点的单链表，能够理解此处代码，后续读者可自行完成链表变式，笔者后续也会出文章介绍不同类型链表并使用代码实现。

LinkList.h

#ifndef LINKEDLIST_H
#define LINKEDLIST_H
 
//节点类
class Node {
public:
    int data;
    Node* next;
    //初始化节点
    explicit Node(int value);
};
 
//链表类
class LinkedList {
private:
    Node* head;
 
public:
    //初始化链表
    LinkedList();
    //尾插节点
    void push_back(int value);
    //尾删节点
    void pop_back();
    //头插节点
    void push_front(int value);
    //头删节点
    void pop_front();
    //遍历打印顺序表
    void printList();
    //析构函数
    ~LinkedList();
};
 
#endif

LinkList.cpp

 
#include "LinkList.h"
#include <iostream>
 
Node::Node(int value) {
    data = value;
    next = nullptr;
}
 
LinkedList::LinkedList() {
    head = nullptr;
}
 
void LinkedList::push_back(int value) {
    Node* newNode = new Node(value);
 
    //遍历寻求到最后节点，再添加节点即可
    if (head == nullptr) {
        head = newNode;
    } else {
        Node* current = head;
        while (current->next != nullptr) {
            current = current->next;
        }
        current->next = newNode;
    }
}
 
void LinkedList::push_front(int value) {
    Node* newNode = new Node(value);
 
    //区别在于是否需要修改头指针
    if (head == nullptr) {
        head = newNode;
    } else {
        newNode->next = head;
        head = newNode;
    }
}
 
void LinkedList::printList() {
    Node* current = head;
    while (current != nullptr) {
        std::cout << current->data << " ";
        current = current->next;
    }
    std::cout << std::endl;
}
 
void LinkedList::pop_back() {
    if (head != nullptr) {
        Node* current = head;
        Node* pre = nullptr;
 
        // 处理只有一个节点的情况
        if (head->next == nullptr) {
            delete head;
            head = nullptr;
        } else {
            // 遍历链表找到最后一个节点
            while (current->next != nullptr) {
                pre = current;
                current = current->next;
            }
 
            // 删除最后一个节点
            pre->next = nullptr;
            delete current;
        }
    }
}
 
void LinkedList::pop_front() {
    //无节点不能删除
    //同时需要判断是否只有一个节点，需要特殊处理
    if(head != nullptr)
    {
        if(head->next != nullptr)
        {
            Node* temp = head;
            head = temp->next;
            delete temp;
        }
        else
        {
            Node* temp = head;
            head = nullptr;
            delete temp;
        }
    }
}
 
LinkedList::~LinkedList() {
    //遍历链表中所有节点，逐个进行释放内存
    Node* current = head;
    Node* pre = nullptr;
    while(current != nullptr)
    {
        pre = current;
        current = current->next;
        delete pre;
    }
}

解释：

创建链表首先需要一个头指针，即上述LinkList类，内部维护一个Node节点指针，其始终指向头节点或者nullptr。

因为想要修改链表，就需要使用其地址才能对其修改，拿到头节点的指针后，头节点也存储着下一个节点的指针，以此类推，可以寻求到整个链表，并在其上进行各种操作。

读者可根据上述代码，自行设计测试，体验一下简单的单向链表，亦可在此基础上拓展功能。

此篇文章到此结束，后续会出关于各种变式链表的文章！