定义

线性表的链式存储方式称为单链表，它是指通过一组任意的存储单元来存储线性表中的数据元素。

为了实现数据元素之间的线性关系，所以每个结点中除了存储自身的值以外，还会存放一个指向后继的指针。

具体的代码如下：

typedef struct LNode{
	int data;//结点的数据
	LNode* Next;//指向下一结点的指针
}LNode,*LinkList;//前者为结点，后者为链表(只是两种不同表述方式)

操作

在单链表的具体实现中，有两种实现方式，一种是带头结点的单链表，一种是不带头结点的单链表。

两者的共同点在于，都有一个头指针用于指向链表的第一个结点。

两者的区别在于，带头结点的单链表会有一个头结点，这个头结点的Next指针指向单链表的第一个结点，所以头指针是指向头结点的；而不带头结点的单链表则是由头指针直接指向第一个结点。

因为带头结点的单链表在代码实现的时候更加简便，所以本文以带头结点的形式来实现单链表各种操作。

初始化

bool InitList(LinkList& L)
{
	L = (LNode*)malloc(sizeof(LNode));//创建头结点
	if (L == NULL)
	{
		cout << "内存不足分配失败!" << endl;
		return false;
	}
	else
	{
		L->next = NULL;//初始化的链表中没有结点，所以指向NULL
		return true;
	}
}

在初始化时，要注意使用malloc函数的判空，因为使用malloc时可能会出现失败的情况，加入判空可以增加代码的健壮性。

结点前插

给定链表的一个结点，实现在此结点的前面插入一个结点，有两种实现方式。

第一，从头开始找到该结点的前驱结点实现插入(这种实现方式需要我们知道头指针，并且时间复杂度为O(n))

第二，原地前插

bool InsertPriorNode(LNode* p, int e) {//在p结点前面插入元素e
	if (p == NULL) {//判断p结点是否为空，如果为空是不能前插的
		return false;
	}
	LNode* L = (LNode*)malloc(sizeof(LNode));
	if (L == NULL) {
		cout << "内存分配失败" << endl;
		return false;
	}
	else {
		L->next = p->next;//新结点连入
		p->next = L;//前链连接上新结点
		L->data = p->data;//数据交换，实现前插
		p->data = e;
		return true;
	}
}

在这种前插方式下，时间复杂度为O(1)，而且不需要知道头指针

如果给定的是需要前插的不是值，而是结点，具体的实现代码如下：

bool InsertPriorNode(LNode* p, LNode *s) {//在p结点前面插入结点s
	if ((p == NULL)||(s == NULL)) {
		return false;
	}
	else {
		s->next = p->next;//同样采用后插方式
		p->next = s;
		int temp;//具体实现时的数据类型可能并不是int，灵活变换即可
		temp = s->data;//交换数据实现前插
		s->data = p->data;
		p->data = temp;
		return true;
	}
}

后插

给定链表的一个结点，实现在此结点的后面插入一个节点，实现方式与前插类似，甚至更简单直观。

bool InsertNextNode(LNode* p, int e) {//在p结点之后插入元素e
	if (p == NULL) {
		return false;
	}
	LNode* L = (LNode*)malloc(sizeof(LNode));
	if (L == NULL) {
		cout << "内存分配失败" << endl;
		return false;
	}
	else {
		L->next = p->next;
		p->next = L;
		L->data = e;
		return true;
	}
}

如果给定的是需要后插的不是值，而是结点，具体的实现代码如下：

bool InsertNextNode(LNode* p, LNode* s) {//在p结点之后插入结点s
	if ((p == NULL)||(s==NULL)) {
		return false;
	}
	else {
		s->next = p->next;
		p->next = s;
		return true;
	}
}

查找

在线性表的查找中，有两种查找方式。

一种是按值查找，一种是按位查找

因为是链式实现的线性表，所以这两种方式都需要遍历这个链表来查找，所以一般来说时间复杂度为O(n)

按值查找代码如下

