Collection与数据结构 顺序表与ArrayList

这篇具有很好参考价值的文章主要介绍了Collection与数据结构 顺序表与ArrayList。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1. 线性表

线性表(linear list)是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构,常见的线性表:顺序表、链表、栈、队列…
线性表在逻辑上是线性结构,也就说是连续的一条直线。但是在物理结构上并不一定是连续的,线性表在物理上存储时,通常以数组和链式结构的形式存储。
Collection与数据结构 顺序表与ArrayList,Collection与数据结构,数据结构,java

2. 顺序表

顺序表是一段物理空间连续的线性表,在底层一般使用数组来实现,在数组的基础上完成增删查改.下面是顺序表的一些接口.

2.1 接口

public interface Ilist {
    void add(int data);//为顺序表的尾部增加元素
    void add(int data ,int pos);//为指定位置添加元素
    void display();//打印顺序表
    int size ();//检测顺序表中元素的个数
    boolean contains(int toFind);//检测顺序表中是否包含该元素
    int indexOf(int toFind);//返回所要寻找第一个元素的下标
    int get(int index);//获取指定下标的元素
    void set(int index,int val);//把指定下标的元素指定为指定元素
    void remove(int toRomve);//移除第一个指定的元素
    void clear();//清空顺序表
}

下面我们来实现这些接口:

import java.util.Arrays;

/**
 * 顺序表底层是用数组来实现的
 */
public class MyArrayList implements Ilist {
    private int[] elem;
    private int size;//记录有效数据
    public static final int DEFAULT_CAPACITY = 5;//默认容量
    private boolean isFull(){
        return size == elem.length;//判断顺序表的容量是否为满
    }
    private void checkPos(int pos){
        if (pos < 0 || pos >= size){
            throw new PosException("pos is false");//判断插入位置是否合法
        }
    }
    private boolean isEmpty(){
        return this.size == 0;
    }

    public MyArrayList() {
        this.elem = new int[DEFAULT_CAPACITY];//默认容量为5
        this.size = 0;
    }//无参数的构造方法
    public void add(int data){//在末尾的位置添加元素
        if (isFull()){
            elem = Arrays.copyOf(elem,elem.length*2);//扩容
        }
        elem [size] = data;
        size++;
    }
    public void add(int data ,int pos){//在指定位置添加元素
        checkPos(pos);
        if (isFull()){
            elem = Arrays.copyOf(elem,elem.length*2);//扩容
        }
        for (int i = size-1; i >= pos ; i--) {//数组整体后移
            elem [i+1] = elem [i];
        }
        elem[pos] = data;
        size++;
    }
    public void display(){//打印顺序表
        System.out.print("["+" ");
        for (int i = 0; i < size; i++) {//打印有效元素
            System.out.print(elem[i]+" ");
        }
        System.out.print("]");
    }
    public int size (){//返回当前顺序表大小
        return this.size;
    }
    public boolean contains(int toFind){
        for (int i = 0; i < size; i++) {//在这里不可以用elem.length,后面的扩容之后未赋值
            if(elem[i] == toFind){
                return true;
            }
        }
        return false;
    }
    public int indexOf(int toFind){//返回要找的元素第一个返回的下标
        for (int i = 0; i < size; i++) {//在这里不可以用elem.length,后面的扩容之后未赋值
            if(elem[i] == toFind){
                return i;
            }
        }
        return -1;
    }
    public int get(int index){//获取index位置的值
        checkPos(index);
        if (isEmpty()){//存在默认容量5,若没有此方法,可能会在未初始化的位置上直接获取元素,获取成功
            //但是为0,不符合实际
            throw new EmptyException("array is empty");
        }
        return elem[index];
    }
    public void set(int index,int val){//把index位置的值改为val
        checkPos(index);
        if (isEmpty()){//存在默认容量5,若没有此方法,可能会在未初始化的位置上直接添加元素,
            //添加成功,但是不符合实际
            throw new EmptyException("array is empty");
        }
        elem[index] = val;
    }
    public void remove(int toRomve){//移除第一次出现的元素
        if (isEmpty()){
            throw new EmptyException("array is empty");
        }
        int index = indexOf(toRomve);//先找到下标的位置
        for (int i = index+1; i < size; i++) {
            elem[i-1] = elem[i];
        }
        elem[size-1] = 0;
        size --;
    }
    public void clear(){
        size = 0;
    }
}

