数据结构-数组

8次阅读

共计 4320 个字符,预计需要花费 11 分钟才能阅读完成。

为什么要学习数据结构?

因为计算机专业必学,数据结构就是研究数据如何在计算机进行组织和存储,使我们高效的操作数据。今天聊一聊线性结构中的数组。

总体来说可划分为以下三种

线性结构:数组,栈,队列,链表,哈希表
树结构:二叉树,二分搜索树,AVL,红黑树,堆,K- D 树,哈夫曼树,Trie 等等
图结构:邻接矩阵,邻接表

数组的数据结构

索引:数组是通过索引来操作数据的,索引从 0 开始
数组名:通过数组名[索引] 可以操作索引对应的数据,scores[2]

动态数组实践

首先一个数据结构,离不开数据的增删改查,那么就自己创建一个类,内部维护一个数组,来模拟这个过程。后面还可以像集合一样,优化使用泛型特性和动态扩容等机制。

1. 创建类,创建成员 arr,用来存放元素。创建 size 用来维护数组内现有的元素个数。
比如数组长度是 10,但是只存了 5 个元素,那么 size 就是 5

public class MyArray {
    // 声明一个数组
    private int[] arr;

    // 数组中存在的元素个数(不是 length,length 是数组的长度,也可以说是容量(capacity))private int size;

    // 因为数组提供了 length 方法,所以不需要创建和维护数组长度的变量
    //private int length;

    public MyArray() {this(10);// 不传参数,数组长度默认就是 10
    }

