【数据结构】从顺序表到ArrayList类

2024-01-23 19:04
文章标签 数据结构 顺序 arraylist 表到

本文主要是介绍【数据结构】从顺序表到ArrayList类，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在这里插入图片描述

文章目录

  • 1.线性表
    • 1.1线性表的概念
    • 2.顺序表
    • 2.1顺序表的概念
    • 2.2顺序表的实现
    • 2.3接口的实现(对数组增删查改操作)
      • 3.ArrayList简介
        • 4. ArrayList使用
    • 4.1ArrayList的构造
    • 4.2 ArrayList的方法
    • 4.3 ArrayList的遍历

1.线性表

1.1线性表的概念

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列…
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。
如图所示：
在这里插入图片描述

2.顺序表

2.1顺序表的概念

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。

2.2顺序表的实现

因为顺序表存储数据是在一段连续的物理地址依次存储的线性结构，我们一般采用数组的形式来进行存储，通过在数组中完成数据的增删查改的操作。
2.2.1数组的创建

public class MyArrayList {
//定义一个未被初始化的数组elempublic int[] elem;//定义一个记录该数组存了多少容量public int size;//将该容量设置为一个常量，为了到后面调构造方法的时候初始化数组的大小public static final int DEFAULT_CAPACITY = 5;//调用构造函数的时候初始化数组的大小，而size成员变量不需要初始化，因为一开始未被初始化，默认初始化为0.public MyArrayList() {this.elem = new int[DEFAULT_CAPACITY];}
}

2.2.2提供一些接口

public interface Ilist {// 新增元素,默认在数组最后新增void add(int data);// 在 pos 位置新增元素void add(int pos, int data);// 判定是否包含某个元素boolean contains(int toFind);// 查找某个元素对应的位置int indexOf(int toFind);// 获取 pos 位置的元素int get(int pos);// 给 pos 位置的元素设为 valuevoid set(int pos, int value);//删除第一次出现的关键字keyvoid remove(int toRemove);// 获取顺序表长度int size();// 清空顺序表void clear();//打印这个数组的内容void display();//判断是否空间满了boolean isFuul();boolean isEmpty();
}

2.2.3提供一些异常类
1.判断数组中是否为空的异常
2.判断下标是否合法的异常

//1.判断数组中是否为空的异常
public class EmptyException extends RuntimeException{public EmptyException() {}public EmptyException(String message) {super(message);}
}
//2.判断下标是否合法的异常
public class PosException extends RuntimeException{public PosException() {}public PosException(String message) {super(message);}
}

2.3接口的实现(对数组增删查改操作)

2.3.1 新增元素,(默认在数组最后新增)

 //往最后位置插入数据public void add(int data) {//判断空间是否满了，如果满了就扩容2倍if(isFuul()) {elem = Arrays.copyOf(elem,2*elem.length);System.out.println("扩容成功");}elem[size] = data;size++;}@Overridepublic boolean isFuul() {return size == elem.length;}

2.3.2打印数组全部内容

//打印数组全部内容@Overridepublic void display() {for (int i = 0; i < size; i++) {System.out.println(elem[i]);}}

2.3.3在 pos 位置新增元素

 // 在 pos 位置新增元素@Overridepublic void add(int pos, int data) {//判断pos是否合法checkPosOfAdd(pos);//判断是否需要扩容if(isFuul()) {elem = Arrays.copyOf(elem,2*elem.length);}//最后在pos位置插入新元素for(int i=size-1;i>=pos;i--) {elem[i+1] = elem[i];}elem[pos] = data;size++;}//判断pos是否合法的方法，在顺序表中插入数据的时候，插入的位置前面必须要有数据。private void checkPosOfAdd (int pos) {if(pos<0 || pos>size) {throw new PosException("pos的位置不合法:"+pos);}}

2.3.4判定是否包含某个元素

// 判定是否包含某个元素//直接遍历数组然后一一和目标元素比较，有就返回true，没有就返回false。@Overridepublic boolean contains(int toFind) {for(int i=0;i< elem.length;i++) {if(toFind == elem[i]) {return true;}}return false;}

2.3.5查找某个元素对应的位置

// 查找某个元素对应的位置//直接遍历数组然后一一和目标元素比较，有就返回对应的下标，没有就返回-1。@Overridepublic int indexOf(int toFind) {for(int i=0;i< elem.length;i++) {if(toFind == elem[i]) {return i;}}return -1;}