public class EmptyException extends NullPointerException{
    public EmptyException(String s) {
        super(s);
    }
}

public class PosException extends ArrayIndexOutOfBoundsException{
    public PosException(String s) {
        super(s);
    }
}

下面通过一些测试用例;来测试:

public class Main {
    public static void main(String[] args) {
        MyArrayList list = new MyArrayList();
        list.add(0);
        list.add(1);
        list.add(3);
        list.add(4);
        list.add(2,2);
        list.add(5);
        list.display();
        System.out.println(list.size());
        list.remove(2);
        list.display();
        System.out.println(list.size());
    }
}

Collection与数据结构 顺序表与ArrayList,Collection与数据结构,数据结构,java

3.ArrayList简介

Collection与数据结构 顺序表与ArrayList,Collection与数据结构,数据结构,java
[说明]

  1. ArrayList是以泛型的方式实现的,使用时必须先实例化.
  2. ArrayList的底层是一段连续的存储空间,并且可以动态扩容,是一个动态类型的顺序表.

4.ArrayList的使用

4.1 ArrayList的构造方法

方法 解释
public ArrayList() 无参构造方法
public ArrayList(int initialCapacity) 指定顺序表初始容量
public ArrayList(Collection<? extends E> c) 利用Collection中的容器来构造

关于第三个构造方法,不太好理解,我们下面来解释一下:ArrayList已经传入了泛型的参数,就是E,这里用来构造ArrayList的Collection类中的元素必须是E的子类.

ArrayList<Integer> list = new ArrayList<>();
ArrayList<Integer> list1 = new ArrayList<>(list);
ArrayList<Number> list2 = new ArrayList<>(list);
ArrayList<Integer> list3 = new ArrayList<>(10);

4.2 ArrayList常见操作

方法 解释
boolean add(E e) 在尾部添加元素
void add(int index,E element) 在指定位置添加元素
boolean addAll(Collection<? extends E> c) 把c中的元素全部添加到顺序表尾部
E remove(int index) 移除指定位置的元素
boolean remove(Object o) 移除遇到的第一个元素o
E get(int index) 获取指定位置的元素
E set(int index,E element) 把指定位置的元素设置为指定的值
void clear() 清空顺序表
boolean contains(Object o) 检测顺序表中是否包含o
int indexOf(Object o) 返回第一个指定元素所在的下标
int lastIndexOf(Object o) 从后向前找,返回第一个元素所在的下标
List subList(int fromIndex,int toIndex) 截取指定范围的字符串,左闭右开

在这里说明一下两个remove方法的区别,避免混淆,第一个remove方法时移除指定位置的元素,传入的元素类型为int类型的数据,而第二个remove方法移除的是第一个遇到的元素,这里传入的参数类型是和顺序表泛型相同的类型,当一个顺序表中存储的是Integer类型的数据的时候,要注意区分下标和元素.
下面对上述方法进行演示:

public static void main(String[] args) {
	List<String> list = new ArrayList<>();
	list.add("JavaSE");
	list.add("JavaWeb");
	list.add("JavaEE");
	list.add("JVM");
	list.add("测试课程");
	System.out.println(list);
	// 获取list中有效元素个数
	System.out.println(list.size());
	// 获取和设置index位置上的元素,注意index必须介于[0, size)间
	System.out.println(list.get(1));
	list.set(1, "JavaWEB");
	System.out.println(list.get(1));
	// 在list的index位置插入指定元素,index及后续的元素统一往后搬移一个位置
	list.add(1, "Java数据结构");
	System.out.println(list);
	// 删除指定元素,找到了就删除,该元素之后的元素统一往前搬移一个位置
	list.remove("JVM");
	System.out.println(list);
	// 删除list中index位置上的元素,注意index不要超过list中有效元素个数,否则会抛出下标越界异常
	list.remove(list.size()-1);
	System.out.println(list);
	// 检测list中是否包含指定元素,包含返回true,否则返回false
	if(list.contains("测试课程")){
	list.add("测试课程");
	}
	// 查找指定元素第一次出现的位置:indexOf从前往后找,lastIndexOf从后往前找
	list.add("JavaSE");
	System.out.println(list.indexOf("JavaSE"));
	System.out.println(list.lastIndexOf("JavaSE"));
	// 使用list中[0, 4)之间的元素构成一个新的SubList返回,但是和ArrayList共用一个elementData数组
	List<String> ret = list.subList(0, 4);
	System.out.println(ret);
	list.clear();
	System.out.println(list.size());
}