    public MyArray(int capacity) {arr = new int[capacity];//// 初始化数组
        size = 0;// 刚开始数组中没有数据
}

2. 创建好了之后,提供一些方法吧,先编写一些基本的方法,比如数组的容量,数组已存在的元素个数,数组是否为空等。这些方法都比较基础,所以也不需要过多解释了。

// 返回数组中存在的元素个数
public int getSize() {return this.size;}

// 获取容量
public int getCapacity() {return arr.length;}

// 判断数组是否为空
public boolean isEmpty() {return this.size == 0;}

// 查看数组中是否包含指定元素
public boolean contains(int e)
{for(int x = 0; x < size; x++) {if(arr[x] == e) {return true;}
    }
    return false;
}

// 查找指定元素在数组中的位置,如果没有,返回 -1
public int find(int e)
{for(int x = 0; x < size; x++) {if(arr[x] == e) {return x;}
    }
    return -1;
}

3. 添加元素,首先是添加元素到末尾。因为 size 就是目前数组内元素的个数,也就是需要添加到末尾索引的位置。如下图所示,要想添加元素到末尾,那么获取 size 的位置,添加就可以了,添加过后,维护一下 size 的数量。哦,对,记得方法的开始判断一下元素的边界,增加程序的健壮性。

// 添加元素到数组末尾
public void addLast(int e)
{if(size == arr.length) {throw new IllegalArgumentException("Add last failed.Array is Full");
    }
    arr[size] = e;
    size++;
}

如果想在指定索引处添加一个元素呢?除了添加以外,还要维护其他的数据。比如下图所示,原来数组是 66 88 99 100,现在要插入元素为“77”到索引 1 的位置,那么就要把索引 1 以后的元素,全部向右移动一格,给 ”77″ 腾出个地方,然后在插入,就解决问题了。(注意不可以跳跃插入,最大使用索引不能超过 size 所在的索引)

// 通过索引添加元素
public void addByIndex(int index,int e)
{
    // 插入的元素的索引只能在 0 和 size 期间
    if(index < 0 || index > size) {throw new ArrayIndexOutOfBoundsException("Add failed.Require index >=0 & <= size");
    }
    // 添加一个元素,size 就加一,等 size 个数等于数组长度时,抛异常
    if(size == arr.length) {throw new IllegalArgumentException("Add last failed.Array is Full");
    }
    // 改变原始数据的位置,从 size- 1 的位置到 index 的位置
    for(int i = size - 1; i >= index; i--)
    {arr[i + 1] = arr[i];
    }
    // 插入新的元素
    arr[index] = e;
    size++;
}

那添加一个元素到头部也就很 easy 了,因为原理和上面一样,需要把头部往后的所有元素都向右移动一格,然后在插入。仔细一看,向尾部和头部插入元素都可以复用上面的代码。

// 添加元素到数组末尾
public void addLast(int e)
{addByIndex(size,e);
}

// 添加元素到数组开头
public void addFirst(int e)
{addByIndex(0,e);
}

4. 删除元素,删除元素和添加其实差不多,添加是要把从添加位置的索引到最后的元素索引的所有数据做一个向右移动,删除是把从添加位置的索引到最后的元素索引的所有元素做一个向左移动。


public int removeByIndex(int index)
{if(index < 0 || index >= size) {throw new ArrayIndexOutOfBoundsException("Remove failed.Require index >=0 & <= size");
    }
    int temp = arr[index];
    for(int x = index; x < size; x++)
    {arr[x] = arr[x + 1];
    }
    size--;
    return temp;
}

public int removeFirst()
{return removeByIndex(0);
}
public int removeLast()
{return removeByIndex(size-1);
}


// 按照元素删除
public boolean removeElement(int e)
{int result = find(e);// 先找对应的元素
    if(result != -1)// 如果有这个元素,则删除
    {removeByIndex(result);// 删除这个元素
        return true;
    }
    else
    {return false;}
}

5. 重写 toString,方便使用 System.out.print 的时候显示数据的容量变化以及元素变化

// 展示数组元素的方法
@Override
public String toString() {StringBuilder sb = new StringBuilder();
    sb.append(String.format("Array size = %d,capacity=%d\n",size,arr.length));
    sb.append("[");
    for(int x = 0; x < size; x++)
    {sb.append(arr[x]);
        if(x != size - 1)
        {sb.append(",");
        }
    }
    sb.append("]");
    return sb.toString();}

6. 可以自己定义个 main 方法测试一下,都没啥问题。

public static void main(String[] args)
{MyArray arr = new MyArray(20);
    for(int x = 1000; x < 1010; x++)
    {arr.addLast(x);
    }
    System.out.println(arr);
}
Array size = 10,capacity=20
[1000,1001,1002,1003,1004,1005,1006,1007,1008,1009]

7. 泛型
但是这个代码目前是有弊端的,能不能像 Java 中集合那样,可以往数组里面添加任意类型的数据呢?可不可以等到数组容量不够的时候,自动帮我扩容呢?首先先解决一下 ” 泛型 ” 问题,这个问题比较简单,把类改成泛型类就可以啦,增加元素的方法都改成泛型,返回的元素也修改成泛型。

// 这样
public class MyArray<E> {
    // 声明一个数组
    private E[] arr;
// 这样
public MyArray(int capacity) {arr = (E[])new Object[capacity];//// 初始化数组
// 还有这样
public E removeByIndex(int index)
public boolean removeElement(E e)

8. 扩容操作

假如数组是这些元素,那么当 size = capacity 的时候,也就是插入的元素数量等于数组长度,俗话说就是数组满了,那么这时候开始扩容。

扩容的原理其实就是再申请一个比当前这个数组还要大的一个数组(至于大多少呢?你可以自己定义。ArrayList 扩容机制是大原数组的 1.5 倍,当然这个值没有对和错,你自己根据业务场景定就好。但尽量做一个权衡,太大了浪费空间,太小了会经常扩容,导致程序变慢。)然后一次性的把原数组的数据放到新数组,在改变一下变量对数组的引用,让变量指向新数组,这个扩容操作在方法内,方法执行完就弹栈了,也就没有变量在指向原数组了,原数组也就会被垃圾回收了。

扩容内存图解

扩容方法实现

// 数组扩容方法
private void resize(int length) {E[] newArr = (E[])new Object[length];// 声明新的数组
    for(int x = 0; x < size; x++)// 将原数组所有的数据复制到新数组中
    {newArr[x] = arr[x];
    }
    arr = newArr;// 改变引用,变量指向新数组
}

addByIndex 方法的变动,当元素占满数组时,进行扩容

// 元素添加的时候,满了不再抛异常了,进行扩容扩容机制
if(size == arr.length) {resize(arr.length * 2);
    //throw new IllegalArgumentException("Add last failed.Array is Full");
}

如果元素变少时,数组太大,也会浪费空间,可以进行缩容
removeByIndex 方法的变动

// 如果元素个数只占到整体数组长度的一半以下,为了避免浪费内存空间,进行缩容
if(size < arr.length / 2)
{resize(arr.length / 2);
}

明天记录该数组实现的时间复杂度,以及均摊复杂度问题和防止复杂度震荡问题。

正文完
 0

数据结构-数组

8次阅读

共计 14856 个字符,预计需要花费 38 分钟才能阅读完成。

Create by jsliang on 2019-07-31 11:22:27
Recently revised in 2019-08-15 16:00:00

数组 – 最简单的内存数据结构

一 目录

不折腾的前端,和咸鱼有什么区别

| 目录 |
| — |
| 一 目录 |
| 二 前言 |
|  2.1 为什么用数组?|
|  2.2 如何创建和初始化数组?|
|  2.3 如何访问数组?|
|  2.4 二维、三维乃至多维数组以及如何访问?|
|  2.5 来份案例热热身?|
|  2.6 悬难疑惑?|
| 三 数组的增删改查及其工作应用 |
|  3.1 数组的新增操作 |
|  3.2 数组的删除和修改操作 |
|   3.2.1 删除和修改之 splice() |
|   3.2.2 删除和修改之 slice() |
|   3.2.3 删除和修改之 filter() |
|  3.3 数组的查询操作 |
| 四 数组的常用知识点 |
|  4.1 push() – 末尾添加元素 |
|  4.2 unshift() – 开头添加元素 |
|  4.3 pop() – 末尾删除元素 |
|  4.4 shift() – 开头删除元素 |
|  4.5 splice() – 增删改元素 |
|  4.6 concat() – 拼合两个数组 |
|  4.7 filter() – 过滤数组元素 |
|  4.8 forEach() – 遍历操作原数组 |
|  4.9 join() – 数组转字符串 |
|  4.10 indexOf() – 顺序查找第一个 |
|  4.11 lastIndexOf() – 倒序查找第一个 |
|  4.12 map() – 遍历返回新数组 |
|  4.13 reverse() – 反转数组元素 |
|  4.14 slice() – 查找指定位置元素 |
|  4.15 sort() – 数组排序 |
|  4.16 toString() – 数组转字符串 |
|  4.17 includes() – 数组包含某元素 |
|  4.18 fill() – 填充数组 |
|  4.19 reduce() – 数组累计 |
|  4.20 find() – 查找数组元素 |
|  4.21 findIndex() – 查找元素索引 |
| 五 总结 |

二 前言

返回目录

如果小伙伴刚好看到这篇文章,想了解下 算法与数据结构 中,关于 数组 的知识。

那么,希望看到这篇文章的小伙伴拥有:

  1. 基本的 JavaScript 知识。
  2. 知道一点点的数组及其用法。

同时,希望看完这篇文章的小伙伴掌握:

  1. 数组基本常识
  2. 数组的增删改查
  3. 数组的常用知识点

但是,jsliang 无法确定小伙伴是否真具备上面知识点(前置条件),所以前言会简略介绍下数组,希望能先小科普一下,方便后面共同探讨。

如果小伙伴已经清楚数组相关基础知识点,可以跳过【前言】部分;

如果小伙伴不清楚或者想回顾下热热身,可以往下慢慢看。

2.1 为什么用数组?

返回目录

假设你写代码,列出星期一到星期日锻炼的时间,你可能会写成:

let Monday = 1,
  Tuesday = 2,
  Wednesday = 3,
  Thursday = 4,
  Friday = 5,
  Saturday = 6,
  Sunday = 7;

这仅仅是一周的数据。

如果要你统计一年的数据,那样也太麻烦了,毕竟命名 365 个字段,会让人极度不适。

于是有了数组:

let exercise = [1, 2, 3, 4, 5, 6, 7];

这不就变得简便了么。

2.2 如何创建和初始化数组?

返回目录

let a = [];

let b = new Array();

这样都是可行的。

如果你想初始化有长度的数组,或者数组一开始就有值:

let a = [1, 2, 3]; // [1, 2, 3]

let b = new Array(3); // [undefined, undefined, undefined]

let c = new Array([1, 2, 3]); // [1, 2, 3]

let d = new Array(3).fill(1); // [1, 1, 1]

let e = new Array(3).fill([]); // [[], [], []]

当然,后面两个通过 fill() 创建的数组,推荐碰到 fill() 方法的时候再进一步了解。

变量 e 形成的数组会出问题的嗷~

2.3 如何访问数组?

返回目录

let a = [1, 2, 3];
console.log(arr[0]); // 1
console.log(arr[1]); // 2
console.log(arr[2]); // 3

记住数组的下标是从 0 开始的。

如果某个程序猿跟你表白说你是它心中第 0 位的人……你还是拒绝“他”吧,已经走火入魔没救了。

2.4 二维、三维乃至多维数组以及如何访问?

返回目录

我们平时使用的 [1, 2, 3] 这种形式,称为一维数组。

而如果数组中嵌套数组,每嵌套多一层,就加一个维度,例如:

二维数组

let a = [[1, 2, 3], [4, 5]]; // 二维数组

// 访问二维数组
for (let i = 0; i < a.length; i++) {for (let j = 0; j < a[i].length; j++) {console.log(a[i][j]);
  }
}
// 1
// 2
// 3
// 4
// 5

三维数组

let b = [[1, 2, [3, 4]], [5, 6]]; // 三维数组

// 访问三维数组
for (let i = 0; i < b.length; i++) {for (let j = 0; j < b[i].length; j++) {for (let k = 0; k < b[i][j].length; k++) {console.log(b[i][j][k]);
    }
  }
}
// 3
// 4

至于多维数组,小伙伴可以自行推算。

2.5 来份案例热热身?

返回目录

在这里,贴两份代码带大家热热身。

遍历斐波那契数列

const fibonacciSequence = [1, 1, 2, 3, 5, 8, 13];

for (let i = 0; i < fibonacciSequence.length; i++) {console.log(fibonacciSequence[i]);
}

// 1 1 2 3 5 8 13

实现斐波那契数列

const fibonacciSequence = [1, 1];

for (let i = 2; i < 20; i++) {fibonacciSequence[i] = fibonacciSequence[i - 1] + fibonacciSequence[i - 2];
}

console.log(fibonacciSequence);

// [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765]

2.6 悬难疑惑?

返回目录

数组虽然是最简单的内存数据结构,但是有些坑还是需要注意的,以免深陷无法自拔,例如:传值和传址。

// 传值
let str1 = '1';
str2 = str1;
str2 = '2';
console.log(str1); // 1
console.log(str2); // 2

// 传址
let arr1 = [1, 2, 3];
arr2 = arr1;
arr2[0] = 4;
console.log(arr1); // [4, 2, 3]
console.log(arr2); // [4, 2, 3]

问:jsliang 你怎么看传值和传址,能不能详细介绍下?

答:看下我那篇面试文章 jsliang 的 2019 面试准备 或者百度下相关知识点吧,毕竟咱主要目的不是讲这个知识点,在这里引出是为了让小伙伴们热热身。

如果小伙伴觉得非常有必要将热身写成详细清单,小伙伴记得私信我哈

更多的数组问题或者相关隐藏点,还是等我想起来或者小伙伴提到,我再进行补充吧。

三 数组的增删改查及其工作应用

返回目录

提起 算法与数据结构,很多前端小伙伴可能第一时间反应:“卧槽这有卵用”,“为啥面试都搞这个,进去后还不是写 if…else…”……

enm… 还真有用。

jsliang 结合数组的增删改查及其工作中的使用场景,跟你聊聊数组的妙用。

3.1 数组的新增操作

返回目录

话不多说,关门,放、放代码:

let arr = [1, 2, 3];

// 通过 push() 方法
arr.push(4); // [1, 2, 3, 4]

// 通过 length 属性
arr[arr.length] = 5; // [1, 2, 3, 4, 5]

数组新增元素的两种方式:

  • 一种是通过 push() 方法,直接将元素添加到数组最后一位。
  • 另一种是通过利用数组的 length 属性,该属性可以显示数组的长度,而 arr[arr.length] 即给其最大长度后面再加一个长度。

既然上面我们通过两种方式,往数组后面插入了新元素,那么有没有方法,往数组前面插入新元素呢?

有!

let arr = [3, 4, 5];

// 通过 unshift 方法
arr.unshift(2); // [2, 3, 4, 5]

// 通过遍历数组
for (let i = arr.length; i >= 0; i--) {arr[i] = arr[i - 1];
}
arr[0] = 1;
// [1, 2, 3, 4, 5]

很好,通过这四种方式,我们就掌握了往数组头部和数组尾部新增元素。

那么,在工作中它们有何作用呢?

目前使用最多的是 push() 操作,通常用于给数组新增元素。

举例常见的场景:给 Table 新增一行数据。

数据内容
新增 第一行数据 – jsliang
新增 第二行数据 – 梁渣渣

jsliang 尝试自己画了个表格,太小了不好贴图,就使用 Markdown 演示下好了。

如上,我们点击【新增】按钮的时候,就可以直接往 Table 下面新增一行数据。

而如果是 unshift(),目前工作还未接触到,如果有碰到的小伙伴,欢迎贴出应用场景~

3.2 数组的删除和修改操作

返回目录

首先jsliang 觉得删除和修改操作在一定程度上利用的数组 API 非常一致,所以贴在一起写了:

  • splice()
  • slice()
  • filter()

在这里,我们介绍三种方法进行操作。

3.2.1 删除和修改之 splice()

返回目录

对于前端来说,数组的 splice() 方法是个万金油,它能适用于新增、修改、删除这些场景。

那么,如何利用 splice() 进行新增、修改和删除呢?

我们先了解下 splice() 特性:

var months = ['Jan', 'March', 'April', 'June'];

// 新增操作
months.splice(1, 0, 'Feb');
// ['Jan', 'Feb', 'March', 'April', 'June']

// 修改操作
months.splice(4, 1, 'May');
// ['Jan', 'Feb', 'March', 'April', 'May']

// 删除操作
months.splice(4, 1);
// ['Jan', 'Feb', 'March', 'April']

如上,splice() 的语法是:array.splice(start, deleteCount, item1, item2, ...)

  1. start 为数组的开始坐标
  2. deleteCount 为需要从开始坐标起,删除的个数,可以为 0,代表不删除
  3. item 为需要新增进去的元素。

那么,讲到这里,小伙伴们应该对 splice() 有深刻了解了。

下面我们讲讲 splice() 对于修改操作,在工作中的使用场景:

修改 Table 某行的数据

let list = [{ id: '1', name: 'jsliang'},
  {id: '2', name: '梁峻荣'},
  {id: '3', name: 'JavaScriptLiang'},
];

function addData(rowIndex) {
  list.splice(rowIndex, 0, {
    id: '4',
    name: '梁渣渣',
  });
}

addData(1);

console.log(list);
// [//   { id: '1', name: 'jsliang'},
//   {id: '4', name: '梁渣渣'},
//   {id: '2', name: '梁峻荣'},
//   {id: '3', name: 'JavaScriptLiang'},
// ]

如上,我们希望将数据添加到指定位置(addData(n)),这时候我们就使用了 splice() 对其进行操作,从而修改了原数组。

3.2.2 删除和修改之 slice()

返回目录

而作为和 splice() 一个字母之差的 slice(),又是何等的优秀呢?

首先,咱们科普下:

  • splice():所进行的操作会影响到原数组
  • slice():所进行的操作不会影响到原数组

什么意思呢?相信很多小伙伴在网上看数组相关攻略的时候,都会看到一堆的区分:这个方法会影响到原数组,这个方法不会影响到原数组……等等

其实很容易理解:我想吃两块蛋糕,但是现在我只有一块蛋糕。如果我还惦记着自己的减肥,那么我可以将这款蛋糕切成两块,这样我就吃到两块蛋糕(影响到原数组);如果我觉得吃了两块蛋糕不会肥,那我就去照着这块蛋糕的样子,再买一块(不影响原数组)。

当然,这里都说是修改咯,slice() 还是有丢丢影响到数组的:

const str = 'jsliang';
str.slice(0, 2); // 'js'
str.slice(2); // 'liang'

对于 slice() 来说,它的参数为:str.slice(beginSlice, endSlice)。其中:

  • beginSlice:从该索引(以 0 为基数)处开始提取原字符串中的字符。
  • endSlice:结束位置(以 0 为基数),如果不传,默认到数组末尾。

注意,splice() 的第二个参数是影响到数组的个数,而 slice() 的第二个参数是结束的位置,所以 slice() 一般写法是:slice(index, index + length),即需要修改的位置(index),及其影响的长度(length)。

很好,说完这一堆废话,咱们讲讲工作中的使用场景:

let list = [{ id: '1', name: 'jsliang'},
  {id: '2', name: '梁峻荣'},
];

function insertData(rowId) {
  list = [...list.slice(0, list.findIndex(item => item.id === rowId) + 1),
    {
      id: '3',
      name: '',
    },
    ...list.slice(list.findIndex(item => item.id === rowId) + 1),
  ]
}

insertData('1');

console.log(list);
// [//   { id: '1', name: 'jsliang'},
//   {id: '3', name: ''},
//   {id: '2', name: '梁峻荣'},
// ]

还记得在上面我们说过用 slice() 做修改操作,也会影响到原数组 吗?是的,在这份代码我们可以看出,我们根据之前的数组,组合成一个新的数组,让这个元素指向了新的数组地址。

当然,这个并不重要,我们讲讲它的使用场景:在需要修改 Table 某行的时候,我们将其唯一值(id)传递了过去,然后方法 insertData 根据传递的 id 找到那一行,对其进行了修改。

如果你感觉并非那么容易理解,你可以尝试下将 rowId 换成 index,这是个明智的选择。

3.2.3 删除和修改之 filter()

返回目录

首先jsliang 对于 filter() 这个方法也不是很常使用:

我有个朋友,网名就叫 filter(),每次使用它就跟使唤我朋友一样:“filter!我有事请你帮忙~”

但是,作为团队的一枚 螺丝钉,业务写得多了,你还是会接触到同事的代码的,所以还是有必要对其进行了解:

function isBigEnough(element) {return element >= 10;}
var filtered = [12, 5, 8, 130, 44].filter(isBigEnough);
// [12, 130, 44]

// 如果你喜欢用 ES6 的箭头函数
const number = [12, 5, 8, 130, 44];
const filterNumber = number.filter(item => item >= 10);
// [12, 130, 44]

很好,讲到这里,我们就顺带科普下 filter() 这个方法了:

  • 语法arr.filter(callback)
  • callback:用来测试数组的每个元素的函数。返回 true 表示该元素通过测试,保留该元素,false 则不保留。它会返回由通过元素组成的数组,或者是一个空数组 []。它接受以下三个参数:

    • element:数组中当前正在处理的元素
    • index:正在处理的元素在数组中的索引。
    • array:调用了 filter 的数组本身。

所以一个比较完整的 filter() 可以这么写:

const number = [12, 5, 8, 130, 44];
const filterNumber = number.filter((item, index, array) => {console.log(array);
  return item >= 10 && index > 3;
});
// 输出 5 次 [12, 5, 8, 130, 44]
// 最终 filterNumber 的值为 [44]

OK,介绍完毕,咱们看下应用场景:

let list = [{ id: '1', name: 'jsliang'},
  {id: '2', name: '梁峻荣'},
  {id: '3', name: 'JavaScriptLiang'},
];

function changeData(id, newObj) {list = [...list.filter(item => item.id !== id), newObj];
}

changeData('2', {
  id: '4',
  name: '梁渣渣',
});
[{id: "1", name: "jsliang"},
  {id: "3", name: "JavaScriptLiang"},
  {id: "4", name: "梁渣渣"},
]

这样,我们就将 id 为 2 的 梁峻荣 那行修改为 id 为 4 的 梁渣渣

3.3 数组的查询操作

返回目录

上面讲完了新增、删除和修改,最后还是讲讲查询操作。

相比于上面的话题,查询的形式就多了。

例如说,我想知道数组中所有对象的 id:

let list = [{ id: '1', name: 'jsliang'},
  {id: '2', name: '梁峻荣'},
  {id: '3', name: 'JavaScriptLiang'},
];

const ids = list.map(item => item.id);
// ["1", "2", "3"]

无可厚非这也是一种查询,而且在工作中特实用,毕竟像 Ant Design 等,下拉框多选等情况,就需要将数据的 id 查找出来。

又或者说,我想知道 JavaScript 出现在哪个索引值下,它的 id 是多少:

let list = [{ id: '1', name: 'jsliang'},
  {id: '2', name: '梁峻荣'},
  {id: '3', name: 'JavaScriptLiang'},
];

const id1 = list[list.findIndex(item => item.name === 'JavaScriptLiang')].id;
// '3'

// 当然有更快速的
const id2 = list.find(item => item.name === 'JavaScriptLiang').id;
// '3'

当然,JavaScript 还有很多操作,可以查询数组中的数据。

当然,不管怎么说,jsliang 还是强烈推荐将这些方法记下来,然后在工作中不停尝试使用,这样你才会有所提升。

四 数组的常用知识点

返回目录

下面开始无聊的 五年高考三年模拟 试题训练,希望小伙伴能在了解某个方法之后,通过其下面的 LeetCode 进行相应训练,从而熟练掌握数组的常用知识点。

4.1 push() – 末尾添加元素

返回目录

  • MDN – push()

push() 方法将一个或多个元素添加到数组的末尾,并返回该数组的新长度。

let arr = [1, 2, 3];

// 通过 push() 方法
arr.push(4); // [1, 2, 3, 4]

实战 LeetCode

  • 000 – 字谜分组(puzzle-grouping)
  • 020 – 有效的括号(valid-parentheses)
  • 067 – 二进制求和(add-binary)
  • 088 – 合并两个有序数组(merge-sorted-array)
  • 118 – 杨辉三角(pascals-triangle)

4.2 unshift() – 开头添加元素

返回目录

  • MDN – unshift()

unshift() 方法将一个或多个元素添加到数组的开头,并返回该数组的新长度。

let arrA = ['1'];
arrA.unshift('0');
console.log(arrA); // ['0', '1']

let arrB = [4, 5, 6];
arrB.unshift(1, 2, 3);
console.log(arrB); // [1, 2, 3, 4, 5, 6]

实战 LeetCode

  • 066 – 加一(plus-one)
  • 067 – 二进制求和(add-binary)
  • 189 – 旋转数组(rotate-array)
  • 202 – 快乐数(happy-number)

4.3 pop() – 末尾删除元素

返回目录

  • MDN – pop()

pop() 方法从数组中删除最后一个元素,并返回该元素的值。此方法更改数组的长度。

let arr = [1, 2, 3, 4];
for(let i = 0, time = 1; i < arr.length; time++) {console.log(`------\n 第 ${time} 次遍历:`);
  console.log(arr.pop());
  console.log(arr);
}

/* Console:------
第 1 次遍历:4
[1, 2, 3]
------
第 2 次遍历:3
[1, 2]
------
第 3 次遍历:2
[1]
------
第 4 次遍历:1
[]
*/

实战 LeetCode

  • 007 – 整数反转(reverse-integer)
  • 020 – 有效的括号(valid-parentheses)
  • 189 – 旋转数组(rotate-array)
  • 202 – 快乐数(happy-number)
  • 225 – 用队列实现栈(implement-stack-using-queues)

4.4 shift() – 开头删除元素

返回目录

  • MDN – shift()

shift() 方法从数组中删除第一个元素,并返回该元素的值。此方法更改数组的长度。

let str = [1, 2, 3];
console.log(str.shift()); // 1
console.log(str.shift()); // 2
console.log(str.shift()); // 3
console.log(str.shift()); // undefined

实战 LeetCode

  • 014 – 最长公共前缀(longest-common-prefix)
  • 171 – Excel 表列序号(excel-sheet-column-number)
  • 225 – 用队列实现栈(implement-stack-using-queues)
  • 232 – 用栈实现队列(implement-queue-using-stacks)

4.5 splice() – 增删改元素

返回目录

  • MDN – splice()

splice() 方法通过删除或替换现有元素或者原地添加新的元素来修改数组, 并以数组形式返回被修改的内容。此方法会改变原数组。

var months = ['Jan', 'March', 'April', 'June'];
months.splice(1, 0, 'Feb');

console.log(months);
// ['Jan', 'Feb', 'March', 'April', 'June']

months.splice(4, 1, 'May');

console.log(months);
// ['Jan', 'Feb', 'March', 'April', 'May']

实战 LeetCode

  • 026 – 删除排序数组中的重复项(remove-duplicates-from-sorted-array)
  • 027 – 移除元素(remove-element)
  • 088 – 合并两个有序数组(merge-sorted-array)
  • 136 – 只出现一次的数字(single-number)
  • 189 – 旋转数组(rotate-array)

4.6 concat() – 拼合两个数组

返回目录

  • MDN – concat()

concat() 方法用于合并两个或多个数组。此方法不会更改现有数组,而是返回一个新数组。

const newArr = [1, 2, 3].concat(['a', 'b', 'c']);

// [1, 2, 3, 'a', 'b', 'c']

实战 LeetCode

  • 004 – 寻找两个数组的中位数(median-of-two-sorted-arrays)

4.7 filter() – 过滤数组元素

返回目录

  • MDN – filter()

filter() 方法创建一个新数组, 其包含通过所提供函数实现的测试的所有元素。

function isBigEnough(element) {return element >= 10;}
var filtered = [12, 5, 8, 130, 44].filter(isBigEnough);
// [12, 130, 44]

实战 LeetCode

  • 349 – 两个数组的交集(intersection-of-two-arrays)

4.8 forEach() – 遍历操作原数组

返回目录

  • MDN – forEach()

forEach() 方法对数组的每个元素执行一次提供的函数。

const items = ['item1', 'item2', 'item3'];
const copy = [];

// 使用 for 遍历
for (let i = 0; i < items.length; i++) {copy.push(items[i]);
}

// 使用 forEach 遍历
items.forEach(function(item){copy.push(item);
});

实战 LeetCode

  • 073 – 矩阵置零(set-matrix-zeroes)
  • 350 – 两个数组的交集 II(intersection-of-two-arrays-ii)
  • 383 – 赎金信(ransom-note)
  • 434 – 字符串中的单词数(number-of-segments-in-a-string)

4.9 join() – 数组转字符串

返回目录

  • MDN – join()

join() 方法将一个数组(或一个类数组对象)的所有元素连接成一个字符串并返回这个字符串。

var a = ['Wind', 'Rain', 'Fire'];
var myVar1 = a.join();      // myVar1 的值变为 "Wind,Rain,Fire"
var myVar2 = a.join(',');  // myVar2 的值变为 "Wind, Rain, Fire"
var myVar3 = a.join('+'); // myVar3 的值变为 "Wind + Rain + Fire"
var myVar4 = a.join('');    // myVar4 的值变为"WindRainFire"

实战 LeetCode

  • 000 – 字谜分组(puzzle-grouping)
  • 067 – 二进制求和(add-binary)
  • 125 – 验证回文串(valid-palindrome)
  • 190 – 颠倒二进制位(reverse-bit)
  • 242 – 有效的字母异位词(valid-anagram)

4.10 indexOf() – 顺序查找第一个

返回目录

  • MDN – indexOf()

indexOf() 方法返回调用 String 对象中第一次出现的指定值的索引。

'I am jsliang'.indexOf('a', 4); // 9
[1, 3, 1, 4].indexOf(1, 1); // 2
'怪盗 jsliang'.indexOf('我'); // -1

实战 LeetCode

  • 001 – 两数之和(two-sum)
  • 027 – 移除元素(remove-element)
  • 028 – 实现 strStr(implement-strstr)
  • 205 – 同构字符串(isomorphic-strings)
  • 217 – 存在重复元素(contains-duplicate)

4.11 lastIndexOf() – 倒序查找第一个

返回目录

  • MDN – lastIndexOf()

lastIndexOf() 方法返回指定元素(也即有效的 JavaScript 值或变量)在数组中的最后一个的索引,如果不存在则返回 -1。

var array = [2, 5, 9, 2];
var index = array.lastIndexOf(2); // 3

实战 LeetCode

暂无题目

4.12 map() – 遍历返回新数组

返回目录

  • MDN – map()

map() 方法创建一个新数组,其结果是该数组中的每个元素都调用一个提供的函数后返回的结果。

[1, 2, 3, 4].map(item => item * 2) // [2, 4, 6, 8]

[{
  name: 'jsliang',
  age: 24,
}, {
  name: '梁峻荣',
  age: 124
}].map((item, index) => {return `${index} - ${item.name}`;
}) // ['0 - jsliang', '1 - 梁峻荣']

实战 LeetCode

  • 001 – 两数之和(two-sum)
  • 205 – 同构字符串(isomorphic-strings)
  • 412 – FizzBuzz(fizz-buzz)
  • 434 – 字符串中的单词数(number-of-segments-in-a-string)

4.13 reverse() – 反转数组元素

返回目录

  • MDN – reverse()

reverse() 方法将数组中元素的位置颠倒, 并返回该数组。该方法会改变原数组。

let arr = [1, 2, 3];
arr.reverse();
console.log(arr); // [3, 2, 1]

实战 LeetCode

  • 067 – 二进制求和(add-binary)
  • 125 – 验证回文串(valid-palindrome)
  • 171 – Excel 表列序号(excel-sheet-column-number)
  • 190 – 颠倒二进制位(reverse-bit)
  • 344 – 反转字符串(reverse-string)

4.14 slice() – 查找指定位置元素

返回目录

  • MDN – slice()

slice() 方法提取一个字符串的一部分,并返回一新的字符串。

const str = 'jsliang';
str.slice(0, 2); // 'js'
str.slice(2); // 'liang'

实战 LeetCode

  • 005 – 最长回文子串(longest-palindromic-substring)
  • 014 – 最长公共前缀(longest-common-prefix)
  • 088 – 合并两个有序数组(merge-sorted-array)
  • 459 – 重复的字符串(repeated-substring-pattern)

4.15 sort() – 数组排序

返回目录

  • MDN – sort()

sort() 对数组的元素进行排序,并返回数组。

[4, 2, 5, 1, 3].sort(), // [1, 2, 3, 4, 5]
[4, 2, 5, 1, 3].sort((a, b) => a < b), // [5, 4, 3, 2, 1]
['a', 'd', 'c', 'b'].sort(), // ['a', 'b', 'c', 'd']
['jsliang', 'eat', 'apple'].sort(), // ['apple', 'eat', 'jsliang']

实战 LeetCode

  • 268 – 缺失数字(missing-number)
  • 389 – 找不同(find-the-difference)
  • 414 – 第三大的数(third-maximum-number)
  • 448 – 找出所有数组中消失的数字(find-all-numbers-disappeared-in-an-array)
  • 455 – 分发饼干(assign-cookies)

4.16 toString() – 数组转字符串

返回目录

  • MDN – toString()

toString() 返回一个字符串,表示指定的数组及其元素。

let arr = [1, 2, 3];
arr.toString(); // '1,2,3'

实战 LeetCode

  • 190 – 颠倒二进制位(reverse-bit)
  • 191 – 位 1 的个数(number-of-1-bits)
  • 258 – 各位相加(add-digits)
  • 443 – 压缩字符串(string-compression)

4.17 includes() – 数组包含某元素

返回目录

  • MDN – includes()

includes() 方法用来判断一个数组是否包含一个指定的值,根据情况,如果包含则返回 true,否则返回 false。

[1, 2, 3].includes(2);     // true
[1, 2, 3].includes(4);     // false
[1, 2, 3].includes(3, 3);  // false
[1, 2, 3].includes(3, -1); // true
[1, 2, NaN].includes(NaN); // true

实战 LeetCode

  • 263 – 丑数(ugly-number)

4.18 fill() – 填充数组

返回目录

  • MDN – fill()

fill() 方法用一个固定值填充一个数组中从起始索引到终止索引内的全部元素。不包括终止索引。

let arr = [1, 2, 3, 4, 5];
arr = new Array(arr.length).fill(0);
// arr - [0, 0, 0, 0, 0];

实战 LeetCode

  • 073 – 矩阵置零(set-matrix-zeroes)

4.19 reduce() – 数组累计

返回目录

  • MDN – reduce()

reduce() 方法对数组中的每个元素执行一个由您提供的 reducer 函数(升序执行),将其结果汇总为单个返回值。

[1, 2, 3, 4].reduce((prev, next) => {return prev + next;}); // 10
['前端', 'pang', 'liang'].reduce((prev, next, index) => {return (index = 0 ? '-js' : '') + prev +'js' + next;
}); // 前端 -jspang-jsliang

实战 LeetCode

  • 014 – 最长公共前缀(longest-common-prefix)
  • 202 – 快乐数(happy-number)
  • 258 – 各位相加(add-digits)
  • 268 – 缺失数字(missing-number)
  • 049 – 字母异位词分组(group-anagrams)

4.20 find() – 查找数组元素

返回目录

  • MDN – find()

find() 方法返回数组中满足提供的测试函数的第一个元素的值。否则返回 undefined。

var inventory = [{name: 'apples', quantity: 2},
  {name: 'bananas', quantity: 0},
  {name: 'cherries', quantity: 5}
];

function findCherries(fruit) {return fruit.name === 'cherries';}

inventory.find(findCherries));
// {name: 'cherries', quantity: 5}

实战 LeetCode

暂无实战

4.21 findIndex() – 查找元素索引

返回目录

