0.导读
本文记录了学习链表数据结构并试图模仿它的衣陈int本markdown用原码存储衣服gitee仓库(文件名intlist.cpp)，建议这篇文章和原码一起吃，希望能激励你。
//是复制的markdown文本，代码块不是很好Q.Q
本文包括:实现链表类的所有知识、思想、心路历程、疑惑和答案。
-
链表概念
-
成员属性、方法和选择链表类别的原因。
-
链表的push_back与头结点新建问题
-
insert 与 earse实现及其边界：头插尾插头删尾
-
基于递归的反转链表练笔日志
核心素养：
-
数据结构思想
-
边界分析思想
-
变量作用域和值地址的测量
1.链表概念
这里建议观看翁恺的C语言课堂介绍，这是个人遇到的解释链表最清晰的视频。
我们不应该开始实战。
核心思想是:为什么我们需要链表？因为链表的插入和删除比数组更有效。
需要关注的是链表和动态数组数据存储思想的分析。
这里一图胜千言
2.为了实现链表类别，我们需要设计：
-
包装所有成员属性和方法的链表类
-
成员属性结点类是链表的单元
-
头结点，是链表的起点。
-
长度记录器方便 我们的增删改查。
-
尾插操作的起点是尾插操作的起点
class intList { public: class node { public: node() { this->data = 0; this->next = NULL; } /*node(int elem) { this->data = elem; this->next = NULL; }*////没有使用参结构，因为我们维护节点数据类型的指针 int data; node* next; }; node* head; int len; };
思考:指针域指向的对象是下一节点的数据类型还是下一节点存储的数据？
如何实现头结点？
我们需要的是节点的实例对象还是它的指针？
答案是指针。维护 , 维护和。
如果实现了动态数组，我们应该知道维护方法是指针
我们将head和next设计为node的指针，cout<\<head->next->next->next->data;可以实现这种嵌套寻址。
head.next=1st;
思考：尾结点的声明时机？（变量作用域的衡量）
保留此问。
3.新链表和尾插的问题
intList() { this->head = new node; this->head->next = NULL; this->len = -1; } void push_back(int elem) { if (this->head->next==NULL) { //因为链表类可以先创建，再删除，在push。 //链表的初始化:指针分配空间后写入数据NULL。 this->head = new node; //需要注意的是，头结点应该在无参结构中初始化，否则，报野指针 this->head->next = NULL; this->len = -1; //相反，创建指针对象并将其写入匿名数据 node* pos = new node; pos->data = elem; this->head->next = pos; this->len ; // cout << this->head->next->data<<" "; } ///正常尾插，查找方法searchNo后来解释了方法 else { //寻尾 node* pos = this->searchNo(this->len); node* come = new node; come->data = elem; pos->next = come; pos = come; this->len ; // cout << this->pos->data << " "; } }
首先是链表的初始化时机。起初，我写在类别的无参与结构中，但在实战中，我发现它是先建立的，然后删除为空，然后删除为空pushback因此，改为每次pushback判断是否在新建链表。
Q：一大难点是为什么要在这里使用new操作呢？
A：因为head初始为空指针，而我们想对一个空指针进行操作的话，应先为指针解引的地址分配空间。
所以head是new为了保持风格一致，后面pos和come(见下文)也应为指针类型。
这样，对于单元节点，我们节点的指针，并使用堆区new操作维护节点中的数据。
优雅。这也与动态二维数组的思想交换
我们比较以下代码
node pos; pos.data=elem; this->head->next = &pos;
Q：为了连接链表，我们使用了一个选址操作，所有的尾插都使用了这种风格的新节点，不妨考虑一下this->head最后指向什么？ ？(涉及上文结尾声明的时机)
Q：是否可以强求这样node pos？
A: 是的，我们把node pos;设置为list在push_back引用其他涉及结束点更新的方法转换引用传入传出pos。
，翁恺老师说全局变量是有害的，为了强制设计实例对象，增强类中的耦合度是不合理的。
无论如何，这样的操作都不够优雅，next指向下一个节点实例对象的地址吗？
不是的，next指向下一个节点类指针，即指针和指针的赋值操作。
总结:这其实是一个变量作用域和值与地址的问题，而且这个问题藏得很深，很难发现会像作者一样陷入纠结，没有纠结到点，通过跟踪程序很难发现。作者在梳理这篇文章markdown当我发现这个问题时，我真的回答了为什么head，pos一定是指针。
同时回答以上，pos应该是局部变量，用new尾插时声明风格。
4.遍历结构
这里直接从翁恺老师的视频中学习控制结构
for (node* it = this->head->next; it; it = it->next)
关于真假： c 中0是假的，非0是真的，我们可以尝试输出空指针，结果是0x这是十六进制位模式的0000000。
优雅。循环条件是it为真(即指针有指向，不是空指针)，迭代句子it自身更新。
4.1遍历输出
void ptfme() {
for (node* it = this->head->next; it; it = it->next)
{
cout << it->data << " ";
}
}
4.2遍历查找
对于链表由于它的非连续性，我们是不可能像数组那样及其简单地获得某某节点的地址的。
解决方法为，记录一次遍历中(它的功能不正是如此吗)的更新次数，直到这个次数等于我们的预期，返回这个节点（指针）
即，searchNo(int no)方法，得到No.x号元素的地址。
node* searchNo(int no)
{
int ans = 0; int is_found = 1;
for (node* it = this->head->next; it; it = it->next, ans++)
{
if (ans == no)
{
is_found = 0;
// cout << "found\n";
return it;
}
}
if (!is_found) {
// cout << "no this No.x\n";
return NULL;
}
}
基于这个方法，不就可以得到容器的迭代器了吗
4.3基于查找的插删操作
现在我们可以轻松获得链表中任意位置的对象指针了，(溢出部分的代价由操作者承担)，插删操作就有了起点
首先是插删的基本参数，位置和插入对象。
然后是链表插删的思想：断链，重新成链。
//这里仅实现中间插入：用serachNo方法获得插入点左右节点，插入come的左侧comel.next改为链接come，come。next链接come右侧come1；
//事实上，当情况为头插尾插时，又有不同。应该加上if语句判断边界处理
void insert(int no,int elem) {
node* comel = this->searchNo(no);
node* comer = this->searchNo(no)->next;
node* come = new node;
come->data = elem;
comel->next = come;
come->next = comer;
this->len++;
cout << "is_insert,new inlist:\n";
this->ptfme();
}
//这里先实现普通删除，用searchNo方法获得删除节点，左侧链接右侧，重点delete掉。
void earse(int no) {
if (no == this->len)
{
this->pop_back();
}
else
{ if (no == 0)
this->pop_head();
else
{
node* earsing = this->searchNo(no);
node* earl = this->searchNo(no - 1);
node* earr = this->searchNo(no)->next;
earl->next = earr;
delete earsing;
earsing = NULL;
this->len--;
cout << "is_earse,newlint:\n";
this->ptfme();
}
}
4.4插删操作的边界：头尾插删
尾插已实现。
以下给出头尾删
void pop_back() {
//一般尾删需要找到倒数第二个元素即链表长度大于等于二
//获得尾结点指针，删除尾结点内容，更新尾结点为倒二节点。
if (this->head->next->next)
{
node* pos = this->searchNo(this->len);
node* newpos = this->searchNo(--this->len);
// cout << "popelem：" << newpos->next->data;
delete newpos->next;
newpos->next = NULL;
pos = newpos;
//if(newpos->next)cout << "popelem：" << newpos->next->data;
this->ptfme();
return;
}
else
{
//一个元素的尾删，即链表置空
//获得节点指针，delete，头结点置空
if (this->head->next)
{
node* temp = this->searchNo(0);
delete temp;
temp = NULL;
this->head->next = NULL;
this->ptfme();
return;
}
else {
cout << "NULL_inilist,wrong_pop";
return;
}
}
}
//头删同理
void pop_head() {
//2+
if (this->head->next->next)
{
node* newhead = new node;
newhead->next = this->searchNo(1);
delete this->head;
this->head = newhead;
cout << "is head_back,newlist:\n";
this->ptfme();
}
else
{
if (this->head->next)
{
node* temp = this->searchNo(0);
delete temp;
temp = NULL;
this->head->next = NULL;
this->ptfme();
return;
}
else {
cout << "NULL_inilist,wrong_pop";
return;
}
}
}
头插略(忘了写QAQ)
思想都是想通的，当做您的小练笔吧（:> ,<:）
5.基于递归实现反转链表
是力扣挺经典的一道题，我就顺带拿来练笔了
不同于算法题只需要一种返回翻转完毕后的链表的头结点的算法，我希望的是获得一种把this对象翻转的方法
所以最终我设计了如下框架
//对于实节点数少于两个（0或1）的链表，做空实现，对于合法的链表，做算法得到newhead，用newhead更新this->head
void reverse()
{
if (this->head->next->next)
{
node* newhead= _reverse(this->head);
this->head= newhead;
}
this->ptfme();//打印列表函数
return;
}
node* _reverse(node* _head){}
解决完这些前置的小问题，来到重难点递归算法部分
推荐观看@bilibili_筱可爱233 的算法讲解视频
先上算法
//蛮短但蛮难
node* _reverse(node* _head) {
//递归结构
if (_head->next==NULL) return _head;
node* newhead = _reverse(_head->next); //
//反转算法
_head->next->next = _head;
_head->next = NULL;
return newhead;//
}
如果你和笔者一样初识递归或者一直难以搞定递归，建议多上草稿本，画画递归闭环和出口，写写程序运行流程，以下是笔者对这个算法的个人理解，仅供参考。
如上分隔，这个算法分为两部分，且看我一图讲完
第一部分为递归结构，用以进入最底层递归和获取尾节点指针
经过如图，经紫框的控制结构，我们获得最底层递归的result 5th，退出5th递归据需4th递归，做了与value第二部分的算法后返回value，退出4th进入3rd，……最终把value()传递给target(
intlist::node* newhead)
第二部分为算法内容，用以修改链表指向。
赋值语句是要从右往左看的，不难看出算法的起点是倒数第二层递归，算法主体head是func4的参（4th节点），所以尾结点表达式为head.next
所以是吧head.next左边的指针的指向(指向head.next)赋给了head.next的右边。
这样head.next.next不就指向了它左边的节点吗。
注意这里的head.next.next并不是6th节点，我们并没有为他new空间也没有声明6th节点，它的正确读法应该为(head.next).next，
这里的next并非时如它的标识符那样指下一个节点，而是对象指针(head->next)的解引的成员属性——它的指针域，现在指向了4th。
做完这些后，4th递归结束，返回与上述算法无关的新链表（is_building）的new_head,然后返回值传给了func3的value,依次上传。而fun3的参是3th节点指针，重复上述算法对(3th.next)这个节点指针修改，结果是4th的next（在上一层递归中被擦除）被修改为了3th，3th.next被擦除。依次进行算法，新链表最终建立完成。
小结，核心素养是对“next”这个概念的辨析，他只是一个指针而不是“下一个”的意思，可以说是很有误导性了。
结果：
原因很显然啊，我们的算法起点是4th，结束点就并非是1st而是原来的空头结点（默认值为0），所以会带0；又因为我们处理这个算法返回的头结点的语句是this->head= newhead;而在我们的遍历结构中起点是this.head.next;所以会发生“左截断，右延长”的灵异现象
思考：上述语句改为
this->head->next= newhead;呢？
结果：
很有意思，确实成功包含了10th元素 9，也有完整的9到1的翻转列表。却陷入了死循环
因为没有管理head的指向
解决方法：将this->head new一下
node* newhead= _reverse(this->head);
this->head = new node;
this->head->next= newhead;
思考，覆盖指针head而并未delete回收head，堆区数据是否丢失：否，经我们的操作head又重新链回了这段数据。
输出结果显然是“9 8 7 6 5 4 3 2 1 0”
尾删也不太对，因为“0”是head指针来的，这个head指针被是尾结点.next连上，形成闭环链表，而尾删方法作用对象是尾结点。所以我们要删除尾结点.next
void reverse()
{
if (this->head->next->next)
{
node* newhead= _reverse(this->head);
this->head->next= newhead;
}
//错误的，尾删
this.pop_back();
this->ptfme();//打印列表函数
return;
}
：
//正确的，尾.next删
node* tail = this->searchNo(this->len);
tail->next = NULL;
结果符合预期
至此，基于递归的翻转链表实现完成，特别有意思真的，自己捣鼓试出了好多东西，可能这就是计算机的魅力吧。
Q：最后的最后是链表类的析构问题，如何回收我们再堆区写入的每个节点的数据？
A： 必须分清楚delete的目标，删除我们声明的每个与堆区有关的标识符吗？
不是的，是写在堆区那块物理空间的内的数据。我们仅需要一种算法，得到每个节点的地址(即通过searchNo方法得到这个节点的指针)，delete指针即可。
6.析构问题：delete节点
核心问题是要free掉节点的同时不丢失next指针，所以，先创建q维护p.next节点，再delete掉p，以下为《大话数据结构》中的实现
后记：此次对链表容器的实现，较好地锻炼了数据结构思维与边界处理思维，变量选取的权衡。
数据结构与与算法真的真的太核心了，我是用c++实现的嘛，可是在参阅资料时那些基于java，c的课程其实都能听的，因为底层的数据结构和算法都是共通的(其中感触最深的莫过于翁凯的c语言给出的链表遍历结构)
不妨将我们的cpp拆分为头文件和cpp，就获得了专属的int类型list容器。
最后贴上成品原码（懒得git的话）
#include<bits/stdc++.h>
using namespace std;
class intList {
public:
class node {
public:
node() {
this->data = 0;
this->next = NULL;
}
/*node(int elem) {
this->data = elem;
this->next = NULL;
}*///并没有用到有参构造，因为我们维护的是节点数据类型的指针
int data;
node* next;
};
node* head;
int len;
intList() {
this->head = new node;
this->head->next = NULL;
this->len = -1;
}
void push_back(int elem) {
if (this->head->next==NULL) {
//结点的新建应该包含pos的初始化,因为链表类可以先被创建，再删除干净，在push。
this->head = new node;
this->head->next = NULL;
this->len = -1;
//不是深拷贝，而是创建指针对象并写入匿名数据
node* pos = new node;
pos->data = elem;
this->head->next = pos;
this->len++;
// cout << this->head->next->data<<" ";
}
else {
//寻尾
node* pos = this->searchNo(this->len);
node* come = new node;
come->data = elem;
pos->next = come;
pos = come;
this->len++;
// cout << this->pos->data << " ";
}
}
//遍历
void ptfme() {
cout << endl;
for (node* it = this->head->next; it; it = it->next)
{
cout << it->data << " ";
}
cout << "\nptfover\n";
return;
}
node* searchNo(int no)
{
int ans = 0; int is_found = 1;
for (node* it = this->head->next; it; it = it->next, ans++)
{
if (ans == no)
{
is_found = 0;
// cout << "found\n";
return it;
}
}
if (!is_found) {
// cout << "no this no\n";
return NULL;
}
}
void ptffrom(int no) {
for (node* it=this->searchNo(no); it; it = it->next)
{
cout << it->data << " ";
}
}
void insert(int no,int elem) {
node* comel = this->searchNo(no);
node* comer = this->searchNo(no)->next;
node* come = new node;
come->data = elem;
comel->next = come;
come->next = comer;
this->len++;
cout << "is_insert,new inlist:\n";
this->ptfme();
}
void earse(int no) {
if (no == this->len)
{
this->pop_back();
}
else
{ if (no == 0)
this->pop_head();
else
{
node* earsing = this->searchNo(no);
node* earl = this->searchNo(no - 1);
node* earr = this->searchNo(no)->next;
earl->next = earr;
delete earsing;
earsing = NULL;
this->len--;
cout << "is_earse,newlint:\n";
this->ptfme();
}
}
}
//头尾插删有边界问题
void pop_back() {
//一般尾删需要找到倒数第二个元素即链表长度大于等于二
if (this->head->next->next)
{
node* pos = this->searchNo(this->len);
node* newpos = this->searchNo(--this->len);
// cout << "popelem：" << newpos->next->data;
delete newpos->next;
newpos->next = NULL;
pos = newpos;
//if(newpos->next)cout << "popelem：" << newpos->next->data;
this->ptfme();
return;
}
else
{
//一个元素的尾删
if (this->head->next)
{
node* temp = this->searchNo(0);
delete temp;
temp = NULL;
this->head->next = NULL;
this->ptfme();
return;
}
else {
cout << "NULL_inilist,wrong_pop";
return;
}
}
}
void pop_head() {
//2+
if (this->head->next->next)
{
node* newhead = new node;
newhead->next = this->searchNo(1);
delete this->head;
this->head = newhead;
cout << "is head_back,newlist:\n";
this->ptfme();
}
else
{
if (this->head->next)
{
node* temp = this->searchNo(0);
delete temp;
temp = NULL;
this->head->next = NULL;
this->ptfme();
return;
}
else {
cout << "NULL_inilist,wrong_pop";
return;
}
}
}
//递归结构实现链表翻转 返回新链表头结点
//我们这种头结点结构不太适用，因为
void reverse()
{
if (this->head->next->next)
{
node* newhead= _reverse(this->head);
this->head = new node;
this->head->next= newhead;
}
//this->pop_back();
//正确的尾.next删
node* tail = this->searchNo(this->len);
tail->next = NULL;
this->ptfme();
return;
}
node* _reverse(node* _head) {
if (_head->next==NULL) return _head;
node* newhead = _reverse(_head->next); //
_head->next->next = _head;
_head->next = NULL;
return newhead;//
}
};
int main() {
intList intlist;
//intlist.push_back(1);
// intlist.push_back(0);
// intlist.pop_head();
for (int i = 1; i < 10; i++)intlist.push_back(i);
intlist.ptfme();
intlist.reverse();
intlist.reverse();
return 0;
//intlist.earse(intlist.len);
//cout << intlist.head->next->data << " " << intlist.head->next->next->data << " "; 结点链接测试案例
//cout << intlist.pos->data;尾结点测试案例
//intlist.ptfme();
}