4.3 ArrayList的遍历

ArrayList有四种遍历方式,一种是通过sout直接输出,一种是for-i,一种是for-each,一种是使用迭代器.

import java.util.ArrayList;
import java.util.Iterator;
public class TestArrayList {
    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);
        //通过sout去遍历ArrayList
        System.out.println(list);
        //通过fori遍历
        for (int i = 0; i < list.size(); i++) {
            System.out.print(list.get(i)+" ");
        }
        System.out.println();
        //通过foreach遍历
        for (int x:list) {
            System.out.print(x+" ");
        }
        System.out.println();
        //通过迭代器遍历
        Iterator<Integer> iterator = list.iterator();
        while (iterator.hasNext()){
            System.out.print(iterator.next()+" ");
        }
        System.out.println();
     }
}

4.4 ArrayList扩容机制

ArrayList是动态的顺序表,在顺序表的容量不够的时候会自动扩容,下面是底层代码对ArrayList的扩容机制.

	public boolean add(E e) {
        modCount++;//底层是C/C++代码
        add(e, elementData, size);//调用另一个重载的add方法,指定添加容积
        return true;
    }
	private void add(E e, Object[] elementData, int s) {
        if (s == elementData.length)//容器满的时候需要扩容
            elementData = grow();//调用grow方法扩容
        elementData[s] = e;
        size = s + 1;
    }
	private Object[] grow() {
        return grow(size + 1);//最小容积是size+1,就是指定的添加容积+1
    }
    private Object[] grow(int minCapacity) {//传入指定的最小容积
        int oldCapacity = elementData.length;
        if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            int newCapacity = ArraysSupport.newLength(oldCapacity,//对数组扩容
                    minCapacity - oldCapacity, /* minimum growth */    //计算原容量和最小容积的差值
                    oldCapacity >> 1  //原容量的一半         /* preferred growth */);
            return elementData = Arrays.copyOf(elementData, newCapacity);//正式扩容
        } else {
            return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
        }
    }
	public static int newLength(int oldLength, int minGrowth, int prefGrowth) {
        // preconditions not checked because of inlining
        // assert oldLength >= 0
        // assert minGrowth > 0
        int prefLength = oldLength + Math.max(minGrowth, prefGrowth); // might overflow
        //若pre大,1.5被扩容,若是min大,直接加上指定的最小容积
        if (0 < prefLength && prefLength <= SOFT_MAX_ARRAY_LENGTH) {
            return prefLength;
        } else {
            // put code cold in a separate method
            return hugeLength(oldLength, minGrowth);
        }
    }

[总结]文章来源地址https://www.toymoban.com/news/detail-849673.html

  1. 预估要扩容的大小
  • 初步预估按照1.5倍扩容.
  • 如果用户所需大小预估超过1.5,则按照用户所需大小扩容.
  1. 使用copyOf扩容.