2.3.6 获取 pos 位置的元素 如果顺序表为空返回-1或者抛出异常，不为空返回pos位置的元素

// 获取 pos 位置的元素 如果顺序表为空返回-1或者抛出异常，不为空返回pos位置的元素@Overridepublic int get(int pos) {//判断pos位置是否合法checkPosOfGet(pos);//判断这个顺序表是否为空if(isEmpty()) {throw new EmptyException("顺序表为空");}return elem[pos];}

2.3.7判断顺序表是否为空

 //判断顺序表是否为空@Overridepublic boolean isEmpty() {return size == 0;}//判断pos合不合法的方法private void checkPosOfGet (int pos) {if(pos<0 || pos>size) {throw new PosException("pos的位置不合法:"+pos);}}

2.3.8给 pos 位置的元素设为 value

 // 给 pos 位置的元素设为 value@Overridepublic void set(int pos, int value) {//判断pos是否合法checkPosOfSet(pos);//判断顺序表是否为空if(isEmpty()) {throw new EmptyException("顺序表为空");}//修改pos位置的内容this.elem[pos] = value;}private void checkPosOfSet (int pos) {if (pos < 0 || pos > size) {throw new PosException("pos的位置不合法:" + pos);}}

2.3.9删除元素 如果顺序表中为空，则删不了，之后我们先找到我们要删的这个数。

//删除元素 如果顺序表中为空，则删不了，之后我们先找到我们要删的这个数。@Overridepublic void remove(int toRemove) {//判断顺序表中是否为空if(isEmpty()) {throw new EmptyException("顺序表为空");}//找到我们需要删的这个数int indexof = indexOf(toRemove);for(int i = indexof;i<size-1;i++) {elem[i] = elem[i+1];}size--;}

2.3.10获取顺序表长度 直接返回size

// 获取顺序表长度 直接返回size@Overridepublic int size() {return this.size;}

2.3.11清空顺序表

// 清空顺序表@Overridepublic void clear() {size = 0;}

3.ArrayList简介

在集合框架中，ArrayList是一个普通的类，实现了List接口，具体框架图如下：
在这里插入图片描述
【说明】

  1. ArrayList是以泛型方式实现的，使用时必须要先实例化
  2. ArrayList实现了RandomAccess接口，表明ArrayList支持随机访问
  3. ArrayList实现了Cloneable接口，表明ArrayList是可以clone的
  4. ArrayList实现了Serializable接口，表明ArrayList是支持序列化的
  5. 和Vector不同，ArrayList不是线程安全的，在单线程下可以使用，在多线程中可以选择Vector或者CopyOnWriteArrayList
  6. ArrayList底层是一段连续的空间，并且可以动态扩容，是一个动态类型的顺序表
4. ArrayList使用

4.1ArrayList的构造

1.ArrayList() 无参构造：

List<Integer> list1 = new ArrayList<>();

2.ArrayList(int initialCapacity)指定顺序表初始容量:

List<Integer> list2 = new ArrayList<>(5);

3.ArrayList(Collection<? extends E> c) 利用其他 Collection 构建 ArrayList:相当于传入其他的ArrayList顺序表，使得这个顺序表的大小容量与数据类型和传入的顺序表是一致的。

List<Integer> list3 = new ArrayList<>(list2);

4.2 ArrayList的方法

4.2.1尾插法

public static void main(String[] args) {List<Integer> list2 = new ArrayList<>(5);list2.add(1);list2.add(2);list2.add(3);list2.add(4);list2.add(5);System.out.println(list2);}

结果显示：
在这里插入图片描述
4.2.2将目标值插到指定index位置

 list2.add(1,6);System.out.println(list2);

结果显示：
在这里插入图片描述
4.2.3删除 index 位置元素

 list2.remove(2);System.out.println(list2);

结果显示：
在这里插入图片描述
4.2.4获取下标 index 位置元素

System.out.println(list2.get(3));

结果显示：
在这里插入图片描述

4.3 ArrayList的遍历

ArrayList 可以使用三方方式遍历：for循环+下标、foreach。
1.for循环+下标：

 public static void main(String[] args) {List<Integer> list2 = new ArrayList<>(5);list2.add(1);list2.add(2);list2.add(3);list2.add(4);list2.add(5);for (int i = 0; i < list2.size(); i++) {System.out.print(list2.get(i)+" ");}}

结果显示：
在这里插入图片描述
2.foreach：

