单链表基础知识点_单链表的相关知识

链表的基础概念：

链表是一种常见的数据结构，它通过指针或引用将一系列数据节点连接成一个数据链。每个节点通常包括两部分：一个是存储数据元素的数据域，另一个是存储下一个节点地址的指针域。这些节点在运行时可以动态生成，无需预先知道数据总量，因此链表在内存使用上非常灵活。

链表的主要特点包括：

1. 非连续和非顺序存储：链表在物理存储结构上是非连续和非顺序的，这意味着链表中的节点可以分布在内存的不同位置。节点的存储位置是由指针或引用确定的，而不是通过数组索引。
2. 动态性：链表可以在运行时动态地添加和删除节点，而无需移动其他节点。这使得链表在插入和删除操作方面比数组更高效。
3. 灵活性：链表不需要预先分配内存空间，可以根据需要动态地分配和释放内存。这使得链表在处理大量数据时非常有用，因为可以根据实际需要动态地调整内存使用。

链表的主要操作包括：

1. 插入节点：在链表的指定位置插入一个新的节点。这通常涉及到修改指针或引用，以便将新节点正确地链接到链表中。
2. 删除节点：从链表中删除一个指定的节点。这同样需要修改指针或引用，以确保链表的结构在删除节点后仍然保持正确。
3. 查找节点：在链表中查找一个特定的节点。这通常涉及到遍历链表，比较每个节点的数据域以找到匹配的节点。

链表与数组的主要区别：

链表与数组的主要区别在于它们在内存使用、插入和删除操作以及随机访问方面的效率。数组在内存使用上是连续的，可以通过索引快速访问任何元素，但在插入和删除元素时可能需要移动大量元素。而链表则相反，它在内存使用上是非连续的，插入和删除操作更高效，但随机访问效率较低，因为需要从头节点开始遍历链表以找到目标节点。

总的来说，链表是一种非常有用的数据结构，特别适用于需要动态添加和删除元素的情况。然而，它也有一些缺点，比如内存消耗较大（每个节点都需要存储指向下一个节点的指针）以及随机访问效率较低。因此，在选择使用链表还是其他数据结构时，需要根据具体的应用场景和需求进行权衡。

单链表的读取

对于单链表实现获取第i个元素的数据的操作 GetElem，在算法上，相对要麻烦一些。
获得链表第i个数据的算法思路:

1. 声明一个结点p指向链表第一个结点，初始化j从1开始;
2. 当j<i时，就遍历链表，让p的指针向后移动，不断指向下一结点，j累加1;
3. 若到链表末尾p为空，则说明第i个元素不存在;
4. 否则查找成功，返回结点p的数据。

 代码实现如下：

//初始条件：顺序线性表L已存在，1<=i<=ListLength(L)
//操作结果：用e返回L中第i个数据元素的值
Status GetElem(LinkList L, int i, ElemType* e)
{
	int j;
	LinkList p;//声明一结点p
	p = L->next;//让p指向链表L的第一个结点
	j = 1;//j为计时器
	while (p && j < i) {//p不为空或者计时器j还没有等于i时，循环继续
		p = p->next;//让p指向下一个结点
		++j;
	}
	if (!p || j > i) {
		return ERROR;//第i个元素不存在
		*e = p->x;//取第i个元素的数据
		return OK;
	}
}

Status是一个整型，返回OK代表1，ERROR代表0。

单链表的插入与删除

单链表的插入

只需要让 s->next 和 p->next  的指针做改变就好了。

s->next=p->next;
p->next=s;

也就是说让p的后继结点改成 s 的 后继结点，再把结点 s 变成 p 的后继结点。 

 

 这两句的顺序不可以交换，如果先 p->next=s;再s->next=p->next;因为此时第一句会使得将 p->next 给覆盖成s的地址了。那么s->next=p->next，其实就等于s->next=s，这样真正的拥有 ai+1数据元素的结点就没了上级。这样的插入操作就是失败的。

对于单链表的表头和表尾的特殊情况，操作是相同的。

单链表第i个数据插入结点的算法思路:

1. 声明一结点p指向链表第一个结点，初始化j从1开始;
2. 当j<i时，就遍历链表，让p的指针向后移动，不断指向下一结点,j累加1;
3. 若到链表末尾p为空，则说明第i个元素不存在;
4. 否则查找成功，在系统中生成一个空结点s;
5. 将数据元素e赋值给 s->x;
6. 单链表的插入标准语句s->next=p->next; p->next=s;
7. 返回成功。

代码实现：

//初始条件：顺序线性表L已存在，1<=i<=ListLength(L)
//操作结果：在 L 中第i个位置插入新的数据元素e，L的长度加1；
Status ListDelete(LinkList* L, int i, ElemType* e)
{
	int j;
	LinkList p, s;
	p = *L;
	j = 1;
	while (p && j < i) {//寻找第i个结点
		p = p->next;
		++j;
	}
	if (!p || j > i) 
		return ERROR;//第i个元素不存在
	s = (LinkList)malloc(sizeof(Node));//生成新结点
	s->x = e;
	s->next = p->next;//将p的后继结点赋值给s的后继
	p->next = s;//将s赋值给p的后继
	return OK;
}

在这段代码中，使用了malloc标准函数，它的作用就是生成一个新的结点，其类型与Node是一样的，其实质就是在内存中寻找了一小块空地，准备用来存放e数据s结点。

单链表的删除

设存储元素ai的结点为q，要实现将结点q删除单链表的操作，其实就是将它的前继结点的指针绕过，指向它的后继结点即可。

q=p->next;
p->next=q->next;

 单链表第i个数据删除结点的算法思路:

1. 声明一结点p指向链表第一个结点，初始化j从1开始;
2. 当j<i 时，就遍历链表，让p的指针向后移动，不断指向下一个结点，j累加1;
3. 若到链表末尾p为空，则说明第i个元素不存在;
4. 否则查找成功，将欲删除的结点 p->next 赋值给 q;
5. 单链表的删除标准语句 p->next=q->next;
6. 将q结点中的数据赋值给e，作为返回;
7. 释放q结点;
8. 返回成功。

代码实现：

//初始条件：顺序线性表L已存在，1<=i<=ListLength(L)
//操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1；
Status ListDelete(LinkList* L, int i, ElemType* e)
{
	int j;
	LinkList p, q;
	p = *L;
	j = 1;
	while (p->next && j < i) {//遍历寻找第i个元素
		p = p->next;
		++j;
	}
	if (!(p->next) || j > i) 
		return ERROR;//第i个元素不存在
	q = p->next;
	p->next = q->next;//将q 的后继赋值给p的后继
	*e = q->x;//将q结点中的数据给e
	free(q);//让系统回收此结点，释放内存
	return OK;
}

 这段代码，使用了free函数，它的作用就是让系统回收一个Node结点，释放内存。

小总结：

单链表插入和删除算法其实都是由两部分组成:第一部分就是遍历查找第i个元素;第二部分就是插入和删除元素。

对于插入或删除数据越频繁的操作，单链表的效率优势就越是明显。