  • MDN – findIndex()

findIndex() 方法返回数组中满足提供的测试函数的第一个元素的索引。否则返回 -1。

var array1 = [5, 12, 8, 130, 44];

function isLargeNumber(element) {return element > 13;}

array1.findIndex(isLargeNumber); // 3

实战 LeetCode

暂无实战

五 总结

返回目录

经过前面一系列的折腾,我们基本对数组的各种操作有所了解,虽然谈不上 精通,但是支持日常工作是毫无问题的了。

写到这里,jsliang 查询了下字数:36800。

是的,路漫漫其修远兮,就连我一开始写这篇文章的时候,我也没想到它有这么多的内容可以写,而且还是没有将一些 ES6、ES7 的数组新特性加上的情况下篇幅。

数组 – 最简单的内存数据结构,也是工作中最常使用的数据结构。

如果你觉得 jsliang 写得很 OK,欢迎点赞、留言、加微信好友、关注微信公众号等。

咱们,将继续探索,扎实编程基础,了解更多的数据结构和算法!

所有联系方式尽在:jsliang 的文档库


不折腾的前端,和咸鱼有什么区别!

jsliang 会每天更新一道 LeetCode 题解,从而帮助小伙伴们夯实原生 JS 基础,了解与学习算法与数据结构。

扫描上方二维码,关注 jsliang 的公众号,让我们一起折腾!

<img alt=” 知识共享许可协议 ” style=”border-width:0″ src=”https://i.creativecommons.org…; />
<span xmlns:dct=”http://purl.org/dc/terms/&quot; property=”dct:title”>jsliang 的文档库 </span> 由 梁峻荣 采用 知识共享 署名 - 非商业性使用 - 相同方式共享 4.0 国际 许可协议进行许可。
基于 https://github.com/LiangJunro… 上的作品创作。
本许可协议授权之外的使用权限可以从 https://creativecommons.org/l… 处获得。

正文完
 0

数据结构数组

8次阅读

共计 11357 个字符,预计需要花费 29 分钟才能阅读完成。

数据结构 - 数组

数组

