数据结构专题——线性表之顺序表及其 Java 实现

本贴最后更新于 2826 天前,其中的信息可能已经时移世异

上一篇博客中,博主为大家介绍了关于数据结构的三个基本概念:数据结构数据类型抽象数据类型

在本篇博客中,博主将为大家介绍本系列中第一个出场的数据结构——线性表。顾名思义,线性表就是一种具有像线一样性质的表。比如在操场上站成一列的学生们,总有一个打头,一个结尾,中间的任何一个学生都知道自己前一名同学是谁和后一名同学是谁,就像有一根线将他们串了起来一样。

像这种从逻辑上看,具有零个或多个数据元素的有限序列我们就称之为线性表(List).

让我们简单来解读一下线性表的概念。首先它是一个序列,也就是说在线性表中的元素之间是有顺序的,当这个线性表不为空时,除了第一个元素只有后继元素,最后一个元素只有前驱元素之外,其余的元素都有且只有一个前驱和一个后继。线性表中同样允许没有元素,这时我们称之为空表。

还记得我们在上一篇博客中提到的,数据结构是相互之间存在一种或多种特定关系的数据元素的集合,这种结构可以是逻辑结构或者是物理结构。上面对线性表的定义,明显是从逻辑结构上进行的。

那么如果从不同的存储形式(物理结构)上来看,在内存中顺序存储的线性表我们称之为顺序表,在内存中链式存储的线性表我们称之为链表。

也就是说,顺序表与链表也都是数据结构,它们是从物理存储结构角度上定义的线性表,可以看作是抽象的线性表在计算机编程语言中具体的实现。

接下来我们就一起来定义一下,线性表的抽象数据类型(ADT)

