【数据结构】初识链表

顺序表的优缺点

缺点：

• 中间/头部的插入删除，时间复杂度效率较低，为O(N)

• 空间不够的时候需要扩容。

  • 如果是异地扩容，增容需要申请新空间，拷贝数据，释放旧空间，会有不小的消耗。

• 扩容可能会存在空间浪费。

  • 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。

优点：

• 尾差尾删足够快。
• 下标的随机访问和修改足够快。

链表的初步认知

针对顺序表的缺点，链表就被设计出来了。
链表的特点即，按需申请释放。
当我们需要一块空间时，我们就申请一块空间。当我们需要添加数据时，就继续增加一个一个小块。
主要是就是一个一个小块之间的连接。为了方便连接和管理，每一个结点中都存有一个指针，用于指向下一个结点。正式一个一个“链接”起来，所以叫做链表。

下面图中主要标识了顺序表和链表的逻辑结构的不同。
对于顺序表，我们只需要知道指向这块内存空间的指针即可。
但是对于链表，我们仅仅知道指向第一块内存空间的指针是不够的，因为一块与一块之间没有连接。所以对于每一块，都必须存有指向下一块空间的指针。

定义单链表的结构

链表的逻辑图：

链表的物理图：

//Single List Table
typedef int SLTDataType;
typedef struct SListNode
{SLTDataType data;struct SListNode* next;//SLTNode* next 是不可以的
}SLTNode;

下面，我们再来写一个打印单链表的的函数。

void PrintSList(SLTNode* phead)
{SLTNode* p = phead;while (p != NULL){printf("%d ", p->data);p=p->next;}printf("NULL\n");
}

然后，接下来，我们再来在主函数中自己建一个单链表，其实也就是开辟几个结点的空间，然后使得结点之间可以“链接”起来即可。

int main()
{SLTNode* n1 = (SLTNode*)malloc(sizeof(SLTNode));n1->data = 1;SLTNode* n2 = (SLTNode*)malloc(sizeof(SLTNode));n2->data = 2;SLTNode* n3 = (SLTNode*)malloc(sizeof(SLTNode));n3->data = 3;n1->next = n2;n2->next = n3;n3->next = NULL;PrintSList(n1);
}

由上图，我们可以知道代码的逻辑。

• 动态分配内存，创建3个 SLTNode 类型的节点，并将其地址赋值给指针 n1、n2、n3。
• 然后将3个结点的next字段都赋值。
• 然后将链表链接起来。
  • n1->next = n2;将节点 n1 的 next 指针指向节点 n2，表示 n1 的下一个节点是 n2。
  • n2->next = n3;将节点 n2 的 next 指针指向节点 n3，表示 n2 的下一个节点是 n3。
  • n3->next = NULL;将节点 n3 的 next 指针设置为 NULL，表示链表到此结束。
• 最后打印链表。

我们进行逐语句调试，在监视窗口中观察n1,n2,n3的变化。

我们可以看出来，n1、n2 和 n3 的物理地址并不连续。
根据结构体的定义，我们可以计算出结构体的大小。

如果内存连续，地址应该是：

而根据我们的监视信息，并非连续，这正是因为在代码中使用了 malloc 动态分配内存。
malloc 从堆中分配内存，而堆内存的分配通常是非连续的，具体取决于系统内存分配器的实现和当前堆内存的使用情况。因此，动态分配的内存块通常在物理地址上是分散的。

---

---

这一篇小博客，我们认识链表，下面我们将接着实现链表。
加油！