一、单链表基础概念讲解
上一张我们分析了顺序表，可以看出顺序表的好处有以下几点：
1、顺序表在查找某个元素时比较简单；顺序表可以直接通过下标的方式就可以访问到了这个元素
2、顺序表在插入到末尾，或者删除末尾元素也是比较简单的；这个时候也可以直接通过下标的方式直接访问到这个元素；
但是顺序表野有自己的缺点，如下：
1、顺序表在插入到中间某个位置时，是比较困难的；因为后面的元素需要挨个的移动；
2、同理，顺序表在删除中间某个位置的元素是，也是比较困难的；后面的元素也是要挨个移动到前面；
那么问题的关键就在这个地方了：
1、如果我们不是频繁的往中间去插元素或者去删除元素；我们知识在最后插入元素；或者主要的操作是遍历和查找元素的话，我们用顺序表，无疑是最快的；
那么，如果，那么我们就引入了链表的操作；
所谓的链表，就是每一个节点都是在存储上不连续的；都是可以通过上一个节点去访问到的；那么这其中有一个问题就是；如果在链表的最后面插入时候，就会存在需要遍历整个链表才能访问到最后一个元素的问题；所以我们为了解决这样的问题；我们直接定义出尾指针，来记录出最后一个节点；
综上：
我们可以看出链表的有点在于插入和删除；缺点是在查找某个元素时候，比较麻烦，需要遍历到这个元素才能把这个位置的内容取出；
二、单链表基本操作
1、单链表准备数据
什么是单链表；我们用图来表示以下：
image.png
我们的每个元素都是这样的；有自己的数据域，和一个指向下一个节点的指针阈；
所以我们这样来操作：
//结点
typedef struct Node {
int data;
Node * next;
}Node;
//创建列表
typedef struct ListMine {
Node *head;
Node *tail;
int length;
}ListMine;
2、单链表创建和析构
//创建空链表
void createList(ListMine* SL)
{
SL->head = SL->tail = NULL;
SL->length = 0;
}
void distroyList(ListMine* SL)
{
Node* cur = SL->head;
while (cur != NULL)
{
Node* tmp = cur->next;
free(cur);
cur = tmp;
}
free(SL);
}
3、单链表插入和删除
图示：
1、插入操作：
image.png
2、删除操作：
image.png
//插入结点
bool insert(ListMine*SL, int i, int data)
{
Node *p = SL->head; //0
if (i > SL->length)
{
cout << "insert location error" << endl;
return false;
}
Node *n = (Node*)calloc(1,sizeof(Node)); //分配新内存；
n->data = data;
n->next = NULL;
if (i == 0)
{
SL->head = SL->tail = n;
SL->length += 1;
return true;
}
//之所以单独抽出来，是因为这样可以增快最后插入的时间
//这就是为了告诉自己，尾指针的作用
//后面如果有栈和队列的操作的时候，就会明白这个的重要性了
if (i == SL->length)
{
SL->tail->next = n;
SL->tail = n;
SL->length ++;
return true;
}
//后面这就是重要的一般插入的问题了
int j = 0;
while (j < i - 1 && p->next)
{
p = p->next;
++j;
}
n->next = p->next;
p->next = n;
SL->length++;
return true;
}
//删除结点
bool del(ListMine*SL, int i)
{
Node *p = SL->head; //0
int j = 0;//0
while (j < i-1 && p->next)
{
p = p->next;
++j;
}
Node *willfree = p->next;
p->next = p->next->next;
delete willfree; //释放内存
return true;
}
3、main函数验证
///主函数///
int main() {
ListMine* SL = (ListMine*)calloc(1, sizeof(ListMine));
createList(SL);
int i = 0;
for (; i < 10; i++)
{
insert(SL, i, i);
}
del(SL, 7);
Node*cur = SL->head;
while (cur!= NULL)
{
cout << "the data is " << cur->data << endl;
cur = cur->next;
}
distroyList(SL);
}
运行结果如下：
image.png
