为什么要使用链表？

• 我们在某些场合使用顺序表插入，删除大量元素时需要移动大量的数据，这会将整个程序的执行效率减弱，数据量大的时候无论是添加元素还是删除元素，毫无疑问是对整个数据的乾坤大挪移
• 所以有没有一种方法可以在插入和删除元素的时候不用对整个数据移动？不必再练什么乾坤大挪移，宽敞、是每个成功男人背后都应给征服的邻域，效率、是每个成功靓仔背后都应该掌握的技巧。

什么是链表？

• 链表是线性表的链性存储方式， 逻辑上相邻的数据在计算机物理存储上不必相邻。
• 不知道大家有没有见过绿皮火车，绿皮火车就相当于是一个链表，每一节车厢就像是一个结点，（什么是结点？结点就像一节火车，结点是用来表示数据的一个逻辑概念）而假如这辆绿皮火车每节车厢只有两间房，一间是乘客，一间是专门和下一节车厢链接的地方，如果没有这一间房那么就会丢失下一节车厢。
• 而链表就是像这种火车一样，一节一节的，链表的每一个结点有两个空间，一个用来存放数据即数据域，一个用来存放指针，这个指针指向的是下一个结点即指针域，就像一条铁链子把所有的结点链接在一起一环扣一环，而这条链子有一个头，即头结点，头结点是不存数据的。

链表的概念

• 每一个结点都有一个指针域和一个数据域
• 每一个结点的指针域都指向下一个结点的内存地址，最后一个结点的指针域置为NULL

链表的定义

• 使用结构体定义
• typedef struct _LinkNode {
  type data; //结点的数据域
  struct _LinkNode *next; //结点的指针域
  } LinkList, LinkNode; //链表，链表的结点

链表的初始化

typedef struct _LinkNode {
int data;
struct _LinkNode *next;
}LinkNode, LinkList;

void InitLink(LinkList* &L) {
L = new ListNode;
L->next = NULL;
}

完整代码示例

#include <iostream>
#include <string>

using namespace std;
/*
struct _LinkNode {
	int data;    //链表的数据域
	struct _LinkNode* next;  //链表的指针域
};

struct _LinkNode LinkNode, LinkList;  //链表的结点、链表

bool InitLinkList(_LinkNode* &L) {
	L = new _LinkNode; //创建一个新结点做为头结点，用L指针指向头结点

	if (!L) return false;
    
	L->next = NULL;
	return true;
}
*/

typedef struct _LinkNode {
	int data;   //链表的数据域
	struct _LinkNode* next; //链表的指针域
}LinkList, LinkNode;        //链表、链表的结点

//初始化链表
bool InitLink(LinkList* &L) {//
	L = new LinkNode;  //创建一个新结点做为头结点，用L指针指向头结点

	if (!L) return false;   //创建新结点失败

	L->next = NULL;         //头结点的指针域置为NULL
	return true;
}

int main(void) {
	//_LinkNode* L = NULL;
	//_LinkNode* s = NULL;
	LinkList* L = NULL;
	LinkNode* s = NULL;

	if (InitLink(L)) {
		cout << "初始化链表成功" << endl;
	}
	else {
		cout << "初始化链表失败" << endl;
	}

	return 0;
}

---------腾讯课堂奇牛学院-canxin