C语言数据结构--链表 - 赵建华的个人博客

1.链表表示和实现（单链表+双向链表）

顺序表的问题及思考

问题：

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

增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。

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

思考：如何解决以上问题呢？下面给出了链表的结构来看看。

1.1 链表的概念及结构

概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

实际中要实现的链表的结构非常多样，以下情况组合起来就有8种链表结构：

1. 单向、双向

2. 带头、不带头

3. 循环、非循环

虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：

1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。

2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。

1.2单链表的实现

// 1、无头+单向+非循环链表增删查改实现
typedef int SLTDateType;
typedef struct SListNode
{
	SLTDateType data;
	struct SListNode* next;
}SListNode;
// 动态申请一个节点
SListNode* BuySListNode(SLTDateType x);
// 单链表打印
void SListPrint(SListNode* plist);
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x);
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x);
// 单链的尾删
void SListPopBack(SListNode** pplist);
// 单链表头删
void SListPopFront(SListNode** pplist);
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x);
// 单链表在pos位置之前插入x
void SListInsert(SListNode** pplist, SListNode* pos, SLTDateType x);
// 单链表删除pos位置的值
void SListErase(SListNode** pplist, SListNode* pos);

SLTNode* BuyListNode(SLTDataType x)
{
	//新节点
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}


	newnode->data = x;
	newnode->next = NULL;

	return newnode;
}


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

void SListPushBack(SLTNode** pphead, SLTDataType x)
{

	SLTNode* newnode = BuyListNode(x);

	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		//找到尾节点
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}

		//连接
		tail->next = newnode;
	}
}

void SListPushFront(SLTNode** pphead, SLTDataType x)
{
	SLTNode* newnode = BuyListNode(x);

	newnode->next = *pphead;
	*pphead = newnode;

}


void SLitsPopBack(SLTNode** pphead)
{
	//温柔
	/*if (*pphead == NULL)
	{
		return;
	}*/
	//粗暴
	assert(*pphead != NULL);

	if ((*pphead)->next == NULL)
	{
		SLTNode* prev = NULL;
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		tail = NULL;
		prev->next = NULL;
	}
	
}
void SLitsPopFront(SLTNode** pphead)
{
	assert(*pphead!=NULL);

	SLTNode* head = (*pphead)->next;
	free(*pphead);
	*pphead = head;
}


SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{
	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->data==x)
		{
			return cur;
		}
		else
		{
			cur = cur->next;
		}
	}
	return NULL;
}

void SListInsert(SLTNode** phead, SLTNode* pos, SLTDataType x)
{
	
	SLTNode* newnode = BuyListNode(x);
	if (*phead == pos)
	{
		newnode->next = *phead;
		*phead = newnode;
	}
	else
	{
		//找到pos前一个位置
		SLTNode* posPrev = *phead;
		while (posPrev->next != pos)
		{
			posPrev = posPrev->next;
		}
		posPrev->next = newnode;
		newnode->next = pos;
	}
	
}


void SListInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);
	SLTNode* newnode = BuyListNode(x);
	newnode->next = pos->next;
	pos->next = newnode;

}

void SListErase(SLTNode** phead, SLTNode* pos)
{
	assert(phead); 
	assert(pos);
	if (*phead = pos)
	{
		*phead = pos->next;
		free(pos);
	}
	else
	{
		SLTNode* prev = *phead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}

		prev->next = pos->next;
		free(pos);
		pos = NULL;
	}
}


void SListEraseAfter(SLTNode* pos)
{
	assert(pos->next);

	SLTNode* next = pos->next;
	pos->next = next->next;
	free(next);
	next = NULL;
}

void SListDestory(SLTNode** phead)
{
	assert(phead);

	SLTNode* cur = *phead;
	while (cur)
	{
		SLTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	*phead = NULL;

}

1.3 双向链表的表示和实现

// 2、带头+双向+循环链表增删查改实现
typedef int LTDataType;
typedef struct ListNode
{
	LTDataType _data;
	struct ListNode* _next;
	struct ListNode* _prev;
}ListNode;

// 创建返回链表的头结点.
ListNode* ListCreate();
// 双向链表销毁
void ListDestory(ListNode* plist);
// 双向链表打印
void ListPrint(ListNode* plist);
// 双向链表尾插
void ListPushBack(ListNode* plist, LTDataType x);
// 双向链表尾删
void ListPopBack(ListNode* plist);
// 双向链表头插
void ListPushFront(ListNode* plist, LTDataType x);
// 双向链表头删
void ListPopFront(ListNode* plist);
// 双向链表查找
ListNode* ListFind(ListNode* plist, LTDataType x);
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x);
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos);

LTNode* BuyListNode(LTDateType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode;
}

LTNode* ListInit()
{
	//哨兵位头结点
	LTNode*phead = (LTNode*)malloc(sizeof(LTNode));
	phead->next = phead;
	phead->prev = phead;

	return phead;
}


