数据结构数组的的学习笔记。

数据结构-数组

1. 数组概述

  1. 特点

    顺序存放、可以随机访问。

  2. 缺点

    数组功能比较弱,考虑封装。

2. 封装自己的数组

  1. 引入

    为了增强数组的功能,我们对数组进行二次封装,虽然Java已经有ArrayList对数组进行了封装,但为了学习,我们对数组进行封装。

  2. 代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    package top.tobing.ds.array;

    public class Array<E> {

    private E[] data;
    private int size;

    // 构造函数,传入数组的容量capacity构造Array
    public Array(int capacity) {
    data = (E[]) new Object[capacity];
    size = 0;
    }

    // 默认构造
    public Array() {
    this(10);
    }

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

    // 获取数组的元素个数
    public int getSize() {
    return size;
    }

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

    // 在所有元素后添加一个元素
    public void addLast(E e) {
    add(size, e);
    }

    // 在使用元素前添加一个元素
    public void addFirst(E e) {
    add(0, e);
    }

    // 在索引index处添加一个元素
    public void add(int index, E e) {

    if (index < 0 || index > data.length) {
    throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= size");
    }

    if (index == data.length) {
    resize(2 * data.length);
    }

    for (int i = size; i > index; i--) {
    data[i] = data[i - 1];
    }

    data[index] = e;

    size++;
    }


    // 获取index索引位置的值
    public E get(int index) {
    if (index < 0 || index >= size) {
    throw new IllegalArgumentException("Get failed. Index is illegal.");
    }
    return data[index];
    }

    // 修改index索引出的值为e
    public void set(int index, E e) {
    if (index < 0 || index >= size) {
    throw new IllegalArgumentException("Set failed, Index is illegal.");
    }
    data[index] = e;
    }

    // 查找数组中是否包含元素e
    public boolean contains(E e) {
    for (int i = 0; i < size; i++) {
    if (data[i].equals(e)) {
    return true;
    }
    }
    return false;
    }

    // 查找数组中元素e所在的索引,如果不存在元素e,返回-1
    public int find(E e) {
    for (int i = 0; i < size; i++) {
    if (data[i].equals(e)) {
    return i;
    }
    }
    return -1;
    }

    // 删除数组中索引为index位置的元素,返回被删除的元素
    public E remove(int index) {
    if (index < 0 || index >= size) {
    throw new IllegalArgumentException("Rmove failed. Index is illegal.");
    }

    E temp = data[index];
    for (int i = index; i < size - 1; i++) {
    data[i] = data[i + 1];
    }
    size--;
    data[size] = null;

    // 懒汉式:避免复杂度震荡
    if (size == data.length / 4 && data.length / 2 != 0) {
    resize(data.length / 2);
    }
    return temp;
    }

    // 删除元素第一个元素
    public E removeFirst() {
    E temp = remove(0);
    return temp;
    }

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

    // 删除数组中元素e
    public void removeElement(E e) {
    int index = find(e);
    if (index != -1) {
    remove(index);
    }
    }

    @Override
    public String toString() {
    StringBuilder builder = new StringBuilder();
    builder.append(String.format("Array: size = %d, capacity = %d\n", size, data.length));
    builder.append('[');
    for (int i = 0; i < data.length; i++) {
    builder.append(data[i]);
    if (i != data.length - 1) {
    builder.append(", ");
    }
    }
    builder.append("]");
    return builder.toString();
    }

    // 将数组的容量变成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;
    }
    }
  3. 代码中的注意点

    泛型数组在通过指定大小创建时要以(E[])Objec[capacity]方式。

    添加add或者删除remove元素的时候要对传入的index进行合法性校验。

    add和remove都是采用覆盖的方式,区别两种的实现:一个是从后往前移,另一个则相反。

    add和remove的同时要维护size,即更新size。

    remove操作时要对size所在的位置置为null,以至于gc回收。

    find操作判断元素是否相等时要使用equals。

    动态数组时,要注意remove的容量调整时机,使用懒汉式可以避免复杂度震荡。

  4. 复杂度分析

    函数名 复杂度 其他
    add(int,E) O(n) 移动挪位
    addFirst O(n)
    addLast O(1)、O(n) 不用挪位、容量变化
    remove(int,E) O(n) 移动覆盖
    removeFirst O(n)
    removeLast O(1)、O(n) 不用覆盖、容量变化
    removeElement(E) O(n) 遍历查找
    contains O(n)
    find O(n)
    get O(1)

    resize复杂度分析:加上容量为n、n+1次addLast,触发resize,纵观2n+1基本操作平均,每次addLast,进行2次基本操作,O(1)。 这次叫做均摊复杂度分析。

    addLast和removeLast同时存在是,如果采用饿汉式,即size=capacity/2立马缩减容量,容易引发复杂度震荡。因此考虑使用懒汉式。即推迟到size=capacity/4,才将capacity置为原理一半。

3. 拓展

查看Java对ArrayList的实现,对比我们的实现。

评论