  • 数据结构中最基本的一个结构就是 线性结构 ,而线性结构又分为连续存储结构和离散存储结构。所谓的 连续存储结构 其实就是数组。
  • 优点:插入块如果知道坐标可以快速去地存取
  • 缺点:查找慢, 删除慢, 大小固定

二次封装数组的增删改查

基类的定义
  • 定义一个 工具类 名称 -Array
  • 接受的参数包括 基本类型和自定义类型(用泛型来接受,基本类型用包装类)
  • 自定义属性两个:size 用来表示数组的大小,data 用来表示一个准确的集合
  • 概念区分:size 表示数组的大小,capacity 表示数组容量的大小
  • 构造函数:有参构造,接受一个 int 值,用来初始化数组容量;无参构造:给容量一个默认值
  • toString()方法,输出数组的大小和数组容量的大小,以及数组中的值
  • getSize()方法,调用方通过方法来获取数组的大小
  • getCapacity()方法,调用方通过方法来获取数组容量的大小
  • isEmpty()方法,调用方通过方法来判断数组是否为空(指的是数组中是否有值,没值就为空)
基类的代码
package com.datastructure.array;

/**
 * @program: test
 * @description: 自定义数组封装工具类
 * @author: Mr.Yang
 * @create: 2019-05-01 15:36
 **/
public class Array<E> {

