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

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

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

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

像这种从逻辑上看,具有零个或多个数据元素的有限序列我们就称之为线性表(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 的实现。看看尽管功能都是实现的差不多,为什么大牛写的代码就很优雅、效率高。不断地比较、吸收、学习,我们才能进步下去。

相关帖子

欢迎来到这里!

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

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

推荐标签 标签

  • 智能合约

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

    1 引用 • 11 回帖 • 5 关注
  • Sym

    Sym 是一款用 Java 实现的现代化社区(论坛/BBS/社交网络/博客)系统平台。

    下一代的社区系统,为未来而构建

    524 引用 • 4601 回帖 • 699 关注
  • HBase

    HBase 是一个分布式的、面向列的开源数据库,该技术来源于 Fay Chang 所撰写的 Google 论文 “Bigtable:一个结构化数据的分布式存储系统”。就像 Bigtable 利用了 Google 文件系统所提供的分布式数据存储一样,HBase 在 Hadoop 之上提供了类似于 Bigtable 的能力。

    17 引用 • 6 回帖 • 73 关注
  • Mac

    Mac 是苹果公司自 1984 年起以“Macintosh”开始开发的个人消费型计算机,如:iMac、Mac mini、Macbook Air、Macbook Pro、Macbook、Mac Pro 等计算机。

    166 引用 • 595 回帖 • 1 关注
  • Openfire

    Openfire 是开源的、基于可拓展通讯和表示协议 (XMPP)、采用 Java 编程语言开发的实时协作服务器。Openfire 的效率很高,单台服务器可支持上万并发用户。

    6 引用 • 7 回帖 • 94 关注
  • Angular

    AngularAngularJS 的新版本。

    26 引用 • 66 回帖 • 536 关注
  • 微软

    微软是一家美国跨国科技公司,也是世界 PC 软件开发的先导,由比尔·盖茨与保罗·艾伦创办于 1975 年,公司总部设立在华盛顿州的雷德蒙德(Redmond,邻近西雅图)。以研发、制造、授权和提供广泛的电脑软件服务业务为主。

    8 引用 • 44 回帖 • 1 关注
  • RYMCU

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

    4 引用 • 6 回帖 • 52 关注
  • OpenShift

    红帽提供的 PaaS 云,支持多种编程语言,为开发人员提供了更为灵活的框架、存储选择。

    14 引用 • 20 回帖 • 633 关注
  • PWL

    组织简介

    用爱发电 (Programming With Love) 是一个以开源精神为核心的民间开源爱好者技术组织,“用爱发电”象征开源与贡献精神,加入组织,代表你将遵守组织的“个人开源爱好者”的各项条款。申请加入:用爱发电组织邀请帖
    用爱发电组织官网:https://programmingwithlove.stackoverflow.wiki/

    用爱发电组织的核心驱动力:

    • 遵守开源守则,体现开源&贡献精神:以分享为目的,拒绝非法牟利。
    • 自我保护:使用适当的 License 保护自己的原创作品。
    • 尊重他人:不以各种理由、各种漏洞进行未经允许的抄袭、散播、洩露;以礼相待,尊重所有对社区做出贡献的开发者;通过他人的分享习得知识,要留下足迹,表示感谢。
    • 热爱编程、热爱学习:加入组织,热爱编程是首当其要的。我们欢迎热爱讨论、分享、提问的朋友,也同样欢迎默默成就的朋友。
    • 倾听:正确并恳切对待、处理问题与建议,及时修复开源项目的 Bug ,及时与反馈者沟通。不抬杠、不无视、不辱骂。
    • 平视:不诋毁、轻视、嘲讽其他开发者,主动提出建议、施以帮助,以和谐为本。只要他人肯努力,你也可能会被昔日小看的人所超越,所以请保持谦虚。
    • 乐观且活跃:你的努力决定了你的高度。不要放弃,多年后回头俯瞰,才会发现自己已经成就往日所仰望的水平。积极地将项目开源,帮助他人学习、改进,自己也会获得相应的提升、成就与成就感。
    1 引用 • 487 回帖
  • CentOS

    CentOS(Community Enterprise Operating System)是 Linux 发行版之一,它是来自于 Red Hat Enterprise Linux 依照开放源代码规定释出的源代码所编译而成。由于出自同样的源代码,因此有些要求高度稳定的服务器以 CentOS 替代商业版的 Red Hat Enterprise Linux 使用。两者的不同在于 CentOS 并不包含封闭源代码软件。

    238 引用 • 224 回帖 • 1 关注
  • SQLServer

    SQL Server 是由 [微软] 开发和推广的关系数据库管理系统(DBMS),它最初是由 微软、Sybase 和 Ashton-Tate 三家公司共同开发的,并于 1988 年推出了第一个 OS/2 版本。

    21 引用 • 31 回帖 • 1 关注
  • 996
    13 引用 • 200 回帖 • 6 关注
  • Ngui

    Ngui 是一个 GUI 的排版显示引擎和跨平台的 GUI 应用程序开发框架,基于
    Node.js / OpenGL。目标是在此基础上开发 GUI 应用程序可拥有开发 WEB 应用般简单与速度同时兼顾 Native 应用程序的性能与体验。

    7 引用 • 9 回帖 • 391 关注
  • Laravel

    Laravel 是一套简洁、优雅的 PHP Web 开发框架。它采用 MVC 设计,是一款崇尚开发效率的全栈框架。

    20 引用 • 23 回帖 • 723 关注
  • GitLab

    GitLab 是利用 Ruby 一个开源的版本管理系统,实现一个自托管的 Git 项目仓库,可通过 Web 界面操作公开或私有项目。

    46 引用 • 72 回帖 • 2 关注
  • Java

    Java 是一种可以撰写跨平台应用软件的面向对象的程序设计语言,是由 Sun Microsystems 公司于 1995 年 5 月推出的。Java 技术具有卓越的通用性、高效性、平台移植性和安全性。

    3187 引用 • 8213 回帖
  • QQ

    1999 年 2 月腾讯正式推出“腾讯 QQ”,在线用户由 1999 年的 2 人(马化腾和张志东)到现在已经发展到上亿用户了,在线人数超过一亿,是目前使用最广泛的聊天软件之一。

    45 引用 • 557 回帖 • 67 关注
  • Scala

    Scala 是一门多范式的编程语言,集成面向对象编程和函数式编程的各种特性。

    13 引用 • 11 回帖 • 132 关注
  • Flutter

    Flutter 是谷歌的移动 UI 框架,可以快速在 iOS 和 Android 上构建高质量的原生用户界面。 Flutter 可以与现有的代码一起工作,它正在被越来越多的开发者和组织使用,并且 Flutter 是完全免费、开源的。

    39 引用 • 92 回帖 • 1 关注
  • 职场

    找到自己的位置,萌新烦恼少。

    127 引用 • 1705 回帖
  • HTML

    HTML5 是 HTML 下一个的主要修订版本,现在仍处于发展阶段。广义论及 HTML5 时,实际指的是包括 HTML、CSS 和 JavaScript 在内的一套技术组合。

    107 引用 • 295 回帖
  • Docker

    Docker 是一个开源的应用容器引擎,让开发者可以打包他们的应用以及依赖包到一个可移植的容器中,然后发布到任何流行的操作系统上。容器完全使用沙箱机制,几乎没有性能开销,可以很容易地在机器和数据中心中运行。

    491 引用 • 917 回帖 • 2 关注
  • Webswing

    Webswing 是一个能将任何 Swing 应用通过纯 HTML5 运行在浏览器中的 Web 服务器,详细介绍请看 将 Java Swing 应用变成 Web 应用

    1 引用 • 15 回帖 • 629 关注
  • InfluxDB

    InfluxDB 是一个开源的没有外部依赖的时间序列数据库。适用于记录度量,事件及实时分析。

    2 引用 • 73 关注
  • WebSocket

    WebSocket 是 HTML5 中定义的一种新协议,它实现了浏览器与服务器之间的全双工通信(full-duplex)。

    48 引用 • 206 回帖 • 334 关注
  • Bootstrap

    Bootstrap 是 Twitter 推出的一个用于前端开发的开源工具包。它由 Twitter 的设计师 Mark Otto 和 Jacob Thornton 合作开发,是一个 CSS / HTML 框架。

    18 引用 • 33 回帖 • 659 关注