C/C++ 学习笔记：04 传统链表

传统链表

在任何一个工程中项目中，都免不了要对数据进行有组织的运算，这些组织方式，最终的目的是要让我们处理数据更加高效。
不同的数据组织方式，会有不同的特性，这些特性对于某些运算还说是非常关键的，但也可能是毫不敏感的。
因此我们的任务就是使用恰当的数据组织方式（即数据结构）来处理对某方面运算敏感的数据，让程序整体性能最大化。

链表就是一种最普遍的数据组织方式，它不需要连续 的大片内存也可以存储大量的数据，而且对于数据的插入和删除运算响应速度也够快，但查找性能一般。（“高大上”：红黑树–>算法中的贵族：哈希算法）

链表：是最普遍的数据组织方式，链表的全称是“链式存储的线性表”，换句话说，链表就是将线性相关的数据用链式存储的方式串起来的一种数据结构。
（1、线性关系：数学意义上来讲，数据有三种关系，集合、线性关系、非线性关系。而集合意思就是数据之间“没有关系”，而所谓的线性关系就是一对一，非线性关系就是一对多。2、链式存储：不管是线性还是非线性，指的都是这对数据的内在逻辑关系，不管我们怎么处置它们，它们都不以人的意志所转移的。我们能做的就是：如何在内存中选择合适的方式存放它们。这里就有两种方式：a、顺序存储，b、链式存储。怎么理解呢？把顺序存储理解为用砖头水泥砌的一排墙，这样一来，想要在中间插入或者删除就i显得很吃力了，需要移动一大片的砖头（内存），而这时链式存储就相当轻松了，我们不把砖头一个个用水泥砌上去，而是将它们分开存放，用指针把它们连接起来，使他们逻辑上保持连贯，因为链表中的节点是离散分部的，所以在设计链表节点的时候至少预留一个可以保存其他地址的指针针（即链表的节点有数据域也至少还要有一个地址域）；综上所述：链表的优点①不需要一块连续的内存②插入删除效率高③节点扩展容易。

传统的链表有：单向链表、单向循环链表、双向链表、双向循环链表；

下面详细详细来介绍单向链表的使用。一般对链表的使用无非就是初始化空链表、创建新节点、插入节点、删除节点、移动节点、查找节点、遍历节点。

1、设计节点

假设我们要处理的设计类型为datatype，我们只需要在节点中增加一个指向本节点的指针即可。

typedef struct node
{
	datatype data;
	struct node *next;
}listnode,*singly_list;

2、初始化空链表

第一种空链表直接了当，使用一个指向的空（NULL）的指针head即可。第二种使用一个指向头节点的指针。这个所谓的节点是不带有效数据的节点，在链表中插入节点是时候就不需要关注头指针head是否为空，换句话说使用第一种纯粹的空链表在插入节点的时候我们需要判断当时的头指针是否为空。一般，都是建立带头指针的空链表。

bool is_empty(singly_list list)//判断链表list是否为空
{
	return list->next == NULL;
}

singly_list init_list(void)
{
	singly_list mylist = malloc(sizeof(listnode));//创建一个节点
	if (mylist != NULL)
	{
		mylist->next = NULL;
	}
	return mylist;
}

3、插入节点

链表的最大优点就是插入删除方便，快速。对单链表而言就是修改两个指针。假设要将一个250插入到200后面，指针new和p分别指向250和200，假设函数insert（）接受new和p两个参数，实现将new插到p的后面

void insert(singly_list p, singly_list new)
{
	if (p == NULL || new == NULL)
	return;
	new->next = p->next;
	p->next = new;
}

4、删除节点

对一个链表而言，由于单链表没有指向前驱节点的指针，所以，删除一个节点时，需要另一个指针p辅助才行。（200§–>250(delete)–>300）

bool remove_node(singly_list mylist,singly_list delete)
{
	if (is_empty(mylist))
	return false;
	
	singly_list p = mylist;
	while (p != NULL && p->next != delete)//①要先找到要删除的节点的前面一个节点p
	{
		p = p->next;
	}
	if (p == NULL)
	return false;

	p->next = delete->next;//②将节点200的下一个节点指向300
	delete->next = NULL;//③将250的指针置空

	return ture；
}

5、移动节点

将一个节点从一个地方移动到另外一个地方，其实这是两个操作：先将该节点从原来的位置删除，然后将该节点插入到新的位置（想把data（p）移动到achor节点的后面）
由于之前对插入和删除都做了封装，那么移动和删除的操作如下

void move_node(singly_list mylist, singly_list p; singly_list achor)
{
	if(mylist == NULL || p == NULL || anchor == NULL)
	return;
	
	remove_node(mylist,p);//删除
	insert_node(achor,p);//插入
}

6、查找节点

由于一个指定的节点数据找到这个节点指针，也是常用的基本操作；思路：用一个指针p沿着链表头一直向下找，找到为止（或者找不到）

singly_list find_node(singly_list mylist, datatype data)
{
	if(is_empty(mylist))
	return NULL;
	
	singly_list p;
	for(p = mylist->next; p != NULL; p = p->next)
	{
		if(p->data == data)//如果找到指针的数据，则返回指针
		break;
	}
	return p;
}