链表是一种逻辑上连续,内存上分散的线性表数据结构,是用一组任意的空间(可以连续,也可以不连续)来存放数据元素。每个数据元素成为一个”结点“,每个结点由数据域和指针域组成。
- 访问元素(Access)O(N)
- 搜索元素(Search)O(N)
- 插入元素(Insert)O(1)
- 删除元素(Delete)O(1)
特点:写的快读的慢(应用于写多读少)
最基本的链表如图所示:
以下参考:数据结构:链表及其C++实现 - 菜鸡刘 - 博客园 (cnblogs.com)
插入操作:
假如需要在C结点后面插入F结点,只需要使C结点的指针指向F,F结点的指针指向结点D即可,如图所示
需要注意的是,在具体实现的时候,需要先暂存C结点的指针,先将其赋值给F结点指针,然后再将F结点的地址赋值给C结点的指针,否则会丢失D结点的地址,链表就会在此处断开。
删除操作:
假如需要删除D结点,则直接让C结点的指针指向E结点即可,如图所示
具体代码实现:
本文利用C++面向对象的特性与模板实现了一个链表类,并实现了插入、删除、查找、拷贝构造、拷贝赋值等基本操作。
结点类实现:
// 链表节点类
template<typename T>
class node
{
public:node() : next(nullptr){} // 这是构造函数node(T val) : data(val), next(nullptr) {} // 这是有参构造
private:T data;node* next;friend class list<T>; //同时在node类中将链表类list声明为友元,便于访问node的成员。
};
链表类声明:
链表类list的声明如下,主要实现了以下操作。list类包含两个成员属性head_ptr和length,前者是链表的头指针,后者储存链表的长度。
template<typename T>
class list
{
public:list(); // 构造函数list(const list<T>& l); // 拷贝构造list<T>& operator= (const list<T>& l); // 拷贝赋值 void insert_node(int index, T val); // 在index处插入结点void del_node(int index); // 删除index处结点T get_node(int index); // 获取index处结点值int find(int value); // 查找值value,找到返回index,找不到返回-1int get_length(); // 获取链表长度void push_back(T val); // 在链表尾部插入数据~list(); // 析构函数private:node<T>* head_ptr; // 链表头指针int length; // 链表长度
};
插入实现:
对于插入操作,本文将其分为了三种情况
- 超出索引,抛出异常
- 插在空链表的头
- 一般情况
// 在index处插入结点
template<typename T>
void list<T>::insert_node(int index, T val)
{if((index > this->length)) // 超过索引,最多可以插到当前结点的下一个结点,否则就是超过索引{throw runtime_error("index out of this list`s range");}else if((this->head_ptr == nullptr) && (index == 0)) // 插在空链表的头{this->head_ptr = new node<T>;this->head_ptr->next = nullptr;this->head_ptr->data = val;this->length++;} else // 一般情况{node<T>* p1 = this->head_ptr;node<T>* p2 = new node<T>;for(int i = 0; i < index - 1; i++){p1 = p1->next;}p2->data = val;p2->next = p1->next;p1->next = p2;this->length++;}
}
删除实现:
删除操作需要注意的是,每个结点都是通过new在堆区申请的内存,因此删除节点需要手动释放其内存。
// 删除index处结点
template<typename T>
void list<T>::del_node(int index)
{node<T>* p1 = this->head_ptr;node<T>* p2 = nullptr;for(int i = 0; i < index - 1; i++){p1 = p1->next;}p2 = p1->next->next;delete p1->next;p1->next = p2;this->length--;
}
索引实现:
// 获取index处结点值
template<typename T>
T list<T>::get_node(int index)
{if(index > this->length - 1) // 超过索引{throw runtime_error("index out of this list`s range");}node<T>* p1 = this->head_ptr;for(int i = 0; i < index; i++){p1 = p1->next;}return p1->data;
}
查找实现:
// 查找值value,找到返回index,找不到返回-1
template<typename T>
int list<T>::find(int value)
{node<T>* p1 = this->head_ptr;for(int i = 0; i < this->length; i++){if(p1->data == value){return i;}p1 = p1->next;}return -1;
}
析构实现:
析构函数需要做的就是释放链表每个节点的内存。
// 析构函数
template<typename T>
list<T>::~list()
{// 清空链表node<T>* p1 = this->head_ptr;node<T>* p2 = p1->next;while(p2 != nullptr){delete p1;p1 = p2;p2 = p2->next;}delete p1;this->length = 0;this->head_ptr = nullptr;}
力扣练习:
【203】移除链表元素
【206】反转链表
视频来源:【数据结构2】链表Linkedlist_哔哩哔哩_bilibili