【Java数据结构与算法】顺序表

系列文章目录

第一章 时间复杂度和空间复杂度

---

---

前言

List属于一个接口，继承自Collection。关于List的实现类有ArrayList和

---

一、线性表

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

二、顺序表

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

1. ArrayList类实现了List接口，重写了List中的方法。
2. ArrayList是以泛型方式实现的，使用时必须先实例化。

三、ArrayList的基本概念

构造方法

1. List<Integer> list1 = new ArrayList<>(); 使用无参数的构造方法，即构造一个空的列表
2. List<Integer> list2 = new ArrayList<>(int initialCapacity);在构造方法中，传入数值作为ArrayList的初始容量。

常用的操作方法

方法	解释
void add(int index,E element)	将元素e插入到index位置中
boolean add(E element)	尾插e
E remove(int index)	删除index位置的元素
boolean remove(Object o)	删除遇到的第一个o
E get(int index)	获取index位置的元素
E set(int index,E element)	设置index位置的元素为element
void clear()	清空
boolean contains(Object o)	判断o是否在线性表中
int indexOf(Object o)	返回第一个o所在下标
int lastIndexOf(Object o)	返回最后一个o下标
List subList(int fromIndex,int toIndex)	截取部分list

ArrayList的遍历方式

在ArrayList类中，用数组作为数据存储的方式，在该类中已经自动重写了toString方法。
遍历的方式有for循环、迭代器、从后往前打印等方式，在代码块中作演示

 //1.for循环遍历
        for (int i = 0; i < arrayList.size(); i++) {
            System.out.print(arrayList.get(i) + " ");
        }
        System.out.println();
        System.out.println("==================");
        //2.for-each
        for (int x : arrayList) {
            System.out.print(x + " ");
        }
        System.out.println();
        System.out.println("===================");
        //3.arrayList重写toString方法
        System.out.println(arrayList);
        //4.迭代器
        Iterator<Integer> iterator = arrayList.iterator();
        while (iterator.hasNext()) {
            System.out.print(iterator.next()+" ");
        }
        System.out.println(); 
        System.out.println("=======================");
        //5.从后往前打印
        ListIterator<Integer> listIterator = arrayList.listIterator(arrayList.size());
        while (listIterator.hasPrevious()) {
            System.out.print(listIterator.previous() + " ");
        }
        System.out.println();
    }

四、ArrayList的一些机制

自动扩容机制

在ArrayList的构造方法中，我们可以选择传入参数initialCapacity初始化顺序表的容量。而在无参的构造方法中，顺序表是如何选择初始容量的？
在下面的图片中，显示的是ArrayList数据的初始状态。

如下图，在顺序表无参的构造方法中，转义之后为this.elementData = {}
可以看到，ArrayList()只是初始化了一个顺序表，但是并未分配大小。那么在哪里实现的自动扩容？

在add方法中，为了插入元素e，再调用重载方法add并传入参数为元素e，数组elementData，数组长度size

我们来到add(E e, Object[] elementData, int s)方法中，如下图所示，在此处进行了判断，s( size) = 0 ,elementData.length = 0 条件成立，调用grow方法

在grow方法中，传入参数minCapacity = 1

继续进入重载的方法grow中，传入的minCapacity值为1，符合if判断，而在if代码块中的则设定newCapacity扩容1.5倍。

总结：第一次使用add时，分配了大小为10的内存；在接下来的扩容中，以1.5倍进行扩容。

subList方法

在第三点中，我们已经知道了subList方法是截取顺序表中的一部分内容。以左闭右开的范围截取元素。
在下图中，通过subList方法打印出来的结果为 [1,2,3]

如果我们对subList中的数据进行修改会发生什么问题？
使用list接收截取出来的数据，并把list中的0下标数据改为7，这时候我们打印list和arrayList的内容

 List<Integer> list = arrayList.subList(0,3);
        list.set(0,7);
        System.out.println(list);
        System.out.println(arrayList);

在结果中，我们可以看到两个顺序表中0下标值都变成了7，因此我们可以知道，subList方法并不是生成一个新的顺序表，而是指向了arrayList顺序表。

总结

顺序表是最基础的数据结构之一，它所拥有的方法我们都可以用简单的逻辑进行复刻（但是标准库中的ArrayList类还是更好的）
源码☞顺序表源码

原文地址：https://blog.csdn.net/Starc_/article/details/140522167

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！