共计 7941 个字符，预计需要花费 20 分钟才能阅读完成。
今日目录：
1：可能说出线性表的概念
2：可能说出数组的存储构造
3：可能说出数组查问，插入，删除操作的特点及对应的工夫复杂度
4：可能实现动静数组 ArrayList 的代码编写
1、线性表
在数据结构中，数据的逻辑构造分为 线性构造 和非线性构造。
线性构造：n 个数据元素的有序（秩序）汇合。其特色如下：
1．汇合中必存在惟一的一个 ” 第一个元素 ”；
2．汇合中必存在惟一的一个 ” 最初的元素 ”；
3．除最初元素之外，其它数据元素均有惟一的 ” 后继 ”；
4．除第一元素之外，其它数据元素均有惟一的 ” 前驱 ”。
数据结构中线性构造指的是数据元素之间存在着“一对一”的线性关系的数据结构。当然这个线性并不是说肯定是直线，常见的线性数据结构有：数组(一维)，链表，栈，队列；它们也是咱们后续学习其余数据结构的根底，表现形式如下：
绝对应于线性构造，非线性构造的逻辑特色是一个结点元素可能对应多个间接前驱和多个后继，比方后续要学习的：树，图，堆等，如下图
2、数组根底
2.1、概念和构造
数组（Array）是一种用 间断的内存空间 存储 雷同数据类型 数据的线性数据结构。
int[] array = new int[]{10,20,30}
int[] array = new int[6];
数组的示意形式：应用 下标 来获取数组元素数据
思考一下操作平台是如何依据下标来找到对应元素的内存地址的呢？
咱们拿一个长度为 10 的数组来举例，int [] a= new int[10]，在上面的图中，计算机给数组调配了一块间断的空间，100-139，其中内存的起始地址为 baseAddress=100
咱们晓得，计算机给每个内存单元都调配了一个地址，通过地址来拜访其数据，因而要拜访数组中的某个元素时，首先要通过一个 寻址公式 计算要拜访的元素在内存中的地址：
a[i] = baseAddress + i * dataTypeSize其中 dataTypeSize 代表数组中元素类型的大小，在这个例子中，存储的是 int 型的数据，因而 dataTypeSize= 4 个字节
下标为什么从 0 开始而不是 1 呢？
从数组存储的内存模型上来看，“下标”最确切的定义应该是“偏移（offset）”。后面也讲到，如果用 array 来示意数组的首地址，array[0] 就是偏移为 0 的地位，也就是首地址，array[k] 就示意偏移 k 个 type_size 的地位，所以计算 array[k] 的内存地址只须要用这个公式:
array[k]_address = base_address + k * type_size然而如果下标从 1 开始，那么计算 array[k]的内存地址会变成：
array[k]_address = base_address + (k-1)*type_size比照两个公式，不难发现从数组下标从 1 开始如果依据下标去拜访数组元素，对于 CPU 来说，就多了一次减法指令。
当然另一方面也是因为历史起因，c 语言设计者应用 0 开始作为数组的下标，起初的高级语言沿用了这一设计。
2.2、数组的特点
2.2.1、查问 O(1)
数组元素的拜访是通过下标来拜访的，计算机通过数组的首地址和寻址公式可能很疾速的找到想要拜访的元素
public int test01(int[] a,int i){return a[i];
// a[i] = baseAddress + i * dataSize
}代码的执行次数并不会随着数组的数据规模大小变动而变动，是常数级的，所以查问数据操作的工夫复杂度是 O(1)
2.2.2、插入删除 O(n)
数组是一段间断的内存空间，因而为了保障数组的连续性会使得数组的插入和删除的效率变的很低。
数据插入：
假如数组的长度为 n，当初如果咱们须要将一个数据插入到数组中的第 k 个地位。为了把第 k 个地位腾出来给新来的数据，咱们须要将第 k～n 这部分的元素都程序地往后挪一位。如下图所示：
插入操作对应的工夫复杂度是多少呢？
最好状况下是 O(1)的，最坏状况下是 O(n)的，均匀状况下的工夫复杂度是 O(n)。
数据删除：
同理可得：如果咱们要删除第 k 个地位的数据，为了内存的连续性，也须要搬移数据，不然两头就会呈现空洞，内存就不间断了，工夫复杂度依然是 O(n)。
思考一下在什么场景下用什么方法能进步数据删除的效率呢？
实际上，在某些非凡场景下，咱们并不一定非得谋求 数组中数据的连续性。如果咱们将屡次删除操作集中在一起执行，删除的效率是不是会进步很多呢？举个例子
数组 a[6] 中存储了 6 个元素：a1,a2,a3,a4,a5,a6。当初，咱们要顺次删除 a1,a2 这两个元素。
为了防止 a3,a4,a5,a6 这几个数据会被搬移两次，咱们能够先记录下曾经删除的数据。每次的删除操作并不是真正地搬移数据，只是记录数据曾经被删除。当数组没有更多空间存储数据时，咱们再触发执行一次真正的删除操作，这样就大大减少了删除操作导致的数据搬移。
对于这种思维，不就是 JVM 标记革除垃圾回收算法的核心思想吗？
这其实就是通知咱们，咱们并不需要去死记硬背某个数据结构或者算法，而是了解和学习它背地的思维和解决技巧。
3、面试实战
3.1、11：盛最多水的容器
华为，腾讯最近面试题：11：盛最多水的容器
1：暴力破解，奢侈解法
class Solution {
// 暴力破解法 枚举出所有坐标的组合, 求出每个组合
public int maxArea(int[] height) {
// 定义包容水的最大值
int max = 0 ;
for (int i=0; i<height.length;i++) {for (int j=i+1;j<height.length;j++) {int area = (j-i) * Math.min(height[i], height[j]);
max = Math.max(max, area);
}
}
return max;
}
}2：双指针（左右指针）（双指针夹逼）
class Solution {public int maxArea(int[] height) {
// 定义最大水的值
int res = 0;
// 定义双指针
int i=0;
int j= height.length -1;
while (i!=j) {int rest = Math.min(height[i],height[j]) * (j - i);
if (height[i] < height[j] ) {i++;}else {j--;}
res = res > rest ? res:rest;
}
return res;
}
}3.2、283：挪动零
字节跳动，滴滴打车最近面试题：283：挪动零
1：双指针（快慢指针），一维数组的下标变换操作思维
class Solution {// 双指针挪动 工夫复杂度 O(n) 空间复杂度 O(1)
public void moveZeroes(int[] nums) {if (nums == null || nums.length < 2) {return;}
// 从前到后非零元素的指针
int p1 = 0;
for (int i =0; i < nums.length; i++) {if (nums[i] != 0) {nums[p1] = nums[i];
p1++;
}
}
while (p1 < nums.length) {nums[p1] = 0;
p1++;
}
}
}留神查看精选题解，还有一次循环解决问题的解法
4、动静数组
4.1、需要
设计一个基于数组的汇合容器，满足以下条件：
1：java 中间接操作数组尽管获取数据比拟不便，然而插入删除比拟麻烦；因而容器要屏蔽（封装）底层的数组操作细节，反对数据的查问，插入，删除操作
2：java 中的数组类型一旦申请之后大小是不可变的，而容器须要反对动静扩容
4.2、实现
基于 java 语言的个性，咱们先定义接口，面向接口编程
（1）定义容器接口com.itheima.array.inf.List
package com.itheima.array.inf;
/**
* Created by 传智播客 * 黑马程序员.
*/
public interface List {
/**
* 返回容器中元素的个数
* @return
*/
int size();
/**
* 判断容器是否为空
* @return
*/
boolean isEmpty();
/**
* 查问元素在容器中的索引下标
* @param o 元素对象
* @return 在容器中的下标 不存在则返回 -1
*/
int indexOf(int o);
/**
* 判断容器是否蕴含某个特定的元素
* @param e
* @return
*/
boolean contains(int e);
/**
* 将元素增加到容器结尾
* @param e 要增加的元素
* @return 是否增加胜利
*/
boolean add(int e);
/**
* 向指定地位增加元素，该地位及当前的元素后移
* @param index 地位下标
* @param element 元素对象
*/
void add(int index, int element);
/**
* 用指定的元素替换指定地位的数据
* @param index 指定的地位索引下标
* @param element 新的元素
* @return 原始的元素
*/
int set(int index, int element);
/**
* 获取指定地位的元素
* @param index 索引下标
* @return 该地位的元素
*/
int get(int index);
/**
* 移除指定地位的元素
* @param index 索引下标
* @return 被移除的元素
*/
int remove(int index);
/**
* 革除容器中所有元素
*/
void clear();}（2）创立接口的实现类：com.itheima.array.ArrayList并且实现 List 接口。
（3）咱们的汇合容器底层要基于数组存储数据，因而定义成员数组，另外还须要返回汇合容器中元素的个数，因而定义一个代表元素个数的成员变量
// 存储元素的数组
int[] elementData;
// 容器中元素个数
private int size;（4）定义构造方法，在容器初始化时初始化数组，并定义一个初始化容量大小
// 容器默认容量大小
private final int DEFAULT_CAPACITY = 10;
public ArrayList() {this.elementData = new int[DEFAULT_CAPACITY];
}并且还能够重载构造函数，初始化时能够指定数组容量
public ArrayList(int initCapaticy) {if (initCapaticy > 0) {this.elementData = new int[initCapaticy];
}else {throw new IllegalArgumentException("initCapaticy error"+initCapaticy);
}
}（5）实现 size,isEmpty,indexOf,contains 等办法
@Override
public int size() {return size;}
@Override
public boolean isEmpty() {return size == 0;}
@Override
public int indexOf(int o) {for (int i=0; i < size; i++) {if ( elementData[i] == o) {return i;}
}
return -1;
}
@Override
public boolean contains(int e) {return indexOf(e) >=0;
}（6）实现增加元素到容器尾部的办法add，这个过程中波及到容器的动静扩容
@Override
public boolean add(int e) {
// 增加之前先确保容量是否够
ensureCapacity(size+1);
this.elementData[size++] = e;
return true;
}
private void ensureCapacity(int minCapacity) {if (minCapacity > this.elementData.length) {grow(minCapacity);
}
}
private void grow(int minCapacity) {
int oldCapacity = this.elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity < minCapacity) {newCapacity = minCapacity;}
// 用新的容量大小创立新的数组, 并将原数组中的数据拷贝到新数组中，并使得 this.elementData 指向新数组
copyOf(newCapacity);
}
private void copyOf(int newCapacity) {int[] newarray = new int[newCapacity];
System.arraycopy(this.elementData,0,newarray,0,size);
this.elementData = newarray;
}（7）实现 add(int index, int element),set(int index, int element),get(int index) 办法，办法中先查看索引地位是否正当，而后查看是否须要扩容，最初在指定索引地位插入元素
@Override
public void add(int index, int element) {rangeCheck(index);
// 因为要加一个元素，之前的元素不会被笼罩，只会向后挪动，所以可能在元素后移之前要先扩容
ensureCapacity(size+1);
// 扩容实现后先将从 index 处的元素顺次后移
System.arraycopy(this.elementData,index,this.elementData,index+1,size-index);
// 在 index 地位存入数据
this.elementData[index] = element;
size++;
}
@Override
public int set(int index, int element) {rangeCheck(index);
int oldElement = this.elementData[index];
this.elementData[index] = element;
return oldElement;
}
private void rangeCheck(int index) {if (index < 0 || index >size) {throw new IndexOutOfBoundsException("index:"+index+",size="+this.size);
}
}
@Override
public int get(int index) {rangeCheck(index);
return this.elementData[index];
}（8）实现remove(int index),clear
@Override
public int remove(int index) {rangeCheck(index);
int oldValue = this.elementData[index];
// 要挪动元素的个数
int moveCount = size - index -1;
System.arraycopy(this.elementData,index+1,this.elementData,index,moveCount);
// 清理最初一个地位的元素
this.elementData[size-1] = 0;
// 容器中元素个数 -1
size--;
return oldValue;
}
@Override
public void clear() {for (int i = 0; i < size; i++) {elementData[i] = 0;
}
size = 0;
}（9）重写一下 ArrayList 的 toString 办法，不便打印输出
@Override
public String toString() {// 依照 [1,2,3,5,6] 的格局输入数组中的元素
StringBuilder sb = new StringBuilder("[");
for (int i=0 ;i < size; i++) {sb.append(this.elementData[i]).append(",");
}
sb.append("]");
return sb.toString();}（10）编写测试类实现测试：com.itheima.array.ArrayListTest
package com.itheima.array;
import com.itheima.array.inf.List;
/**
* Created by 传智播客 * 黑马程序员.
*/
public class ArrayListTest {public static void main(String[] args) {List list = new ArrayList();
// 增加数据
list.add(1);
list.add(2);
list.add(3);
list.add(4);
list.add(5);
System.out.println("索引为 4 的元素:"+list.get(4));
list.add(6);
list.add(7);
list.add(8);
list.add(9);
list.add(10);
// 再添就要扩容了
list.add(11);
System.out.println("size="+list.size()+"--"+list);
System.out.println("是否蕴含 8:"+list.contains(8)+", 汇合容器是否为空:"+list.isEmpty());
list.add(12);
list.add(13);
list.add(14);
list.add(15);
// 既要扩容，元素又要后移
list.add(13,141);
System.out.println("size="+list.size()+"--"+list);
int set = list.set(13, 142);
System.out.println("set 办法返回的值:"+set+"-- 实现后的 list:"+list);
int remove = list.remove(13);
System.out.println("remove 办法返回的值:"+remove+"--remove 后的 list:"+list);
list.clear();
System.out.println("clear 之后:"+list);
}
}
思考一下课后实现：将 ArrayList 革新成能存储任意 jiava 类型数据的容器，应该如何实现？
提醒：将 int 类型的数组变换成 Object 类型的数组，而后革新相应的接口办法，增加泛型
作为高级语言编程者，是不是数组就无用武之地了呢？
当然不是，有些时候，用数组会更适合些，我总结了几点本人的教训。
1.Java ArrayList 无奈存储根本类型，比方 int、long，须要封装为 Integer、Long 类，而 Autoboxing、Unboxing 则有肯定的性能耗费，所以如果特地关注性能，或者心愿应用根本类型，就能够选用数组。
2. 如果数据大小当时已知，并且对数据的操作非常简单，用不到 ArrayList 提供的大部分办法，也能够间接应用数组。
总结一下就是说：对于业务开发，间接应用容器就足够了，省时省力。毕竟损耗一丢丢性能，齐全不会影响到零碎整体的性能。但如果你是做一些十分底层的开发，比方开发网络框架，性能的优化须要做到极致，这个时候数组就会优于容器，成为首选。
本文由传智教育博学谷 – 狂野架构师教研团队公布，转载请注明出处！
如果本文对您有帮忙，欢送关注和点赞；如果您有任何倡议也可留言评论或私信，您的反对是我保持创作的能源