到了这里,关于Collection与数据结构 顺序表与ArrayList的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构与算法分析】反转链表与顺序表(内含源码,思路清晰)

      顺序表和链表都是数据结构中常见的线性表。它们的主要区别在于 内存管理方式不同 。   顺序表(Array)是由一系列元素按照一定顺序依次排列而成,它使用连续的内存空间存储数据。顺序表使用一个数组来存储数据,数组中的每个元素都可以通过下标来访问。顺序

    2024年02月07日
    浏览(101)
  • 【数据结构与算法】之8道顺序表与链表典型编程题心决!

                                                                                    个人主页:秋风起,再归来~                                                                                             数据结构与算

    2024年04月14日
    浏览(51)
  • 【数据结构与算法】顺序表与链表(单链表和双链表)超详解图示与源码。

                                                       大家好,今天我们来学习数据结构中的顺序表与链表!源码在最后附上 首先我们先来认识一下 顺序表 :                                       **如上图所示:很多人会以为数组就是顺序表,顺序表就是数组,这

    2024年02月21日
    浏览(55)
  • 【数据结构】链表与LinkedList

    作者主页: paper jie 的博客 本文作者:大家好,我是paper jie,感谢你阅读本文,欢迎一建三连哦。 本文录入于《JAVA数据结构》专栏,本专栏是针对于大学生,编程小白精心打造的。笔者用重金(时间和精力)打造,将javaSE基础知识一网打尽,希望可以帮到读者们哦。 其他专栏

    2024年02月08日
    浏览(47)
  • 【数据结构(三)】链表与LinkedList

    ❣博主主页: 33的博客❣ ▶️文章专栏分类:数据结构◀️ 🚚我的代码仓库: 33的代码仓库🚚 🫵🫵🫵 关注我带你学更多数据结构知识 在上一篇文章中,我们已经认识了顺序表,通过源码我们知道ArrayList底层是使用数组来存储元素,当在ArrayList任意位置插入或者删除元素时,

    2024年04月13日
    浏览(49)
  • 【数据结构】哈希表与哈希桶

    👀 樊梓慕: 个人主页  🎥 个人专栏: 《C语言》 《数据结构》 《蓝桥杯试题》 《LeetCode刷题笔记》 《实训项目》 《C++》 《Linux》 《算法》 🌝 每一个不曾起舞的日子,都是对生命的辜负 目录 前言 1.概念 2.哈希冲突 3.解决哈希冲突 3.1闭散列 3.2开散列(哈希桶) 4.模拟实

    2024年03月21日
    浏览(44)
  • 【C/C++数据结构】链表与快慢指针

    目录 一、单链表 二、双向循环链表 三、判断链表是否带环 四、链表的回文结构判断 五、复制带随机指针的链表 优点 :头部增删效率高,动态存储无空间浪费 缺点 :尾部增删、遍历效率低,不支持随机访问节点 头结点 :单链表头结点可有可无,带头结点更方便进行初始

    2024年02月16日
    浏览(77)
  • 【数据结构与算法】图——邻接表与邻接矩阵

    图(Graph)是由顶点的有穷非空集合和顶点之间边的集合组成,通常表示为:G(V,E),其中, G表示一个图,V是顶点的集合,E是边的集合 。 在图中数据元素,我们则称之为顶点(Vertex)。 图中,任意两个顶点之间都可能有关系,顶点之间的逻辑关系用边来表示,边集可以是

    2024年02月02日
    浏览(41)
  • 【数据结构】链表(单链表与双链表实现+原理+源码)

    博主介绍:✌全网粉丝喜爱+、前后端领域优质创作者、本质互联网精神、坚持优质作品共享、掘金/腾讯云/阿里云等平台优质作者、擅长前后端项目开发和毕业项目实战✌有需要可以联系作者我哦! 🍅附上相关C语言版源码讲解🍅 👇🏻 精彩专栏推荐订阅👇🏻 不然下次找

    2024年01月24日
    浏览(122)
  • 【数据结构 | 入门】线性表与链表 (问题引入&实现&算法优化)

    🤵‍♂️ 个人主页: @计算机魔术师 👨‍💻 作者简介:CSDN内容合伙人,全栈领域优质创作者。 本文是浙大数据结构学习笔记专栏 这里我们引入一个问题,最常见的多项式,我们如何使用编程将多项式表示出来呢? 我们可以使用数组来表示,但是会随着一个问题,如下图底

    2024年01月21日
    浏览(67)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包