数据结构-单链表的读取，插入与删除

我会带着你远行 2022-06-11 06:37 188阅读 0赞

链表定义：

struct ListNode
    {
        
      int value;
      ListNode *next;
    };

## 单链表读取 ##

在顺序存储结构中，比如数组中，想要获取某一个位置的数据是非常容易的一件事，但是在链表中却要麻烦一些，因为链表的存储单元并不是连续的，而且我们只知道链表的头结点，也就是想知道第i个位置的数据，只能从头找下去，并没有什么其他的好方法。  
需要注意的是，如果i大于链表的长度的话程序会异常，所以需要加上判断。

#include<iostream>
    using namespace std;
    
    struct ListNode
    {
        
    int value;
    ListNode *next;
    };
    
    ListNode* GetElem(ListNode * L,int i);
    void CreateList(ListNode * L,int n);
    int main()
    {
        
    	ListNode * L = new ListNode;
    	L->next = nullptr;
    	CreateList(L,5);
    	ListNode* elem = GetElem(L,3);
    	if (elem==nullptr)
    	{
        
    	 cout<<"error"<<endl;
    	} 
    	else
    	{
        
    	 cout<<elem->value<<endl;
    	}
    	getchar();
    	getchar();
    	return 0;
    }
    void CreateList(ListNode * L,int n)
    {
        
    	cin>>L->value;//输入第一个结点的数据值
    	n--;
    	for (int i = 0; i < n; i++)
    	{
        
    		ListNode * p = new ListNode;
    		cin>>p->value;
    		p->next = nullptr;
    		L->next = p;
    		L = p;
    	}
    }
    ListNode* GetElem(ListNode * L,int i)
    {
        
    	int j = 1;
    	ListNode *p=L;
    	while (p && j<i)
    	{
        
    		p = p->next;
    		j++;
    	}
    	if (!p || j>i)
    	{
        
    		return nullptr;
    	}
    	return p;
    }

在上面的代码中，传入GetElem函数的是链表的头结点，这个代码和《大话数据结构》这本书里面的例程有些不同，如果有人也碰巧看那本书的话，可以留意一下。

## 单链表插入 ##

相比于顺序存储结构，链表的读取确实麻烦了些，但是好在插入和删除方便。比如要在链表的第三个结点之后插入一个结点。  
![这里写图片描述][format_png]  
这里的1-6只是结点里面存的数据，不决定结点的顺序。  
（1）找到链表中第三个结点p  
（2）创建一个新的结点q `ListNode *q=(ListNode*)malloc(sizeof(ListNode));q->value=4;`  
（3）q先与原链表第四个结点链接`q->next = p->next;`  
（4）原链表第三个结点与q链接`p->next = q;`  
（3和4的顺序不能对调，所以图示就是这样）  
![这里写图片描述][format_png 1]  
我们假设一下，如果3，4对调了，也就是说先让第三个结点指向q，因为我们是可以在原链表上找到第三个结点的，但是一旦指向发生了变化，原链表断了，原链表的第四个结点就已经找不到了。但是不对调的话，在原链表没有断开之前就把q与第四个结点连起来了，又由于本来我们就找到了原链表的第三个结点，所以即便断开了，那又能怎么样呢？？

#include<iostream>
    using namespace std;
    
    struct ListNode
    {
        
    int value;
    ListNode *next;
    };
    void showList(ListNode * L);
    ListNode* ListInsert(ListNode * L,int i);
    void CreateList(ListNode * L,int n);
    int main()
    {
        
    	ListNode * L = new ListNode;
    	L->next = nullptr;
    	CreateList(L,5);
    	ListNode* Head = ListInsert(L,3);
    	showList(Head);
    	getchar();
    	getchar();
    	return 0;
    }
    void CreateList(ListNode * L,int n)
    {
        
    	cin>>L->value;//输入第一个结点的数据值
    	n--;
    	for (int i = 0; i < n; i++)
    	{
        
    		ListNode * p = new ListNode;
    		cin>>p->value;
    		p->next = nullptr;
    		L->next = p;
    		L = p;
    	}
    }
    ListNode* ListInsert(ListNode * L,int i)
    {
        
    	int j=1;
    	ListNode *p=L;
    	while (p && j<i)
    	{
        
    		p = p->next;
    		j++;
    	}
    	if (!p || j>i)
    	{
        
    		return nullptr;
    	}
    	
    	ListNode *q=(ListNode*)malloc(sizeof(ListNode));
    	
    	q->value=4;
    	//3
    	q->next = p->next;
    	//4
    	p->next = q; 
    
    	return L;
    }
    void showList(ListNode * L)
    {
        
    	ListNode * p = L;
    	while (p)
    	{
        
    		cout<<p->value<<' ';
    		p = p->next;
    	}
    	cout<<endl;
    }

![这里写图片描述][format_png 2]

## 单链表删除 ##

要删除一个链表中第三个结点后面的结点，逻辑与插入操作很类似，同样要考虑原链表断开后的情况：  
![这里写图片描述][format_png 3]  
步骤是这样：  
（1）找到第三个结点p  
（2）找到p后面的结点q（在图中是第四个）`q= p->next;`  
（3）将p指向q后面的结点（在图中是第五个）`p->next = q->next;`  
（4）释放q`free(q);`  
![这里写图片描述][format_png 4]

#include<iostream>
    using namespace std;
    
    struct ListNode
    {
        
    int value;
    ListNode *next;
    };
    void showList(ListNode * L);
    ListNode* ListDelete(ListNode * L,int i);
    void CreateList(ListNode * L,int n);
    int main()
    {
        
    	ListNode * L = new ListNode;
    	L->next = nullptr;
    	CreateList(L,5);
    	ListNode* Head = ListDelete(L,3);
    	showList(Head);
    	getchar();
    	getchar();
    	return 0;
    }
    void CreateList(ListNode * L,int n)
    {
        
    	cin>>L->value;//输入第一个结点的数据值
    	n--;
    	for (int i = 0; i < n; i++)
    	{
        
    		ListNode * p = new ListNode;
    		cin>>p->value;
    		p->next = nullptr;
    		L->next = p;
    		L = p;
    	}
    }
    ListNode* ListDelete(ListNode * L,int i)
    {
        
    	int j  = 1;
    	ListNode *p=L;
    	while (p && j<i)
    	{
        
    		p = p->next;
    		j++;
    	}
    	if (!p || j>i)
    	{
        
    		return nullptr;
    	}
    	//3
    	ListNode *q= p->next;
    	//4
    	p->next = q->next; 
    	free(q);
    	return L;
    }
    void showList(ListNode * L)
    {
        
    	ListNode * p = L;
    	while (p)
    	{
        
    		cout<<p->value<<' ';
    		p = p->next;
    	}
    	cout<<endl;
    }

![这里写图片描述][format_png 5]

[format_png]: /images/20220611/3f511a1303734a779d6a08009610ba90.png
[format_png 1]: /images/20220611/a6769893041841b78c016461ffea71fb.png
[format_png 2]: /images/20220611/b4d4137973f94bb0adb5b4232c0f7f81.png
[format_png 3]: /images/20220611/68f138f5acc6437498045d2d30850ef8.png
[format_png 4]: /images/20220611/6cc9b6fe310c42278aa535dcff820daf.png
[format_png 5]: /images/20220611/03ad6c5a7e9a40529d831e6ed3468024.png