    private Integer size;

    private E[] data;




    /**
     * 有参构造函数
     * @param capacity  封装 data 的容量值
     */
    public Array(Integer capacity){data= (E[]) new Object[capacity];
        size=0;
    }

    /**
     * 无参构造函数,设置默认容量为 10
     */
    public Array(){this(10);
    }

    /**
     * 获取数组中的元素个数
     * @return
     */
    public Integer getSize(){return size;}

    /**
     * 获取数组的容量
     * @return
     */
    public Integer getCapacity(){return data.length;}

    /**
     * 判断数组是否为空
     * @return
     */
    public boolean isEmpty(){return size==0;}

    @Override
    public String toString(){StringBuffer sb = new StringBuffer();
        sb.append(String.format("Array: size = %d , capacity = %d\n",size,data.length));
        sb.append("[");
        for(int i =0;i<size;i++){sb.append(data[i]);
            if(i !=size-1){sb.append(",");
            }
        }
        sb.append("]");
        return sb.toString();}
}
添加的方法
  • add()方法,两个参数,添加元素的索引位置,和元素的值
  • addFirst()方法,在所有元素的最前面添加
  • addLast()方法,在所有元素的最后面添加
添加的代码(增)
/**
     * 在索引为 index 的位置,插入 param
     * 1. 假如在索引为 2 的位置插入元素
     * 2. 需要将原来索引为 2 及其以后的位置向后移动一整位
     * 3. 移动完成之后,在索引为 2 的位置插入指定的值
     * 4. 因为数组中多了一个值,所以 size 需要 +1
     *
     * @param index 元素的索引
     * @param param 值
     */
    public void add(int index, E param) {if (index < 0 || index > size) {throw new IllegalArgumentException("添加失败,索引的值不能小于 0,并且索引的值不能大于数组的大小");
        }
        if (size == data.length) {throw new IllegalArgumentException("添加失败,数组的大小已经等于了数组容量的大小");
        }
        for (int i = size - 1; i >= index; i--) {data[i + 1] = data[i];
        }
        data[index] = param;
        size++;
    }

