Java面向对象基础知识之数组和链表

数组的优点：

  • 随机访问性强
  • 查找速度快
    • 数组要求是一块连续的内存空间来存储，这就要求在物理上这一片空间是连续的，每个元素都有指定的索引index指向内存地址，因此查询对时候，可根据index快速找到对应地址存储的信息，此为查询快.

数组的缺点：

  • 插入和删除效率低

    • 数组进行增删的时候，就必须将目标位置后的所有元素都整体移动，因此就比较耗时，此为增删慢.
  • 可能浪费内存
  • 内存空间要求高，必须有足够的连续内存空间。
  • 数组大小固定，不能动态拓展

链表的优点：

  • 插入删除速度快

    • 链表在物理上是动态地分配储存空间，不要求连续性，但是要求逻辑上的连续。它需要存储每个元素在内存中的地址，以及它相邻元素的地址，然后像链条一样把各元素链起来，保证了在逻辑上的连续性。

比如:

单链表，每个元素除了存储本身的值外，还存储了前驱的引用，也就是存储了前驱所在的内存地址信息。

双链表就是不仅存储了前驱的引用还存储了后继的引用.

  • 增加元素的时候，只需给增加元素添加其前元素或后元素的地址；删除元素的时候，修改目标元素前驱和后驱的首位连接地址. 故此为增删快。
  • 内存利用率高，不会浪费内存大小没有固定，拓展很灵活。

链表的缺点：

  • 不能随机查找，必须从第一个开始遍历，查找效率低

    • 由于没有像数组那样的索引，因此，查询的时候需要遍历整个链表所有元素的内存地址，然后才能确定目标元素，此为查询慢。

内存中的存储形式可以分为连续存储和离散存储两种。因此，数据的物理存储结构就有连续存储和离散存储两种，它们对应了我们通常所说的数组和链表。

因为数组是连续存储的，在操作数组中的数据时就可以根据离首地址的偏移量直接存取相应位置上的数据，但是如果要在数据组中任意位置上插入一个元素，就需要先把后面的元素集体向后移一位为其空出存储空间。

与之相反，链表是离散存储的，所以在插入一个数据时只要申请一片新空间，然后将其中的连接关系做一个修改就可以，但是显然在链表上查找一个数据时就要逐个遍历了。

考虑以上的总结可见，数组和链表各有优缺点。在具体使用时要根据具体情况选择。当查找数据操作比较多时最好用数组；当对数据集中的数据进行添加或删除比较多时最好选择链表。

数组就像身上编了号站成一排的人，要找第10个人很容易，根据人身上的编号很快就能找到。但插入、删除慢，要望某个位置插入或删除一个人时，后面的人身上的编号都要变。当然，加入或删除的人始终末尾的也快

链表就像手牵着手站成一圈的人，要找第10个人不容易，必须从第一个人一个个数过去。但插入、删除快。插入时只要解开两个人的手，并重新牵上新加进来的人的手就可以。删除一样的道理。

总结：

  • 数组静态分配内存，链表动态分配内存;
  • 数组在内存中连续，链表不连续;
  • 数组元素在栈区，链表元素在堆区;
  • 数组利用下标定位，时间复杂度为O(1)，链表定位元素时间复杂度O(n);
  • 数组插入或删除元素的时间复杂度O(n)，链表的时间复杂度O(1);

本篇文章就到这里了，希望能够给你带来帮助，也希望您能够多多关注我们的更多内容!

赞 (0)

