数据结构单向链表和循环链表的插入

左手的ㄟ右手 2022-09-14 11:25 242阅读 0赞

为什么是圆形？ 在单向链表中，为了访问链表的任何节点，我们从第一个节点开始遍历。如果我们位于列表中间的任何节点，则无法访问给定节点之前的节点。这个问题可以通过稍微改变单链表的结构来解决。在单向链表中，下一部分（指向下一个节点的指针）为 NULL。如果我们利用这个链接指向第一个节点，那么我们就可以到达前面的节点。

在我们这篇文章中，解释了使用单向链表在循环链表中实现和插入节点。

实现  
为了实现一个循环单向链表，我们使用一个指向链表最后一个节点的外部指针。如果我们有一个指针 last 指向最后一个节点，那么 last -> next 将指向第一个节点。

指针last指向节点 Z 并且 last -> next 指向节点 P。

为什么我们采用指向最后一个节点而不是第一个节点的指针？ \*  
为了在开头插入一个节点，我们需要遍历整个链表。此外，为了在最后插入，必须遍历整个列表。如果我们使用指向最后一个节点的指针而不是开始\*指针，那么在这两种情况下都不需要遍历整个列表。因此，无论列表的长度如何，在开头或结尾插入都需要恒定的时间。

插入  
节点可以通过三种方式添加：

插入空列表  
在列表开头插入  
在列表末尾插入  
在节点之间插入  
在空列表中插入  
最初，当列表为空时，最后一个指针将为 NULL。

插入后，T是最后一个节点，所以指针last指向节点T。而节点T是第一个也是最后一个节点，所以T指向自己。  
将节点插入空列表的函数，

struct Node *addToEmpty(struct Node *last, int data)
    { 
    	if (last != NULL)
    	return last;
    
    	struct Node *temp =
    		(struct Node*)malloc(sizeof(struct Node));
    
    	temp -> data = data;
    	last = temp;
    	temp -> next = last;
    
    	return last;
    }
    复制代码

在列表的开头插入  
要在列表的开头插入一个节点，请执行以下步骤： \\

创建一个节点，例如 T。  
使 T -> next = last -> next。  
上一个 -> 下一个 = T。  
在列表的开头插入节点的函数，

struct Node *addBegin(struct Node *last, int data)
    { 
    if (last == NULL)
    	return addToEmpty(last, data);
    
    struct Node *temp
    		= (struct Node *)malloc(sizeof(struct Node));
    
    temp -> data = data;
    
    temp -> next = last -> next;
    last -> next = temp;
    
    return last;
    }
    复制代码

在列表末尾插入  
要在列表末尾插入一个节点，请执行以下步骤：

创建一个节点，例如 T。  
使 T -> next = last -> next;  
last -> next = T。  
last = T。  
在列表末尾插入节点的函数

struct Node *addEnd(struct Node *last, int data)
    { 
    if (last == NULL)
    	return addToEmpty(last, data);
    
    struct Node *temp =
    		(struct Node *)malloc(sizeof(struct Node));
    
    temp -> data = data;
    
    temp -> next = last -> next;
    last -> next = temp;
    last = temp;
    
    return last;
    }
    复制代码

在节点之间插入 要在两个节点之间插入一个节点，请执行以下步骤：

创建一个节点，例如 T。  
搜索需要在其后插入 T 的节点，例如该节点是 P。  
使 T -> next = P -> next;  
P -> next = T.  
假设需要在节点值为10后插入12，

在List末尾插入节点的函数，

struct Node *addAfter(struct Node *last, int data, int item)
    { 
    	if (last == NULL)
    	return NULL;
    
    	struct Node *temp, *p;
    	p = last -> next;
    	do
    	{ 
    		if (p ->data == item)
    		{ 
    			temp = (struct Node *)malloc(sizeof(struct Node));
    			temp -> data = data;
    			temp -> next = p -> next;
    			p -> next = temp;
    			if (p == last)
    				last = temp;
    
    			return last;
    		}
    		p = p -> next;
    	} while (p != last -> next);
    
    	cout << item << " not present in the list." << endl;
    	return last;
    }
    复制代码

下面是一个完整的程序，它使用上述所有方法来创建一个循环单向链表。

#include<bits/stdc++.h>
    using namespace std;
    
    struct Node
    { 
    	int data;
    	struct Node *next;
    };
    
    struct Node *addToEmpty(struct Node *last, int data)
    { 
    	if (last != NULL)
    	return last;
    
    	struct Node *temp =
    		(struct Node*)malloc(sizeof(struct Node));
    
    	temp -> data = data;
    	last = temp;
    
    	last -> next = last;
    
    	return last;
    }
    
    struct Node *addBegin(struct Node *last, int data)
    { 
    	if (last == NULL)
    		return addToEmpty(last, data);
    
    	struct Node *temp =
    			(struct Node *)malloc(sizeof(struct Node));
    
    	temp -> data = data;
    	temp -> next = last -> next;
    	last -> next = temp;
    
    	return last;
    }
    
    struct Node *addEnd(struct Node *last, int data)
    { 
    	if (last == NULL)
    		return addToEmpty(last, data);
    	
    	struct Node *temp =
    		(struct Node *)malloc(sizeof(struct Node));
    
    	temp -> data = data;
    	temp -> next = last -> next;
    	last -> next = temp;
    	last = temp;
    
    	return last;
    }
    
    struct Node *addAfter(struct Node *last, int data, int item)
    { 
    	if (last == NULL)
    		return NULL;
    
    	struct Node *temp, *p;
    	p = last -> next;
    	do
    	{ 
    		if (p ->data == item)
    		{ 
    			temp = (struct Node *)malloc(sizeof(struct Node));
    			temp -> data = data;
    			temp -> next = p -> next;
    			p -> next = temp;
    
    			if (p == last)
    				last = temp;
    			return last;
    		}
    		p = p -> next;
    	} while(p != last -> next);
    
    	cout << item << " not present in the list." << endl;
    	return last;
    
    }
    
    void traverse(struct Node *last)
    { 
    	struct Node *p;
    
    	if (last == NULL)
    	{ 
    		cout << "List is empty." << endl;
    		return;
    	}
    
    	p = last -> next;
    
    	do
    	{ 
    		cout << p -> data << " ";
    		p = p -> next;
    
    	}
    	while(p != last->next);
    
    }
    
    int main()
    { 
    	struct Node *last = NULL;
    
    	last = addToEmpty(last, 6);
    	last = addBegin(last, 4);
    	last = addBegin(last, 2);
    	last = addEnd(last, 8);
    	last = addEnd(last, 12);
    	last = addAfter(last, 10, 8);
    
    	traverse(last);
    
    	return 0;
    }
    复制代码

输出：

2 4 6 8 10 12
    复制代码

如果你觉得这篇文章对你有点用的话，麻烦请给我们的开源项目点点star: [http://github.crmeb.net/u/defu][http_github.crmeb.net_u_defu] 不胜感激 ！

[http_github.crmeb.net_u_defu]: http://github.crmeb.net/u/defu