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

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

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

前言

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

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

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

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

2. 鏈表的定義

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

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

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

4. 節(jié)點的插入

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

4.1 頭插法

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

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

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

4.2 尾插法

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

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

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

4.3 插入中間節(jié)點

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

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

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;//前面位置到達了后面節(jié)點的位置
			/*posNode = posNodeFront->next;*///后面位置變成了原來位置的下一個
			if (posNode == NULL) {
				printf("未找到此數(shù)據(jù)\n");
				break;
			}
		}
		newNode->next = posNode->next;
		posNode->next = newNode;
	}
}