链表_链表层 - CSDN
链表 订阅
链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构,操作复杂。由于不必须按顺序存储,链表在插入的时候可以达到O(1)的复杂度,比另一种线性表顺序表快得多,但是查找一个节点或者访问特定编号的节点则需要O(n)的时间,而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。使用链表结构可以克服数组链表需要预先知道数据大小的缺点,链表结构可以充分利用计算机内存空间,实现灵活的内存动态管理。但是链表失去了数组随机读取的优点,同时链表由于增加了结点的指针域,空间开销比较大。链表最明显的好处就是,常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序,数据的存取往往要在不同的排列顺序中转换。链表允许插入和移除表上任意位置上的节点,但是不允许随机存取。链表有很多种不同的类型:单向链表,双向链表以及循环链表。链表可以在多种编程语言中实现。像Lisp和Scheme这样的语言的内建数据类型中就包含了链表的存取和操作。程序语言或面向对象语言,如C,C++和Java依靠易变工具来生成链表。 展开全文
链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构,操作复杂。由于不必须按顺序存储,链表在插入的时候可以达到O(1)的复杂度,比另一种线性表顺序表快得多,但是查找一个节点或者访问特定编号的节点则需要O(n)的时间,而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。使用链表结构可以克服数组链表需要预先知道数据大小的缺点,链表结构可以充分利用计算机内存空间,实现灵活的内存动态管理。但是链表失去了数组随机读取的优点,同时链表由于增加了结点的指针域,空间开销比较大。链表最明显的好处就是,常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序,数据的存取往往要在不同的排列顺序中转换。链表允许插入和移除表上任意位置上的节点,但是不允许随机存取。链表有很多种不同的类型:单向链表,双向链表以及循环链表。链表可以在多种编程语言中实现。像Lisp和Scheme这样的语言的内建数据类型中就包含了链表的存取和操作。程序语言或面向对象语言,如C,C++和Java依靠易变工具来生成链表。
信息
构    成
一系列结点组成
分    类
计算机数据结构
中文名
链表
外文名
linked list
链表特点
线性表的链式存储表示的特点是用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的)。因此,为了表示每个数据元素 与其直接后继数据元素 之间的逻辑关系,对数据元素 来说,除了存储其本身的信息之外,还需存储一个指示其直接后继的信息(即直接后继的存储位置)。由这两部分信息组成一个"结点"(如概述旁的图所示),表示线性表中一个数据元素。线性表的链式存储表示,有一个缺点就是要找一个数,必须要从头开始找起,十分麻烦。根据情况,也可以自己设计链表的其它扩展。但是一般不会在边上附加数据,因为链表的点和边基本上是一一对应的(除了第一个或者最后一个节点,但是也不会产生特殊情况)。不过有一个特例是如果链表支持在链表的一段中把前和后指针反向,反向标记加在边上可能会更方便。对于非线性的链表,可以参见相关的其他数据结构,例如树、图。另外有一种基于多个线性链表的数据结构:跳表,插入、删除和查找等基本操作的速度可以达到O(nlogn),和平衡二叉树一样。其中存储数据元素信息的域称作数据域(设域名为data),存储直接后继存储位置的域称为指针域(设域名为next)。指针域中存储的信息又称做指针或链。由分别表示,,…,的N 个结点依次相链构成的链表,称为线性表的链式存储表示,由于此类链表的每个结点中只包含一个指针域,故又称单链表或线性链表。
收起全文
  • 发送"链表"即可获取。 为什么要学习链表链表主要有以下几大特性: 1、解决数组无法存储多种数据类型的问题。 2、解决数组中,元素个数无法改变的限制(C99的变长数组,C++也有变长数组可以实现)。 3、数组...

    完整源码获取:
    微信关注:嵌入式云IOT技术圈
    发送"链表"即可获取。watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly95YW5neXVhbnhpbi5ibG9nLmNzZG4ubmV0,size_16,color_FFFFFF,t_70

    为什么要学习链表?

    链表主要有以下几大特性:

    1、解决数组无法存储多种数据类型的问题。

    2、解决数组中,元素个数无法改变的限制(C99的变长数组,C++也有变长数组可以实现)。

    3、数组移动元素的过程中,要对元素进行大范围的移动,很耗时间,效率也不高。

    先来感性的认识一下链表,我们先来认识下简单的链表:

    从这幅图我们得出以下信息:

    这个简单链表的构成:

    头指针(Header),若干个节点(节点包括了数据域和指针域),最后一个节点要指向空。

    实现原理:头指针指向链表的第一个节点,然后第一个节点中的指针指向下一个节点,然后依次指到最后一个节点,这样就构成了一条链表。

    接下来看看链表的数据结构:

    struct  list_node
    {
    	int data ; //数据域,用于存储数据
    	struct list_node *next ; //指针,可以用来访问节点数据,也可以遍历,指向下一个节点
    };
    

    那么如何来创建一个链表的一个节点呢?

    我们写个程序演示一下:

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    struct  list_node
    {
    	int data ; 
    	struct list_node *next ;
    };
    
    typedef struct list_node list_single ; 	
    
    int main(void)
    {
    	list_single *node = NULL ;          //1、首先,当然是定义一个头指针
    	node = (list_single *)malloc(sizeof(list_single)); //2、然后分配内存空间
    	if(node == NULL){
    		printf("malloc fair!\n");
    	}
    	memset(node,0,sizeof(list_single)); //3、清一下
    	node->data = 100 ;		    		//4、给链表节点的数据赋值
    	node->next = NULL ;                 //5、将链表的指针域指向空
    	printf("%d\n",node->data);
    	free(node);
    	return 0 ;
    }

    那么,这仅仅只是创建一个链表中的一个节点,为了好看,我们把创建节点封装成函数,以后想创建多少个节点,我们就可以反复调用一个函数来创建,会很方便:

    list_single *create_list_node(int data)
    {
    	list_single *node = NULL ;
    	node = (list_single *)malloc(sizeof(list_single));
    	if(node == NULL){
    		printf("malloc fair!\n");
    	}
    	memset(node,0,sizeof(list_single));
    	node->data = 100 ;
    	node->next = NULL ;
    	return node ;
    }

    接下来在程序上完成的程序:

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    struct  list_node
    {
    	int data ; 
    	struct list_node *next ;
    };
    
    typedef struct list_node list_single ; 	
    list_single *create_list_node(int data)
    {
    	list_single *node = NULL ;
    	node = (list_single *)malloc(sizeof(list_single));
    	if(node == NULL){
    		printf("malloc fair!\n");
    	}
    	memset(node,0,sizeof(list_single));
    	node->data = data;
    	node->next = NULL ;
    	return node ;
    }
    int main(void)
    {
    	int data = 100 ;
    	list_single *node_ptr = create_list_node(data); //创建一个节点
    	printf("node_ptr->data=%d\n",node_ptr->data);   //打印节点里的数据
    	printf("node_ptr->next=%d\n",node_ptr->next);  
    	free(node_ptr);
    	return 0 ;
    }

    执行结果 :



    这样我们就完成一个链表节点的创建了,那么它现在的样子如下图:

    链表的结构里,数据存储了100,因为这个链表只有一个节点,所以它的指针域指向了NULL。

       上面只是建立一个单链表的基本雏形,接下来咱们再来增加一点难度。如果创建多个单链表节点,实现单链表的增删改查?把单链表应用起来。

    1、首先定义一个单链表的数据结构

    创建节点函数原型可定义如下:
    struct list *create_node(int data) ;
    如何创建单链表的节点,主要分以下步骤:
    (1)给当前的每个节点的数据结构配置定量的空间大小
       ep : struct list *node = malloc(sizeof(struct list));
    (2)清节点数据(由于结构体变量在未初始化的时候,数据是脏的)
       ep : memset(node,0,sizeof(struct list));
    (3)给节点初始化数据
       ep : node->id = data ; 
    (4)将该节点的指针域设置为NULL
       ep : node->next = NULL ;

    2、单链表的尾插:

    尾插节点函数原型可定义如下:

    如何将当前链表和新的节点相连接?只要实现:
    header->next = new 
    尾插流程如下:

    (1)获取当前节点的位置,也就是访问头节点
       ep : struct list *p = header ;
    (2)判断是否为最后一个节点,如果不是,移动到下一个节点,如果是,将数据插入尾部。
       ep : while(NULL != p->next) p = p->next ;
            p->next = new ;

    3、单链表的头插

    很好理解,头插就是把新的节点插在原来的节点和原来节点的下一个节点之间的一个节点。如图,新的节点插在头节点和节点1。
    所以可以推出头插流程如下:
    (1)获取当前节点的位置,也就是访问头节点
        ep : struct list *p = header ;
    (2)新的节点的下一个节点设置为原来头节点的下一个节点(第一个节点)
        ep : new->next = p->next ;
    (3)原来的头节点的下一个节点设置为现在新插入的头节点
        ep : p->next = new ;

    4、单链表的遍历

    如图为一条单向链表的模型,看图知道该链表由头节点和若干个节点组成,最后一个节点(尾节点)为NULL 。
    从图中可以得出信息,如果我们要打印出各个节点的数据,要考虑以下问题:
    (1)需要打印头节点吗?(头节点肯定是不用打印的,因为这是我们为了操作方便而设置的一个节点)。
    (2)这条链表有多少个节点我们怎么知道?(通过判断该链表是否已经到达了尾节点,标志就是NULL)
    那么可以得到流程如下:
    (1)获取当前节点的位置,也就是访问头节点
        ep : struct list *p = header ;
    (2)由于头节点我们不需要去打印它,这时候,初始化打印的节点需要从第一个节点开始。
        ep : p = p->next ;  
    (3)判断是否为最后一个节点,如果不是,先打印第一个节点的数据(1),然后移动到下一个节点(2),重复这两个步骤。
       如果是最后一个节点,直接打印数据即可。
        while(NULL != p->next){ printf("node:%d\n",p->data) ; p = p->next ;}
        printf("node:%d\n",p->data);
        当然还可以一句代码解决,这样就达到了先偏移,后取数据。
        while(NULL != p->next){ p = p->next ; printf("node:%d\n",p->data) ; }
     

    5、单链表的删除

    删除节点的函数原型可定义如下:
    int detele_list_node(struct list *pH , int data);
    单向链表的删除要考虑两种情况,一种的普通节点的删除(当然,头节点不能算)
    还有一种是尾节点的前一个节点的删除情况,注意,删除完节点还需要释放对应节点的内存空间。

    删除节点的设计流程:
    (1)先定义两个指针,一个表示当前的节点,另一个表示当前节点的上一个节点。
        ep : struct list *p = header ;  //当前节点
             struct list *prev = NULL ; //当前节点的上一个节点
    (2)遍历整个链表,同时保存当前节点的前一个节点
        ep : while(NULL != p->next)
            { 
              //保存了当前的节点的前一个节点
              prev = p ;  
              //保存当前偏移的节点
              p = p->next ; 
              return 0 ;
            }
    (3)在遍历的过程中查找要删除的数据
        ep : while(NULL != p->next)
            { 
              //保存了当前的节点的前一个节点
              prev = p ;  
              //保存当前偏移的节点
              p = p->next ; 
              //查找到了数据
              if(p->id == data)
              {
              
              }
              return 0 ;
            }
    (4)查找到了数据后,分两种情况删除
        ep : 普通节点的删除
            if(p->id == data)
            {
                prev->next = p->next ;
                free(p);
            }
        ep : 考虑尾节点的下一个节点为NULL的节点删除
            if(p->id == data)
            {
                if(p->next == NULL)
                {
                    prev->next = NULL ;
                    free(p);
                }
            }

    6、单链表的逆序

    逆序步骤:

    单链表的基本操作流程咱们基本搞懂了,下面写一个程序,这将会变得非常非常的简单。

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    typedef struct slist
    {
    	int id ;
    	struct slist *next ;			
    }L;
     
    //创建一个节点 
    L *create_node(int data)
    {
    	//给每个节点分配结构体一样的空间大小 
    	L *p = malloc(sizeof(L));
    	if(NULL == p)
    	{
    		printf("malloc error!\n");
    		return NULL ;
    	}
    	//由于结构体在未初始化的时候一样是脏数据,所以要清 
    	memset(p,0,sizeof(L));
    	//初始化第一个节点 
    	p->id = data ; 
    	//将节点的后继指针设置为NULL 
    	p->next = NULL ;
    }
     
    //链表的尾插 
    void tail_insert(L *pH , L *new)
    {
    	//获取当前的位置 
    	L *p = pH ; 
    	//如果当前位置的下一个节点不为空 
    	while(NULL != p->next)
    	{
    		//移动到下一个节点 
    		p = p->next ;
    	}
    	//如果跳出以上循环,所以已经到了NULL的这个位置
    	//此时直接把新插入的节点赋值给NULL这个位置 
    	p->next = new ;
    }
     
    //链表的头插 
    void top_insert(L *pH , L *new)
    {
    	L *p = pH ;
    	new->next = p->next ;
    	p->next = new ;
    }
     
    //链表的遍历 
    void Print_node(L *pH)
    {
    	//获取当前的位置 
    	L *p = pH ;
    	//获取第一个节点的位置 
    	p = p->next ;
    	//如果当前位置的下一个节点不为空 
    	while(NULL != p->next)
    	{
    		//(1)打印节点的数据 
    		printf("id:%d\n",p->id);
    		//(2)移动到下一个节点,如果条件仍为真,则重复(1),再(2) 
    		p = p->next ;
    	}
    	//如果当前位置的下一个节点为空,则打印数据
    	//说明只有一个节点 
    	printf("id:%d\n",p->id);
    }
     
    //删除链表中的节点 
    int detele_list_node(L * pH , int data)
    {
    	//获取当前头节点的位置 
    	L *p = pH ;
    	L *prev = NULL;
    	while(NULL != p->next)
    	{
    		//保存当前节点的前一个节点的指针 
    		prev = p ;
    		//然后让当前的指针继续往后移动 
    		p = p->next ; 	
    		//判断,找到了要删除的数据  
    		if(p->id == data)
    		{
    			//两种情况,一种是普通节点,还有一种是尾节点
    			if(p->next != NULL)  //普通节点的情况 
    			{
    				prev->next = p->next ;
    				free(p);
    			}
    			else //尾节点的情况 
    			{
    				prev->next = NULL ; //将这个尾节点的上一个节点的指针域指向空 
    				free(p); 
    			}
    			return 0  ;
    		}
    	}
    	printf("没有要删除的节点\n");
    	return -1 ;
    }
     
    void trave_list(L * pH)
    {
    	//保存第一个节点的位置 
    	L *p = pH->next;
    	L *pBack;
    	int i = 0 ;
    	if(p->next == NULL || p == NULL)
    		return ;
    		
    	while(NULL != p->next) //遍历链表 
    	{
    		//保存第一个节点的下一个节点 
    		pBack = p->next ; 
    		//找到第一个有效节点,其实就是头指针的下一个节点 
    		if(p == pH->next) 
    		{
    			//第一个有效节点就是最后一个节点,所以要指向NULL 
    			p->next = NULL ; 
    		} 
    		else
    		{
    			/*
    			new->next = p->next ;
    			p->next = new ;
    			*/
    			p->next = pH->next ; //尾部连接 
    		}
    		pH->next = p ; //头部连接 
    		p = pBack ; //走下一个节点 
    	}
    	top_insert(pH,p); //插入最后一个节点 
    }
     
    int main(int argc , char **argv) 
    {
    	//创建第一个节点 
    	int i ;
    	L *header = create_node(0); 
    	for(i = 1 ; i < 10 ; i++)
    	{
    		tail_insert(header,create_node(i));
    	}
    	Print_node(header);
    	detele_list_node(header,5);
    	putchar('\n');
    	Print_node(header);
    	putchar('\n');
    	trave_list(header);
    	Print_node(header);
    	return 0 ;
    }
    

    运行结果:

    当然,单链表存在一定的弊端,就是查找数据和删除数据的时候比较麻烦,而双链表的出现就是为了解决它的弊端:

    双链表的引入是为了解决单链表的不足:
    (1)双链表可以往前遍历,也可以往后遍历,具有两个方向
    双链表的节点 = 有效数据 + 两个指针(分别指向前一个节点和后一个节点)
    双向链表的图形结构描述:

    struct double_list                                   struct double_list
    {                                                            {
        数据域;                  ep :------->                   int data ;
        指针域(前向指针) ;                                   struct double_list *prev ;
        指针域(后向指针) ;                                   struct double_list *next ;
    };                                                             };
     

    1、双向链表的创建

    struct list *create_node(int data) ;
    创建步骤(与单链表类似,就是多了一个指针):
    (1)给节点申请空间:
       ep : struct double_list *p = malloc(sizeof(struct double_list));
    (2)初始化数据域
       ep : p->data = data ;
    (3)初始化指针域
       ep : p->prev = NULL ; 
            p->next = NULL ;

    2、双向链表的尾插

    双向链表尾插节点的函数可以定义如下:
    void double_list_tail_insert(struct double_list *header , struct double_list *new) ;
    尾插图示操作:

    尾插的步骤:


    (1)找到链表的尾节点
       ep : 和单链表差不多
            DL *p = header ;
            while(NULL != p->next)
                p = p->next ;
    (2)将新的节点连接到尾节点的后面成为新的节点
       1.原来的next指针指向新节点的首地址。            p->next = new ;
       2.新节点的prev指针指向原来的尾节点的首地址。 new->prev = p;
     

    3、双向链表的头插

    双向链表头插节点的函数可以定义如下:
    void double_list_top_insert(struct double_list *header , struct double_list *new) ;

    4、双向链表的遍历

    4.1 正向遍历
        void double_list_for_each(DL *header)
        步骤:和单链表完全一致,没什么好写的。
        
        
    4.2 反向遍历
        void double_list_for_each_nx(DL *header)
        步骤:(1)和单链表一样,先循环找到最后一个节点的地址
              (2)再依靠prev指针循环往前移动
                 2.1 先打印最后一个数据  ep : printf("%d ",p->data);
                 2.2 向前循环遍历         ep : p = p->prev ;
                 
                 判断条件:header->prev != p->prev,
                 header保存的是头节点的地址,
                 header->prev保存的是头节点的prev的地址,
                 header->next保存的是头节点的next的地址,
                 头节点在创建的时候:
                 header->prev = NULL ;
                 header->next = NULL ;
                 所以这个条件这样写header->prev = NULL也是对的。

    5、双向链表节点的删除


    假设需要删除节点1:    
        首先:
        (1)获取当前节点的地址: 
            ep : p = header;
        (2)遍历所有的节点,找到要删除的节点:
            ep : 
            while(NULL != p->next)
            {
                p = p->next ;
                if(p->data == data)
                {
                
                }
            }
        (3)找到要删除的数据以后,需要做判断,判断两种情况,这和单链表差不多
        3.1 如果找到当前节点的下一个节点不为空
        3.1.1    
            那就把当前节点的prev节点指向要删除的这个节点的prev
            因为当前的prev节点保存的是要删除的上一个节点的指针 
            p->next->prev = p->prev ;
        3.1.2    
            然后将当前节点的prev指针(也就是上一个节点的指针)指向当前节点(要删除的)的下一个节点:
            p->prev->next = p->next ;
        3.1.3    
            最后释放删除指针的空间:
            free(p);
            
        3.2 如果找到当前节点的下一个节点为空
        3.2.1   
        直接把当前指针(要删除的节点)的prev指针(保存着当前指针的上一个节点的地址)的下一个next指针设置为空。
        p->prev->next = NULL ;
        3.2.2
        将删除的指针的空间释放:
        free(p);
        看来,双链表学起来比单链表容易多了!确实啊,多了一个方向,操作起来就更加容易了,但是多了一个方向,一维多了一个指针,相比增加了一定的复杂度,但是,只要牢记prev指针和next指针的指向,那么,手画一图,代码即可写出!
    下面给一个案例实现一下双向链表:
     

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    //创建一个双链表的数据结构
    typedef struct __double_list
    {
    	int data ;
    	struct __double_list *prev ;
    	struct __double_list *next ;
    }DL ; 
     
    //创建双向链表并插入一个节点 
    DL *create_dl_node(int data)
    {
    	DL *p = malloc(sizeof(DL));
    	if(NULL == p)
    	{
    		printf("create dl node fair!\n");
    		return NULL ;
    	}
    	//初始化数据 
    	p->data = data ;
    	//初始化指针 
    	p->next = NULL ;
    	p->prev = NULL ;
    }
     
    //双向链表的尾插 
    void double_list_tail_insert(DL *header , DL *new)
    {
    	//取得当前节点的地址 
    	DL *p = header ;
    	//找到链表的尾节点 
    	while(NULL != p->next)
    	{
    		//找不到接着找 
    		p = p->next ;
    	}
    	//找到了尾节点,指向新节点的首地址 
    	p->next = new ;
    	//新节点的prev指针指向原来的尾节点的首地址。
    	new->prev = p;
    }
     
    //双向链表的头插(也就是插在两个节点之间的插入方式)
    void double_list_top_insert(DL *header , DL *new)
    {
    	//新节点的next指针指向原来的节点一的地址
    	new->next = header->next ; 
    	//判断当前节点的下一个节点的地址是否为空
    	if(NULL != header->next) 
    		header->next->prev = new ; //节点1的prev指针指向新节点的地址 
    	header->next = new ;
    	new->prev = header ;
    }
     
    //双向链表的正向遍历 
    void double_list_for_each(DL *header)
    {
    	DL *p = header ;
    	while(NULL != p->next)
    	{
    		p = p->next ;
    		printf("%d ",p->data);
    	}
    }
     
    //双向链表的反向遍历 
    void double_list_for_each_nx(DL *header)
    {
    	DL *p = header ;
    	//先找到尾节点
    	while(NULL != p->next)
    	{
    		p = p->next ;	
    	} 
    	//已经找到了尾节点,向前遍历,注意,遍历到头节点之前
    	//限制条件: != 头结点 
    	while(NULL != p->prev)
    	{
    		printf("%d ",p->data);
    		p = p->prev ;
    	}
    }
     
    //双向链表节点的删除
    int double_list_delete_node(DL *header , int data)
    {
    	//取得当前节点 
    	DL *p = header;
    	//遍历所有的节点 
    	while(NULL != p->next)
    	{
    		p = p->next ;
    		//找到了对应要删除的数据了 
    		if(p->data == data)
    		{
    			//一样存在两种情况
    			//(1)当前节点的下一个节点不为空
    			if(p->next != NULL)
    			{
    				//那就把当前节点的prev节点指向要删除的这个节点的prev
    				//因为当前的prev节点保存的是要删除的上一个节点的指针 
    				p->next->prev = p->prev ;
    				//还要指定它的next节点 
    				p->prev->next = p->next ;
    				free(p);
    			}
    			//(2)当前节点的下一个节点为空 
    			else
    			{
    				//把 
    				p->prev->next = NULL ;
    				free(p); 
    			}
    			return 0 ;
    		}
    	}
    	printf("\n没有找到对应要删除的节点,或者节点已经被删除!\n");
    	return -1 ;	
    } 
     
    int main(void)
    {
    	int i ;
    	DL *header = create_dl_node(0);
    	for(i = 0 ; i < 10 ; i++)
    	{
    		//双向链表的尾插 
    		//double_list_tail_insert(header,create_dl_node(i));
    		//双向链表的头插 
    		double_list_top_insert(header,create_dl_node(i));
    	}
    	//双向链表的正向遍历 
    	printf("双向链表的正向遍历:");
    	double_list_delete_node(header,5);
    	double_list_for_each(header);
    //	double_list_delete_node(header,9);
    	double_list_delete_node(header,5);
    	putchar('\n');
    	printf("双向链表的反向遍历:");
    	double_list_for_each_nx(header);
    	return 0 ;
    }
    

    运行结果:

    展开全文
  • 链表详解(易懂)

    2019-04-24 21:13:32
    链表是一系列的存储数据元素的单元通过指针串接起来形成的,因此每个单元至少有两个域,一个域用于数据元素的存储,另一个或两个域是指向其他单元的指针。这里具有一个数据域和多个指针域的存储单元通常称为节点...
    • 链表是一系列的存储数据元素的单元通过指针串接起来形成的,因此每个单元至少有两个域,一个域用于数据元素的存储,另一个或两个域是指向其他单元的指针。这里具有一个数据域和多个指针域的存储单元通常称为节点(node)。
    • 链表的第一个节点和最后一个节点,分别称为链表的头节点和尾节点。尾节点的特征是其 next 引用为空(null)。链表中每个节点的 next 引用都相当于一个指针,指向另一个节点,借助这些 next 引用,我们可以从链表的头节点移动到尾节点。
    • 链表数据结构中主要包含单向链表、双向链表及循环链表:
    1. 单向链表
        单向链表只有一个指针域,在整个节点中数据域用来存储数据元素,指针域用于指向下一个具有相同结构的节点。
      在这里插入图片描述
      在这里插入图片描述
        单向链表中,每个节点的数据域都是通过一个 Object 类的对象引用来指向数据元素的,与数组类似,单向链表中的节点也具有一个线性次序,即如果节点 a1 的 next 引用指向节点 a2,则 a1 就是 a2 的直接前驱,a2 是 a1 的直接后续。只能通过前驱节点找到后续节点,而无法从后续节点找到前驱节点。
      特点:
        数据元素的存储对应的是不连续的存储空间,每个存储结点对应一个需要存储的数据元素。每个结点是由数据域和指针域组成。 元素之间的逻辑关系通过存储节点之间的链接关系反映出来。
        逻辑上相邻的节点物理上不必相邻。
      缺点:
      1、比顺序存储结构的存储密度小 (每个节点都由数据域和指针域组成,所以相同空间内假设全存满的话顺序比链式存储更多)。
      2、查找结点时链式存储要比顺序存储慢(每个节点地址不连续、无规律,导致按照索引查询效率低下)。
      优点:
      1、插入、删除灵活 (不必移动节点,只要改变节点中的指针,但是需要先定位到元素上)。
      2、有元素才会分配结点空间,不会有闲置的结点。

    2. 双向链表
        要在单向链表中找到某个节点的前驱节点,必须从链表的头节点出发依次向后寻找,但是需要Ο(n)时间。为此我们可以扩展单向链表的节点结构,使得通过一个节点的引用,不但能够访问其后续节点,也可以方便的访问其前驱节点。扩展单向链表节点结构的方法是,在单链表节点结构中新增加一个域,该域用于指向节点的直接前驱节点。该链表称为双向链表。单向链表只能从一个方向遍历,双向链表可以从两个方向遍历。
      在这里插入图片描述
      在这里插入图片描述
        在使用双向链表实现链接表时,为使编程更加简洁,我们使用带两个哑元节点的双向链表来实现链接表。其中一个是头节点,另一个是尾节点,它们都不存放数据元素,头节点的pre 为空,而尾节点的 Next 为空。
      在这里插入图片描述
        在具有头尾节点的双向链表中插入和删除节点,无论插入和删除的节点位置在何处,因为首尾节点的存在,插入、删除操作都可以被归结为某个中间节点的插入和删除;并且因为首尾节点的存在,整个链表永远不会为空,因此在插入和删除节点之后,也不用考虑链表由空变为非空或由非空变为空的情况下 head 和 tail 的指向问题;从而简化了程序。

    3. 循环链表
        头节点和尾节点被连接在一起的链表称为循环链表,这种方式在单向和双向链表中皆可实现。循环链表中第一个节点之前就是最后一个节点,反之亦然。
      在这里插入图片描述
      在这里插入图片描述

    简单用双向列表模拟一下LinkedList,Java代码如下:

    public class Node {//节点类
            private Object previous;//每个节点的前一个指向
            private Object obj;//每个节点中间位置用来存放你存储的东西
            private Object next;//每个节点的后一个指向
            public Object getPrevious() {
                    return previous;
            }
            public void setPrevious(Object previous) {
                    this.previous = previous;
            }
            public Object getObj() {
                    return obj;
            }
            public void setObj(Object obj) {
                    this.obj = obj;
            }
            public Object getNext() {
                    return next;
            }
            public void setNext(Object next) {
                    this.next = next;
            }
    }
    
    public class MyLinkedList {//模拟LinkedList
            //对于每一个LinkedList集合,都有一个首节点和一个尾节点:
            private Node first;//首节点
            private Node last;//尾节点 
            
            
            public void add(Object obj){
                    if(first==null){	//证明我放入的是第一个节点
                            //创建一个独立的节点:
                            Node n=new Node();
                            n.setPrevious(null);
                            n.setObj(obj);
                            n.setNext(null);
                            
                            //将我想象的这个链中的首节点,位节点都设置为n
                            first=n;
                            last=n;
                    }else{	//放入的是第二个节点,第三个节点。。。。。
                            //创建一个独立的节点:
                            Node n=new Node();
                            n.setPrevious(last);
                            n.setObj(obj);
                            n.setNext(null);
                            
                            //将链表的最后一个的下一个指向为n
                            last.setNext(n);
                            
                            //将链表的最后一个指向n
                            last=n;
                    }
            }
            
            public static void main(String[] args) {
                    MyLinkedList list=new MyLinkedList();
                    list.add("java");
                    list.add("css");
                    list.add("solr");
                    list.add("jsp");
                    
                    System.out.println("结束");
      
            }
         
    }
    
    
    展开全文
  • C语言 —— 链表简学

    2020-03-11 22:32:43
    C语言 —— 链表简学链表创建简单链表 链表 链表是一种常见的基础数据结构,结构体指针在这里得到了充分的利用。 链表可以动态的进行存储分配,也就是说,链表是一个功能极为强大的数组,他可以在节点中定义多种数据...

    C语言 —— 链表简学

    链表

    链表是一种常见的基础数据结构,结构体指针在这里得到了充分的利用。

    链表可以动态的进行存储分配,也就是说,链表是一个功能极为强大的数组,他可以在节点中定义多种数据类型,还可以根据需要随意增添,删除,插入节点。

    链表都有一个头指针,一般以head来表示,存放的是一个地址。链表中的节点分为两类,头结点和一般节点,头结点是没有数据域的。链表中每个节点都分为两部分,一个数据域,一个是指针域。

    创建简单链表

    //第一种用typedef
    typedef struct link{
        int id;
        struct link *next;
    } LinkList ;
    //不使用typedef,一般用第一种,这里不细说
    struct link{
    	int id;
    	struct link *next;
    }
    

    创建链表

    LinkList *Create(int n){
        LinkList *head, *node, *end;//定义头节点,普通节点,尾部节点;
        head = (LinkList*)malloc(sizeof(LinkList));//分配地址
        end = head;         //若是空链表则头尾节点一样
        for (int i = 0; i < n; i++) {
            node = (LinkList*)malloc(sizeof(LinkList));
            scanf("%d", &node->id);
            end->next = node;
            end = node;
        }
        end->next = NULL;//结束创建
        return head;
    }
    

    修改链表

    void Change(LinkList *list,int n) { //n为第n个节点
        LinkList *t = list;
        int i = 0;
        while (i < n && t != NULL) {
            t = t->next;
            i++;
        }
        if (t != NULL) {
            printf("输入要修改的值");
            scanf("%d", &t->id);
        }
        else {
            printf("节点不存在");
        }
    }
    

    删除链表:元素也就是把前节点的指针域越过要删除的节点指向下下个节点。即:p->next = q->next;然后放出q节点的空间,即free(q)。

    void Delet(LinkList *list, int n) {
        LinkList *t = list, *in;
        int i = 0;
        while (i < n && t != NULL) {
            in = t;
            t = t->next;
            i++;
        }
        if (t != NULL) {
            in->next = t->next;
            free(t);
        }
        else {
            printf("节点不存在");
        }
    }
    

    插入节点:就是用插入前节点的指针域链接上插入节点的数据域,再把插入节点的指针域链接上插入后节点的数据域。
    插入节点也就是:e->next = head->next; head->next = e

    void Insert(LinkList *list, int n) {
        LinkList *t = list, *in;
        int i = 0;
        while (i < n && t != NULL) {
            t = t->next;
            i++;
        }
        if (t != NULL) {
            in = (LinkList*)malloc(sizeof(LinkList));
            printf("输入要插入的值");
            scanf("%d", &in->id);
            in->next = t->next;//填充in节点的指针域,也就是说把in的指针域指向t的下一个节点
            t->next = in;//填充t节点的指针域,把t的指针域重新指向in
        }
        else {
            printf("节点不存在");
        }
    }
    

    输出链表

    //直接遍历输出
    LinkList *temp;
    temp = h;
    while (temp ->next != NULL) {
            temp  = temp ->next;
            printf("%d  ", h->score);
    }
    

    这篇写完,之后简单用链表实现一个贪吃蛇小游戏。

    展开全文
  • 链表(图文详解)

    2020-06-14 18:19:19
    链表与数组的对比,单链表和双链表的对比,双链表性能比单链表好,为什么不经常使用?有环链表面试题?

    链表的概念

      链表是一种物理存储结构上非连续,非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
    在这里插入图片描述
      链表的结构是多式多样的,当时通常用的也就是两种:
    在这里插入图片描述
    在这里插入图片描述
      无头单向非循环列表:结构简单,一般不会单独用来存放数据。实际中更多是作为其他数据结构的子结构,比如说哈希桶等等。
      带头双向循环链表:结构最复杂,一般单独存储数据。实际中经常使用的链表数据结构,都是带头双向循环链表。这个结构虽然复杂,但是使用代码实现后会发现这个结构会带来很多优势,实现反而简单了。

    链表和数组的区别:

    两者的区别:

    1. 数组静态分配内存,链表动态分配内存。
    2. 数组在内存中是连续的,链表是不连续的。
    3. 数组利用下标定位,查找的时间复杂度是O(1),链表通过遍历定位元素,查找的时间复杂度是O(N)。
    4. 数组插入和删除需要移动其他元素,时间复杂度是O(N),链表的插入或删除不需要移动其他元素,时间复杂度是O(1)。
    数组的优点
    1. 随机访问性比较强,可以通过下标进行快速定位。
    2. 查找速度快
    数组的缺点
    1. 插入和删除的效率低,需要移动其他元素。
    2. 会造成内存的浪费,因为内存是连续的,所以在申请数组的时候就必须规定七内存的大小,如果不合适,就会造成内存的浪费。
    3. 内存空间要求高,创建一个数组,必须要有足够的连续内存空间。
    4. 数组的大小是固定的,在创建数组的时候就已经规定好,不能动态拓展。
    链表的优点
    1. 插入和删除的效率高,只需要改变指针的指向就可以进行插入和删除。
    2. 内存利用率高,不会浪费内存,可以使用内存中细小的不连续的空间,只有在需要的时候才去创建空间。大小不固定,拓展很灵活。
    链表的缺点

    查找的效率低,因为链表是从第一个节点向后遍历查找。

    单链表和双链表的区别:

    在这里插入图片描述

    1. 单链表的每一个节点中只有指向下一个结点的指针,不能进行回溯,适用于节点的增加和删除。
    2. 双链表的每一个节点给中既有指向下一个结点的指针,也有指向上一个结点的指针,可以快速的找到当前节点的前一个节点,适用于需要双向查找节点值的情况。
    双链表相对于单链表的优点:

      删除单链表中的某个节点时,一定要得到待删除节点的前驱,得到其前驱的方法一般是在定位待删除节点的时候一路保存当前节点的前驱,这样指针的总的的移动操作为2n次,如果是用双链表,就不需要去定位前驱,所以指针的总的的移动操作为n次。
      查找时也是一样的,可以用二分法的思路,从头节点向后和尾节点向前同时进行,这样效率也可以提高一倍,但是为什么市场上对于单链表的使用要超过双链表呢?从存储结构来看,每一个双链表的节点都比单链表的节点多一个指针,如果长度是n,就需要n*lenght(32位是4字节,64位是8字节)的空间,这在一些追求时间效率不高的应用下就不适用了,因为他占的空间大于单链表的1/3,所以设计者就会一时间换空间。

    链表环问题

    判断是否有环

      定义一个快指针和一个慢指针,快指针一次走两步,慢指针一次走两步,会出现两种情况,情况一指针走到了空的位置,那就说明这个链表不带环。情况二两个指针相遇,说明这个链表带环。

    获得入环节点

      如果不考虑空间复杂度,可以使用一个map来记录走过的节点,这个指针一直向后遍历如果遇到空,说明这个链表不带环,也就没有入环节点,如果没有遇到空,如果遇到第一个在map中存在的节点,就说明回到了出发点,这个节点就是环的入口节点。如果不建立额外的空间,先使用快慢指针判断这个链表是否有环,如果有环将相遇节点记录,然后一个指针从链表的起始位置开始一次走一步,另一个指针从记录的节点开始一次走一步,当两个节点再次相遇,这个相遇节点就是环的入口节点。
    在这里插入图片描述

    展开全文
  • 链表

    2019-10-29 11:19:32
    单链表: #include <stdio.h> #include <malloc.h> #include <...//头指针+头结点为整个链表的起始 struct node{ int value; char *c; struct node *pnext; }; struct node * create_...
  • 链表基础知识总结

    2018-05-02 20:05:55
    链表和数组作为算法中的两个基本数据结构,在程序设计过程中经常用到。尽管两种结构都可以用来存储一系列的数据,但又各有各的特点。数组的优势,在于可以方便的遍历查找需要的数据。在查询数组指定位置(如查询数组...
  • 1、什么是链表链表的分类? 链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。 数据结构中: 2、链表的分类 共有8种链表结构 ...
  • 单链表的实现

    2019-06-21 11:30:56
    关于单链表的一些操作,今天重新梳理了一下 话不多说,先上代码 #include <stdio.h> #include <stdlib.h> #define OK 1 #define ERROR 0 typedef int ElemType,Status; ......
  • 单链表的应用

    2018-04-06 15:29:51
    单链表的操作:初始化、打印单链表元素、尾插、尾删、头插、头删、任意位置的插入、查找、指定值的删除、任意位置的删除、链表判空、链表节点个数、逆序打印单链表等操作。
  • 链表是一种常见的基础数据结构,结构体指针在这里得到了充分的利用。链表可以动态的进行存储分配,也就是说,链表是一个功能极为强大的数组,他可以在节点中定义多种数据类型,还可以根据需要随意增添,删除,插入...
  • 小猪的数据结构辅助教程——2.7 线性表中的双向循环链表标签(空格分隔): 数据结构本节学习路线图与学习要点学习要点: 1.了解引入双向循环链表的原因 2.熟悉双向循环链表的特点以及存储结构 3.掌握双向循环...
  • C语言链表操作详解

    2019-08-24 20:28:23
    为什么要使用链表 在未学习链表时,我们常用的存储数据的方式无非就是数组。使用数组存储数据的好处就是查询快,但是它的弊端也很明显: 使用前需声明数组的长度,一旦声明长度就不能更改 插入和删除操作需要...
  • 今天将给大家讲述链表的学习心得。学习数据结构,毋庸置疑链表必须学好,后面的栈、队列、树、图都是以链表为基础的;链表的种类很多,有单链表、双链表、循环链表、非循环链表;在此,我们以非循环单链表为例,来讲...
  • 一:单向链表基本介绍链表是一种数据结构,和数组同级。比如,Java中我们使用的ArrayList,其实现原理是数组。而LinkedList的实现原理就是链表了。链表在进行循环遍历时效率不高,但是插入和删除时优势明显。下面对...
  • 暑假参加的第一个公司的就让我手写一个双向链表,并完成插入数据和删除数据的操作。当时我很蒙蔽,懵逼的不是思路,而是手写,虽然写出来了,但是很多边界条件和代码规范自我感觉不好,所以有了这些细心的总结。那么...
  • 静态链表和动态链表的区别: 静态链表和动态链表是线性表链式存储结构的两种不同的表示方式。 1、静态链表是用类似于数组方法实现的,是顺序的存储结构,在物理地址上是连续的,而且需要预先分配地址空间大小。所以...
  • 1.链表是什么 链表是一种上一个元素的引用指向下一个元素的存储结构,链表通过指针来连接元素与元素; 链表是线性表的一种,所谓的线性表包含顺序线性表和链表,顺序线性表是用数组实现的,在内存中有顺序排列,...
  • 今天遇到单向链表的反转的问题,于是静下心来好好想了一番。 解题思路如下图:假设当前创建好的链表如下:首先让头节点与第一个元素节点断开,但是要注意在断开之前需要用p指针指向第一个元素节点来保存第一个元素...
  • 昨天面试官面试的时候问了我一道关于链表的问题:情境如下 面试官:请说一下链表跟数组的区别? 我:数组静态分配内存,链表动态分配内存;数组在内存中连续,链表不连续;数组利用下标定位,时间复杂度为O(1),...
  • C++实现链表基本操作

    2016-01-10 22:01:51
    前几天找实习的时候,一个面试官给我留了一个题,做一个链表demo,要求实现创建、插入、删除等操作。 链表是一种常见的数据结构,它是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中...
1 2 3 4 5 ... 20
收藏数 645,127
精华内容 258,050
关键字:

链表