单向链表及其两种实现
简介
链表是一个功能极为强大的数组，他可以在节点中定义多种数据类型，还可以根据需要随意增添，删除，插入节点。链表都有一个头指针，一般以head来表示，存放的是一个地址。链表中的节点分为两类，头结点和一般节点，头结点是没有数据域的。链表中每个节点都分为两部分，一个数据域，一个是指针域。链表头head指向第一个元素，第一个元素又指向第二个元素，直到最后一个元素不再指向其它元素，被称为“链表尾”，它的地址部分存放一个空地址，链表到此结束。
指针实现
首先使用结构体构建链表：
struct node{
int a; //数据
struct node* next; //指针
};
链表的索引是从1开始的，但索引0是一个头指针，没有存放数据。链表尾部的指针为null(nullptr)
链表的初始化过程为：
首先创建一个头结点分配空间，然后一个变量用于链表体的构造，最后一个标记位置的节点（最后更新到链表尾）
Node *init(int n){ //创建一个n个元素的链表
Node *head,*div,*end; //end只是一个用来标记链表位置的指针，并没有被分配空间，只有实体和头链表被分配空间
head=(Node *)malloc(sizeof(Node));
end=head;
for(int i=0;i<n;i++){
div=(Node *)malloc(sizeof(Node));
scanf("%d",&div->a);
end->next=div;
end=div;
}
end->next=nullptr; //链尾一定要设置为空
return head;
}
链表插入元素：
- 将插入结点的 next 指向插入位置前结点的next（即插入位置的下一个节点）
- 将插入位置前结点的 next 指向插入结点
void insertNode(Node *list,int n){ //在索引n后插入节点
Node *t=list,*div;
int i=0;
while(t!=nullptr&&i<n){
t=t->next;
i++;
}
if(t!=nullptr){
div=(Node *)malloc(sizeof(Node));
scanf("%d",&div->a);
div->next=t->next;
t->next=div;
}else printf("Not found\n");
}
链表删除元素:
找到需要删除节点的前一个节点和后一个节点（这里需要注意考虑是否为空节点），删除链表的元素也就是把前节点的指针指向删除节点的后一个节点
void deleteNode(Node *list,int n){ //删除索引为n的值
Node *t=list,*pre;
int i=0;
while(t!=nullptr&&i<n){
pre=t;
t=t->next;
i++;
}
if(t->next!=nullptr){
pre->next=t->next;
free(t);
}else printf("Not found\n");
}
修改链表的某个节点：
修改链表中的元素,只需要遍历链表找到该节点,对节点中的数据进行更新即可
void change(Node *list,int n){ //修改索引为n的值
Node* t=list;
int i=0;
while(t!=nullptr&&i<n){ //先遍历寻找
t=t->next;
i++;
}
if(t!=nullptr){
scanf("%d",&t->a);
}else printf("Not found!\n");
}
遍历链表：
由链表头开始，每当当前节点的next不为空就继续循环
void show(Node *list){ //展示链表
Node *t=list;
while(t->next!=nullptr){
t=t->next;
printf("%d ",t->a);
}
printf("\n");
}
下面的本人测试的代码：
#include <iostream>
#include <malloc.h>
using namespace std;
typedef struct node{
int a;
struct node* next;
}Node;
Node *init(int n){
Node *head,*div,*end;
head=(Node *)malloc(sizeof(Node));
end=head;
for(int i=0;i<n;i++){
div=(Node *)malloc(sizeof(Node));
scanf("%d",&div->a);
end->next=div;
end=div;
}
end->next=nullptr;
return head;
}
void change(Node *list,int n){ //修改索引为n的值
Node* t=list;
int i=0;
while(t!=nullptr&&i<n){
t=t->next;
i++;
}
if(t!=nullptr){
scanf("%d",&t->a);
}else printf("Not found!\n");
}
void deleteNode(Node *list,int n){ //删除索引为n的值
Node *t=list,*pre;
int i=0;
while(t!=nullptr&&i<n){
pre=t;
t=t->next;
i++;
}
if(t->next!=nullptr){
pre->next=t->next;
free(t);
}else printf("Not found\n");
}
void insertNode(Node *list,int n){ ///在索引n后插入节点
Node *t=list,*div;
int i=0;
while(t!=nullptr&&i<n){
t=t->next;
i++;
}
if(t!=nullptr){
div=(Node *)malloc(sizeof(Node));
scanf("%d",&div->a);
div->next=t->next;
t->next=div;
}else printf("Not found\n");
}
void show(Node *list){ //展示链表
Node *t=list;
while(t->next!=nullptr){
t=t->next;
printf("%d ",t->a);
}
printf("\n");
}
void freeMemory(Node *list){ //释放链表占用的内存
Node *t=list;
while(list->next!=nullptr){
t=list;
list=t->next;
free(t);
}
free(list);
}
int main()
{
int n;
cin>>n;
Node *head=init(n);
show(head);
change(head,3);
show(head);
insertNode(head,0);
show(head);
deleteNode(head,5);
show(head);
freeMemory(head);
return 0;
}
数组模拟链表
思想：链表就是因为有节点在可以连接，那么我们再设一个节点数组，每个节点存放着下个节点的下标，然后头结点即数组下标为0，每个下标存放着下一个下标的值，尾结点存放的下标为0，代表链表的结束
增删改查整体思想和上面一致但代码的实现又有很大不同，比较重要的是理解下面这个循环：
for(int i=a[0].point;i!=0;i=a[i].point){
//......
}
这是增删改查以及遍历必不可少的循环，我们看出是从第一个节点（即头结点）开始，因为point记录的是当前节点的下一个节点，结束的条件是找到最后一个节点，因为最后一个节点的point为0
下面是我的测试代码：
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=1e5+10;
struct node{ ///point即记录位置，data就是需要维护的数据
int point,data;
}a[maxn];
int n; ///链表长度
void init(){ ///链表初始化
scanf("%d",&n);
for(int i=1;i<=n;i++){
cin>>a[i].data;
a[i-1].point=i;
}
a[n].point=0;
}
void add(int pos,int x){ ///向链表pos后增加一个数据x,位置0代表在链表头插入元素
int i,head=0;
if(pos==0){
n++;
a[n].point=n;
a[n].data=x;
swap(a[0].point,a[n].point);
return;
}
i=a[0].point;
pos--;
while(pos--){
i=a[i].point;
if(i==0){
printf("Not found!\n");
return ;
}
}
n++;
a[n].point=n;
a[n].data=x;
swap(a[i].point,a[n].point);
}
void change(int pos,int x){ ///把pos位置的数据改为x
int i;
pos--;
for(i=a[0].point;pos;i=a[i].point,pos--){
if(!i){
printf("Not found!\n");
return;
}
}
a[i].data=x;
}
void deleteNode(int pos){ ///删除链表一个位置节点
int i,pre=0; ///pre记录上一个i,即刚开始是0
pos--;
for(i=a[0].point;pos;i=a[i].point,pos--){
if(!i){
printf("Not found!\n");
return;
}
pre=i;
}
int next=a[i].point;
if(!next){ ///看下一个位置是否为0,若是代表该链表只有一个元素
a[pre].point=0;
}else swap(a[pre].point,a[i].point);
}
void show(){ ///遍历链表
for(int i=a[0].point;i!=0;i=a[i].point)
printf("%d ",a[i].data);
printf("\n");
}
int main()
{
int p,q;
init();
cin>>p>>q;
add(p,q);
show();
cin>>p>>q;
change(p,q);
show();
cin>>p;
deleteNode(p);
show();
return 0;
}