标签：head ListNode pos phead next 链表 SLNode

1. 顺序表的缺陷

1. 在顺序表头部中间插入数据，需要挪动数据效率低下

2. 容量不够时需要扩容，所以可能存在空间浪费

链表可以很好的解决这些问题，下面讲解链表

2. 链表概念及基本结构

链表是一种逻辑上连续,物理内存空间非连续存储的线性结构

typedef int SLDataType;
typedef struct SListNode
{
	SLDataType data;
	struct SListNode* next;
}SLNode;

链表实际在内存中的存储:

链表的逻辑结构:

如图, 链表本身由一个个节点组成，每一个节点都可以通过一个next指针找到下一个节点的地址，以此来实现数据元素之间的逻辑顺序

3. 链表的分类

1. 单向 / 双向

2. 带头或者不带头

3. 循环或者非循环

总共8种，在实际中最常用的只有两种无头单向非循环链表(单链表)和带头双向循环链表(双向链表), 下面分别实现

4. 单链表

单链表结构

实现

SList.h

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>

typedef int SLDataType;
typedef struct SListNode
{
	SLDataType data;
	struct SListNode* next;
}SLNode;

// 创建节点
SLNode* BuyListNode(SLDataType x);
// 尾插
void SLPushBack(SLNode** pphead, SLDataType x);
// 打印
void SLPrint(SLNode* phead);
// 尾删
void SLPopBack(SLNode** pphead);
// 头插
void SLPushFront(SLNode** pphead, SLDataType x);
// 头删
void SLPopFront(SLNode** pphead);
// 查找
SLNode* SLFind(SLNode* phead, SLDataType x);
// pos之前插入
void SLInsertFront(SLNode** pphead, SLNode* pos, SLDataType x);
// pos之后插入
void SLInsertBack(SLNode* pos, SLDataType x);
// pos位置删除
void SLErace(SLNode** pphead, SLNode* pos);
// pos之后删除
void SLEraceAfter(SLNode* pos);

SList.c