ADT List{ Data: 线性表中的数据对象集合为{a1,a2,a3... an},所有元素的数据类型必须都是DataType。 除了第一个元素a1只有后继元素,最后一个元素an只有前驱元素之外,其余的元素都有且只有一个前驱和一个后继。 Operation: int size(); //返回线性表中元素的个数 boolean isEmpty(); //检查线性表是否为空 boolean contains(Object o); //检查线性表是否包含某个元素 boolean add(E e); //在线性表的结尾插入一个元素 void add(int index, E element); //在线性表指定位置插入一个元素 boolean remove(Object o); //在线性表中删除指定元素 E remove(int index); //删除线性表上指定位置的元素 void clear(); //清空整个线性表 E get(int index); //返回指定位置上的元素 E set(int index, E element); //替换指定位置上的元素 }

在 Java 中,我们可以将线性表的抽象数据类型 List 抽象为一个接口类 MyList(为了区分 java.util.List),并将上面我们归纳出的操作放在接口类中。

interface MyList<E>{ int size(); //返回线性表中元素的个数 boolean isEmpty(); //检查线性表是否为空 boolean contains(Object o); //检查线性表是否包含某个元素 boolean add(E e); //在线性表的结尾插入一个元素 void add(int index, E element); //在线性表指定位置插入一个元素 boolean remove(Object o); //在线性表中删除指定元素 E remove(int index); //删除线性表上指定位置的元素 void clear(); //清空整个线性表 E get(int index); //返回指定位置上的元素 E set(int index, E element); //替换指定位置上的元素 }

接下来博主就带着大家一起用 Java 实现一个在内存中顺序存储的线性表(也叫顺序表)。要想在内存中顺序存储,我们必须将元素放在数组当中,因此我们的顺序表就起名叫做 MyArrayList。

  • 首先我们来写这个数据结构的私有成员,一个能装泛型 E 的数组,size 表示列表中元素的数目,以及一个默认的初识数组大小
public class MyArrayList<E> implements MyList<E>{ //在声明MyArrayList时,如不指明大小,则初始大小为10 private static final int DEFAULT_CAPACITY = 10; private E[] contents; private int size = 0; //两种构造函数,允许用户创建指定大小或者默认大小的线性表 public MyArrayList(){ init(DEFAULT_CAPACITY); } public MyArrayList(int initCapacity){ init(initCapacity); } //私有化方法init帮助构造函数来初始化数组contents private void init(int capacity){ //注意不能建立泛型数组,因此我们强行转换一个Object数组 contents = (E[]) new Object[capacity]; }
  • 接下来我们实现获取元素个数和查看是否为空的方法,很简单单行代码即可实现
@Override public int size() { // TODO Auto-generated method stub return this.size; } @Override public boolean isEmpty() { // TODO Auto-generated method stub return size()==0; }
  • 然后是两种不同的插入方法
@Override public boolean add(E e) { // TODO Auto-generated method stub //在插入元素之前,检查数组是否有足够的空间放置新的元素,若没有,则对数组进行扩容 ensureCapacity(); contents[size++] = e; return true; } @SuppressWarnings("unchecked") private void ensureCapacity() { // TODO Auto-generated method stub if(size()>=contents.length) { //此处新数组的容量是旧数组的2倍加1,你可以自己选择扩容的多少 E[] newContents = (E[]) new Object[2*contents.length+1]; //将就数组中的值全部拷于新数组中 System.arraycopy(contents, 0, newContents, 0, size()); //再让contents指向新的数组 contents = newContents; } } @Override public void add(int index, E element) { // TODO Auto-generated method stub //一旦要插入元素的位置为负或大于目前的元素数量就抛出异常 //此处允许index等于size,相当于在列表末尾插入元素 if(index<0 || index>size()) throw new ArrayIndexOutOfBoundsException(); //在插入元素之前,检查数组是否有足够的空间放置新的元素,若没有,则对数组进行扩容 ensureCapacity(); //将数组中从index位置开始的size-index个元素复制到数组从index+1开始的位置去 //相当于将数组中index位置之后的元素顺次向后移动一位 System.arraycopy(contents, index, contents, index+1, size() - index); //将要插入的元素放置到index位置上去 contents[index] = element; this.size++; } /* * 等价与上面的add(int index, E element)方法 * * System.arraycopy(contents, index, contents, index+1, size() - index); * 等价于: * for(int i=size(); i>index; i--){ contents[i] = contents[i-1]; } * @Override public void add(int index, E element) { // TODO Auto-generated method stub //一旦要插入元素的位置为负或大于目前的元素数量就抛出异常 //此处允许index等于size,相当于在列表末尾插入元素 if(index<0 || index>size()) throw new ArrayIndexOutOfBoundsException(); //在插入元素之前,检查数组是否有足够的空间放置新的元素,若没有,则对数组进行扩容 ensureCapacity(); for(int i=size(); i>index; i--) contents[i] = contents[i-1]; //将要插入的元素放置到index位置上去 contents[index] = element; this.size++; }*/
  • 紧接着是两个不同的删除方法
@Override public boolean remove(Object o) { // TODO Auto-generated method stub if(o == null) { for(int i=0; i<size(); i++) { if(contents[i] == null) { //如果找到元素为null,就使用私有方法fastRemove将该位置元素删除 fastRemove(i); return true; } } return false; }else { for(int i=0; i<size();i++) { if(contents[i].equals(o)) { //如果找到元素为o,就使用私有方法fastRemove将该位置元素删除 fastRemove(i); return true; } } return false; } } private void fastRemove(int index) { // TODO Auto-generated method stub //需要从后向前移动的元素数目 int numMoved = size() - index -1; if(numMoved > 0){ //将数组i+1位置开始的numMoved个元素移动到数组i的位置 //相当于将i位置上的元素删除,并将后面的元素向前移一位 System.arraycopy(contents,index+1,contents,index,numMoved); } //将元素数目减一并释放原来最后一位的内存 contents[--size] = null; } /* * 等价与上面的fastRemove(int index)方法 * * System.arraycopy(contents,index+1,contents,index,numMoved); * 等价于: * for(int i=index; i<size()-1; i++){ contents[i] = contents[i+1]; } * private void fastRemove(int index) { // TODO Auto-generated method stub for(int i=index; i<size()-1; i++) contents[i] = contents[i+1]; //将元素数目减一并释放原来最后一位的内存 contents[--size] = null; }*/ @Override public E remove(int index) { // TODO Auto-generated method stub //一旦要插入元素的位置为负或大于目前的元素数量就抛出异常 //此处不允许index等于size checkIndexValidation(index); E element = contents[index]; fastRemove(index); return element; } private void checkIndexValidation(int index) { if(index<0 || index>=size()) throw new ArrayIndexOutOfBoundsException(); }
  • 之后是获取,修改,查看是否为空,查看是否包含,以及清空整个列表这几个简单的方法了:
@Override public void clear() { // TODO Auto-generated method stub for(int i=0; i<size(); i++) { contents[i] = null; } size = 0; } @Override public E get(int index) { // TODO Auto-generated method stub checkIndexValidation(index); return contents[index]; } @Override public E set(int index, E element) { // TODO Auto-generated method stub checkIndexValidation(index); E old = contents[index]; contents[index] = element; return old; } @Override public boolean contains(Object o) { // TODO Auto-generated method stub if(o == null) { for(int i=0 ;i<size(); i++) { if(contents[i] == null) return true; } return false; }else { for(int i=0 ;i<size(); i++) { if(o.equals(contents[i])) return true; } return false; } }

在完成了自己写的一个 MyArrayList 之后,我们分析一下这种数据结构的特点。很明显,对于基于数组实现的线性表来说

我们要读取或修改某一个位置的元素只花费常数时间 O(1)
我们要增加或删除某一个元素最坏情况下要花费线性时间 O(n),因为涉及到移动其它的元素

因此,当我们在遇到频繁访问列表中元素时,ArrayList 是一个很好的选择;但当我们需要频繁添加、删除列表中元素,尤其是在表的前端进行增删操作时,ArrayList 就不是一个特别好的选择了。

到这里我们自己实现的 MyArrayList 就完成了,是不是感觉自己写数据结构也没有那么难呢?但是我们这里完成的这个只是一个很简单的数据结构,也没有实现 Itrable 等接口。

要想真正提高巩固自己的 Java 水平,我们需要在自己写完之后去对比源码中 ArrayList 的实现。看看尽管功能都是实现的差不多,为什么大牛写的代码就很优雅、效率高。不断地比较、吸收、学习,我们才能进步下去。

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...

推荐标签 标签

  • 大疆创新

    深圳市大疆创新科技有限公司(DJI-Innovations,简称 DJI),成立于 2006 年,是全球领先的无人飞行器控制系统及无人机解决方案的研发和生产商,客户遍布全球 100 多个国家。通过持续的创新,大疆致力于为无人机工业、行业用户以及专业航拍应用提供性能最强、体验最佳的革命性智能飞控产品和解决方案。

    2 引用 • 14 回帖
  • BAE

    百度应用引擎(Baidu App Engine)提供了 PHP、Java、Python 的执行环境,以及云存储、消息服务、云数据库等全面的云服务。它可以让开发者实现自动地部署和管理应用,并且提供动态扩容和负载均衡的运行环境,让开发者不用考虑高成本的运维工作,只需专注于业务逻辑,大大降低了开发者学习和迁移的成本。

    19 引用 • 75 回帖 • 683 关注
  • Vue.js

    Vue.js(读音 /vju ː/,类似于 view)是一个构建数据驱动的 Web 界面库。Vue.js 的目标是通过尽可能简单的 API 实现响应的数据绑定和组合的视图组件。

    268 引用 • 666 回帖 • 1 关注
  • Hprose

    Hprose 是一款先进的轻量级、跨语言、跨平台、无侵入式、高性能动态远程对象调用引擎库。它不仅简单易用,而且功能强大。你无需专门学习,只需看上几眼,就能用它轻松构建分布式应用系统。

    9 引用 • 17 回帖 • 639 关注
  • ngrok

    ngrok 是一个反向代理,通过在公共的端点和本地运行的 Web 服务器之间建立一个安全的通道。

    7 引用 • 63 回帖 • 656 关注
  • 知乎

    知乎是网络问答社区,连接各行各业的用户。用户分享着彼此的知识、经验和见解,为中文互联网源源不断地提供多种多样的信息。

    10 引用 • 66 回帖
  • Dubbo

    Dubbo 是一个分布式服务框架,致力于提供高性能和透明化的 RPC 远程服务调用方案,是 [阿里巴巴] SOA 服务化治理方案的核心框架,每天为 2,000+ 个服务提供 3,000,000,000+ 次访问量支持,并被广泛应用于阿里巴巴集团的各成员站点。

    60 引用 • 82 回帖 • 617 关注
  • CSS

    CSS(Cascading Style Sheet)“层叠样式表”是用于控制网页样式并允许将样式信息与网页内容分离的一种标记性语言。

    199 引用 • 543 回帖 • 3 关注
  • 分享

    有什么新发现就分享给大家吧!

    248 引用 • 1795 回帖 • 2 关注
  • Vim

    Vim 是类 UNIX 系统文本编辑器 Vi 的加强版本,加入了更多特性来帮助编辑源代码。Vim 的部分增强功能包括文件比较(vimdiff)、语法高亮、全面的帮助系统、本地脚本(Vimscript)和便于选择的可视化模式。

    29 引用 • 66 回帖
  • MongoDB

    MongoDB(来自于英文单词“Humongous”,中文含义为“庞大”)是一个基于分布式文件存储的数据库,由 C++ 语言编写。旨在为应用提供可扩展的高性能数据存储解决方案。MongoDB 是一个介于关系数据库和非关系数据库之间的产品,是非关系数据库当中功能最丰富,最像关系数据库的。它支持的数据结构非常松散,是类似 JSON 的 BSON 格式,因此可以存储比较复杂的数据类型。

    91 引用 • 59 回帖
  • RYMCU

    RYMCU 致力于打造一个即严谨又活泼、专业又不失有趣,为数百万人服务的开源嵌入式知识学习交流平台。

    4 引用 • 6 回帖 • 61 关注
  • 京东

    京东是中国最大的自营式电商企业,2015 年第一季度在中国自营式 B2C 电商市场的占有率为 56.3%。2014 年 5 月,京东在美国纳斯达克证券交易所正式挂牌上市(股票代码:JD),是中国第一个成功赴美上市的大型综合型电商平台,与腾讯、百度等中国互联网巨头共同跻身全球前十大互联网公司排行榜。

    14 引用 • 102 回帖 • 313 关注
  • Latke

    Latke 是一款以 JSON 为主的 Java Web 框架。

    71 引用 • 535 回帖 • 830 关注
  • Telegram

    Telegram 是一个非盈利性、基于云端的即时消息服务。它提供了支持各大操作系统平台的开源的客户端,也提供了很多强大的 APIs 给开发者创建自己的客户端和机器人。

    5 引用 • 35 回帖 • 1 关注
  • 服务

    提供一个服务绝不仅仅是简单的把硬件和软件累加在一起,它包括了服务的可靠性、服务的标准化、以及对服务的监控、维护、技术支持等。

    41 引用 • 24 回帖 • 1 关注
  • Love2D

    Love2D 是一个开源的, 跨平台的 2D 游戏引擎。使用纯 Lua 脚本来进行游戏开发。目前支持的平台有 Windows, Mac OS X, Linux, Android 和 iOS。

    14 引用 • 53 回帖 • 563 关注
  • 智能合约

    智能合约(Smart contract)是一种旨在以信息化方式传播、验证或执行合同的计算机协议。智能合约允许在没有第三方的情况下进行可信交易,这些交易可追踪且不可逆转。智能合约概念于 1994 年由 Nick Szabo 首次提出。

    1 引用 • 11 回帖 • 2 关注
  • 心情

    心是产生任何想法的源泉,心本体会陷入到对自己本体不能理解的状态中,因为心能产生任何想法,不能分出对错,不能分出自己。

    59 引用 • 369 回帖
  • Caddy

    Caddy 是一款默认自动启用 HTTPS 的 HTTP/2 Web 服务器。

    10 引用 • 54 回帖 • 179 关注
  • Angular

    AngularAngularJS 的新版本。

    26 引用 • 66 回帖 • 561 关注
  • 单点登录

    单点登录(Single Sign On)是目前比较流行的企业业务整合的解决方案之一。SSO 的定义是在多个应用系统中,用户只需要登录一次就可以访问所有相互信任的应用系统。

    9 引用 • 25 回帖 • 4 关注
  • 创造

    你创造的作品可能会帮助到很多人,如果是开源项目的话就更赞了!

    186 引用 • 1021 回帖
  • JavaScript

    JavaScript 一种动态类型、弱类型、基于原型的直译式脚本语言,内置支持类型。它的解释器被称为 JavaScript 引擎,为浏览器的一部分,广泛用于客户端的脚本语言,最早是在 HTML 网页上使用,用来给 HTML 网页增加动态功能。

    730 引用 • 1284 回帖
  • danl
    181 关注
  • 小薇

    小薇是一个用 Java 写的 QQ 聊天机器人 Web 服务,可以用于社群互动。

    由于 Smart QQ 从 2019 年 1 月 1 日起停止服务,所以该项目也已经停止维护了!

    35 引用 • 468 回帖 • 761 关注
  • flomo

    flomo 是新一代 「卡片笔记」 ,专注在碎片化时代,促进你的记录,帮你积累更多知识资产。

    6 引用 • 143 回帖