数据结构之单链表

什么是单链表

单链表是线性链式存储结构，每个节点存数据和下一个节点地址，节点不连续分布在内存。

单链表的结构

我们要先来构建结点的结构

节点分为数据域和指针域

数据域用来储存数据,指针域用来寻找下一个节点的位置

typedef int LDataType;
typedef struct ListNode {
LDataType data; // 存储数据
struct ListNode* next; // 存放后继结点地址
}LNode, * LinkList;

初始化单链表

我们构建的链表是有哨兵位头节点的链表,初始化也就是将哨兵位头节点初始化,由于哨兵位节点并不用来储存数据,我们将其搞成-1.

链表节点的数量是不确定的,我们需要malloc来申请空间,然后我们将新建节点的操作单拎出来来实现,方便之后的使用

// 创建一个新结点
LNode* BuyListNode(int data)
{
LNode* newNode = (LNode*)malloc(sizeof(LNode));
if (newNode == NULL)
{
printf("申请空间失败\\n");
return NULL;

}
newNode->data = data;
newNode->next = NULL;
return newNode;
}

// 初始化链表
LNode* ListInit()
{
LNode* head = BuyListNode(-1);
return head;
}

插入数据

我们观察上面的图片,我们在插入时要记录插入位置的前面一个节点,然后new一个新的节点.

prev,new,next

这个时候我们由两种方式来解决,第一种就是将前面节点记录,将后面节点记录,然后在按照顺序对其进行连接

第二种就是不新起节点,但是这时必须要遵循操作的顺序,不然链表就断链了

先将new的next指向prev的next,再将prev的next指向new.

主要的操作就是这样,但真的实践起来我们还要考虑头插,尾插是否可以实现

边界的处理,要查看能不能实现头插,尾插这样的操作

void ListInsert(LNode* L, int i, LDataType x)
{
assert(L);
assert(i >= 0);
//先new一个新的节点出来
LNode* cur = BuyListNode(x);
LNode* prev = L;
int count = -1;

while (prev&&count<i-1)
{
prev = prev->next;
count++;
}

if (prev == NULL || count != i – 1)
{
free(cur);
return;
}

// prev cur next
LNode* next = prev->next;
prev->next = cur;
cur->next = next;

}

删除数据

删除的逻辑

第一步也是要记录删除节点的前面一个位置的节点

后面也可以和插入哪里类似,这里不做过多的赘述,但是要注意删除的节点要free

主要的操作就是这样,但真的实践起来我们还要考虑头插,尾插是否可以实现

边界的处理

// 删除链表中下标为i的结点，并用x带出结点的值
LDataType ListDelete(LNode* L, int i)
{
//先找出删除位置的前一个位置
assert(L);
assert(i >= 0);
LNode* prev = L;
int count = -1;

while (prev && count < i – 1)
{
prev = prev->next;
count++;
}

if (prev == NULL || count != i – 1)
{
return;
}
//prev cur next
LNode* next = prev->next->next;
LNode* cur = prev->next;
LDataType x = cur->data;
prev->next = next;
free(cur);
return x;
}

销毁单链表

就是将整张表遍历一遍,并且删除节点,为了防止找不到下一个节点我们要记录下一个节点

// 销毁链表
void ListDestroy(LNode* L)
{
LNode* cur = L;

while (cur)
{
LNode* next = cur->next;
free(cur);
cur = next;
}
}

头删尾删,头插尾插,判空

比较简单,这里不多做赘述

bool ListEmpty(LNode* L)
{
assert(L);
return L->next == NULL;
}

void ListPushFront(LNode* L, LDataType x)
{
assert(L);
LNode* newNode = BuyListNode(x);
newNode->next = L->next;
L->next = newNode;
}

void ListPushBack(LNode* L, LDataType x)
{
assert(L);
LNode* tail = L;
while (tail->next)
{
tail = tail->next;
}
tail->next = BuyListNode(x);
}

LDataType ListPopFront(LNode* L)
{
assert(L);
assert(!ListEmpty(L));
LNode* del = L->next;
LDataType x = del->data;
L->next = del->next;
free(del);
return x;
}

LDataType ListPopBack(LNode* L)
{
assert(L);
assert(!ListEmpty(L));
LNode* prev = L;
while (prev->next && prev->next->next)
{
prev = prev->next;
}
LNode* del = prev->next;
LDataType x = del->data;
prev->next = NULL;
free(del);
return x;
}

单链表与顺序表的对比

存储空间

• 顺序表：连续堆内存，预先分配容量，存在闲置空间浪费；存数据 + 无额外开销。
• 单链表：节点离散分布，按需malloc；每个节点多存 1 个next指针，额外空间开销大。

扩容逻辑

• 顺序表：空间满要重新开辟更大数组 + 拷贝全部元素，扩容代价高。
• 链表：不用整体扩容，新增结点单独申请内存，无整体搬迁。

随机存取

• 顺序表：依靠首地址 + 偏移量，支持[下标]随机访问。
• 链表：无连续地址，不支持随机访问，想找第 i 个必须从头挨个走

增删本质区别

• 顺序表：改位置 =移动大量元素（数据搬家）。
• 单链表：找到前驱后 =修改 2 处指针指向，数据不移动。

顺序表适合,频繁的查询,在尾部插入和删除较多,随机访问较多的场景

单链表适合,频繁的头尾插入,删除.