C++鏈表節(jié)點(diǎn)的添加和刪除介紹

更新時(shí)間：2022年01月10日 08:58:12 作者：與C決戰(zhàn)的小蘿卜頭

大家好，本篇文章主要講的是C++鏈表節(jié)點(diǎn)的添加和刪除介紹，感興趣的同學(xué)趕快來看一看吧，對你有幫助的話記得收藏一下，方便下次瀏覽

前言

鏈表是一種動(dòng)態(tài)的數(shù)據(jù)結(jié)構(gòu)，因?yàn)樵趧?chuàng)建鏈表時(shí)，不需要知道鏈表的長度，只需要對指針進(jìn)行操作。

1. 節(jié)點(diǎn)的創(chuàng)建

鏈表的節(jié)點(diǎn)包括兩部分，分別是：數(shù)據(jù)域和（指向下一個(gè)節(jié)點(diǎn)的）指針域。

struct Node {
	int data;
	struct Node* next;
};

2. 鏈表的定義

struct Node* createList() {
	//創(chuàng)建一個(gè)指針來表示表頭
	struct Node* headNode = (struct Node*)malloc(sizeof(struct Node));
	headNode->next = NULL;
	return headNode;
}

3. 創(chuàng)建節(jié)點(diǎn)

struct Node* createNode(int data) {
	//創(chuàng)建一個(gè)新的指針節(jié)點(diǎn)
	struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
	//結(jié)構(gòu)體變量初始化
	newNode->data = data;
	newNode->next = NULL;
	return newNode;
}

4. 節(jié)點(diǎn)的插入

節(jié)點(diǎn)的插入分為三種：頭插法、尾插法、在鏈表中間插入節(jié)點(diǎn)。

4.1 頭插法

頭插法，顧名思義就是在鏈表的第一個(gè)節(jié)點(diǎn)插入一個(gè)節(jié)點(diǎn)。

解決方法：讓新插入的節(jié)點(diǎn)的next指針指向鏈表的頭結(jié)點(diǎn)即可。

void insertNodeByHead(struct Node* headNode, int data) {
	struct Node* newNode = createNode(data);
	newNode->next = headNode->next;
	headNode->next = newNode;
}

4.2 尾插法

尾插法，顧名思義就是在鏈表的末尾增加一個(gè)節(jié)點(diǎn)。

解決思路：首先找到鏈表的最后一個(gè)節(jié)點(diǎn)；然后讓最后的節(jié)點(diǎn)的next指針指向要插入的這個(gè)節(jié)點(diǎn)，插入的節(jié)點(diǎn)的next指針指向NULL即可。

void insertNodeByTail(struct Node* headNode, int data) {
	struct Node* newNode = createNode(data);
	while (headNode->next != NULL)
	{
		headNode = headNode->next;//找到最后一個(gè)節(jié)點(diǎn)
	}
	headNode->next = newNode;
	newNode->next = NULL;
}

4.3 插入中間節(jié)點(diǎn)

插入中間節(jié)點(diǎn)：即在數(shù)據(jù)為 i 的節(jié)點(diǎn)后面添加新的節(jié)點(diǎn)。

解決思路：首先判斷數(shù)據(jù)為 i 的節(jié)點(diǎn)posNode是否在鏈表中存在；然后從第一個(gè)節(jié)點(diǎn)開始查找節(jié)點(diǎn)posNode。找到后就讓插入的節(jié)點(diǎn)的next指針指向posNode的下一個(gè)節(jié)點(diǎn)，posNode的next指針指向新插入的節(jié)點(diǎn)即可。

void insertNodeByCenter(struct Node* headNode, int data, int i) {
	struct Node* posNode = headNode;
	/*struct Node* posNodeFront = headNode;*/
	struct Node* newNode = createNode(data);
	if (posNode == NULL) {
		printf("無法查找此數(shù)據(jù)，鏈表為空\n");
	}
	else {
		while (posNode->data != i) {
			posNode = posNode->next;//前面位置到達(dá)了后面節(jié)點(diǎn)的位置
			/*posNode = posNodeFront->next;*///后面位置變成了原來位置的下一個(gè)
			if (posNode == NULL) {
				printf("未找到此數(shù)據(jù)\n");
				break;
			}
		}
		newNode->next = posNode->next;
		posNode->next = newNode;
	}
}