void ListPushBack(LTNode* phead, LTDateType x)
{
	assert(phead);

	//LTNode* tail = phead->prev;
	//LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));

	//newnode->data = x;

	////phead                    tail   newnode

	//tail->next = newnode;
	//newnode->prev = tail;
	//newnode->next = phead;
	//phead->prev = newnode;
	ListInsert(phead, x);
}

void ListPrint(LTNode* phead)
{
	assert(phead);

	LTNode* cur = phead->next;
	while (cur!=phead)
	{
		printf("%d ",cur->data );
		cur = cur->next;
	}
	printf("\n");
}


void ListPushFront(LTNode* phead, LTDateType x)
{
	assert(phead);
	/*LTNode* newnode = BuyListNode(x);
	LTNode* next = phead->next;

	phead->next = newnode;
	newnode->prev = phead;

	newnode->next = next;
	next->prev = newnode;*/
	ListInsert(phead->next, x);
}

void ListPopFront(LTNode* phead)
{
	assert(phead);
	//如果链表为空,则不要头删;
	assert(phead->next != phead);
	/*
	LTNode* next = phead->next;
	LTNode* tail = next->next;

	phead->next = tail;
	tail->prev = phead;
    free(next); */
	ListErase(phead->next);
}

void ListPopBack(LTNode* phead)
{
	assert(phead);
	assert(phead);
	assert(phead->next!=phead);

	//LTNode* cur = phead->prev;
	//if (phead->next == phead)
	//	return;
	//cur->prev->next= phead;
	//phead->prev = cur->prev;
	//free(cur);
	ListErase(phead->prev);
	
}

LTNode* ListFind(LTNode* phead, LTDateType x)
{
	assert(phead);

	LTNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}

	return NULL;
}
//pos之前插入
void ListInsert(LTNode* pos, LTDateType x)
{
	assert(pos);
	LTNode* posPrev = pos->prev;
	LTNode* newnode = BuyListNode(x);

	//posPrev  newnode   pos

	posPrev->next = newnode;
	newnode->prev = posPrev;

	newnode->next = pos;
	pos->prev = newnode;
}

//删除pos
void ListErase(LTNode* pos)
{
	assert(pos);

	LTNode* posPrev = pos->prev;
	LTNode* posNext = pos->next;

	
	posPrev->next = posNext;
	posNext->prev = posPrev;

	free(pos);
	pos = NULL;
	
}

void ListDestory(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;

	while (cur)
	{
		LTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
	phead = NULL;
}

2.链表的常见OJ题

1.反转单链表：206. 反转链表 - 力扣（LeetCode）

2.链表的中间结点：876. 链表的中间结点 - 力扣（LeetCode）

3.合并两个有序链表：21. 合并两个有序链表 - 力扣（LeetCode）

4.判断链表是否有环？：141. 环形链表 - 力扣（LeetCode）

5.求环形链表的入口点？：142. 环形链表 II - 力扣（LeetCode）

3.顺序表和链表的区别和联系

顺序表：

优点：空间连续、支持随机访问

缺点：

中间或前面部分的插入删除时间复杂度O(N)

2.增容的代价比较大。

链表：

缺点：以节点为单位存储，不支持随机访问

优点：

任意位置插入删除时间复杂度为O(1)

没有增容消耗，按需申请节点空间，不用了直接释放。

4.顺序表和链表概念选择题

概念选择题：

1.在一个长度为n的顺序表中删除第i个元素，要移动____个元素。如果要在第i个元素前插入一个元素，要后移____个元素。 A n - i，n - i + 1 B n - i + 1，n - i C n - i，n - i D n - i + 1，n - i + 1

2.取顺序表的第i个元素的时间同i的大小有关() A 对 B 错

3.在一个具有 n 个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是。 A O（1） B O（n） C O（n2） D O（nlog2n）

4.下列关于线性链表的叙述中，正确的是（）。 A 各数据结点的存储空间可以不连续，但它们的存储顺序与逻辑顺序必须一致 B 各数据结点的存储顺序与逻辑顺序可以不一致，但它们的存储空间必须连续 C 进行插入与删除时，不需要移动表中的元素 D 以上说法均不正确

5.设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用（）最节省时间。 A 单链表 B 单循环链表 C 带尾指针的单循环链表 D 带头结点的双循环链表

6.链表不具有的特点是（）。 A 插入、删除不需要移动元素 B 不必事先估计存储空间 C 可随机访问任一元素 D 所需空间与线性表长度成正比

7.在一个单链表中，若删除 P 所指结点的后续结点，则执行 ? A p = p->next；p->next = p->next->next; B p->next = p->next; C p->next = p->next->next; D p = p->next->next

8.一个单向链表队列中有一个指针p，现要将指针r插入到p之后，该进行的操作是____。 A p->next = p->next->next B r->next = p; p->next = r->next C r->next = p->next; p->next = r D r = p->next; p->next = r->next E r->next = p; p->next = r F p = p->next->next

答案:1.A 2.B 3.B 4.C 5.D 6.C 7.C 8.C