Fork me on GitHub

数据结构-数组

通过二次封装创建属于自己的数组

创建一个Array类,实现一些简单的方法

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
public class Array {

private int[] data;
private int size;

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

// 无参数的构造函数,默认数组的容量capacity=10
public Array(){
this(10);
}

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

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

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

这样就实现了一个数组的简单封装,接下来就要对数组中的元素进行增删改查操作了

添加元素

添加元素时,需要将传入的下标后面的元素都向后挪一位,再将传入的元素插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 在index索引的位置插入一个新元素e
public void add(int index, int e){

if(size == data.length)
throw new IllegalArgumentException("Add failed. Array is full.");

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

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

data[index] = e;

size ++;
}

在方法的内部对下标进行判断,防止用户跨空间操作
这样还可以实现两个插入操作

1
2
3
4
5
6
7
8
9
// 向所有元素后添加一个新元素
public void addLast(int e) {
add(size, e);
}

// 在所有元素前添加一个新元素
public void addFirst(int e) {
add(0, e);
}

重写父类的toString方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
@Override
public String toString(){

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

编写一个main函数进行测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Main {

public static void main(String[] args) {

Array arr = new Array(20);
for(int i = 0 ; i < 10 ; i ++)
arr.addLast(i);

System.out.println(arr);

arr.add(1, 100);
System.out.println(arr);

arr.addFirst(-1);
System.out.println(arr);
}
}

结果

1
2
3
4
5
6
Array: size = 10 , capacity = 20
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Array: size = 11 , capacity = 20
[0, 100, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Array: size = 12 , capacity = 20
[-1, 0, 100, 1, 2, 3, 4, 5, 6, 7, 8, 9]

修改元素

1
2
3
4
5
6
7
8
9
10
11
12
13
// 获取index索引位置的元素
public int 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, int e) {
if (index < 0 || index >= size)
throw new IllegalArgumentException("Set failed. Index is illegal.");
data[index] = e;
}

在方法的内部对下标进行判断,防止用户查询数组中未使用的空间

查找元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 查找数组中是否有元素e
public boolean contains(int e) {
for (int i = 0; i < size; i++) {
if (data[i] == e)
return true;
}
return false;
}

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

删除元素

删除元素和添加元素类似

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 从数组中删除index位置的元素, 返回删除的元素
public int remove(int index) {
if (index < 0 || index >= size)
throw new IllegalArgumentException("Remove failed. Index is illegal.");

int ret = data[index];
for (int i = index + 1; i < size; i++)
data[i - 1] = data[i];
size--;
return ret;
}

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

将元素删除后,原来最后一位的元素并没有被删除,因为用户根本访问不到那个元素,所以也没有必要进行删除

编写main函数进行测试

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
public class Main {

public static void main(String[] args) {

Array arr = new Array(20);
for (int i = 0; i < 10; i++)
arr.addLast(i);
System.out.println(arr);

arr.add(1, 100);
System.out.println(arr);

arr.addFirst(-1);
System.out.println(arr);
// [-1, 0, 100, 1, 2, 3, 4, 5, 6, 7, 8, 9]

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

arr.removeElement(4);
System.out.println(arr);

arr.removeFirst();
System.out.println(arr);
}
}

结果

1
2
3
4
5
6
7
8
9
10
11
12
Array: size = 10 , capacity = 20
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Array: size = 11 , capacity = 20
[0, 100, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Array: size = 12 , capacity = 20
[-1, 0, 100, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Array: size = 11 , capacity = 20
[-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Array: size = 10 , capacity = 20
[-1, 0, 1, 2, 3, 5, 6, 7, 8, 9]
Array: size = 9 , capacity = 20
[0, 1, 2, 3, 5, 6, 7, 8, 9]

使用泛型

上面封装的数组类只支持整形对象,如果想要让其支持更多的类型,就要使用泛型了
Array更改为支持泛型的类

1
2
3
4
5
6
7
8
9
10
11
public class Array<E> {

private E[] data;
private int size;

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

新建一个Student类进行测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Student {

private String name;
private int score;

public Student(String studentName, int studentScore){
name = studentName;
score = studentScore;
}

@Override
public String toString(){
return String.format("Student(name: %s, score: %d)", name, score);
}

public static void main(String[] args) {

Array<Student> arr = new Array<>();
arr.addLast(new Student("Alice", 100));
arr.addLast(new Student("Bob", 66));
arr.addLast(new Student("Charlie", 88));
System.out.println(arr);
}
}

结果

1
2
Array: size = 3 , capacity = 10
[Student(name: Alice, score: 100), Student(name: Bob, score: 66), Student(name: Charlie, score: 88)]

动态数组

上面的数组中使用的都是静态数组,创建时容量有多大,就一直是这么大了;但是大部分情况是不知道容量的大小,如果开辟空间大了,就会造成浪费;如果小了,就没法存储下数据.这时动态数组的优势就体现出来了.

这里先写一个动态扩容(缩容)的方法

1
2
3
4
5
6
7
8
// 将数组空间的容量变成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;
}

这个方法应该在添加元素,删除元素时调用,当数组的容量到达一定量的时候,就需要调用这个resize方法了

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
// 在index索引的位置插入一个新元素e
public void add(int index, E e){

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

if(size == data.length)
resize(2 * data.length);

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

data[index] = e;

size ++;
}


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

E ret = data[index];
for(int i = index + 1 ; i < size ; i ++)
data[i - 1] = data[i];
size --;
data[size] = null; // loitering objects != memory leak

if(size == data.length / 2)
resize(data.length / 2);
return ret;
}

简单测试一下

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
public class Main {

public static void main(String[] args) {

Array<Integer> arr = new Array<>();
for(int i = 0 ; i < 10 ; i ++)
arr.addLast(i);
System.out.println(arr);

arr.add(1, 100);
System.out.println(arr);

arr.addFirst(-1);
System.out.println(arr);

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

arr.removeElement(4);
System.out.println(arr);

arr.removeFirst();
System.out.println(arr);
}
}

结果

1
2
3
4
5
6
7
8
9
10
11
12
Array: size = 10 , capacity = 10
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Array: size = 11 , capacity = 20
[0, 100, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Array: size = 12 , capacity = 20
[-1, 0, 100, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Array: size = 11 , capacity = 20
[-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Array: size = 10 , capacity = 10
[-1, 0, 1, 2, 3, 5, 6, 7, 8, 9]
Array: size = 9 , capacity = 10
[0, 1, 2, 3, 5, 6, 7, 8, 9]

时间复杂度分析

添加操作 O(n)

  • addLast(e) O(1)(O(n))
    在所有元素后添加元素,可以根据索引直接赋值,时间复杂度是O(1)
    最坏的情况,需要对数组进行扩容,需要进行resize操作,此时的复杂度是O(n)

  • addFirst(e) O(n)
    在所有元素前添加元素,后面的所有元素都需要向后移一位,时间复杂度是O(n)

  • add(index, e) O(n/2) = O(n)
    添加元素时,由于不确定元素将被插在那里,近似取n/2,当n无限大时,近似O(n)

删除操作 O(n)

  • removeFirst(e) O(n)
    从数组中删除第一个元素,后面的所有元素都需要向前移一位,时间复杂度是O(n)

  • removeLast(e) O(1) (O(n))
    从数组中删除最后一个元素,根据索引可以直接删除,时间复杂度是O(1)
    最坏的情况,需要对数组进行缩容,需要进行resize操作,此时的复杂度是O(n)

  • remove(index, e) O(n/2) = O(n)
    和添加元素类似

修改操作 O(1)

  • set(index, e) O(1)
    根据下标直接进行赋值即可

查找操作

  • get(index) O(1)

  • contains(e) O(n)

  • find(e) O(n)
    contains(e)find(e)需要对数组进行遍历

resize复杂度分析

假设当前capacity=8,并且每一次添加操作都使用的是addLast,这样在进行第9次添加操作时,就会触发resize,这个过程一共进行了17次基本操作(赋值)

8次正常赋值, 扩容时又进行了8次赋值, 最后将第9个元素赋值,共8+8+1, 平均每次addLast进行了2次基本操作

假设当前capacity=n,进行n+1addLast操作,触发resize,总共进行2n+1次基本操作,平均每次addLast操作,进行2次基本操作,这样均摊计算的话,均摊复杂度是O(1)级别的!
同理, removeLast是一样的,也是O(1)级别的

但是, 当我们同时关注addLastremoveLast,当容量刚好装满时,
此时调用addLast, 需要进行resize操作, 此时时间复杂度是O(n)级别的;
再进行removeLast操作, 此时元素个数刚好是容量的一半, 又需要进行resize操作,此时时间复杂度也是O(n)级别的.
出现问题的原因是在进行removeLast操作时,resize过于着急了,解决方案是使用更懒惰的
策略,当size = capacity/4时,再进行resize容量减半操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 从数组中删除index位置的元素, 返回删除的元素
public E remove(int index){
if(index < 0 || index >= size)
throw new IllegalArgumentException("Remove failed. Index is illegal.");

E ret = data[index];
for(int i = index + 1 ; i < size ; i ++)
data[i - 1] = data[i];
size --;
data[size] = null; // loitering objects != memory leak

if(size == data.length / 4 && data.length / 2 != 0)
resize(data.length / 2);
return ret;
}

Array源码

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
public class Array<E> {

private E[] data;
private int size;

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

// 无参数的构造函数,默认数组的容量capacity=10
public Array() {
this(10);
}

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

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

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

// 在index索引的位置插入一个新元素e
public void add(int index, E e) {

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

if (size == data.length)
resize(2 * data.length);

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

data[index] = e;

size++;
}

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

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

// 获取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] == e)
return true;
}
return false;
}

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

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

E ret = data[index];
for (int i = index + 1; i < size; i++)
data[i - 1] = data[i];
size--;
data[size] = null; // loitering objects != memory leak

if (size == data.length / 4 && data.length / 2 != 0)
resize(data.length / 2);
return ret;
}

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


// 从数组中删除第一个元素, 返回删除的元素
public E removeFirst() {
return remove(0);
}

// 从数组中删除最后一个元素, 返回删除的元素
public E removeLast() {
return remove(size - 1);
}


// 将数组空间的容量变成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;
}

@Override
public String toString() {

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


}

完整代码

-------------本文结束感谢您的阅读-------------
坚持原创技术分享,您的支持将鼓励我继续创作!
0%