#include "SList.h"
// 创建节点
SLNode* BuyListNode(SLDataType x)
{
	SLNode* node = (SLNode*)malloc(sizeof(SLNode));
	if (NULL == node)
	{
		perror("BuyListNode::malloc");
		return;
	}
	else
	{
		node->data = x;
		node->next = NULL;
		return node;
	}
	return NULL;
}
// 尾插
void SLPushBack(SLNode** pphead, SLDataType x)
{
	assert(pphead);
	SLNode* newnode = BuyListNode(x);
	if (NULL == *pphead)
	{
		*pphead = newnode;
	}
	else
	{
		// 找尾
		SLNode* tail = *pphead;
		while (tail->next)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}
// 打印
void SLPrint(SLNode* phead)
{
	SLNode* cur = phead;
	printf("HEAD -> ");
	while (cur)
	{
		printf("%d -> ", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}
// 尾删
void SLPopBack(SLNode** pphead)
{
	assert(pphead);
	assert(*pphead);
	if (NULL == (*pphead)->next)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLNode* tail = *pphead, *prev = NULL;
		while (tail->next)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		prev->next = NULL;
	}
}
// 头插
void SLPushFront(SLNode** pphead, SLDataType x)
{
	assert(pphead);
	SLNode* newnode = BuyListNode(x);
	SLNode* next = *pphead;
	*pphead = newnode;
	newnode->next = next;
}
// 头删
void SLPopFront(SLNode** pphead)
{
	assert(pphead);
	assert(*pphead);
	SLNode* next = (*pphead)->next;
	free(*pphead);
	*pphead = next;
}
// 查找
SLNode* SLFind(SLNode* phead, SLDataType x)
{
	SLNode* cur = phead;
	while (cur)
	{
		if (x == cur->data)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}
// pos之前插入
void SLInsertFront(SLNode** pphead, SLNode* pos, SLDataType x)
{
	assert(pphead);
	assert(pos);
	SLNode* newnode = BuyListNode(x);
	if (*pphead == pos)
	{
		SLNode* next = *pphead;
		*pphead = newnode;
		newnode->next = next;
	}
	else
	{
		SLNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = newnode;
		newnode->next = pos;
	}
}
// pos之后插入
void SLInsertBack(SLNode* pos, SLDataType x)
{
	assert(pos);
	SLNode* newnode = BuyListNode(x);
	SLNode* next = pos->next;
	pos->next = newnode;
	newnode->next = next;
}
// pos位置删除
void SLErace(SLNode** pphead, SLNode* pos)
{
	assert(pphead);
	assert(*pphead);
	assert(pos);
	if (*pphead == pos)
	{
		SLNode* next = pos->next;
		free(pos);
		*pphead = next;
	}
	else
	{
		SLNode* prev = *pphead, *next = pos->next;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = next;
		free(pos);
	}
}
// pos之后删除
void SLEraceAfter(SLNode* pos)
{
	assert(pos);
	assert(pos->next);
	SLNode* next = pos->next->next;
	free(pos->next);
	pos->next = next;
}

test.c

#include "SList.h"
void t1()
{
	// 测试打印, 尾插, 尾删
	SLNode* head = NULL;
	SLPushBack(&head, 1);
	SLPushBack(&head, 2);
	SLPushBack(&head, 3);
	SLPopBack(&head);
	SLPrint(head);
}
void t2()
{
	// 测试头插，头删
	SLNode* head = NULL;
	SLPushFront(&head, 1);
	SLPushFront(&head, 2);
	SLPushFront(&head, 3);
	SLPopFront(&head);
	SLPrint(head);
}
void t3()
{
	// 测试查找,pos前/后插入
	SLNode* head = NULL;
	SLPushBack(&head, 1);
	SLPushBack(&head, 2);
	SLPushBack(&head, 3);
	SLPushBack(&head, 4);
	SLPushBack(&head, 5);
	/*SLInsertFront(&head, SLFind(head, 1), 6);
	SLInsertFront(&head, SLFind(head, 4), 7);*/
	SLInsertBack(SLFind(head, 3), 6);
	SLInsertBack(SLFind(head, 5), 7);
	SLPrint(head);
}
void t4()
{
	// 测试pos位置,之后删除
	SLNode* head = NULL;
	SLPushBack(&head, 1);
	SLPushBack(&head, 2);
	SLPushBack(&head, 3);
	SLPushBack(&head, 4);
	SLPushBack(&head, 5);
	//SLErace(&head, SLFind(head, 3));
	SLEraceAfter(SLFind(head, 1));
	SLPrint(head);

}
int main()
{
	//t1();
	//t2();
	//t3();
	t4();
}

6. 双向链表

双向链表结构

实现

List.h

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>

typedef int LTDataType;
typedef struct ListNode
{
	struct ListNode* prev;
	LTDataType data;
	struct ListNode* next;
}ListNode;

// 初始化
ListNode* LTInit();
// 创建节点
ListNode* BuyListNode(LTDataType x);
// 打印
void LTPrint(ListNode* phead);
// 尾插
void LTPushBack(ListNode* phead, LTDataType x);
// 头插
void LTPushFront(ListNode* phead, LTDataType x);
// 尾删
void LTPopBack(ListNode* phead);
// 头删
void LTPopFront(ListNode* phead);
// 查找
ListNode* LTFind(ListNode* phead, LTDataType x);
// pos之前插入
void LTInsert(ListNode* pos, LTDataType x);
// pos位置删除
void LTErace(ListNode* pos);
// 销毁
void LTDestroy(ListNode* phead);

List.c

#include "List.h"
// 创建节点
ListNode* BuyListNode(LTDataType x)
{
	ListNode* node = (ListNode*)malloc(sizeof(ListNode));
	if (NULL == node)
	{
		perror("BuyListNode::malloc fail");
		return;
	}
	node->prev = node->next = NULL;
	node->data = x;
	return node;
}
// 初始化
ListNode* LTInit()
{
	ListNode* Guard = BuyListNode(-1);
	Guard->prev = Guard->next = Guard;
	Guard->data = -1;
	return Guard;
}
// 打印
void LTPrint(ListNode* phead)
{
	assert(phead);
	ListNode* cur = phead->next;
	printf("GUARD <-> ");
	while (cur != phead)
	{
		printf("%d <-> ", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}
// 尾插
void LTPushBack(ListNode* phead, LTDataType x)
{
	assert(phead);
	ListNode* newnode = BuyListNode(x);
	ListNode* tail = phead->prev;

	phead->prev = newnode;
	tail->next = newnode;
	newnode->next = phead;
	newnode->prev = tail;
}
// 头插
void LTPushFront(ListNode* phead, LTDataType x)
{
	assert(phead);
	ListNode* newnode = BuyListNode(x);
	ListNode* next = phead->next;

	phead->next = newnode;
	newnode->prev = phead;
	newnode->next = next;
	next->prev = newnode;
}
// 判断链表是否为空
bool isLTEmpty(ListNode* phead)
{
	assert(phead);
	return phead->next == phead;
}
// 尾删
void LTPopBack(ListNode* phead)
{
	assert(phead);
	assert(!isLTEmpty(phead));
	ListNode* tail = phead->prev, *Pretail = tail->prev;

	Pretail->next = tail->next;
	phead->prev = Pretail;
	free(tail);
}
// 头删
void LTPopFront(ListNode* phead)
{
	assert(phead);
	assert(!isLTEmpty(phead));
	ListNode* first = phead->next, * next = first->next;

	phead->next = next;
	next->prev = phead;
	free(first);
	
}
// 查找
ListNode* LTFind(ListNode* phead, LTDataType x)
{
	assert(phead);
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		if (x == cur->data)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}
// pos之前插入
void LTInsert(ListNode* pos, LTDataType x)
{
	assert(pos);
	ListNode* newnode = BuyListNode(x);
	ListNode* Prevpos = pos->prev;

	Prevpos->next = newnode;
	newnode->prev = Prevpos;
	newnode->next = pos;
	pos->prev = newnode;
}
// pos位置删除
void LTErace(ListNode* pos)
{
	assert(pos);
	ListNode* next = pos->next, * prev = pos->prev;
	prev->next = next;
	next->prev = prev;
	free(pos);
}
void LTDestroy(ListNode* phead)
{
	assert(phead);
	ListNode* cur = phead->prev;
	while (cur != phead)
	{
		ListNode* prev = cur->prev;
		free(cur);
		cur = prev;
	}
	free(phead);
}