写在前面：
今天我们来动手实现一下链表结构，链表在我们后续的数据结构中用的十分频繁，可以说就是实现后续很多数据结构一个的基本工具，也是最容易的数据结构之一，我们先从最基础的单向链表讲起，小白刚开始学习肯定会被折磨的头疼，我也是这样的，但只要啃下这块硬骨头就已经前进一大步了！
何为链表
我们先看下面这张图来理解一下什么是链表，直接讲代码可能会比较头晕，我们先从图入手。
上面就是一个最基本的单向链表，链表的作用有很多，它可以存储数据也可以连接不同的结点信息，解决很多问题。
链表首先一个很重要的性质就是需要一个头结点，但是头结点的实现也有两种，一种是像上面一样直接将存有数据的结点当成头结点，但是每次插入结点的时候可能都需要将头结点指向新的结点；另一种可能会更好理解一些，head指针单独指向一个空结点，这个结点不存任何东西（如下图所示），所有新创建的结点都接到头结点之后，我更喜欢这种方式，因为实现起来也更容易理解一些，所以接下来的代码都以这种方式实现。
链表的创建
我们先以单向链表的实现为例，结点结构体也以最简单的形式创建。
struct node
{
int data; //数据
node* next; //指向下一个结点的指针
};接下来就是对于链表的初始化操作了，其实很多人包括我自己，刚开始之所以对链表很抗拒，是因为不知道如何进行结点的创建，只要知道如何创建，后面就顺风顺水啦~
node* head = NULL; //将头指针设为全局变量，方便使用
//结点的初始化
void init_node()
{
node* new_node = new node;
new_node->data = -1; //将数据初始化一个不可能插入的数据
new_node->next = NULL; //初始化指针为空
head = new_node; //将头指针指向这一个新创建的结点，这样就有了一个空结点啦~
}头插法
实现起来非常简单，只需要三步即可，直接看下面图解。
void head_insert(int key)
{
node* new_node = new node;
new_node->data = key;
new_node->next = head->next; //将新结点的next指向head的ne
head->next = new_node; //将head的next指向新结点
}尾插法
其实尾插法可以和头插法一样，也创建一个尾指针，只不过不是让它指向空结点，而是指向最后一个结点，每次插入新结点都将尾指针指向它，这样每次采用尾插法时可以直接找到链表的最后一个结点，进行插入操作。
但是，为了方便初学者理解，我们暂时不引入上述操作，而是在只有头指针的基础上进行插入，大家后续可以尝试自己去创建一个尾指针，我们这里就用一个临时指针去寻找链表的最后一个结点。
void end_insert(int key)
{
node* new_node = new node;
node* temp = head; //创建一个临时指针
while (temp->next != NULL) //将临时指针指向最后一个结点
temp = temp->next;
new_node->data = key; //给新结点赋值
new_node->next = temp->next; //将新结点的next指向temp的next
temp->next = new_node; //将temp的next指向新结点
}删除结点
删除结点的操作其实和插入操作比较类似，需要用到两个临时指针，一个去找到要删除的结点，一个去找到要删除结点的前一个结点。
void delete_node(int key)
{
node* temp = head->next; //创建一个临时指针寻找删除结点
node* prev = head; //同样创建一个指针寻找删除结点的前一个结点
while (temp->data != key && temp != NULL)
{
prev = temp;
temp = temp->next;
}
if (temp == NULL)
{
cout << "没有此结点" << endl;
return;
}
prev->next = temp->next; //让前一个结点指向删除结点的next
temp->next = NULL; //让删除结点的next指向空
delete[]temp;
temp = NULL;
}遍历链表
相信经过上面的学习，对你来说链表的遍历就已经是小儿科啦，话不多说直接上代码！
void show()
{
node* temp = head->next; //创建一个临时指针
if (temp == NULL)
{
cout << "当前还没有创建结点" << endl;
return;
}
while (temp != NULL) //遍历整个链表
{
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}全部代码
#include<bits/stdc++.h>
using namespace std;
struct node
{
int data; //数据
node* next; //指向下一个结点的指针
};
node* head = NULL; //将头指针设为全局变量，方便使用
void init_node(); //初始化结点
void head_insert(int); //头插法
void end_insert(int); //尾插法
void delete_node(int); //删除结点
void show(); //遍历链表
int main()
{
init_node();
head_insert(4);
head_insert(9);
end_insert(7);
show();
delete_node(4);
show();
}
void show()
{
node* temp = head->next;
if (temp == NULL)
{
cout << "当前还没有创建结点" << endl;
return;
}
while (temp != NULL)
{
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}
void init_node()
{
node* new_node = new node;
new_node->data = -1;
new_node->next = NULL;
head = new_node;
}
void head_insert(int key)
{
node* new_node = new node;
new_node->data = key;
new_node->next = head->next; //将新结点的next指向head的ne
head->next = new_node; //将head的next指向新结点
}
void end_insert(int key)
{
node* new_node = new node;
node* temp = head; //创建一个临时指针
while (temp->next != NULL) //将临时指针指向最后一个结点
temp = temp->next;
new_node->data = key; //给新结点赋值
new_node->next = temp->next; //将新结点的next指向temp的next
temp->next = new_node; //将temp的next指向新结点
}
void delete_node(int key)
{
node* temp = head->next;
node* prev = head;
while (temp->data != key && temp != NULL)
{
prev = temp;
temp = temp->next;
}
if (temp == NULL)
{
cout << "没有此结点" << endl;
return;
}
prev->next = temp->next;
temp->next = NULL;
delete[]temp;
temp = NULL;
}如果大家有什么问题的话，欢迎在下方评论区进行讨论哦~