    /**
     * 在所有元素之前添加值
     *
     * @param param
     */
    public void addFirst(E param) {add(0, param);
    }

    /**
     * 在所有元素之后添加值
     *
     * @param param
     */
    public void addLast(E param) {add(size, param);
    }
测试代码
package com.datastructure.array;

/**
 * @program: test
 * @description:
 * @author: Mr.Yang
 * @create: 2019-05-01 16:46
 **/
public class ArrayTest {public static void main(String[] args) {Array<Integer> integerArray = new Array<Integer>(20);
        for(int i = 0; i < 10 ; i ++){integerArray.addLast(i);
        }
        System.out.println(integerArray);

        System.out.println("-------------------- 索引为 3 的地方添加元素 -----------------------");
        integerArray.add(3,666);
        System.out.println(integerArray);

        System.out.println("-------------------- 所有元素的最后面添加值 -----------------------");
        integerArray.addLast(10000);
        System.out.println(integerArray);

        System.out.println("-------------------- 所有元素的最前面添加值 -----------------------");
        integerArray.addFirst(-1);
        System.out.println(integerArray);
    }
}
测试结果
Array: size = 10 , capacity = 20
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
-------------------- 索引为 3 的地方添加元素 -----------------------
Array: size = 11 , capacity = 20
[0, 1, 2, 666, 3, 4, 5, 6, 7, 8, 9]
-------------------- 所有元素的最后面添加值 -----------------------
Array: size = 12 , capacity = 20
[0, 1, 2, 666, 3, 4, 5, 6, 7, 8, 9, 10000]
-------------------- 所有元素的最前面添加值 -----------------------
Array: size = 13 , capacity = 20
[-1, 0, 1, 2, 666, 3, 4, 5, 6, 7, 8, 9, 10000]
添加的方法
  • set,两个参数,修改的元素的索引位置,和将要修改的值
添加的代码(改)
/**
     * 修改数组中元素的值
     * @param index
     * @param param
     */
    public void set(int index,E param){if(index<0 || index>= size){throw new IllegalArgumentException("获取失败,索引值无效");
        }
        data[index]=param;
    }
测试代码
package com.datastructure.array;

/**
 * @program: test
 * @description:
 * @author: Mr.Yang
 * @create: 2019-05-01 16:46
 **/
public class ArrayTest {public static void main(String[] args) {Array<Integer> integerArray = new Array<Integer>(20);
        for (int i = 0; i < 10; i++) {integerArray.addLast(i);
        }
        System.out.println(integerArray);