相关推荐

  • Java面向对象的三大特征

    java面向对象的三大特征:"封装.继承.多态".更多Java技术知识,请登陆疯狂软件教育官网.微信搜索微信号:疯狂软件,参加2015年优惠活动,有机会获得优惠劵和代金劵. 以本文为例,User类中的变量为私有变量,只能通过创建对象(此时构造方法自动调用)来赋值. 外界只能通过公有方法api()来访问User类. Admin类继承了User类,调用了其构造方法,还重写了method_1方法,增加了一个特有方法power(). User文件 public class User { /**

  • Java 面向对象的特征解析与应用

    Java 面向对象的特征解析与应用

    ## 类和对象 * 面向对象与面向过程 面向过程:是指类似在C语言学习中,所写的代码都在主程序(main())中运行,非常的繁琐. 面向对象:首先创建一个类,类中包括对一个事物描述的性质(成员变量)和方法(成员方法). 面向对象是指对一个事物的描述. eg:对一个手机进行描述,创建一个名为phone的类. passage ...; public class phone { //成员变量 String name; double price; String color; //成员方法 call(St

  • Java面向对象的封装特征深度解析

    Java面向对象的封装特征深度解析

    目录 面向对象三大特征 封装 private关键字--实现类封装 访问器方法和更改器方法 包--类的集合 导入包 从人的角度理解包 不加访问权限--实现包封装 总结 在上一篇文章中,我们了解了面向对象的基础内容,这一篇将会更加深入地了解面向对象的特征. 面向对象三大特征 面向对象语言有三大特征: 封装 继承 多态 封装 对一个类实现封装,意味着限制其它类对该类数据的访问. 简单来讲,封装就是隐藏数据,就是保护对象的数据.对象,听起来总是那么地抽象,为了更好地理解封装,我将对象具体指向人,从人的角

  • Java面向对象之多态

    Java面向对象之多态

    目录 一.前言 二.什么是多态? 三.多态的实现条件 四.多态的访问特点 1.我们建一个service包放Animal类 2.再servic包下建一个impl包,包下放Cat类 3.我们在建一个controller包,在里面建一个动物测试类 4.弄完之后我们程序一运行 4.1为什么两个有区别呢? 五.多态的优点和缺点? 六.为什么要分开建包 一.前言 前面我们了解和学习了继承的使用,现在我们来学习三大面向对象之一的多态. 多态使java面向对象丰富起来,所以学好多态十分重要. 二.什么是多态?

  • Java 面向对象之继承篇详解原理与特点

    目录 一.前言 二.继承 什么是继承呢? 继承的好处与弊端 继承的使用场景? 继承的格式: 继承的特点: 重写的概念: super关键字 super和this的比较 一.前言 前面我也们讲述了相关封装的,现在我们先认识的继承的概念和使用. 二.继承 什么是继承呢? 继承在显示生活中也不少见,比如继承财产之类的,在我们java学习中也有类似的使用, 继承者称作子类也叫派生类,被继承者称作父类.基类或超类,objec类是所有类的父类 (后期介绍) 继承的好处与弊端 好处:就是提高了代码的维护性(多个

  • Java面向对象基础知识之枚举

    Java面向对象基础知识之枚举

    目录 一.枚举的定义 二.枚举的声明 三.枚举的转换 四.枚举的方法 五.标志枚举(二进制枚举) 总结 一.枚举的定义 枚举是一组命名整型常量.枚举类型是使用enum关键字声明的. C# 枚举是值类型.换句话说,枚举包含自己的值,且不能继承或传递继承. 二.枚举的声明 声明枚举的一般语法: enum <enum_name> { enumeration list }; 其中, enum_name指定枚举的类型名称. enumeration list是一个用逗号分隔的标识符列表. 枚举列表中的每个

  • Java面向对象基础知识之抽象类和接口

    抽象类(abstract): 抽象类不能创建实例,它只能作为父类被继承.抽象类是从多个具体类中抽象出来的父类,它具有更高层次的抽象.从多个具有相同特征的类中抽象出一个抽象类,以这个抽象类作为其子类的模板,从而避免了子类的随意性. (1) 抽象方法只作声明,而不包含实现,可以看成是没有实现体的虚方法 (2) 抽象类不能被实例化 (3) 抽象类可以但不是必须有抽象属性和抽象方法,但是一旦有了抽象方法,就一定要把这个类声明为抽象类 (4) 具体派生类必须覆盖基类的抽象方法 (5) 抽象派生类可以覆盖基

  • Java面向对象基础知识之委托和lambda

    委托定义类型,类型指定特定方法签名.可将满足此签名的方法(静态或实例)分配给该类型的变量,然后(使用适当参数)直接调用该方法,或将其作为参数本身传递给另一方法再进行调用.以下示例演示了委托的用法. using System; using System.Linq; public class Program { public delegate string Reverse(string s); static string ReverseString(string s) { return new st

  • Java面向对象基础知识之数组和链表

    数组的优点: 随机访问性强 查找速度快 数组要求是一块连续的内存空间来存储,这就要求在物理上这一片空间是连续的,每个元素都有指定的索引index指向内存地址,因此查询对时候,可根据index快速找到对应地址存储的信息,此为查询快. 数组的缺点: 插入和删除效率低 数组进行增删的时候,就必须将目标位置后的所有元素都整体移动,因此就比较耗时,此为增删慢. 可能浪费内存 内存空间要求高,必须有足够的连续内存空间. 数组大小固定,不能动态拓展 链表的优点: 插入删除速度快 链表在物理上是动态地分配储存空

  • Java面向对象基础知识之封装,继承,多态和抽象

    目录 一.封装 二.继承 三.多态 四.抽象 总结 一.封装 封装:是面向对象方法的重要原则,就是把对象的属性和行为(数据)结合为一个独立的整体,并尽可能隐藏对象的内部实现细节,就是把不想告诉或者不该告诉别人的东西隐藏起来,把可以告诉别人的公开,别人只能用我提供的功能实现需求,而不知道是如何实现的.增加安全性 public class Person { private String name; private int gender; private int age; public String

  • Java基础知识精通数组的使用

    目录 1.数组 2.数组定义格式 3.访问数组 4.遍历数组 前言:本文章正式踏入数组部分,今天来讲一下数组. 1.数组 数组是一组数据结构,用来储存一组相同类型值的集合. 数组就是一个容器. 数组就是个引用数据类型. 作用: 用来装数据,方便对数据进行管理操作. 特点: 一旦创建数组,就不能改变长度. 数组里面所有的元素的类型必须是相同数据类型的. 数组中既可以储存基本数据类型,也可以存储引用数据类型. 2.数组定义格式 格式一:元素的数据类型[] 数组的名字 = new 元素的数据类型[元素

  • Java异常基础知识解析

    Java异常基础知识解析

    Java程序运行的非正常现象叫做运行错误,根据其性质可分为两类:错误(Error)和异常(Exception); 他们有一个共同的父类(也是所有异常的顶级父类):Throwable. 异常类结构 Error Error(错误)由JVM生成并抛弃不做处理:此类错误通常与代码和执行的操作无关,是虚拟机中出现了比较严重的问题,程序本身无法解决(常见的错误有死循环.内存泄漏等). 一个常见的错误为Java虚拟机错误(VirtualMachineError),当JVM不再有继续执行操作所需的内存资源时,将

  • Java集合基础知识 List/Set/Map详解

    Java集合基础知识 List/Set/Map详解

    一.List Set 区别 List 有序,可重复: Set 无序,不重复: 二.List Set 实现类间区别及原理 Arraylist 底层实现使用Object[],数组查询效率高 扩容机制 1.6采用(capacity * 3)/ 2 + 1,默认容量为10: 1.7采用(capacity >> 2 + capacity)实现,位移动效率高于数学运算,右移一位等于乘以2倍: 读取速度快,写入会涉及到扩容,所以相对较慢. LinkedList底层采用双向链表,只记录 first 和 las

  • 详解java接口基础知识附思维导图

    详解java接口基础知识附思维导图

    接口: 官方的含义是---->java接口是一系列方法的声明,是一些方法特征的集合 疑问: 那为什么不用抽象类呢?把他们共有的方法集合起来放在一个抽象类里面,同样可以调用哇,但是反过来想一想如果这些方法,不是同一个类,就比如飞这个方法,飞机有飞这个方法,蚊子有飞这个方法,如果让他连同时继承拥有飞这个抽象类里面,是不符合单一职责原则的,所以我们可以提供一个飞的接口,飞机,蚊子来实现这个接口,那么飞机和蚊子就拥有飞的能力啦,这是我对接口的理解 因为最近在学习java 面向对象中的接口,就画了思维导图

  • Java面向对象基础之多态性,抽象类和接口

    一.多态性 多态是指一个对象可以拥有多种不同的形态,继承是实现多态的基础. 1.1 引用多态和方法多态 引用多态:父类引用可以指向本类的对象,也可以指向子类的对象 方法多态: 1.创建本类对象时,调用的方法为本类方法: 2.创建子类对象时,调用的方法为子类重写或继承的方法. 首先建立父类Animal,包含一个eat()方法,如下代码所示: public class Animal { public void eat(){ System.out.println("动物可以吃东西"); }

随机推荐