精华内容
下载资源
问答
  • 双向链表 引言 页面的前进与回退 ...所以要想让其时间复杂度达到O(1),可以选择增加一个指向直接前驱的指针域。 双向链表的基本操作 //定义结构体变量 typedef struct node{ int data; //data域存放数据 str

    双向链表

    引言

    页面的前进与回退

    在这里插入图片描述

    已知某指针q的位置,求指针p。
    在这里插入图片描述

    由于单链表节点中只有一个指向其直接后继结点的指针域,因此若已知某结点的指针域为p,找其前驱结点只能从该链表的头结点开始,顺链查找,直到找到某个结点q的直接后继为p为止。q所指的结点即为p的直接前驱,其时间复杂度为O(n)。

    所以要想让其时间复杂度达到O(1),可以选择增加一个指向直接前驱的指针域。
    在这里插入图片描述

    双向链表的基本操作

    //定义结构体变量
    typedef struct node{
    	int data;			//data域存放数据
    	struct node *prev;	//prev指针域存放上一个结点的地址
    	struct node *next;	//next指针域存放下一个结点的地址
    }LNode,*Linklist;
    
    //创建头结点
    Linklist CreatList(); 
    
    //双向链表判空操作
    int isEmpty(Linklist head); 
    
    //链表的创建 [头插法]
    void ListByInsertHead(Linklist head );
    
    //链表的创建[尾插法]
    void ListByInsertTail(Linklist head );
     
    //将p结点插入q结点之前 
    void Insert(LNode *p, LNode *q);
    
    //删除给定结点
    void delete_Node(LNode *p); 
    
    //删除链表
    void delete_List(LNode *p); 
    

    链表创建头结点[初始化]

    在这里插入图片描述

    /**
    *创建链表,返回头指针。
    **/
    Linklist CreatList(){
    	Linklist head = (Linklist)malloc(sizeof(LNode));//创建头结点
    	head->next=NULL;	//将next指针域置空
    	head->prev=NULL;	//将prev指针域置空
    	return head;		//返回头结点
    }
    
    /**
    *双向链表判空操作
    **/
    int isEmpty(Linklist head){
    	if(head->next==NULL && head->prev==NULL){
    		//为空 
    		return 1;
    	}
    	//不为空 
    	return 0; 	
    }
    

    如何连接我相信大家画图都是知道的,但是有时候代码跑不起来的原因就是因为插入的次序没有。

    链表头插法创建

    在这里插入图片描述

    断开两个连接

    在这里插入图片描述

    我们先看一下原图

    在这里插入图片描述

    断的次序(head->next后断):

    在这里插入图片描述

    特殊情况:

    当只存在head结点时,head的next指针域为空。

    在这里插入图片描述

    已知Head结点和p结点,上面共四步:

    Head->next=p;(1)
    p->prev=Head;(2)
    Head->next->prev=p;(3)
    p->next=Head->next;(4)
    

    3 4 1

    /**
    *头插法创建链表
    **/
    void ListByInsertHead(Linklist head ){
    	
    	LNode *p;	//指针p用来接受数据,进行插入
    	int x;
    	while(scanf("%d",&x)&&x!=-1){
    		p=(Linklist)malloc(sizeof(LNode)) ;
    		p->data=x;
    		
            //头插法
            //只有头结点时,头结点的next域为NULL,不存在prev指针域,第一步要放在第三步之前,此时未更新head->next
    		if(head->next!=NULL){	
    			head->next->prev=p;
    		}
    		p->next=head->next;	//单链表头插操作
    		head->next=p;		//单链表头插操作
    		p->prev=head;		//将p的prev指针域指向head(这一步放哪都行)
            
    	}
    	return ;
    }
    
    

    链表尾插法创建

    在这里插入图片描述

    在这里插入图片描述

    此时有四步改动

    p->next=s;(1)
    p=s;(2)
    s->prev=p;(3)
    s->next=p->next;(4)
    //还有一种写法是s->next=NULL;
    

    3 2

    /**
    *尾插法创建链表
    **/
    void ListByInsertTail(Linklist head ){
    
    	LNode *p,*s;	//指针p用来保存尾指针位置,指针s用来存数据进行插入
    	p=head;//只有头结点时,头结点即为最后一个结点
    	int x;
    	while(scanf("%d",&x)&&x!=-1){
    		s=(Linklist)malloc(sizeof(LNode)) ;
    		s->data=x;
        
            //尾插法
            s->next=p->next;//s的结点指向尾结点p的下一个,即NULL
    		p->next=s;//将尾结点的next指针指向要插入的结点
            //第三步和第四步不能交换
    		s->prev=p;//要插入的结点的前一个结点更新为尾结点
    		p=s;//将尾结点更新为新插入的结点
            
           
    
        }
    	
    	return ;	
    }
    
    /**
    *尾插法创建链表第二种写法
    **/
    void ListByInsertTail(Linklist head ){
    
    	LNode *p,*s;	//指针p用来保存尾指针位置,指针s用来存数据进行插入
    	p=head;//只有头结点时,头结点即为最后一个结点
    	int x;
    	while(scanf("%d",&x)&&x!=-1){
    		s=(Linklist)malloc(sizeof(LNode)) ;
    		s->data=x;
        
            //尾插法
    		p->next=s;//将尾结点的next指针指向要插入的结点
            //第二步和第三步不能交换
    		s->prev=p;//要插入的结点的前一个结点更新为尾结点
    		p=s;//将尾结点更新为新插入的结点
        }
    	s->next=NULL;//尾结点指向为空
        
    	return ;	
    }
    

    指定结点前插入

    在q结点前插入p结点

    在这里插入图片描述

    在这里插入图片描述

    此处共有四处改动

    p->prev=q->prev;(1)
    q->prev->next=p;(2)
    p->next=q;(3)
    q->prev=p;(4)
    
    /**
    *指定结点前插入(在q结点前插入p结点)
    **/
    
    void Insert(LNode *p, LNode *q){
        //只有等q指针前面那个结点的相关操作处理完之后才能修改q->prev
    	p->prev=q->prev;
    	q->prev->next=p;
        
    	p->next=q;
    	q->prev=p;
    }
    
    

    链表删除

    在这里插入图片描述

    在这里插入图片描述

    特殊:p为尾指针在这里插入图片描述

    上述有三处改动

    p->prev->next=p->next;(1)
    p->next=p->prev(2)
    free(p)(3)
    
    /**
    *删除指定结点
    **/
    
    void delete_Node(LNode *p){
    	p->prev->next=p->next;
    	if(p->next!=NULL){
    		p->next->prev=p->prev;
    	}                                                    
    	free(p);
    }
    
    

    双向链表完整代码

    #include<stdio.h>
    #include<stdlib.h>
    #include<windows.h>
    typedef struct node{
    	int data;
    	struct node *prev;
    	struct node *next;
    }LNode,*Linklist;
    
    //创建链表
    Linklist CreatList(); 
    
    //双向链表判空操作
    int isEmpty(Linklist head); 
    
    //链表的创建 [头插法]
    void ListByInsertHead(Linklist head );
    
    //链表的创建[尾插法]
    void ListByInsertTail(Linklist head );
     
    
    //将p结点插入q结点之前 
    void Insert(LNode *p, LNode *q);
    
    //删除p结点
    void delete_Node(LNode *p); 
    
    //删除链表
    void delete_List(LNode *p); 
    
    //打印链表
    void print_List(Linklist head);
    
    
    int main(){
    	
    	Linklist head = CreatList();
    	printf("%d\n",isEmpty(head)); 
    	ListByInsertTail(head);
    	print_List(head);
    	printf("\n");
    	Linklist head1 = CreatList();
    	ListByInsertHead(head1);
    	print_List(head1);
    //	LNode *t = (Linklist)malloc(sizeof(LNode));
    //	t->data=10;
    //	Insert(t,head->next);
    //	print_List(head);
    //	printf("\n");
    //	delete_Node(t);
    //	print_List(head);
    //	delete_List(head);
    	return 0;
    	
    } 
    
    Linklist CreatList(){
    	Linklist head = (Linklist)malloc(sizeof(LNode));
    	head->next=NULL;
    	head->prev=NULL;
    	return head;
    }
    
    int isEmpty(Linklist head){
    	if(head->next==NULL && head->prev==NULL){
    		//为空 
    		return 1;
    	}
    	//不为空 
    	return 0; 	
    }
    
    void ListByInsertHead(Linklist head ){
    	
    	LNode *p;
    	int x;
    	while(scanf("%d",&x)&&x!=-1){
    		p=(Linklist)malloc(sizeof(LNode)) ;
    		p->data=x;
    		
    		if(head->next!=NULL){
    			head->next->prev=p;
    		}
    		p->next=head->next;
    		head->next=p;
    		p->prev=head;
    	}
    	return ;
    }
    
    void ListByInsertTail(Linklist head ){
    
    	LNode *p,*s;
    	p=head;
    	int x;
    	while(scanf("%d",&x)&&x!=-1){
    		s=(Linklist)malloc(sizeof(LNode)) ;
    		s->data=x;
    		s->next=p->next; 
    		p->next=s;
    		s->prev=p;
    		p=s;
    	}
    	//s->next=NULL;
    	return ;
    	
    	
    }
    				
    void Insert(LNode *p, LNode *q){
    	p->prev=q->prev;
    	q->prev->next=p;
    	p->next=q;
    	q->prev=p;
    }
    
    
    void delete_Node(LNode *p){
    	p->prev->next=p->next;
    	if(p->next!=NULL){
    		p->next->prev=p->prev;
    	}                                                    
    	free(p);
    }
    
    void delete_List(LNode *p){
    	LNode *t,*temp;
    	t=p->next;
    	while(t){
    		temp=t->next;
    		delete_Node(t);
    		t=temp;
    		print_List(p);
    	}
    	free(p);
    }
    void print_List(Linklist head){
    	Linklist p;
    	p=head;
    	while(p->next){
    		p=p->next;
    		printf("%d ",p->data);	
    	} 
    	
    	system("pause"); 
    	printf("\n");
    	while(p->prev){	
    		printf("%d ",p->data);
    		p=p->prev;
    	}
    }
     
    

    循环双向链表的实现

    小思考:自己实现循环双向链表

    循环双向链表和双向链表的操作基本一致, 注意由于head指针的prev域和尾指针的next域不为空,因此部分操作需要增加对这两个指针的连接

    双向循环链表完整代码:

    #include<stdio.h>
    #include<stdlib.h>
    #include<windows.h>
    typedef struct node{
    	int data;
    	struct node *prev;
    	struct node *next;
    }LNode,*Linklist;
    
    //创建链表
    Linklist CreatList(); 
    
    //双向循环链表判空操作
    int isEmpty(Linklist head); 
    
    //链表的创建 [头插法]
    void ListByInsertHead(Linklist head );
    
    //链表的创建[尾插法]
    void ListByInsertTail(Linklist head );
     
    
    //将p结点插入q结点之前 
    void Insert(LNode *p, LNode *q);
    
    //删除p结点
    void delete_Node(LNode *p); 
    
    //删除链表
    void delete_List(LNode *p); 
    
    //打印链表
    void print_List(Linklist head);
    
    
    int main(){
    	
    		Linklist head = CreatList();
    		printf("%d\n",isEmpty(head));
    	ListByInsertTail(head);
    	print_List(head);
    	printf("\n");
    	//Linklist head1 = CreatList();
    	//ListByInsertHead(head1);
    	//print_List(head1);
    	LNode *t = (Linklist)malloc(sizeof(LNode));
    	t->data=10;
    	Insert(t,head->next);
    	print_List(head);
    	printf("\n");
    	delete_Node(t);
    	print_List(head);
    	delete_List(head);
    	return 0;
    	
    } 
    
    Linklist CreatList(){
    	Linklist head = (Linklist)malloc(sizeof(LNode));
    	head->next=head;
    	head->prev=head;
    	return head;
    }
    
    int isEmpty(Linklist head){
    	if(head->next==head && head->prev==head){
    		//为空 
    		return 1;
    	}
    	//不为空 
    	return 0; 	
    }
    
    void ListByInsertHead(Linklist head ){
    	
    	LNode *p;
    	int x;
    	while(scanf("%d",&x)&&x!=-1){
    		p=(Linklist)malloc(sizeof(LNode)) ;
    		p->data=x;
    		
    		head->next->prev=p;
    		p->next=head->next;
    		head->next=p;
    		p->prev=head;
    	}
    	return ;
    }
    
    void ListByInsertTail(Linklist head ){
    
    	LNode *p,*s;
    	p=head;
    	int x;
    	while(scanf("%d",&x)&&x!=-1){
    		s=(Linklist)malloc(sizeof(LNode)) ;
    		s->data=x;
    		s->next=p->next;
    		//增加代码:尾指针所指的下一个结点即头指针的prev修改为要插入的结点,即将头指针与新要插入的结点连接起来
    		p->next->prev=s; 
    		p->next=s;
    		s->prev=p;
    		p=s;
    	}
    	return ;
    	
    	
    }
    				
    void Insert(LNode *p, LNode *q){
    	p->prev=q->prev;
    	q->prev->next=p;
    	p->next=q;
    	q->prev=p;
    }
    
    
    void delete_Node(LNode *p){
    	p->prev->next=p->next;
    	//if(p->next!=NULL){ //p->next不会为空,可删去 
    	p->next->prev=p->prev;
    //	}                                                    
    	free(p);
    }
    
    void delete_List(LNode *p){
    	LNode *t,*temp;
    	t=p->next;
    	while(t!=p&&t!=p){//判断条件改为当t又绕回一圈时即链表只剩一个结点 
    		temp=t->next;
    		delete_Node(t);
    		t=temp;
    		print_List(p);
    		printf("\n");
    	}
    	free(p);
    }
    void print_List(Linklist head){
    	Linklist p;
    	p=head->next;
    	while(1){
    	
    		printf("%d ",p->data);	
    		if(p->next==head){
    			break;
    		}	
    		p=p->next;
    	} 
    	
    	system("pause"); 
    	printf("\n");
    	while(1){	
    		printf("%d ",p->data);
    		
    		if(p->prev==head){
    			break;
    		}
    		p=p->prev;
    	}
    }
     
    

    模拟链表

    引言

    前面介绍的链表都是由指针实现的,链表中结点的分配和回收都是动态的,称为"动态链表“。与之对应的,还有一种"静态链表",又称模拟链表,静态链表由数组实现,每个数据元素除了存储数据信息外,还要存储逻辑相邻的下一个数据元素在数组中的位置。可见,静态链表虽然是用数组实现的,但是逻辑相邻的数据元素不一定在物理上是相邻的。

    下表就是一个模拟链表,他的存储顺序是:a1->a2->a3->a4->a5->……,但是他的物理顺序是a4->a2-a3->a1->a5->……

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-aCqcRdob-1615363269774)(.\双向链表.assets\image-20201208221730863.png)]

    模拟链表通过两个数组实现链式存储,data数组用来存储当前结点的数据,next数组用来存储下一个结点的位置。(是不是感觉和链表很像),通过相同点的数组下标,标识每一个元素存储的数据及下一个结点的位置信息,一样的,第一个结点并没有存放任何元素。

    模拟链表的基本操作

    //定义next=-1为空 
    typedef struct{
    	int data;
    	int next;
    }imitate;
    
    //定义静态链表 
    imitate im[Maxsize];
    
    //链表表头和新要插入的位置 
    int head,pos;
    
    //初始化链表
    void init_list(); 
    
    //链表判空操作
    int isEmpty() ;
    
    //链表增加结点
    void add_toList(); 
    
    //指定位置之后插入结点
    int add_postoList(int point,int x); 
    
    //删除指定位置元素
    int delete_pos_list(int point); 
    

    模拟链表的初始化

    在这里插入图片描述

    /**
    *链表初始化
    **/
    void init_list(){
    	head=0;//头结点放在0位置
    	pos=1; 
    	im[0].next=-1; 
    }
    

    链表判空

    int isEmpty(){
    	if(im[head].next==-1){
    		return 1;
    	}
    	return 0;
    }
    

    链表增加节点

    在这里插入图片描述

    在这里插入图片描述

    /**
    *链表尾部增加结点
    **/
    void add_toList(int x){
        //从头开始遍历,找到尾结点
    	int i=head;
    	
    	while(im[i].next!=-1){
    		i=im[i].next;
    	}
    	
        im[pos].data=x;//读入新要插入的元素
        
    	im[i].next = pos;//将尾结点的next指针指向新要插入的元素
    	im[pos].next = -1;//将新插入的元素的尾指针置空
    	++pos;
    }
    

    指定位置后增加结点

    在这里插入图片描述

    在这里插入图片描述

    /**
    *链表指定位置后增加结点 成功返回1 失败返回0
    *point变量表示链表中第几个数据
    **/
    int add_postoList(int point,int x){
    	
    	for(int i= im[head].next;i!=-1;i=im[i].next){
    		if((--point)==0){//找到那个要增加结点的位置
    			im[pos].data=x;//读入值yuanxie
    			im[pos].next=im[i].next;//新插入的值的下一个结点为第point个位置的结点的下一个结点
    			im[i].next=pos;//第point个结点的下一个结点更新为新插入的结点
    			++pos;//插入点后移
    			return 1;
    		}
    	}
    	return 0; 
    }
    

    删除指定位置的结点

    在这里插入图片描述

    在这里插入图片描述

    /**
    *链表指定位置删除结点 成功返回1 失败返回0
    *point变量表示链表中第几个数据
    **/
    int delete_pos_list(int point){
    	point=point-1;//找要删除的结点的前一个结点
    	for(int i= im[head].next;i!=-1;i=im[i].next){
    		if((--point)==0){		//循环找到那个结点
    			im[i].next=im[im[i].next].next; //该结点等于要删除的结点的下一个结点。
    			return 1;
    		}
    	}
    	return 0;
    }
    
    展开全文
  • 文章目录循环链表循环单链表循环双链表静态链表说明 循环链表  循环链表一般包括循环单链表和循环双链表,如下图所示: 循环单链表   循环单链表与单链表的区别在于,表中最后一个结点的指针不是NULL,而改为...

    循环链表

     循环链表一般包括循环单链表和循环双链表,如下图所示:
    循环链表

    循环单链表

      循环单链表与单链表的区别在于,表中最后一个结点的指针不是NULL,而改为指向头结点,从而使整个链表形成一个环。
      一般对循环单链表只设尾指针不设头指针,其原因是,如果设的是头指针,对表尾进行操作需要O(n)的时间复杂度,而若设的是尾指针r,那么r->next即为头指针,对表头与表尾进行操作都只需要O(1)的时间复杂度。

     单链表与循环单链表:
     详细的单链表操作请参照单链表的定义及基本操作 ,在本文中只给出单链表与循环单链表的不同之处,根据描述稍加修改单链表的代码即可。

    1. 判空
      循环单链表中,表尾结点*r的next域指向L,表中没有指针域为NULL的结点。因此,循环单链表的判空条件不是头结点的指针是否为空,而是它是否等于头指针

    2. 插入、删除
      循环单链表的插入、删除算法与单链表几乎一样,不同的是如果在表尾进行,那么要让单链表继续保持循环的性质,即让尾结点的next域指向头结点

    3. 遍历
      单链表只能从表头结点开始往后顺序遍历整个链表,循环单链表可以从表中的任意一个结点开始遍历整个链表。

    4. 查找
      单链表的查找是从表头开始,找到表尾停止。而循环单链表中,若从表头开始查找,那与单链表的操作一致。若从表的任意位置开始查找,那么需要一个计数变量sum,当sum=表长时还未找到,则查找失败,退出循环。


    循环双链表

     循环双链表与双链表的区别在于,表中最后一个结点的next域指向头结点,头结点的prior域指向最后一个结点。

     双链表与循环双链表:
     详细的单链表操作请参照双链表的定义及基本操作 ,在本文中只给出双链表与循环双链表的不同之处,根据描述稍加修改双链表的代码即可。

    1. 判空
      循环双链表中,当循环双链表为空时,其头结点的prior域和next域都等于L。

    2. 插入、删除
      循环双链表的插入、删除算法与双链表几乎一样,不同的是如果在表尾进行,那么要让双链表继续保持循环的性质,即让尾结点的next域指向头结点,同时让头结点的prior域指向尾结点

    3. 遍历
      双链表只能从表头结点开始往后顺序遍历整个链表,循环双链表可以从表中的任意一个结点开始遍历整个链表。

    4. 查找
      双链表的查找是从表头开始,找到表尾停止。而循环双链表中,若从表头开始查找,那与双链表的操作一致。若从表的任意位置开始查找,那么需要一个计数变量sum,当sum=表长时还未找到,则查找失败,退出循环。


    静态链表

     静态链表借助数组来描述线性表的链式存储结构,结点也有数据域data和指针域next,这里的指针是结点的相对地址(数组下标),又称游标。和顺序表一样,静态链表也需要预先分配一块连续的内存空间。

     静态链表结构类型描述:

    #define MaxSize 50  //静态链表的最大长度
    typedef struct SLinkList{
    	ElemType data;  //数据元素
    	int next;  //下一个元素的数组下标
    }SLinkList[MaxSize];
    

     静态链表以next == -1作为其结束的标志

     静态链表的实例:

    静态链表

    说明

     先简单对循环链表和静态链表进行总结,具体的实现代码均未给出,若以后得空,则再补上。持续更新中。。。

    展开全文
  • 文章目录前言单链表单循环链表双链表循环链表错误纠正说明时间复杂度比较关于头结点 前言 博主最近在复习算法与数据结构,由于平时主力语言是Python,所以找了个用Python讲解数据结构的视频看了下,链接为:...

    前言

    博主最近在复习算法与数据结构,由于平时主力语言是Python,所以找了个用Python讲解数据结构的视频看了下,链接为:https://www.bilibili.com/video/av20982396?p=1。
    关于链表,视频里讲的很清楚,但是代码有几处小错误,现将其代码纠正,并添加视频里没有讲到的双循环链表代码。
    那么我们直接上代码吧。

    单链表

    class Node(object):
        """单链表结点"""
        def __init__(self, elem):
            self.elem = elem
            self.next = None
    
    
    class SinglyLinkedList(object):
        def __init__(self, node=None):
            self.__head = node
    
        def is_empty(self):
            """判断链表是否为空"""
            return self.__head is None
    
        def length(self):
            """返回链表长度"""
            cur = self.__head
            count = 0
            while cur is not None:
                count += 1
                cur = cur.next
            return count
    
        def travel(self):
            """遍历链表"""
            cur = self.__head
            while cur is not None:
                print(cur.elem, end=' ')
                cur = cur.next
            print()
    
        def add(self, elem):
            """向链表头部添加元素"""
            node = Node(elem)
            node.next = self.__head
            self.__head = node
    
        def append(self, elem):
            """向链表尾部添加元素"""
            node = Node(elem)
            if self.is_empty():
                self.__head = node
            else:
                cur = self.__head
                while cur.next is not None:
                    cur = cur.next
                cur.next = node
    
        def insert(self, pos, elem):
            """向链表位置pos处插入元素
    
            Args:
                pos: 插入位置,从0开始计数
                elem: 需要插入的元素
            """
            if pos <= 0:
                self.add(elem)
            elif pos > (self.length() - 1):
                self.append(elem)
            else:
                pre = self.__head
                count = 0
                while count < (pos-1):
                    count += 1
                    pre = pre.next
                # 当循环退出后,pre指向pos-1位置
                node = Node(elem)
                node.next = pre.next
                pre.next = node
    
        def remove(self, elem):
            """从链表中删除第一个值为elem的元素"""
            cur = self.__head
            pre = None
            while cur is not None:
                if cur.elem == elem:
                    if cur == self.__head:
                        self.__head = cur.next
                    else:
                        pre.next = cur.next
                    break
                else:
                    pre = cur
                    cur = cur.next
    
        def search(self, elem):
            """查找链表中是否存在元素elem"""
            cur = self.__head
            while cur is not None:
                if cur.elem == elem:
                    return True
                else:
                    cur = cur.next
            return False
    
    
    if __name__ == '__main__':
        singly_linked_list = SinglyLinkedList()
        print(singly_linked_list.is_empty())
        print(singly_linked_list.length())
        print('===================')
    
        singly_linked_list.append(1)
        print(singly_linked_list.is_empty())
        print(singly_linked_list.length())
        print('===================')
    
        singly_linked_list.append(2)
        singly_linked_list.append(3)
    
        singly_linked_list.add(7)
    
        singly_linked_list.append(4)
        singly_linked_list.append(5)
    
        singly_linked_list.insert(0, 13)  # 13, 7, 1, 2, 3, 4, 5
        singly_linked_list.travel()
    
        singly_linked_list.insert(2, 99)  # 13, 7, 99, 1, 2, 3, 4, 5
        singly_linked_list.travel()
    
        singly_linked_list.insert(11, 22)  # 13, 7, 99, 1, 2, 3, 4, 5, 22
        singly_linked_list.travel()
    
        singly_linked_list.remove(13)
        singly_linked_list.travel()  # 7 99 1 2 3 4 5 22
    
        singly_linked_list.remove(22)
        singly_linked_list.travel()  # 7 99 1 2 3 4 5
    
        singly_linked_list.remove(3)
        singly_linked_list.travel()  # 7 99 1 2 4 5
    
        print(singly_linked_list.search(1000))  # False
        print(singly_linked_list.search(7))  # True
        print(singly_linked_list.search(5))  # True
        print(singly_linked_list.search(2))  # True
    
    

    如上所示,测试代码已经在main函数中给出了。

    单循环链表

    class Node(object):
        def __init__(self, elem):
            """单循环链表结点"""
            self.elem = elem
            self.next = None
    
    
    class SinglyLinkedCircularList(object):
        """单向循环链表"""
        def __init__(self, node=None):
            self.__head = node
            if node:
                node.next = node
    
        def is_empty(self):
            """判断链表是否为空"""
            return self.__head is None
    
        def length(self):
            """求链表长度"""
            if self.is_empty():
                return 0
            cur = self.__head
            count = 1  # 下方循环退出时,链表至少有一个结点
            while cur.next != self.__head:
                count += 1
                cur = cur.next
            return count
    
        def travel(self):
            """遍历链表"""
            if self.is_empty():
                return
            cur = self.__head
            while cur.next != self.__head:
                print(cur.elem, end=' ')
                cur = cur.next
            # 退出循环时,cur指向最后一个结点
            print(cur.elem)
    
        def add(self, elem):
            """向链表头部添加元素"""
            node = Node(elem)
            if self.is_empty():
                node.next = node
                self.__head = node
            else:
                cur = self.__head
                while cur.next != self.__head:
                    cur = cur.next
                node.next = self.__head
                self.__head = node
                cur.next = node
    
        def append(self, elem):
            """向链表尾部添加元素"""
            node = Node(elem)
            if self.is_empty():
                node.next = node
                self.__head = node
            else:
                cur = self.__head
                while cur.next != self.__head:
                    cur = cur.next
                node.next = self.__head
                cur.next = node
    
        def insert(self, pos, elem):
            """向链表位置pos处插入元素
    
            Args:
                pos: 插入的位置,从0开始计数
                elem: 插入的元素
            """
            if pos <= 0:
                self.add(elem)
            elif pos > (self.length() - 1):
                self.append(elem)
            else:
                pre = self.__head
                count = 0
                while count < (pos - 1):
                    count += 1
                    pre = pre.next
                # 退出循环,pre指向插入位置的前一个结点
                node = Node(elem)
                node.next = pre.next
                pre.next = node
    
        def remove(self, elem):
            """删除链表中第一个为elem的元素"""
            if self.is_empty():
                return
            cur = self.__head
            pre = None
            while cur.next != self.__head:
                if cur.elem == elem:
                    # 头结点
                    if cur == self.__head:
                        rear = self.__head
                        while rear.next != self.__head:
                            rear = rear.next
                        rear.next = cur.next
                        self.__head = cur.next
                    else:  # 中间结点
                        pre.next = cur.next
                    return
                else:
                    pre = cur
                    cur = cur.next
            # 退出循环, cur指向尾结点
            if cur.elem == elem:
                # 链表中只有一个结点
                if cur == self.__head:
                    self.__head = None
                else:
                    pre.next = self.__head
    
        def search(self, elem):
            """查找链表中是否存在元素elem"""
            if self.is_empty():
                return False
            cur = self.__head
            while cur.next != self.__head:
                if cur.elem == elem:
                    return True
                else:
                    cur = cur.next
            # 退出循环,cur指向尾结点
            if cur.elem == elem:
                return True
            return False
    
    
    if __name__ == '__main__':
        singly_linked_circular_list = SinglyLinkedCircularList()
        print(singly_linked_circular_list.is_empty())
        print(singly_linked_circular_list.length())
        print('===================')
    
        singly_linked_circular_list.append(1)
        print(singly_linked_circular_list.is_empty())
        print(singly_linked_circular_list.length())
        print('===================')
    
        singly_linked_circular_list.append(2)
        singly_linked_circular_list.append(3)
    
        singly_linked_circular_list.add(7)
    
        singly_linked_circular_list.append(4)
        singly_linked_circular_list.append(5)
    
        singly_linked_circular_list.insert(0, 13)  # 13, 7, 1, 2, 3, 4, 5
        singly_linked_circular_list.travel()
    
        singly_linked_circular_list.insert(2, 99)  # 13, 7, 99, 1, 2, 3, 4, 5
        singly_linked_circular_list.travel()
    
        singly_linked_circular_list.insert(11, 22)  # 13, 7, 99, 1, 2, 3, 4, 5, 22
        singly_linked_circular_list.travel()
    
        singly_linked_circular_list.remove(13)
        singly_linked_circular_list.travel()  # 7 99 1 2 3 4 5 22
    
        singly_linked_circular_list.remove(22)
        singly_linked_circular_list.travel()  # 7 99 1 2 3 4 5
    
        singly_linked_circular_list.remove(3)
        singly_linked_circular_list.travel()  # 7 99 1 2 4 5
    
        print(singly_linked_circular_list.search(666))  # False
        print(singly_linked_circular_list.search(7))  # True
        print(singly_linked_circular_list.search(5))  # True
        print(singly_linked_circular_list.search(1))  # True
    
    

    双链表

    class Node(object):
        def __init__(self, elem):
            """双链表结点"""
            self.elem = elem
            self.pre = None
            self.next = None
    
    
    class DoubleLinkedList(object):
        def __init__(self, node=None):
            self.__head = node
    
        def is_empty(self):
            """判断链表是否为空"""
            return self.__head is None
    
        def length(self):
            """获取链表长度"""
            cur = self.__head
            count = 0
            while cur is not None:
                count += 1
                cur = cur.next
            return count
    
        def travel(self):
            """遍历链表"""
            cur = self.__head
            while cur is not None:
                print(cur.elem, end=' ')
                cur = cur.next
            print()
    
        def add(self, elem):
            """向双链表头部添加元素"""
            node = Node(elem)
            if self.is_empty():  # 链表为空
                self.__head = node
            else:
                node.next = self.__head
                node.next.pre = node
                self.__head = node
    
        def append(self, elem):
            """向链表尾部添加结点"""
            node = Node(elem)
            if self.is_empty():
                self.__head = node
            else:
                cur = self.__head
                while cur.next is not None:
                    cur = cur.next
                cur.next = node
                node.pre = cur
    
        def insert(self, pos, elem):
            """向链表位置pos处插入元素elem"""
            if pos <= 0:
                self.add(elem)
            elif pos > (self.length() - 1):
                self.append(elem)
            else:
                cur = self.__head
                count = 0
                while count < pos:
                    count += 1
                    cur = cur.next
                # 退出循环时,cur即为pos位置
                node = Node(elem)
                node.next = cur
                node.pre = cur.pre
                cur.pre.next = node
                cur.pre = node
    
        def remove(self, elem):
            """删除链表中第一个值为elem的结点"""
            if self.is_empty():
                return
            cur = self.__head
            while cur is not None:
                if cur.elem == elem:
                    if cur == self.__head:  # 若是头结点
                        self.__head = cur.next  # 链表中只有一个结点
                        if cur.next:
                            cur.next.pre = None
                    else:
                        cur.pre.next = cur.next
                        if cur.next:  # 如果不是尾结点
                            cur.next.pre = cur.pre
                    break
                else:
                    cur = cur.next
    
        def search(self, elem):
            """查找链表中是否存在元素elem"""
            cur = self.__head
            while cur is not None:
                if cur.elem == elem:
                    return True
                else:
                    cur = cur.next
            return False
    
    
    if __name__ == '__main__':
        double_linked_list = DoubleLinkedList()
        print(double_linked_list.is_empty())
        print(double_linked_list.length())
        print('===================')
    
        double_linked_list.append(1)
        print(double_linked_list.is_empty())
        print(double_linked_list.length())
        print('===================')
    
        double_linked_list.append(2)
        double_linked_list.append(3)
    
        double_linked_list.add(7)
    
        double_linked_list.append(4)
        double_linked_list.append(5)
    
        double_linked_list.insert(0, 13)  # 13, 7, 1, 2, 3, 4, 5
        double_linked_list.travel()
    
        double_linked_list.insert(2, 99)  # 13, 7, 99, 1, 2, 3, 4, 5
        double_linked_list.travel()
    
        double_linked_list.insert(11, 22)  # 13, 7, 99, 1, 2, 3, 4, 5, 22
        double_linked_list.travel()
    
        double_linked_list.remove(13)
        double_linked_list.travel()  # 7 99 1 2 3 4 5 22
    
        double_linked_list.remove(22)
        double_linked_list.travel()  # 7 99 1 2 3 4 5
    
        double_linked_list.remove(3)
        double_linked_list.travel()  # 7 99 1 2 4 5
    
        print(double_linked_list.search(100))  # False
        print(double_linked_list.search(7))  # True
        print(double_linked_list.search(2))  # True
        print(double_linked_list.search(5))  # True
    
    

    双循环链表

    class Node(object):
        """双循环链表结点"""
        def __init__(self, elem):
            self.elem = elem
            self.pre = None
            self.next = None
        
    
    class DoubleLinkedCircularList(object):
        def __init__(self, node=None):
            self.__head = node
            if node:
                node.next = node
        
        def is_empty(self):
            """判断链表是否为空"""
            return self.__head is None
        
        def length(self):
            """求取链表长度"""
            if self.is_empty():
                return 0
            cur = self.__head
            count = 1
            while cur.next != self.__head:
                count += 1
                cur = cur.next
            return count
    
        def travel(self):
            """遍历链表"""
            if self.is_empty():
                return
            cur = self.__head
            while cur.next != self.__head:
                print(cur.elem, end=' ')
                cur = cur.next
            # 退出循环,cur指向尾结点
            print(cur.elem)
        
        def add(self, elem):
            """向链表头部添加元素"""
            node = Node(elem)
            if self.is_empty():
                self.__head = node
                node.next = node
            else:
                cur = self.__head
                while cur.next != self.__head:
                    cur = cur.next
                # 退出循环,cur指向尾结点
                cur.next = node
                node.next = self.__head
                self.__head.pre = node
                self.__head = node
        
        def append(self, elem):
            """向链表尾部添加元素"""
            node = Node(elem)
            if self.is_empty():
                self.__head = node
                node.next = node
            else:
                cur = self.__head
                while cur.next != self.__head:
                    cur = cur.next
                # 退出循环,cur指向尾结点
                cur.next = node
                node.pre = cur
                node.next = self.__head
        
        def insert(self, pos, elem):
            """往双向循环链表位置pos处插入元素
    
            Args:
                pos: 插入位置
                elem: 插入的元素
            """
            if pos <= 0:
                self.add(elem)
            elif pos > (self.length() - 1):
                self.append(elem)
            else:
                cur = self.__head
                count = 0
                while count < pos:
                    count += 1
                    cur = cur.next
                # 退出循环,cur指向需要插入的位置pos
                node = Node(elem)
                node.next = cur
                node.pre = cur.pre
                cur.pre.next = node
                cur.pre = node
        
        def remove(self, elem):
            """删除链表中第一个值为elem的结点"""
            if self.is_empty():
                return
            cur = self.__head
            while cur.next != self.__head:
                if cur.elem == elem:
                    if cur == self.__head:  # 删除的是头结点
                        rear = self.__head
                        while rear.next != self.__head:
                            rear = rear.next
                        self.__head = cur.next
                        self.__head.pre = None
                        rear.next = self.__head
                    else:  # 删除的是中间结点
                        cur.next.pre = cur.pre
                        cur.pre.next = cur.next
                    return
                else:
                    cur = cur.next
            # 退出循环,cur指向尾结点
            if cur.elem == elem:
                if cur == self.__head:  # 链表中只有一个结点
                    self.__head = None
                else:
                    cur.pre.next = self.__head
        
        def search(self, elem):
            """查找链表中是否存在值为elem的结点"""
            if self.is_empty():
                return False
            cur = self.__head
            while cur.next != self.__head:
                if cur.elem == elem:
                    return True
                else:
                    cur = cur.next
            # 退出循环,cur指向尾结点
            if cur.elem == elem:
                return True
            return False
    
    
    if __name__ == '__main__':
        double_linked_circular_list = DoubleLinkedCircularList()
        print(double_linked_circular_list.is_empty())
        print(double_linked_circular_list.length())
        print('===================')
    
        double_linked_circular_list.append(1)
        print(double_linked_circular_list.is_empty())
        print(double_linked_circular_list.length())
        print('===================')
    
        double_linked_circular_list.append(2)
        double_linked_circular_list.append(3)
    
        double_linked_circular_list.add(7)
    
        double_linked_circular_list.append(4)
        double_linked_circular_list.append(5)
        double_linked_circular_list.travel()  # 7, 1, 2, 3, 4, 5
    
        double_linked_circular_list.insert(0, 13)  # 13, 7, 1, 2, 3, 4, 5
        double_linked_circular_list.travel()
    
        double_linked_circular_list.insert(2, 99)  # 13, 7, 99, 1, 2, 3, 4, 5
        double_linked_circular_list.travel()
    
        double_linked_circular_list.insert(11, 22)  # 13, 7, 99, 1, 2, 3, 4, 5, 22
        double_linked_circular_list.travel()
    
        double_linked_circular_list.remove(13)
        double_linked_circular_list.travel()  # 7 99 1 2 3 4 5 22
    
        double_linked_circular_list.remove(22)
        double_linked_circular_list.travel()  # 7 99 1 2 3 4 5
    
        double_linked_circular_list.remove(3)
        double_linked_circular_list.travel()  # 7 99 1 2 4 5
    
        print(double_linked_circular_list.search(100))  # False
        print(double_linked_circular_list.search(7))  # True
        print(double_linked_circular_list.search(2))  # True
        print(double_linked_circular_list.search(5))  # True
    
    

    错误纠正说明

    对于单链表、单循环链表、双链表代码纠正了视频里两处错误:

        def insert(self, pos, elem):
            if pos < 0:
                self.add(elem)
    

    纠正为现在的:

        def insert(self, pos, elem):
            if pos <= 0:
                self.add(elem)
    

    双链表add(self, elem)方法由原来的:

    	def add(self, elem):
    		"""向双链表头部添加元素"""
    		node = Node(elem)
    		node.next = self.__head
    		self.__head = node
    		node.next.pre = node
    
    

    纠正为现在的:

        def add(self, elem):
        	"""向双链表头部添加元素"""
            node = Node(elem)
            if self.is_empty():  # 链表为空
                self.__head = node
            else:
                node.next = self.__head
                node.next.pre = node
                self.__head = node
    

    如果代码中还有其他错误,或者我改错了欢迎读者朋友们评论区指证,我会及时纠正。

    时间复杂度比较

    操作 单链表 单循环链表 双链表 双向循环链表
    初始化 O(1)O(1) O(1)O(1) O(1)O(1) O(1)O(1)
    判空 O(1)O(1) O(1)O(1) O(1)O(1) O(1)O(1)
    求长度 O(n)O(n) O(n)O(n) O(n)O(n) O(n)O(n)
    遍历 O(n)O(n) O(n)O(n) O(n)O(n) O(n)O(n)
    头部插入/删除元素 O(1)O(1) O(n)O(n) O(1)O(1) O(n)O(n)
    尾部插入/删除元素 O(n)O(n) O(n)O(n) O(n)O(n) O(n)O(n)
    中间插入/删除元素 O(n)O(n) O(n)O(n) O(n)O(n) O(n)O(n)
    查找元素 O(n)O(n) O(n)O(n) O(n)O(n) O(n)O(n)

    可以看到,除了在头部插入/删除元素外,各种链表的其他操作的时间复杂度都是一样的。循环链表因为尾结点的next域(类似C++中的指针)要指向头结点,所以每当在头部插入/删除元素时,都需要遍历链表找到尾结点从而修改其next域,这样就提高了时间复杂度。

    关于头结点

    需要说明的是,文章上述部分以及代码中所提到的头结点应该叫做首元结点(链表中第一个元素所在的结点)会更为准确。
    通常我们说的头结点是首元结点之前的一个结点,它的数据域可以不去定义,也可以存储链表长度等信息。而这个时候头指针就指向头结点而不是首元结点了。也就是说链表的头指针始终保存的是链表的地址,无论这个链表有没有头结点。
    设置头结点的主要作用为(参考链接):

    • 对带头结点的链表,在表的任何结点之前插入结点或删除表中任何结点,所要做的都是修改前一结点的指针域,因为任何元素结点都有前驱结点。若链表没有头结点,则首元素结点没有前驱结点,在其前插入结点或删除该结点时操作会复杂些。
    • 对带头结点的链表,头指针是指向头结点的非空指针,因此空表与非空表的处理是一样的。
      详细信息还可以参考这篇文章:链表头结点存在的意义
      然后关于头结点的使用我们再看一道牛客网上的题目吧:

    如果一个链表的最常用的操作是在末尾插入结点和删除结点,则选用()最节省时间。
    A. 带头结点的双循环链表
    B. 单循环链表
    C. 带尾指针的单循环链表
    D. 单链表

    这道题的答案应该是A。A中可以利用头结点的数据域存储尾结点的地址,那么每次插入和删除就可以直接访问尾结点,时间复杂度为O(1)O(1)。而其他三种链表中,单链表和单循环链表插入时都需要找到尾结点,时间复杂度为O(n)O(n),而带尾指针的单循环链表插入元素时间复杂度为O(1)O(1)。在末尾删除元素时,剩下的三种链表都需要找到倒数第二个结点,时间复杂度为O(n)O(n)。综上,选择A最节省时间。
    该题在牛客网上的链接:题目讨论

    展开全文
  • DS09-实现循环双链表

    2019-02-18 18:47:49
    循环双链表存在许多优点,比如可以实现时间复杂度均为O(1)的栈和队列,是对于单链表的优化,实现时注意每个节点的两个指针域都要进行维护. 代码如下: /** * 实现循环双链表 * @author ChenZhuJi * * @param &lt...

    循环双链表存在许多优点,比如可以实现时间复杂度均为O(1)的栈和队列,是对于单链表的优化,实现时注意每个节点的两个指针域都要进行维护.
    代码如下:

    /**
     * 实现循环双链表
     * @author ChenZhuJi
     *
     * @param <E>
     */
    public class LoopDoubleLinkedList<E> {
    	private class Node {
    		@SuppressWarnings("unused")
    		Node last,next;
    		E e;
    		public Node(Node last,E e,Node next) {
    			this.last = last;
    			this.e = e;
    			this.next = next;
    		}
    		public Node() {
    			this(null,null,null);
    		}
    		@Override
    		public String toString() {
    			return e.toString();
    		}
    	}
    	
    	private Node dummyHead;	//虚拟头节点
    	private int size;//链表长度
    	
    	public LoopDoubleLinkedList() {
    		dummyHead = new Node();
    	}
    	
    	public boolean isEmpty() {
    		return size == 0;
    	}
    	public int getsize() {
    		return size;
    	}
    	
    	/**
    	 * 向循环双链表中指定索引添加元素
    	 * @param index 索引值
    	 * @param e 添加的元素
    	 */
    	public void add(int index,E e) {
    		if(index < 0 || index > size ) {
    			throw new IllegalArgumentException("索引越界");
    		}
    		if( isEmpty() ) {		//当链表为空时添加第一个节点
    			Node newNode = new Node(dummyHead, e, dummyHead);
    			dummyHead.next = newNode;
    			dummyHead.last = newNode;
    			size ++;
    			return;
    		} else {		//当链表不为空时的操作
    			Node pre = dummyHead;
    			for(int i = 0; i <index; i++) {
    				pre = pre.next;
    			}
    			Node newNode = new Node(pre, e, pre.next);
    			pre.next = newNode;
    			pre.next.next.last= newNode;
    			size ++;
    			return;
    		}
    	}
    	
    	/**
    	 * 向循环双链表表头添加元素
    	 * @param e 要添加的元素
    	 */
    	public void addFirst(E e) {
    		add(0, e);
    	}
    	
    	/**
    	 * 向循环双链表表尾添加元素
    	 * @param e 要添加的元素
    	 */
    	public void addLast(E e) {
    		add(size,e);
    	}
    	
    	/**
    	 * 删除循环列表中指定索引的元素,返回被删除的元素
    	 * @param index 索引值
    	 * @return 被删除的元素
    	 */
    	public E remove(int index) {
    		if( isEmpty() || index < 0 || index >= size) {
    			throw new IllegalArgumentException("链表已经为空或索引越界!");
    		}
    		Node pre = dummyHead;
    		for(int i = 0; i < index; i++) {
    			pre = pre.next;
    		}
    		Node ret = pre.next;
    		ret.next.last = pre;
    		pre.next = ret.next;
    		ret.last = null;
    		ret.next = null;
    		size --;
    		return ret.e;
    	}
    	
    	/**
    	 * 删除循环双链表中的第一个元素
    	 * @return 被删除的元素
    	 */
    	public E removeFirst() {
    		return remove(0);
    	}
    	
    	/**
    	 * 删除循环双链表中的最后一个元素
    	 * @return 被删除的元素
    	 */
    	public E removeLast() {
    		return remove(size -1);
    	}
    	
    	/**
    	 * 获取链表中指定索引的节点的元素
    	 * @param index 索引值
    	 * @return 元素值
    	 */
    	public E get(int index) {
    		if(index < 0 || index >= size ) {
    			throw new IllegalArgumentException("索引越界");
    		}
    		Node pre = dummyHead;
    		for(int i = 0; i <= index; i++) {
    			pre = pre.next;
    		}
    		return pre.e;
    	}
    	
    	/**
    	 * 获取链表中第一个结点的元素值
    	 * @return 第一个元素
    	 */
    	public E getFirst() {
    		return get(0);
    	}
    	
    	/**
    	 * 获取链表中最后一个节点的元素值
    	 * @return 最后一个元素值
    	 */
    	public E getLast() {
    		return get(size -1);
    	}
    	
    	/**
    	 * 将链表中指定索引的节点值设置为e
    	 * @param index 索引值
    	 * @param e 更改的节点值
    	 */
    	public void set(int index,E e) {
    		if(index < 0 || index >= size ) {
    			throw new IllegalArgumentException("索引越界");
    		}
    		Node pre = dummyHead;
    		for(int i = 0; i <= index; i++) {
    			pre = pre.next;
    		}
    		pre.e = e;
    	}
    	
    	/**
    	 * 判断链表中是否包含某个元素e
    	 * @param e 节点元素值
    	 * @return 是否包含
    	 */
    	public boolean contains(E e) {
    		Node pre = dummyHead;
    		while(pre.next != dummyHead) {
    			pre = pre.next;
    			if(pre.e.equals(e)) {
    				return true;
    			}
    		}
    		return false;
    	}
    	
    	@Override
    	public String toString() {
    		StringBuilder sb = new StringBuilder("LoopDoubleLinkedList: size = "+ size +", [ dummyHead <=>");
    		Node pre = dummyHead;
    		while(pre.next != dummyHead) {
    			pre = pre.next;
    			sb.append(pre.e + " <==> ");
    		}
    		sb.append("dummyHead ]");
    		return sb.toString();
    	}
    	
    	public static void main(String[] args) {
    		LoopDoubleLinkedList<Integer> ldll = new LoopDoubleLinkedList<Integer>();
    		for(int i = 0; i < 5; i++) {
    			ldll.addLast(i);
    			System.out.println(ldll);
    		}
    		ldll.removeLast();
    		System.out.println(ldll);
    	}
    }
    
    展开全文
  • 4.时间复杂度比较 删除结点中“值等于某定值”的结点: 查找:O(n),删除O(1) 删除结点中指定结点指向的结点 单向:O(n) 找前驱 双向:O(1) 5.数组vs链表 操作 数组 链表 插入/删除 O(n) O(1) 随机访问 O...
  • 循环链表前言一、循环单链表的初始化二、判断是否为空或表尾结点三、循环双链表的初始化四、循环双链表的插入与删除 前言 对于循环单链表而言,在进行插入和删除时,可以让指针指向尾部,对于表头(通过尾部找到头部...
  • 区别: 1. 无头单向非循环链表:结构简单,一般不会单独用来存数据。实际中更多是作为其他数据结构的子结 构,如哈希桶、图的邻接表等等。...中间或前面部分的插入删除时间复杂度为O(n);并且增容的代价比较大 ...
  • 单链表有一个大问题就是访问后继结点比较方便,但是如果访问前驱结点,就需要从头开始来一遍,时间复杂度为O(n),这就很让人不爽了,所以就有了双链表。 顾名思义,双链表就是结点中有两个指针prior和next,分别...
  • 双向循环链表

    2014-08-14 18:01:14
    用c++实现的双向循环链表,实现时间复杂度为1,用指针传递值,功能完整
  • 你看 本来你获取第一个结点的时间复杂度是 O(1) ,获取最后一个结点的时间复杂度是O(n) 但是我是用了循环链表,我有个指针直接指向了尾结点,而且这个指针的下一个结点就是头结点(或者第一个元素结点)
  • 单链表结点中只有一个指向其后继的指针,这使得单链表只能从头结点依次顺序的向后遍历,访问后继结点时间复杂度为O(1),访问...此外,双链表可以很方便地找到其前驱结点,因此,插入,删除结点算法的时间复杂度为O(1)
  • 问题描述在电路分析中,通常以图论为数学工具,进行建模,求解。我们只研究二端元件,可以将电路中的每一个元件用一条边来表示,元件的端点用顶点来表示。...连接一个顶点的时间复杂度是O(n)。断开一个...
  • 链表 : 数据结构分析 数组地址值是连续的,链表地址值...头节点:记录基地址,尾节点,指向空,在链表中查询数据,时间复杂度O(n),需要遍历,删除数据的时候,因为不需要保持连续性,所以时间复杂度为O(n). ...
  • 在实现队列的链表结构中,时间复杂度最优的是: 仅设置头指针的单循环链表 仅设置尾指针的单循环链表 仅设置头指针的双向链表 仅设置尾指针的双向链表 答案 2 前提:队列中的结点从队尾插入,从队头删除;队列中的结点...
  • 一、单链表、循环单链表、循环双链表各自特点 链表是一种常见的基础数据结构,是一种线性表,但是并不会按线性的顺序存储数据,而是在每个节点里存到下一个节点的指针。由于不须按顺序存储,链表在插入的时候可以...
  • 单链表、双向链表循环链表

    千次阅读 2019-07-26 14:26:09
    常见链表 学习三种常见的链表结构,他们分别是:单链表、双向链表循环链表。 单链表 单链表有两个较特殊节点,头结点...但相对于数据的插入删除需要做大量的搬移操作,链表的插入,删除的时间复杂度为O(1)。但是链...
  • 文章目录单向循环链表 circular linked list 不用头指针,而用尾指针从单向链表循环链表:把尾结点指针从空指针改为指向头结点再到访问首结点和尾结点的时间复杂度都为O(1)的循环链表:撤掉头指针,改用尾指针双向...
  • 5.双链表循环链表 双链表 如果某链表经常进行查找结点前驱的操作,我们希望查状前驱的时间复杂度也达到O(1),这时可以用空间换时间:即每个结点再增加一个指向前驱的指针域prior,使链表可以进行双向查找,这种...
  • 文章目录双链表与循环链表双链表单链表 VS 双链表双链表的初始化(带头结点)双链表的插入双链表的删除双链表的遍历循环链表循环单链表循环双链表 双链表与循环链表 双链表 单链表 VS 双链表 单链表:无法逆向检索,...
  • 写在前面的话: 版权声明:本文为博主原创文章,转载请注明出处! 博主是一个小菜鸟,并且非常玻璃心!...在单链表中,我们设了next指针,这使得我们查找下一个结点的时间复杂度为O(1),但是如果我们想要查找...
  • 四种常见的链表包括:单向链表,单向循环链表,双向链表,双向循环链表。要实现的链表操作包括is_empty() 判断链表是否为空length() 求链表长度traversing() 遍历所有节点元素add() 头部添加节点append() 尾部添加...
  • 为什么要引入双链表:单链表只能从头结点开始依次的往后遍历,当需要访问前一个结点时,时间复杂度达到了O(n),因此引入了双链表解决这一问题。 双链表的一个结点有两个指针prior和next,分别指向前驱结点和后继...
  • 四种常见的链表包括:单向链表,单向循环链表,双向链表,双向循环链表。 要实现的链表操作包括 - is_empty() 判断链表是否为空 - length() 求链表长度 - traversing() 遍历所有节点元素 - add() 头部添加节点 - ...
  • 访问后继节点时间复杂度为O(1),访问前驱节点为O(n)。 为了克服这个缺点,引入双链表。 1、双链表单个节点。 prior data next prior为前驱指针域 data为数据域 next为后继指针域 节点类型描述如下: ...
  • 这学期的数据结构课有讲到链表,所以再来温故一下,毕竟温故知新嘛。 链表与数组的区别 ...数组利用下标定位元素,时间复杂度为O(1),链表在最坏情况下是O(n);即在随机性查找上数组比链表更...
  • 链表的种类有很多。我们常常会用到的链表有:单向链表、双向链表...我们不必在创建时指定链表的长度,因为链表可以无限的插入节点延伸,且插入和删除数据时,其时间复杂度都是 O(1)。 1. 单向链表 1.1 单向链表结构...
  • 不同链表的简单总结】 1.基本单链表--首端插入和删除时间复杂度为O(1),定位操作和尾操作时间复杂度为O(n) ...双链表--两端插入和删除的时间复杂度为O(1) 链表的一些优点】 1.表结构是由一些链接起来...
  • 如果算法中需要频繁地找某结点的前趋结点,单链表的解决方式是遍历整个链表,增加算法的时间复杂度,影响整体效率。 为了快速便捷地解决这类问题,在单向链表的基础上,给各个结点额外配备一个指针变量,用于指向每...
  • 如果算法中需要频繁地找某结点的前趋结点,单链表的解决方式是遍历整个链表,增加算法的时间复杂度,影响整体效率。为了快速便捷地解决这类问题,在单向链表的基础上,给各个结点额外配备一个指针变量,用于指向每个...
  • 双向循环链表简介

    2020-09-18 16:22:46
    点时就遇到最高时间复杂度O(n),遍历一周; 双向循环链表则只需要O(1),详细代码如下; 定义链表结点 给出了两个指针prior 和 next,一个指向前驱结点,一个指向后继结点; struct DulNode{ string ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 466
精华内容 186
关键字:

循环双链表时间复杂度