        System.out.println("-------------------- 索引为 3 的地方修改值为 1010-----------------------");
        integerArray.set(3, 1010);
        System.out.println(integerArray);

    }
}
测试结果
Array: size = 10 , capacity = 20
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
-------------------- 索引为 3 的地方修改值为 1010-----------------------
Array: size = 10 , capacity = 20
[0, 1, 2, 1010, 4, 5, 6, 7, 8, 9]
添加的方法
  • get()方法,一个参数,索引值,根据索引返回对应的值
  • contains()方法,一个参数,判断数组中是否包含某个元素
  • find()方法,一个参数,查找数组中是否包含 param,如果包含返回索引值,不包含返回 -1
  • findAll()方法,一个参数,查找数组中是否包含 param,返回包含的索引数组
添加的代码(查)
 /**
     * 获取索引位置的元素
     * @param index
     * @return
     */
    public E get(Integer index){if(index<0 || index>=size){throw new IllegalArgumentException("获取失败,索引的值不能小于 0,并且索引的值不能大于等于数组的大小");
        }
        return data[index];
    }

    /**
     * 查看数组中是否包含某个元素
     * @param param
     * @return
     */
    public boolean contains(E param){for(int i = 0 ; i < size ; i++){if(data[i] == param){return true;}
        }
        return false;
    }


    /**
     * 查找数组中是否包含 param,如果包含返回索引值,不包含返回 -1
     * @param param
     * @return
     */
    public Integer find(E param){for(int i = 0 ; i < size ; i++){if(data[i] == param){return i;}
        }
        return -1;
    }

    /**
     * 查找数组中是否包含 param
     * 1. 创建一个 int 数组用来接收返回的索引值
     * 2. 索引容量最大为数组的大小
     * 3. 用临时变量来存储 int 数组的大小
     * 4. 如果相等,给 int 数组 为临时变量的元素赋值(相等的索引),临时变量自增
     * @param param
     * @return
     */
    public Integer[] findAll(E param){
        int intTemp=0;
        Integer[] integers = new Integer[size];
        for(int i = 0 ; i < size ; i++){if(data[i] == param){integers[intTemp]=i;
                intTemp++;
            }
        }
        return integers;
    }
测试代码
package com.datastructure.array;

import java.util.Arrays;

/**
 * @program: test
 * @description:
 * @author: Mr.Yang
 * @create: 2019-05-01 16:46
 **/
public class ArrayTest {public static void main(String[] args) {Array<Integer> integerArray = new Array<Integer>(20);
        for (int i = 0; i < 10; i++) {integerArray.addLast(i);
        }
        integerArray.addLast(3);

        System.out.println(integerArray);

        System.out.println("-------------------- 得到索引为 3 的值 -----------------------");
        System.out.println(integerArray.get(3));

        System.out.println("-------------------- 判断是否包含有包含 3 的值 -----------------------");
        System.out.println(integerArray.contains(3));

        System.out.println("-------------------- 查找是否包含参数,并返回索引 -----------------------");
        System.out.println(integerArray.find(3));

        System.out.println("-------------------- 查找是否包含参数,并返回索引数组 -----------------------");
        System.out.println(Arrays.asList(integerArray.findAll(3)));

    }
}
测试结果
Array: size = 11 , capacity = 20
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 3]
-------------------- 得到索引为 3 的值 -----------------------
3
-------------------- 判断是否包含有包含 3 的值 -----------------------
true
-------------------- 查找是否包含参数,并返回索引 -----------------------
3
-------------------- 查找是否包含参数,并返回索引数组 -----------------------
[3, 10, null, null, null, null, null, null, null, null, null]
添加的方法
  • remove()方法,数组中删除 index 位置的元素,并且返回对应的值
  • removeFirst()方法,删除第一位元素
  • removeLast()方法,删除最后一位元素
  • removeElement()方法,查看某个值是否在数组中存在,如果存在, 删除并返回 true,如果不存在 返回 false、
  • removeLast()方法,查找所有元素,获取所有相等的索引,遍历移除
添加的代码(删)
/**
     * 从数组中删除 index 位置的元素,并且返回对应的值
     * 1. 假如删除索引为 3 的元素
     * 2. 需要将索引大于 3 的元素向前移动一位
     * 3. 因为数组中少了一个值,所以元素 -1
     * 4. 用临时变量来存储删除的值,用来返回
     * @param index
     * @return
     */
    public E remove(int index){if(index<0 || index>=size){throw new IllegalArgumentException("删除失败,索引的值不能小于 0,并且索引的值不能大于等于数组的大小");
        }
        E temp=data[index];
        for(int i = index+1 ; i < size ; i++){data[i-1]=data[i];
        }
        size--;
        return temp;
    }

    /**
     * 删除第一位元素
     * @return
     */
    public E removeFirst(){return remove(0);
    }

    /**
     * 删除最后一位元素
     */
    public E removeLast(){return remove(size-1);
    }

    /**
     * 查看某个值是否在数组中存在,如果存在, 删除并返回 true,如果不存在 返回 false
     * @param param
     */
    public boolean removeElement(E param){Integer index = find(param);
        if(index != -1){remove(index);
            return true;
        }
        return false;
    }

   /**
     * 遍历数组,移除元素
     * @param param
     */
    public void removeAllElement(E param){for(E d:data){removeElement(param);
        }
    }
测试代码
package com.datastructure.array;

import java.util.Arrays;

/**
 * @program: test
 * @description:
 * @author: Mr.Yang
 * @create: 2019-05-01 16:46
 **/
public class ArrayTest {public static void main(String[] args) {Array<Integer> integerArray = new Array<Integer>(20);
        for (int i = 0; i < 10; i++) {integerArray.addLast(i);
        }
        integerArray.addLast(3);
        integerArray.addLast(4);

