java数据结构-顺序表

顺序表?

引用维基百科对顺序表的定义:

顺序表是计算机内存中以数组的形式保存的线性表,是指用一组地址连续的存储单元依次存储元素的线形结构。

采用顺序存储结构的线性表简称为顺序表。顺序表的存储特点是:只要确定了起始位置,表中的任意位置都可以通过此公式得到:Loc(ai)=Loc(a0) + (i - 1) * L 其中L是元素数据类型的存储空间大小,同时1 <= i <= n。计算一个元素的内存地址,即用下标减1乘其数据类型存储空间大小加上基地址!

存储


顺序表实现

顺序表接口

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
/**
* 顺序表接口
* @author weishilei
*
* @param <T>
*/
public interface ISeqList<T> {

/**
* 返回顺序表长度
* @return
*/
int length();

/**
* 新增元素
* @param data
* @return
*/
boolean add(T data);

/**
* 指定位置新增元素
* @param index
* @param data
* @return
*/
boolean add(int index, T data);

/**
* 删除指定位置上的元素
* @param index
* @return
*/
T remove(int index);

/**
* 删除指定元素
* @param data
* @return
*/
boolean remove(T data);

/**
* 删除全部指定元素
* @param data
* @return
*/
int removeAll(T data);

/**
* 设置指定位置上的值
* @param index
* @param data
* @return
*/
T set(int index, T data);

/**
* 返回指定位置上的值
* @param index
* @return
*/
T get(int index);

/**
* 查询是否保护指定元素
* @param data
* @return
*/
boolean contains(T data);

/**
* 查询指定元素下标
* @param data
* @return
*/
int indexOf(T data);

/**
* 查询指定元素最后一次的下标
* @param data
* @return
*/
int lastIndexOf(T data);

/**
* 输出
* @return
*/
String toString();
}

顺序表实现类

代码逻辑简单已有注释。

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
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
/**
* 顺序表
* @author weishilei
*
* @param <T>
*/
@SuppressWarnings("unchecked")
public class SeqList<T> implements ISeqList<T> {

private int length;
private Object[] table;

public SeqList(T[] array) {
if (array != null) {
table = new Object[array.length];
this.length = array.length;
for (int i = 0; i < array.length; i++) {
table[i] = array[i];
}
}
}

public SeqList(int length) {
table = new Object[length];
this.length = 0;
}

@Override
public int length() {
return this.length;
}

@Override
public boolean add(T data) {
if (data == null) {
return false;
}

//扩容一倍
if (length == table.length) {
arrayCapacity();
}
table[length] = data;
length++;

return true;
}

@Override
public boolean add(int index, T data) {
if (data == null || index < 0 || index > length) {
return false;
}

//扩容一倍
if (length == table.length) {
arrayCapacity();
}

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

return true;
}

@Override
public T remove(int index) {
if (index < 0 || index > length) {
return null;
}

Object data = table[index];
//插入位置是最后一位
if (index == length - 1) {
table[index] = null;
length--;
return ((T)data);
}

for (int i = index; i < length; i++) {
table[i] = table[i + 1];
}
length--;

return (T)data;
}

@Override
public boolean remove(T data) {
if (data == null) {
return false;
}

boolean flag = false;
int index = 0;
for (int i = 0; i < length; i++) {
if (data.equals(table[i])) {
index = i;
flag = true;
break;
}
}

if (flag) {
this.remove(index);
}

return flag;
}

@Override
public int removeAll(T data) {
if (data == null) {
return 0;
}

int count = 0;

while (this.indexOf(data) != -1) {
this.remove(data);
count++;
}

return count;
}

@Override
public T set(int index, T data) {
if (index < 0 || index > length || data == null) {
return null;
}

Object oldData = table[index];
table[index] = data;

return (T)oldData;
}

@Override
public T get(int index) {
if (index == 0 || index > length) {
return null;
}

return (T)table[index];
}

@Override
public boolean contains(T data) {
if (data == null) {
return false;
}

boolean flag = false;
for (int i = 0; i < length; i++) {
if (data.equals(table[i])) {
flag = true;
break;
}
}

return flag;
}

@Override
public int indexOf(T data) {
if (data == null) {
return -1;
}

int index = -1;
for (int i = 0; i < length; i++) {
if (data.equals(table[i])) {
index = i;
break;
}
}

return index;
}

@Override
public int lastIndexOf(T data) {
if (data == null) {
return -1;
}

int index = -1;
for (int i = length; i < 0; i--) {
if (data.equals(table[i])) {
index = i;
break;
}
}

return index;
}

@Override
public String toString() {
StringBuilder result = new StringBuilder();
result.append("[ ");
for (int i = 0; i < length; i++) {
result.append(table[i].toString());
if (i != length - 1) {
result.append(", ");
}
}
result.append(" ]");

return result.toString();
}

/**
* 顺序表扩容
*/
private void arrayCapacity() {
int newLength = this.table.length * 2;
Object[] newData = new Object[newLength];
for (int i = 0; i < this.table.length; i++) {
newData[i] = this.table[i];
}

this.table = newData;
}

}

总结

优点

  1. 查询元素效率高。
  2. 元素与其相邻元素在物理内存上也是相邻的。

缺点

  1. 数组大小因是静态,所以在扩容时效率低。
  2. 顺序表插入和删除基于位置操作,需要移动内部元素位置故时间效率开销较大。

坚持分享,您的支持将鼓励我继续努力!