# 概述

计算机中的线性结构有两种方法实现，第一种就是喜闻乐见的数组形式。第二种则是链式结构.
与数组相比链式结构可以使用碎片的内存块来实现存储。常简逻辑形式如下:

如图所示链表中的每一个元素都是一个单独的对象，每个对象之间通过指针 (引用) 的方式相连接.
这种连接方式使得，链表的大小位动态的可以随时添加和减少 (在存在 MMU 的计算机中); 也是因为这种链接方式，链表丧失了数组的常数级数据访问的速度.

链表存在两种类型：单链表和双链表。上面的就是单链表的例子，下面的则为双链表

与单链表相比，双链表多了一个可以逆向查找的操作，以存储空间为代价解决了单链表不能逆向查找的问题

# 单链表概述

所有数据结构最大的目的就是更高效用内存的增删查改数据.
单链表也不例外，所以单链表数据结构组成中在逻辑上分为了 数据域和指针域。数据域用于存储指定类型的数据，指针域用于存储下一个链表节点的地址.
链表之所以称之为链式，就是因为指针域的指针存在。当这些相同类型的数据节点按某种顺序通过指针链接起来就被称为链表

图中红色箭表示链表是如何链接起来的

# 节点结构

在 c 语言中数组无法包含不同的数据类，所以很显然链表这种数据结构只能通过 struct 来实现
常见的链表节点如下:

	typedef struct SingListNode{
	int val;
	struct SingListNode *next;
	}SingListNode_t;

这里再留一个 cpp 的写法 (纪念我早已忘记的 cpp)

	struct SinglyListNode {
	//cpp 不需要 typedef 就可以使用结构体的名称来声明变量
	int val;
	SinglyListNode *next;
	SinglyListNode(int x) : val(x), next(NULL) {}
	};

# 操作

有了上面的存储结构还不能称之为数据结构。前面说过数据结构的存在是为了高效的利用内存对数据进行增删查改，所以有存储结构必定会有在其之上的一系列操作
这里再啰嗦一下上面说过的一些话
在链表中访问单链表中的随机元素平均的时间复杂度为 O (N). 因为每一次我们都只能从链表的头部进行遍历，直到找到第 n 个元素
如上图：如果想要访问第 3 个节点，那么在链表中唯一的方法就是从头节点开始每一次通过 next 指针进行跳转到下一个节点.
即 10 通过 next 获得到节点 2 的地址，节点 2 通过自己的 next 获取到节点 3 的地址，进行了两次转跳.

# 常用操作分析

在链表中最为常用的算法就是 添加和删除 ，在这两个操作中会涉及到 "大量" 的指针操作抽象逻辑，理解了这两个操作之后就可以很容易的实现其他的链表操作

# 添加操作

# 在表中插入一个节点

当给定一个节点 prev_node , 如果我们想要在它后面添加一个新的值 val , 在逻辑上我们分为如下几步:

初始化新节点，并将 val 赋值给新节点 cur 的 val ;
将 cur 的 next 字段链接到 prev_node 的下一个节点 next_node ;
将 prev_node 的 next 字段链接到 cur

与数组不同，链表不需要将所有元素移动到插入元素之后。时间复杂度为 O (1)

# 特例一：在头部插入节点

上面所上述的是链表中的节点插入，但是我们还需要考虑到整个链表的所有位置的插入。例如：表头和表尾总所周知，我们使用头节点来定位整个链表故在列表的头部加入一个新节点 head 非常致命

初始化新节点，并将 val 赋值给新节点 cur 的 val ;
将新节点链接到原始节点 head
让 cur 变为 head

# 特例二：在尾部插入节点

尾部插入节点更为简单

初始化新节点，并将 val 赋值给新节点 cur 的 val ;
找到 end 节点，将 end 节点链接到 cur
cur 节点链接到空指针

# 删除操作

# 在表中删除现有节点

从单链表中删除现有节点 cur , 可以分为两步:

找到 cur 的上一个节点 prev_node 及其下一个节点 next ;
链接到 prev_node 到 cur 的 next_node
将 cur 的 next 字段链接到 NULL , 然后释放 cur 节点.

ps: 图中的节点指向了自己然后被 free 掉后等价于指向空

在 step 1 中，需要找出 prev_node 和 next_node . cur 的字段很容易找出 next_node , 但是，我们必须从头结点遍历链表，以找出 prev_node , 其的平均时间是 O (N), 其中 N 是链表的长度.
因此，删除结点的时间复杂度将是 O (N).

# 特例一：删除头节点

同样删除头部节点也是一个较为特殊的操作，一个不小心整个链表就会丢失.

head 的 next 字段链接到 head->next 的 next 字段上.
head 的 next 连接道空指针，然后释放 head .

# 特例二：删除尾节点

尾节点的操作也很简单，需要记住最终指向空即可，设尾节点为 tail

找到 tail 的上一个节点 prev_node .
将 prev_node 的 next 字段指向空指针.
tail 的 next 字段链接到空指针，然后释放.

# 代码实现

下面的代码以带头节点的链表格式实现。大体思路实现与不带头节点的链表原理一致.
接口格式源于 leetcode 707 链表设计 .
各位可自行测试自己的实现方式，本文的所有代码都在本地测试过，放心食用 (ฅ・ω・ฅ)