        System.out.println(integerArray);

        System.out.println("-------------------- 数组中删除 6 位置的元素,并且返回对应的值 -----------------------");
        System.out.println(integerArray.remove(6));
        System.out.println(integerArray);

        System.out.println("-------------------- 删除第一位元素 -----------------------");
        System.out.println(integerArray.removeFirst());
        System.out.println(integerArray);

        System.out.println("-------------------- 删除最后一位元素 -----------------------");
        System.out.println(integerArray.removeLast());
        System.out.println(integerArray);

        System.out.println("-------------------- 查看 8 是否在数组中存在,返回 true 和 fals-----------------------");
        System.out.println(integerArray.removeElement(8));
        System.out.println(integerArray);

        System.out.println("-------------------- 查找所有元素,获取所有相等的索引,遍历移除 -----------------------");
        integerArray.removeAllElement(3);
        System.out.println(integerArray);

    }
}
测试结果
Array: size = 12 , capacity = 20
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 3, 4]
-------------------- 数组中删除 6 位置的元素,并且返回对应的值 -----------------------
6
Array: size = 11 , capacity = 20
[0, 1, 2, 3, 4, 5, 7, 8, 9, 3, 4]
-------------------- 删除第一位元素 -----------------------
0
Array: size = 10 , capacity = 20
[1, 2, 3, 4, 5, 7, 8, 9, 3, 4]
-------------------- 删除最后一位元素 -----------------------
4
Array: size = 9 , capacity = 20
[1, 2, 3, 4, 5, 7, 8, 9, 3]
-------------------- 查看 8 是否在数组中存在,如果存在, 删除并返回 true,如果不存在 返回 false、-----------------------
true
Array: size = 8 , capacity = 20
[1, 2, 3, 4, 5, 7, 9, 3]
-------------------- 查找所有元素,获取所有相等的索引,遍历移除 -----------------------
Array: size = 6 , capacity = 20
[1, 2, 4, 5, 7, 9]
数组动态扩容
添加的方法
  • resize()方法,定义为私有,调用方不能通过方法来调用,去修改,否则容易造成 BUG
  • 扩容倍数,如果用固定值,不好抉择。比如:100 容量,扩容 10 个,没有意义,很快就满了;100 容量,扩充 1000 个,太多了,容易早证浪费。最好选择倍数,都在同一个单位级别,这里代码选择的是 2 倍
  • 添加的时候需要判断扩容,删除的时候需要删除容量,减少资源浪费
  • 删除的时候,当元素减少到容量的 1 / 4 的时候开始缩,缩减到容量的 1 /2
  • 如果选择 1 / 2 的时候开始缩减,然后缩减到 1 / 2 会有一定的问题,例如:容量 10,现在容量满了,来了一个元素,需要扩容,按照设置的扩容机制,会扩容 2 倍,也就是 20 容量,如果删除了一个元素,元素达到了容量的 1 /2,我们开始进行缩减,缩减 1 /2,容量又变为 10。如果一直在这个临界值,那么元素会一直进行扩容缩减扩容缩减,性能影响太大。
  • 如果选择 1 / 4 的时候开始缩减,然后缩减到 1 /2,这样能够较好的避开以上问题,例如:容量 10,容量满了,来了一个元素,扩容容量到了 20,如果删除一个元素,还不到容量的 1 /4,所以还不会进行缩减,如果真的到了容量的 1 / 4 的时候,我们选择缩减 1 /2,容量也需要一定的元素,才会进行扩容,防止了容量一直扩容或者缩减
添加的代码
    /**
     * 扩容方法
     * 1. 需要 new 一个 object,new E[i]  java 不支持这样写
     * 2.object 是所有类的基类,用 object 然后强转一下就可以
     * 3. 扩展之后,需要将原数组中的值,放入扩展之后的数组中
     * @param newCapacity
     */
    private void resize(int newCapacity) {E[] newData = (E[]) new Object[newCapacity];
        for(int i=0;i<size;i++){newData[i]=data[i];
        }
        data=newData;
    }
修改的代码
  • add() 和 remove()
/**
     * 在索引为 index 的位置,插入 param
     * 1. 假如在索引为 2 的位置插入元素
     * 2. 需要将原来索引为 2 及其以后的位置向后移动一整位
     * 3. 移动完成之后,在索引为 2 的位置插入指定的值
     * 4. 因为数组中多了一个值,所以 size 需要 +1
     *
     * @param index 元素的索引
     * @param param 值
     */
    public void add(int index, E param) {if (index < 0 || index > size) {throw new IllegalArgumentException("添加失败,索引的值不能小于 0,并且索引的值不能大于数组的大小");
        }
        if (size == data.length) {resize(2 * data.length);
        }
        for (int i = size - 1; i >= index; i--) {data[i + 1] = data[i];
        }
        data[index] = param;
        size++;
    }


/**
     * 从数组中删除 index 位置的元素,并且返回对应的值
     * 1. 假如删除索引为 3 的元素
     * 2. 需要将索引大于 3 的元素向前移动一位
     * 3. 因为数组中少了一个值,所以元素 -1
     * 4. 用临时变量来存储删除的值,用来返回
     * @param index
     * @return
     */
    public E remove(int index){if(index<0 || index>=size){throw new IllegalArgumentException("删除失败,索引的值不能小于 0,并且索引的值不能大于等于数组的大小");
        }
        E temp=data[index];
        for(int i = index+1 ; i < size ; i++){data[i-1]=data[i];
        }
        size--;
        if(size == data.length / 4){resize(data.length / 2);
        }
        return temp;
    }
测试代码
package com.datastructure.array;

import java.util.Arrays;

/**
 * @program: test
 * @description:
 * @author: Mr.Yang
 * @create: 2019-05-01 16:46
 **/
public class ArrayTest {public static void main(String[] args) {Array<Integer> integerArray = new Array<Integer>(10);
        for (int i = 0; i < 10; i++) {integerArray.addLast(i);
        }
        System.out.println(integerArray);

        System.out.printf("-------------------- 将容量设置为 10,添加 10 个元素,元素的容量 : %d -------------------\r\n",integerArray.getCapacity());

        integerArray.addLast(21);
        System.out.printf("-------------------- 元素 +1,元素的容量 : %d --------------------\r\n",integerArray.getCapacity());


        integerArray.removeLast();
        System.out.printf("-------------------- 元素 -1,元素的容量 : %d --------------------\r\n",integerArray.getCapacity());

        integerArray.removeLast();
        System.out.printf("-------------------- 元素 -1,元素的容量 : %d --------------------\r\n",integerArray.getCapacity());

        for(int x=0;x<=5;x++){integerArray.removeLast();
        }
        System.out.printf("-------------------- 元素 -1/4,元素的容量 : %d --------------------\r\n",integerArray.getCapacity());


    }
}
测试结果
Array: size = 10 , capacity = 10
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
-------------------- 将容量设置为 10,添加 10 个元素,元素的容量 : 10 -------------------
-------------------- 元素 +1,元素的容量 : 20 --------------------
-------------------- 元素 -1,元素的容量 : 20 --------------------
-------------------- 元素 -1,元素的容量 : 20 --------------------
-------------------- 元素 -1/4,元素的容量 : 10 --------------------

正文完
 0