public static void main(String[] args) {List<Integer> list2 = new ArrayList<>(5);list2.add(1);list2.add(2);list2.add(3);list2.add(4);list2.add(5);System.out.println("foreach循环下：");for (Integer integer:list2) {System.out.print(integer+" ");}}

结果显示：
在这里插入图片描述
最后，ArrayList是一个动态类型的顺序表，不够空间会自动扩容。

好久没更新了，在这我向我的老铁们道个歉，从今天开始更新关于java的数据结构的内容，希望大家多多支持。🌹🌹🌹🌹🌹🌹🌹🌹🌹🌹🌹🌹🌹🌹

这篇关于【数据结构】从顺序表到ArrayList类的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/637231。

相关文章

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

上篇：6.1.数据结构-c/c++模拟实现堆上篇（向下，上调整算法，建堆，增删数据）-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小)： 2.2 C语言代码（手写堆） 2.3 C++代码（使用优先级队列 priority_queue）
阅读更多...
Java ArrayList扩容机制 （源码解读）

Java ArrayList扩容机制 （源码解读）

结论：初始长度为10，若所需长度小于1.5倍原长度，则按照1.5倍扩容。若不够用则按照所需长度扩容。 一. 明确类内部重要变量含义         1：数组默认长度         2:这是一个共享的空数组实例，用于明确创建长度为0时的ArrayList ，比如通过 new ArrayList<>(0)，ArrayList 内部的数组 elementData 会指向这个 EMPTY_EL
阅读更多...
顺序表之创建，判满，插入，输出

顺序表之创建，判满，插入，输出

文章目录 🍊自我介绍🍊创建一个空的顺序表，为结构体在堆区分配空间🍊插入数据🍊输出数据🍊判断顺序表是否满了，满了返回值1，否则返回0🍊main函数 你的点赞评论就是对博主最大的鼓励 当然喜欢的小伙伴可以：点赞+关注+评论+收藏（一键四连）哦~ 🍊自我介绍   Hello,大家好，我是小珑也要变强（也是小珑），我是易编程·终身成长社群的一名“创始团队·嘉宾”
阅读更多...
《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多，算法平均时间性能比直接插入排序差。当初始记录无序，n较大时， 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In
阅读更多...
web群集--nginx配置文件location匹配符的优先级顺序详解及验证

web群集--nginx配置文件location匹配符的优先级顺序详解及验证

文章目录 前言优先级顺序优先级顺序(详解)1. 精确匹配（Exact Match）2. 正则表达式匹配（Regex Match）3. 前缀匹配（Prefix Match） 匹配规则的综合应用验证优先级 前言 location的作用 在 NGINX 中，location 指令用于定义如何处理特定的请求 URI。由于网站往往需要不同的处理方式来适应各种请求，NGINX 提供了多种匹
阅读更多...
【408数据结构】散列 （哈希）知识点集合复习考点题目

【408数据结构】散列 （哈希）知识点集合复习考点题目

苏泽  “弃工从研”的路上很孤独，于是我记下了些许笔记相伴，希望能够帮助到大家    知识点 1. 散列查找 散列查找是一种高效的查找方法，它通过散列函数将关键字映射到数组的一个位置，从而实现快速查找。这种方法的时间复杂度平均为(
阅读更多...
浙大数据结构：树的定义与操作

浙大数据结构：树的定义与操作

四种遍历 #include<iostream>#include<queue>using namespace std;typedef struct treenode *BinTree;typedef BinTree position;typedef int ElementType;struct treenode{ElementType data;BinTree left;BinTre
阅读更多...
Python 内置的一些数据结构

Python 内置的一些数据结构

文章目录 1. 列表 (List)2. 元组 (Tuple)3. 字典 (Dictionary)4. 集合 (Set)5. 字符串 (String) Python 提供了几种内置的数据结构来存储和操作数据，每种都有其独特的特点和用途。下面是一些常用的数据结构及其简要说明： 1. 列表 (List) 列表是一种可变的有序集合，可以存放任意类型的数据。列表中的元素可以通过索
阅读更多...
浙大数据结构：04-树7 二叉搜索树的操作集

浙大数据结构：04-树7 二叉搜索树的操作集

这道题答案都在PPT上，所以先学会再写的话并不难。 1、BinTree Insert( BinTree BST, ElementType X ) 递归实现，小就进左子树，大就进右子树。 为空就新建结点插入。 BinTree Insert( BinTree BST, ElementType X ){if(!BST){BST=(BinTree)malloc(sizeof(struct TNo
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2