# 链表部分

	typedef struct MyLinkedList
	{
	int val;
	struct MyLinkedList *next;
	} MyLinkedList;

	MyLinkedList *myLinkedListCreate()
	{
	MyLinkedList node = (MyLinkedList )malloc(sizeof(MyLinkedList));
	node->val = 0;
	node->next = NULL;
	return node;

	}

	int myLinkedListGet(MyLinkedList *obj, int index)
	{
	// 1. index < 0
	// 2. 链表为空
	// 3. index 过大
	if (index < 0 && !(obj->next))
	return -1;

	MyLinkedList *head = obj->next;

	查找第 index 个节点, 可能存在两种情况
	// 1. 存在第 index 个节点
	// 2. 不存在第 index 个节点
	for (int i = 0; head && i < index; i++)
	{ // 查 value 不需要获取前一个节点
	head = head->next;
	}

	//head 非空代表存在整个值返回 -1 ,
	// 否则返回 val
	return (head ? head->val : -1);
	}

	void myLinkedListAddAtHead(MyLinkedList *obj, int val)
	{
	// 初始化新节点
	MyLinkedList node = (MyLinkedList )malloc(sizeof(MyLinkedList));

	node->val = val;

	// 指向 head 后面的节点
	// 如果为空，也会指向空，所以无需 next 指向空
	node->next = obj->next;
	obj->next = node;
	}

	void myLinkedListAddAtTail(MyLinkedList *obj, int val)
	{

	// 当链表为空，尾插变头插
	if (NULL == obj->next)
	{
	myLinkedListAddAtHead(obj, val);
	return;
	}

	// 初始化节点
	MyLinkedList node = (MyLinkedList )malloc(sizeof(MyLinkedList));
	node->val = val;
	node->next = NULL;

	// 查找最后一个节点
	MyLinkedList *tail = obj->next;
	while (tail->next)
	{ //obj 为空无法获取到前一个节点
	tail = tail->next;
	}

	// 尾节点指向新节点
	tail->next = node;
	}

	void myLinkedListAddAtIndex(MyLinkedList *obj, int index, int val)
	{
	// 过滤非法 index < 0, 使用头插法，题目要求，正常情况过滤负数，特判头节点
	if (index <= 0)
	return myLinkedListAddAtHead(obj, val);

	// 找到第 index-1 个节点
	int i = 0;
	MyLinkedList *head = obj->next;
	for (i = 0; head->next && i < index - 1; i++)
	{ // 和获取第 index 值类似，只不过这里需要获取前一个节点
	head = head->next;
	}

	// 判断退出条件
	if (index - 1 != i)
	{
	return;
	}

	// 初始化节点，避免浪费空间
	MyLinkedList node = (MyLinkedList )malloc(sizeof(MyLinkedList));
	node->val = val;

	// 插入节点
	node->next = head->next;
	head->next = node;

	}

	void myLinkedListDeleteAtIndex(MyLinkedList *obj, int index)
	{

	// 异常拦截
	if (!(obj->next) \|\| index < 0)
	return;

	// 分类讨论
	MyLinkedList *temp = NULL;

	// 1. 删除头节点
	if (0 == index)
	{
	temp = obj->next;
	obj->next = obj->next->next;
	temp->next = temp;
	free(temp);
	return;
	}

	// 找到第 index - 1 个节点
	int i = 0;
	MyLinkedList *head = obj->next;

	for (i = 0; head->next && i < index - 1; i++)
	{
	head = head->next;
	}

	// 不存在则退出函数
	if (i != index - 1 \|\| (NULL == head->next))
	return;

	// 删除节点
	temp = head->next;
	head->next = head->next->next;
	temp->next = temp;
	free(temp);
	}

	void myLinkedListFree(MyLinkedList *obj)
	{
	// 异常拦截
	if (!obj)
	return;

	MyLinkedList *head = obj->next;
	MyLinkedList *temp = NULL;

	while (head)
	{
	temp = head->next;
	free(head);
	head = temp;
	}

	obj = NULL;
	}

# 本地测试主函数

	int main(void)
	{

	int index = 1, val = 1;
	MyLinkedList *obj = myLinkedListCreate();

	for (int i = 0; i < 10; i++)
	{
	myLinkedListAddAtHead(obj, i);
	}

	printfList(obj);
	int param_1 = myLinkedListGet(obj, index);
	printf("The index %d value is %d\n", index, param_1);
	printf("=====================head insert============================\n");
	myLinkedListAddAtHead(obj, val);
	printfList(obj);

	printf("====================end insert=============================\n");
	val = 15;
	myLinkedListAddAtTail(obj, val);
	printfList(obj);

	printf("====================index insert=============================\n");
	val = 30;
	index = 2;
	myLinkedListAddAtIndex(obj, index, val);
	printfList(obj);

	printf("====================delete=============================\n");
	index = 1;
	myLinkedListDeleteAtIndex(obj, index);
	printfList(obj);
	myLinkedListFree(obj);

	return 0;

	}

大道五十，天衍四十九，人遁其一！

链表