单链表操作图文详解

超、凢脫俗 2023-06-23 08:57 58阅读 0赞

**链表的概念**  
相信大家都创建过数组，在创建数组的时候需要定义数组的长度，直接分配出我们需要的内存空间。而链表每次则只需分配出一个节点的内存。链表通过指针将各个节点组合到一起，就形成了一个**链式的结构**。  
单链表有两个部分：**数据部分和指针部分**。数据部分存放数据，指针部分存放指向下一个节点的指针。

链表的创建  
创建链表就需要创建一个结构体，这个结构体要有数据和指针。

typedef struct node {
        
    	int data;
    	struct node *next;
    }node, *linklist;

typedef的作用是将strcut node取一个别名：node  
在定义结构体变量时就可直接定义为

node n1;  //等同于struct node n1

而后面的\*linklist是什么意思呢？就是相当于在定义的时候直接定义为指针

linklist L;  //等同于struct node *L

**头指针、头结点的概念**  
头指针：指向第一个节点。  
头结点：数据部分不存放内容，指针部分存放头指针。  
![在这里插入图片描述][20191218140437260.png]  
**创建头结点**

void create_head(linklist *L)  //传进来的参数应该为节点的地址 &L
    {
        
    	(*L) = (linklist)malloc(sizeof(node));
    
    	(*L)->next = NULL;  //当头结点无指向时，为空链表 
    }

上面这个函数等同于

void create_head(node **L)
    {
        
    	(*L) = (linklist)malloc(sizeof(node));
    	
    	(*L)->next = NULL;  //当头结点无指向时，为空链表 
    }

这两种形式都可以实现要求，不过我建议还是用第一种方法，更易理解。

**链表的创建**

void create_linklist(linklist L, int len)
    {
        
    	linklist p1,p2;
    	p1 = L;
    	int i = 0;
    	while (i<len) {
        
    		p2 = (linklist)malloc(sizeof(node));
    		p1->next = p2;
    		p2->data = i;
    		p1 = p2;
    		i++;
    	}
    	p2->next = NULL;
    }

p1指向L，p2为一个节点指针，但没有指向任何变量。当为p2分配了一片内存之后（malloc后），p2就指向了一个节点变量。  
要将p1和p2链接起来才会成为链表，因此p1->next就要指向p2（p1->next=p2）等同于L的后继节点已经指向了一下个节点。  
![在这里插入图片描述][2019121815022694.png]  
这时p1再指向p2  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lvaGUxMg_size_16_color_FFFFFF_t_70]  
进入下一个循环，p2通过malloc又指向下一片空间，p1又将指向p2,循环上面的步骤,就将链表建立了起来。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lvaGUxMg_size_16_color_FFFFFF_t_70 1]  
当循环到长度len时，这个节点的next就为NULL。

**插入节点**  
当我们需要在链表中插入一个节点的时候，需要malloc一个节点然后将其插入相应的位置  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lvaGUxMg_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lvaGUxMg_size_16_color_FFFFFF_t_70 3]

void insert_node(linklist L, int n)
    {
        
    	linklist p1,p2;
    	p1 = L;
    	int i = 0;
    	while (i<n) {
        
    		p1 = p1->next;
    		i++;
    	}
    	p2 = (linklist)malloc(sizeof(node));
    	p2->data = 1996;  //插入想要的数据
    	p2->next = p1->next;  //将新节点的后继节点连接到原来节点的后继节点上
    	p1->next = p2;  //将原来节点的后继节点指向新的节点
    }

**输出链表**

void print_linklist(linklist L)
    {
        
    	linklist p = L;
    	while (p->next != NULL) {
        
    		printf("data is %d\n",p->next->data);  //将链表中的数据输出
    		p = p->next;
    	}
    }

**删除节点**  
![在这里插入图片描述][20191218162303590.png]  
将要删除的节点保存到q，将q的前继节点链接到q的后继节点上，再将q的内存释放掉，就删除了这个节点。

void delete_node(linklist L, int n)
    {
        
    	linklist p, q;
    	p = L;
    	int i = 0;
    	while (i<n) {
        
    		p = p->next;
    		i++;
    	}
    	q = p->next;
    	p->next = q->next;
    	free(q);
    }

**链表所有操作用C语言实现**

#include <stdio.h>
    #include <stdlib.h>
    
    typedef struct node {
        
    	int data;
    	struct node *next;
    }node, *linklist;
    
    void create_head(linklist *L);
    void create_linklist(linklist L, int len);
    void insert_node(linklist L, int n);
    void print_linklist(linklist L);
    void delete_node(linklist L, int n);
    
    
    int main(int argc, char **argv)
    {
        
    	linklist L;
    	create_head(&L);
    	create_linklist(L,8);
    	print_linklist(L);
    	insert_node(L,3);
    	print_linklist(L);
    	delete_node(L,3);
    	print_linklist(L);
    
    	
    }
    
    void create_head(linklist *L)
    {
        
    	(*L) = (linklist)malloc(sizeof(node));
    
    	(*L)->next = NULL;
    }
    
    void create_linklist(linklist L, int len)
    {
        
    	linklist p1,p2;
    	p1 = L;
    	int i = 0;
    	while (i<len) {
        
    		p2 = (linklist)malloc(sizeof(node));
    		p1->next = p2;
    		p2->data = i;
    		p1 = p2;
    		i++;
    	}
    	p2->next = NULL;
    }
    
    void insert_node(linklist L, int n)
    {
        
    	linklist p1,p2;
    	p1 = L;
    	int i = 0;
    	while (i<n) {
        
    		p1 = p1->next;
    		i++;
    	}
    	p2 = (linklist)malloc(sizeof(node));
    	p2->data = 1996;
    	p2->next = p1->next;
    	p1->next = p2;
    }
    
    void print_linklist(linklist L)
    {
        
    	linklist p = L;
    	while (p->next != NULL) {
        
    		printf("data is %d\n",p->next->data);
    		p = p->next;
    	}
    }
    
    void delete_node(linklist L, int n)
    {
        
    	linklist p, q;
    	p = L;
    	int i = 0;
    	while (i<n) {
        
    		p = p->next;
    		i++;
    	}
    	q = p->next;
    	p->next = q->next;
    	free(q);
    }

[20191218140437260.png]: https://img-blog.csdnimg.cn/20191218140437260.png
[2019121815022694.png]: https://img-blog.csdnimg.cn/2019121815022694.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lvaGUxMg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191218150419470.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lvaGUxMg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lvaGUxMg_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20191218150859959.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lvaGUxMg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lvaGUxMg_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/2019121815565927.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lvaGUxMg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lvaGUxMg_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20191218155716614.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lvaGUxMg==,size_16,color_FFFFFF,t_70
[20191218162303590.png]: https://img-blog.csdnimg.cn/20191218162303590.png