LNode* LocateElem(LinkList L, int e) {
	if (L == NULL) {
		cout << "传入链表为空，查找失败!" << endl;
		return NULL;	
	}
	else {
		LNode* p;
		p = L->next;//因为带头结点，所以会指向头结点的下一个结点
		while ((p != NULL) && (p->data != e)) {
			p = p->next;
		}
		return p;
	}
}

按位查找代码如下

LNode* GetElem(LinkList L, int i) {
	int j = 1;//标记当前p指向第几个结点
	LNode* p=L->next;
	if (i == 0) {
		return L;
	}
	if (i < 1) {
		return NULL;
	}
	while ((p!=NULL)&&(j<i)) {
		p = p->next;
		j++;
	}
	return p;
}

建立单链表

建立单链表可以采用两种方式，一种是头插法，一种是尾插法

头插法是每次输入的都从头部插入，尾插法是每次输入都从尾部插入

采用头插法可以用上面已经封装好的插入函数来实现

头插法

LinkList List_HeadInsert(LinkList& L) {
	int a = 0;
	while (true) {
		cout << "请输入元素值：";
		cin >> a;
		if (a != 9999) {
			InsertNextNode(L, a);
		}
		else {
			break;
		}
	}
	return L;
}

尾插法

每次都要找到最后元素

LinkList List_TailInsert(LinkList& L) {
	int a;
	LNode* p=L;
	while (p->next != NULL) {
		p = p->next;//找到最后元素
	}
	while (true) {
		cout << "请输入要插入的元素的值:";
		cin >> a;
		if (a != 9999) {
			LNode* s = (LNode*)malloc(sizeof(LNode));//创建新结点
			s->data = a;//新结点的元素值为输入的a
			p->next = s;//将新节点连上链表
			s->next = NULL;//新的末尾要指NULL，防止出错
			p = p->next;//p始终指向最后一个结点
		}
		else {
			break;
		}
	}
	return L;
}

删除

删除结点有两种方式，一种需要知道头指针，一种只需要知道当前结点的指针即可

需要知道头指针的删除

bool ListDelete(LinkList& L, int i, int& e)
{
	LNode* p;
	p=GetElem(L, i-1);//p指向要删除的前一个位置
	if (p == NULL) {
		//说明前一个结点都不存在，那么无法删除
		return false;
	}
	else if (p->next == NULL) {
		//说明输入要删除的结点本身就不存在，不需要删除,直接成功
		return true;
	}
	else {
		LNode* q = p->next;//q指向要删除的结点
		e = q->data;//返回删除的值
		p->next = q->next;//链接断开
		free(q);//释放无用指针
		return true;
	}
}

不需要头指针的删除

bool ListDelete(LNode* p, int& e) {
	if (p == NULL) {
		//说明这个结点本身就不存在
		return false;
	}
	else if (p->next == NULL) {
		//说明这个结点后面是没有结点的，那么这种删除只能通过从头结点查找上一个结点来删除，所以会失败
		return false;
	}
	else {
		e = p->data;//返回删除的值
		LNode* s = p->next;
		p->data = s->data;
		p->next = s->next;
		free(s);
		return true;
	}
}

求表长

求表长比较简单，一个while循环遍历以下就行，时间复杂度为O(n)

int GetListLength(LinkList L) {
	int length = 0;
	LNode* p = L;
	if (p == NULL) {
		//说明头结点的不存在，表还未创建
		cout << "表还未创建!" << endl;
		return -1;
	}
	else if (p->next == NULL) {
		//说明表创建了，但是没有元素，那么长度为0
		return 0;
	}
	else {
		while (p->next != NULL) {
			length++;
			p = p->next;
		}
		return length;
	}
}

总结

单链表的具体实现还是比较简单的，主要是要弄清楚指针的指向，以及各种操作细节之处的先后顺序，如果顺序不当可能会导致最后结果的错误。

以上是复习数据结构带头结点的单链表时做的一些笔记，难免有遗漏与错误之处，请不吝予以指正。