精华内容
下载资源
问答
  • 数组链表存储结构

    千次阅读 2020-09-18 11:19:13
     链表中的元素在内存中不是顺序存储的,而是通过存在元素中的指针联系到一起。 2、数组必须事先定义固定的长度,不能适应数据动态的增减的情况。当数据增加时,可能超出原先定义的元素个数;当数据减少时,造成内存...

    本文主要说一下数组、链表、二叉树、HashMap存储结构,及其优缺点。

    数组和链表

    1、数组是将元素在内存中连续存放。
       链表中的元素在内存中不是顺序存储的,而是通过存在元素中的指针联系到一起。
    2、数组必须事先定义固定的长度,不能适应数据动态的增减的情况。当数据增加时,可能超出原先定义的元素个数;当数据减少时,造成内存浪费;
       链表动态地进行存储分配,可以适应数据动态地增减的情况。
    3、(静态)数组从栈中分配空间,对于程序员方便快速,但是自由度小;
        链表从堆中分配空间,自由度大但是申请管理比较麻烦。

    黄色数组,蓝色链表结构

    链表:单链表、双向链表、循环链表

    由其存储结构可以看出:数组在查询效率比较高直接通过索引就查询,插入和删除效率低,因为要移动后面所有元素。链表在查询效率上低,但是插入删除效率高

    二叉树

    几种特殊的二叉树:满二叉树、完全二叉树、平衡二叉树

    满二叉树:全是满的

    完全二叉树:如果二叉树中除去最后一层节点为满二叉树,且最后一层的结点依次从左到右分布,则此二叉树被称为完全二叉树。

    平衡二叉树:

    二叉树可以采用顺序存储结构和链式存储结构。对于完全二叉树和满二叉树采用顺序存储结构比较适合

    1)一个完全二叉树如下:

    2)但是对于一般的二叉树如下,是不是很浪费空间。

    再看极限的,abcd4个元素需要15个长度的数组来存,实在是太浪费了。

    3)在2)中我们呢看到这种不适合用数组。

    我们用二叉链表

    为了方便访问某结点的双亲,还可以给链表结点增加一个双亲字段parent,用来指向其双亲结点。这种叫三叉链表

    HashMap

    数组+链表+红黑树。

    传入的数组长度必须是2的指数次幂。如果传入13,在put会转成大于13最接近2的指数次幂的值,那就是16了。

    为什么必须是2的指数次幂?

    先留着

    hash冲突?

    不同的entry通过哈希函数等计算出来下标一样,就叫hash冲突

    解决hash冲突?

    一种是开放寻址法,另一种是链表法,好像好有其他方法。

    开放寻址法:

    比如计算出Entry6的下标是2,但是2下标已经有值了,就往后找,3也被占了,4没有则放入4.

    链表法:

    链表法也正是被应用在了HashMap中,HashMap中数组的每一个元素不仅是一个Entry对象,还是一个链表的头节点。每一个Entry对象通过next指针指向它的下一个Entry节点。当新来的Entry映射到与之冲突的数组位置时,只需要插入到对应的链表中即可

    Java 1.8以后是数组+单链表+红黑树(链表>8时转成红黑树)

    链表缺点就是查询效率低,如果链表太长,那么效率也低,红黑树是接近于平衡的二叉树,远远高于链表的查询效率。

    展开全文
  • 第一种方法,正序循环数组: 1.设置哨兵节点 2. 把哨兵节点sentineNode赋值给一个临时节点tempNode.循环数据1 进来的时候,建立一个新的节点newNode,赋值为1. 3. 需要注意的是,哨兵节点sentineNode现在是整个链表...

    给定数组:[1,2,3,4,5,6,7,8].转成链表结构

    第一种方法,正序循环数组:

    1.设置哨兵节点
    在这里插入图片描述
    2. 把哨兵节点sentineNode赋值给一个临时节点tempNode.循环数据1 进来的时候,建立一个新的节点newNode,赋值为1.

    在这里插入图片描述
    3. 需要注意的是,哨兵节点sentineNode现在是整个链表的head节点.然后我们把临时节点指向newNode.
    在这里插入图片描述我们遵循上面的步骤即可。

    代码如下:

        @Data
        public class Node {
            int val;
            Node next;
           public  Node(int x) { val = x; }
        }
    
    public Node changeArrayToNode(int[] arr) {
            if(arr == null || arr.length <= 0){return null;}
    
            Node sentineNode = new Node(0);  //建立哨兵节点
            Node tempNode = sentineNode;  //tempNode变量指向哨兵节点
            for(int i = 0; i < arr.length; i++) {
                Node newNode = new Node(arr[i]);
                tempNode.next = newNode;    //临时节点‘后继指针’指向新节点
                tempNode = newNode;        //把新节点赋给临时变量tempNode
            }
            return sentineNode.next;
        }
    

    时间复杂度与空间复杂度都是O(n)

    第二种方法:逆序遍历数组,从链表的未节点开始赋值

    逆序遍历和正序遍历原理是一样的,这里加深理解。

    在这里插入图片描述
    逆序遍历进来第一个值是8,我们创建一个新节点NewNode,并且让headNode变量指向NewNode; 进来第一个数据7的时候,我们把7的newNode节点的‘后继指针’指向刚才的headNode节点。然后再把headNode变量指向7的newNode节点。依次循环。

    代码如下:

    public Node changeArrayToNode2(int[] arr) {
            if(arr == null || arr.length <= 0){return null;}
    
            Node headNode = null;
            for(int i = arr.length - 1; i >= 0; i--) {
                Node newNode = new Node(arr[i]);
                newNode.next = headNode;
                headNode = newNode;
            }
            return headNode;
        }
    

    总之,我们在链表问题的时候,要多想一下临时节点与哨兵节点。

    展开全文
  • 数组链表存储详解

    千次阅读 2018-09-25 21:35:25
    顺序表的存储:由存储空间一段连续的地址组成,一边表现为数组,可以通过下标跟初始位置确定第i个元素的位置,因此顺序表的优点是便于查询数据。 链表:由存储空间内不连续的空间组成,每一个存储单元中除了存储所...

    顺序表的存储:由存储空间一段连续的地址组成,一边表现为数组,可以通过下标跟初始位置确定第i个元素的位置,因此顺序表的优点是便于查询数据。

    链表:由存储空间内不连续的空间组成,每一个存储单元中除了存储所需数据,还存储下一个存储单元的位置,优点是方便扩充跟插入节点。

    下边说一说顺序表(数组)跟链表的增删改查的时间复杂度:

    数组:

    1、有序数组:

    添加数据:时间复杂度 :O(n)

    原因:因为有序数组,我们查找时采用的是二分查找,时间复杂度O(log n),找到数据应该存放的位置后,将插入位置跟插入位置以后的数据统一后移一个单位,此时时间复杂度O(n),总的时间复杂度O(n)+O(log n)属于O(n)级别。

    查找数据:时间复杂度 :O(log n)

    原因:因为有序数组,我们查找时采用的是二分查找,时间复杂度O(log n),以2的指数级别缩减查找长度。

    删除数据:时间复杂度 :O(n)

    原因:因为有序数组,我们查找时采用的是二分查找需要删除的数据,时间复杂度O(log n),删除完成以后需要将删除位置后边的数据前移一个位置,时间复杂度O(n),总的时间复杂度O(n)+O(log n)属于O(n)级别。

    修改数据:时间复杂度 :O(n)

    原因:因为有序数组,我们将数据修改后,需要进行一次数据比较移动,因此时间复杂度属于O(n)级别

    2、无序数组:

    添加数据:当数组中还有空间时,时间复杂度 :O(1),当数组中无空间时,需要重新开辟空间,将以前的元素复制过来,时间复杂度 :O(n),

    查找数据:时间复杂度 :O(n)

    原因:因为数组无序,我们查找时时必须遍历整个数组,因此时间复杂度为O(n)。

    删除数据:时间复杂度 :O(n)

    原因:因为数组无序,我们必须遍历整个数组找到要删除的数据,时间复杂度为O(n),删除完成后还需要将删除位置后边的数据前移一个位置,时间复杂度O(n),总的时间复杂度为2O(n),属于O(n)级别。

    修改数据:时间复杂度 :O(n)

    原因:因为数组无序,我们必须遍历整个数组进行修改,因此时间复杂度为O(n)。

    链表:

    增加数据:链表有序时:O(n) ,无序时O(1)

    原因:因为有序链表无二分查找一说,所以我们需要遍历整个链表去找到插入位置,无需链表只需要在表头或者表尾添加数据即可。

    删除数据:O(n)

    原因:我们需要遍历整个链表去查找需要删除的数据。

    修改数据:O(n)

    原因:我们需要遍历整个链表去查找需要修改的数据。

    查找数据:O(n)

    原因:我们需要遍历整个链表去查找需要的数据。链表有序无序对查找数据的时间复杂度级别不影响,因为有序无序都需要遍历一遍链表,但是相对于无序,有序还是更快一点的,毕竟不需要遍历完链表,比遍历完边表肯定要快。

    展开全文
  • c++使用数组实现双链表list

    千次阅读 2018-10-25 22:41:20
    List 是标准类库中的一个类,可以简单视之为双向链表,以线性列的方式管理物件集合。list 的特色是在集合的任何位置增加或删除元素都很快,但是不支持随机存取。list 是类库提供的众多容器(container)之一,除此...

    List 是标准类库中的一个类,可以简单视之为双向链表,以线性列的方式管理物件集合。list 的特色是在集合的任何位置增加或删除元素都很快,但是不支持随机存取。list 是类库提供的众多容器(container)之一,除此之外还有vector、set、map、…等等。
    我们可以使用数组实现list。
    这里我只实现int类型的list,其他类型可以使用模板实现。

    这是list的方法

    #include<iostream>
    using namespace std;
    typedef int T; 
    class ArrayList2 { 
       public:
        ArrayList2();//构造空线性表
        ArrayList2(int n);//构造长度(即size)为n的线性表
        ~ArrayList2();//析构函数 
    	int find(T &x) const;//如果存在,则返回第一次出现的x的位置,否则返回-1。
    	void push_back(const T&x); //将x放在最后一项
        void insert(int position,const T&x); 
        //如果0 = <position <= size(),则将x插入到位置位置。
        //否则,动作为空。
        ArrayList2(const ArrayList2& c);//拷贝构造函数 
        const ArrayList2& operator =(ArrayList2& c);//重载=符号 
        int size()const;//返回线性表中元素个数
        int capacity() const; //返回数组的容量
        bool full()const; //如果表满,返回true,否则,返回false。
        bool empty()const{
        	return count==0;
    	}//如果表空,返回true,否则,返回false。
        void clear();//将表置为空表
    	
        void traverse(void (* visit)(T& a)) ;
        //将函数(* visit)应用到表中每个元素上.void 
        void  retrieve(int position,T&x) const;
        //如果0 = <position <= size() - 1,则用x返回位于position的元素
        //否则,动作为空。
        void replace(int position,const T&x);
        //如果0 = <position <= size() - 1,则将位置position的元素修改成x。
        //否则,动作为空。
        void erase(int position,T&x);
        //如果0 = <position <= size() - 1,则将位置position的元素删除,
        //并将删除的元素用x返回,否则,动作为空。
        void erase(int position);
        T&operator [](int position);//重载[]符号 
        //如果0 = <position <= size() - 1,则返回位于position的元素
        //否则,动作为空。
       
        
    private:
        T * elems; 
        int count; //记录数组elems中存储的元素个数
        int arraySize ; // 数组长度
    };
    
    
    

    下面是方法的实现`

    ArrayList2::ArrayList2(){
        	this->elems=NULL;
        	this->count=0;
        	this->arraySize=0;
    	}
    ArrayList2::ArrayList2(int n){
        	this->elems=new int[n];
        	this->count=n;
        	for(int i=0;i<n;i++)
        	this->elems[i]=0; 
        	this->arraySize=n;
    	} 
     
    ArrayList2::ArrayList2(const ArrayList2& c){
        	this->elems=new int[c.capacity()];
        	for(int i=0;i< c.size();i++)
        	this->elems[i]=c.elems[i];
        	this->count=c.size();
        	this->arraySize=c.capacity();
    	}
    ArrayList2::~ArrayList2(){
        	delete[] this->elems;
        	elems=NULL;
    	} 
    void ArrayList2::clear(){
    	     for(int i=0;i<this->count;i++)
    	     this->elems[i]=0;
    		 this->count=0; 
        }
        
    void ArrayList2::push_back(const T& x){
    		if(this->full()){
    		//判断是否数组已满 
    		T *tmp=new int[this->arraySize+1];
    		for(int i=0;i<this->size();i++)
    		tmp[i]=elems[i];
    		delete []elems;
    		elems=tmp;
        	this->elems[count]=x;
        	count++;
    		this->arraySize++;}
        	else {
        		this->elems[count]=x;
        		count++;
        		
    		}
    	}
    void ArrayList2::insert(int position,const T &x ){
        	if(position>=0&&position<=this->size()){
        		//cout<<"count="<<this->count<<endl;
        		count++;
        		if(count>this->arraySize){
        			T *tmp=new int[count];
    		        for(int i=0;i<this->size();i++)
    		        tmp[i]=elems[i];
    	        	delete []elems;
    		        elems=tmp;
        	        //this->elems[count-1]=x;
        	        
    		        this->arraySize++;
    			}
        	 
        		for(int i=this->count-1;i>position;i--){
        			this->elems[i]=this->elems[i-1];
    			}
    			this->elems[position]=x;
    			
    		}
    	}
    void ArrayList2::erase(int position ,T &x){
        	if(position>=0&&position<=this->size()-1){
        		x=this->elems[position];
        		for(int i=position;i<this->size()-1;i++){
        			this->elems[i]=this->elems[i+1];
    			}
    			this->count--;
    		}
        
    	}
    void ArrayList2::erase(int position){
        	if(position>=0&&position<=this->size()-1){
        		//x=this->elems[position];
        		for(int i=position;i<this->size()-1;i++){
        			this->elems[i]=this->elems[i+1];
    			}
    			this->count--;
    		}
    	}
    int ArrayList2::find( T& x)const {
        	for(int i=0 ; i<this->size(); i++ ){
        		if(x==this->elems[i]){
        			return i;
    			}
    		}
    		return -1;
    	} 
    void ArrayList2::retrieve(int position,T &x)const {
        	if(position>=0&&position<=this->size()-1)
    		x= this->elems[position];
        	
    	}
    void ArrayList2::traverse(void(*visit)(T&a)){
        	for(int i=0;i<this->size();i++)
        	(*visit)(elems[i]);
    	}
    const ArrayList2& ArrayList2::operator =( ArrayList2 &c) {
            count=c.size();
            arraySize=c.capacity();
        	this->elems=new int[c.capacity()];
        	for(int i=0;i< count;i++)
        	this->elems[i]=c.elems[i];
        	return *this;
    	}
    void ArrayList2::replace(int position,const T &x){
        	if(position>=0&&position<=this->size()-1)
    		 this->elems[position]=x;
        
    	}
    int ArrayList2::capacity() const{
        	return this->arraySize;
    	}
    int ArrayList2::size() const {
        	return this->count; 
    	
    	} 
    bool ArrayList2::full()const {
        	return this->count==this->arraySize;
    	}
    T& ArrayList2::operator [](int position){
            if(position>=0&&position<size()){
            	return this->elems[position];
    		}
    	}
    

    好了,使用数组实现list完成!!!
    `

    展开全文
  • 如何用数组来模拟实现链表

    千次阅读 2020-10-18 22:08:39
    习惯了定义一个Node类型作为链表的节点,如此一来,无论是插入、删除,还是查找,代码实现都非常便捷。但如果用数组来实现链表,又该如何去考虑呢?
  • 数组链表的比较

    2020-03-06 12:15:55
    链表恰好相反,链表中的元素在内存中不是顺序存储的,而是通过存在元素中的指针联系到一起。比如:上一个元素有个指针指到下一个元素,以此类推,直到最后 一个元素。 访问元素数组如果应用需要快速访问数据,...
  • 数组链表是两种基本的数据结构,他们在内存存储上的表现不一样,所以也有各自的特点 数组 一、数组的特点 1.在内存中,数组是一块连续的区域 2.数组需要预留空间 在使用前需要提前申请所占内存的...
  • HashMap实现原理,利用数组链表存储元素 必备面试题,必考项目之一,整理了一下发出来。 hashmap底层: 1.底层数组+链表实现,可以存储null键和null值,线程不安全。 HashMap的主干是一个Entry数组。Entry是...
  • 这里不得不介绍两个概念:顺序存储和随机存储,主要介绍将通过数组(代表顺序存储)和链表(代表随机存储)进行展开。 数组 数组存储方式为顺序存储,简单的来说,就是系统为待存储内容在内存中寻找一块连续...
  • java 数组链表

    2020-06-17 21:29:03
    线性表包括数组链表 1.数组特点 ①.存储空间:连续的内存空间,存储在栈中。 ②.可以通过数组下标快速找到值,因为是一段连续的存储空间,所以根据第一个值和数组下标根据公式即可计算出当前需要寻找的值。 ③...
  • 1.数组转换为链表结构,主要思想可以按照头插法或尾插法,要手动生成一个新的结点,分配存储空间,然后按照顺序,将数组中对应的元素放在链表对应的数据区。 /* 用数组创建链表 */ Linklist ArrayToList(int *...
  • 因为是线性表,不能只讲链表,所以今天提一下静态链表以及数组链表、静态链表之间的对比。 数组基本结构没得说,插入和删除的操作也是有的(虽然看着不比较诡异) 一般是动态分配一个足够长的,记录有多少个元素后...
  • 数组是由有限个相同类型的变量所组成的有序集合,它可以进行元素的插入、删除、查找等操作,它的物理存储方式是顺序存储,访问方式是随机访问,利用下标查找数组元素的时间复杂度O[1],中间插入,删除数组元素的时间...
  • 数组元素进行增加或则删除 效率极低。 对数组元素进行前后位置的移动,效率极低。 需要提前知道需要的空间是多大,要不然只有分配很大,导致浪费很大的内存 优点: 相较于链表,C语言已经封装好了数组的相关...
  • 数组链表的区别

    千次阅读 多人点赞 2021-03-31 00:16:14
    数组链表的区别
  • 数组链表

    2020-12-16 14:16:06
    作为线性表的两种存储方式 —— 链表数组,这对相爱相杀的好基友有着各自的优缺点。接下来,我们梳理一下这两种方式。 数组其实是开辟了两个空间的,在内存中,数组的名由一个对应的内存地址保存数据,然后就是...
  • 本文先介绍线性表的几个基本组成部分:数组、单向链表(One-way LinkedList)、双向链表(two-way linked-list )。数组数组有上界和下界,数组元素在上下界内是连续的。存储10、20、30、40、50的数组的示意图如下...
  • 数组链表

    2020-05-26 19:49:28
    一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构,操作复杂。由于不必须按顺序存储链表在插入的时候可以达到O(1)的复杂度,比另一种线性表顺序表快得多, 但是查找一个...
  • 数组链表的区别浅析

    万次阅读 多人点赞 2018-08-17 16:08:43
    链表是一种上一个元素的引用指向下一个元素存储结构,链表通过指针来连接元素元素链表是线性表的一种,所谓的线性表包含顺序线性表和链表,顺序线性表是用数组实现的,在内存中有顺序排列,通过改变数组大小...
  • 图解数组链表

    2018-10-31 18:14:28
    有时候需要在内存中存储一系列元素。 比如待办事项,用数组还是链表呢? 数组意味着所有待办事项在内存中都是相连...链表的每个元素存储了下一个元素地址,从而使得一系列的随机的内存地址串在了一起。 只...
  • 我的c#学习之路(二)——数组链表和字典 注:由于本人学习过c++,所以就基本上跳过了运算符介绍以及各种... 在c#中只能使用内建数组,可分为一维数组和多维数组数组必须事先定义固定的长度(元素个数),不能...
  • 线性表之数组链表

    2019-08-02 15:10:14
    了解线性表,然后对数组链表进行介绍,知道他们的区别和联系。
  • 数组链表的区别?

    千次阅读 2020-10-31 19:25:23
    今天来说下两种最基本的数据结构——数组链表,它们无处不在!下面我们来一一介绍下他们,首先了解下内存分配的! 内存的工作原理 假设你去看演出,需要将东西寄存。寄存处有一个柜子,柜子有很多抽屉。 每个抽屉...
  • 数据结构之数组链表的区别

    万次阅读 多人点赞 2019-03-27 19:03:59
    第一题便是数据结构中的数组链表的区别 数组(Array) 一、数组特点: 所谓数组,就是相同数据类型的元素按一定顺序排列的集合;数组存储区间是连续的,占用内存比较大,故空间复杂的很大。但数组的二分查找...
  • 线性表(Linear List):数组链表、队列、栈 非线性表:树 图 连续的内存空间和相同类型的数据 性能 低效“插入”和“删除” 警惕 数组越界 数组链表的区别 “链表适合插入、删除,时间复杂度 O(1);...
  • 数组存储区间连续,占用内存严重,...实现原理:用一个数组存储元素,但是这个数组存储的不是基本数据类型。HashMap实现巧妙的地方就在这里,数组存储元素是一个Entry类,这个类有三个数据域,key、value(键值对
  • 数据结构(数组结构、链表结构)

    千次阅读 2018-02-05 16:30:20
    数据结构: 数据结构是指相互之间存在一种或多种特定关系的数据元素的集合 1.集合 数据结构中的元素之间除了“同属一个集合” 的相互关系外,别无其他关系; 2.线性结构 数据结构中的元素存在一对一的...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 194,418
精华内容 77,767
关键字:

数组元素存储链表的首地址