1、链表
1.1、链表的结构
- 每个链表开头都有一个头指针Head
- 尾节点的指针域为NULL，用于判断此列表是否结束
- 如果一个链表开始就为NULL，那么该链表为空链表
- 链表中的先后不代表在真实内存中的位置，只是单纯的逻辑上关系
1.2、创建链表
- 我们首先利用结构体创建一个Student的结构体
//利用链表创建3个学生的信息，学生信息包括姓名和年龄
struct Student
{
char name[20];
int age;
//这里存放的下个节点的地址
Student *next;
};
- 接着我们给我们的节点赋值，跟着上面的图，我们知道需要一个头节点（无数据，只存地址），一个尾节点（有数据，地址为NULL）
Student c = { "t3",21, nullptr};//尾节点，指针域为nullptr
Student b = { "t2",27,&c };
Student a = { "t1",22,&b };
Student* head = &a; //头指针，指向a,无值
1.3、链表数据的遍历
创建完链表后，我们来输出一下内容，那么我们就需要链表a的地址，然后输出完当前内容后，将指针指向下一个地址
//定义一个指针来指向head
Student *pointer = head;
//循环到尾节点（nullptr）时结束
while (pointer)
{
cout << pointer->name << " " << pointer->age << endl;
//输出完后指向下一个
pointer = pointer->next;
}
1.4、链表的查找
- 我们查找一下t2这个人，并返回他的年龄
while (pointer)
{
if (pointer->name=="t2")
{
cout << pointer->age << endl;
break;
}
pointer = pointer->next;
}
if (pointer==nullptr)
{
cout << "没有找到此人" << endl;
}
1.5、链表的插入
我们首先手动新加一条数据
Student d = { "t4",21,nullptr };
区别与数组，我们不需要移动任何数据，只需要将要插入的地方的前一项地址指向插入的数据，插入的数据再指向后一条数据即可(PS:灵魂画手，不要介意)
这里需要注意一点，先指向C，不然早断开C会找不到C的地址，也就是E的指针域要先指向C的地址，防止丢失。
那么我们就在t2的后面插入一条数据
//before指向前一条数据
//pointer指向后一条数据
Student* before = head;
Student *pointer = before->next;
while (before)
{
if (before->name=="t2")
{
d.next = pointer; //赋值&c的地址
before->next = &d; //t2断开c的地址，链接d的地址
break;
}
//如果不匹配，就让俩个指针往后走
before = pointer;
pointer = before->next;
}
1.6、链表的删除
那么删除就只需要将要被删除的节点指向的地址，给到前一个节点。
那我们就删除上面新加的t4
before = head;
pointer = before->next;
//这里需要注意是因为要删除后一个，所以pointer作为循环条件
while (pointer)
{
if (pointer->name == "t4")
{
before->next = pointer->next;
break;
}
before = pointer;
pointer = pointer->next;
}
2、链表和数组的区别
| 数组 | 链表 | |
|---|---|---|
| 内存占用 | 连续内存 | 灵活，无限制 |
| 元素类型 | 相同类型 | 可以相同，可以不同 |
| 组织形式 | 在内存中连续排序 | 各节点在内存中彼此分散，靠指针联系 |
| 插入删除元素 | 需要遍历 | 只修改某个或几个节点的指针 |
