pexels-photo-577585

线性表

定义

将具有线性关系的数据存储到计算机中所使用的存储结构称为线性表。

线性,是指数据在逻辑结构上具有线性关系。

分类

逻辑结构上相邻的数据在物理结构存储分两种形式:

  • 数据在内存中集中存储,采用顺序表示结构,称为” 顺序存储”;
  • 数据在内存中分散存储,采用链式表示结构,称为” 链式存储”;

顺序表

定义

逻辑上具有线性关系的数据按照前后的次序全部存储在一整块连续的内存空间中,之间不存在空隙,这样的存储结构称为顺序存储结构。

使用线性表的顺序存储结构生成的表,称为顺序表。

实现

顺序表的存放数据的特点和数组一样,所以我们这里采用数组来实现,这里我们来用数组来简单实现 Java 中常用的 ArrayList。

接口定义:

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
package one.wangwei.algorithms.datastructures.list;

/**
* List Interface
*
* @param <T>
* @author https://wangwei.one/
* @date 2018/04/27
*/
public interface IList<T> {

/**
* add element
*
* @param element
* @return
*/
public boolean add(T element);

/**
* add element at index
*
* @param index
* @param element
* @return
*/
public boolean add(int index, T element);

/**
* remove element
*
* @param element
* @return
*/
public boolean remove(T element);

/**
* remove element by index
*
* @param index
* @return
*/
public T remove(int index);

/**
* set element by index
*
* @param index
* @param element
* @return old element
*/
public T set(int index, T element);

/**
* get element by index
*
* @param index
* @return
*/
public T get(int index);

/**
* clear list
*/
public void clear();

/**
* contain certain element
*
* @param element
* @return
*/
public boolean contains(T element);

/**
* get list size
*
* @return
*/
public int size();

}

源代码

接口实现:

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
package one.wangwei.algorithms.datastructures.list.impl;

import one.wangwei.algorithms.datastructures.list.IList;

import java.util.Arrays;

/**
* Array List
*
* @param <T>
* @author https://wangwei.one
* @date 2018/04/27
*/
public class MyArrayList<T> implements IList<T> {

/**
* default array size
*/
private final int DEFAULT_SIZE = 10;

/**
* array size
*/
private int size = 0;

/**
* array
*/
private T[] array = (T[]) new Object[DEFAULT_SIZE];

/**
* add element
*
* @param element
* @return
*/
@Override
public boolean add(T element) {
return add(size, element);
}

/**
* add element at index
*
* @param index
* @param element
* @return
*/
@Override
public boolean add(int index, T element) {
if (index < 0 || index > size) {
throw new ArrayIndexOutOfBoundsException("Index: " + index + ", Size: " + size);
}
// need grow
if (size >= array.length) {
grow();
}
// copy array element
if (index < size) {
System.arraycopy(array, index, array, index + 1, size - index);
}
array[index] = element;
size++;
return true;
}

/**
* grow 50%
*/
private void grow() {
int growSize = size + (size >> 1);
array = Arrays.copyOf(array, growSize);
}

/**
* remove element
*
* @param element
* @return
*/
@Override
public boolean remove(T element) {
for (int i = 0; i < size; i++) {
if (element == null) {
if (array[i] == null) {
remove(i);
return true;
}
} else {
if (array[i].equals(element)) {
remove(i);
return true;
}
}
}
return false;
}

/**
* remove element by index
*
* @param index
* @return
*/
@Override
public T remove(int index) {
checkPositionIndex(index);
T oldElement = array[index];
// need copy element
if (index != (size - 1)) {
System.arraycopy(array, index + 1, array, index, size - index - 1);
}
--size;
array[size] = null;
// shrink 25%
int shrinkSize = size - (size >> 2);
if (shrinkSize >= DEFAULT_SIZE && shrinkSize > size) {
shrink();
}
return oldElement;
}

/**
* shrink 25%
*/
private void shrink() {
int shrinkSize = size - (size >> 2);
array = Arrays.copyOf(array, shrinkSize);
}

/**
* set element by index
*
* @param index
* @param element
* @return
*/
@Override
public T set(int index, T element) {
checkPositionIndex(index);
T oldElement = array[index];
array[index] = element;
return oldElement;
}

/**
* get element by index
*
* @param index
* @return
*/
@Override
public T get(int index) {
checkPositionIndex(index);
return array[index];
}

/**
* check index
*
* @param index
*/
private void checkPositionIndex(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
}
}

/**
* clear list
*/
@Override
public void clear() {
for (int i = 0; i < size; i++) {
array[i] = null;
}
size = 0;
}

/**
* contain certain element
*
* @param element
*/
@Override
public boolean contains(T element) {
for (int i = 0; i < size; i++) {
if (element == null) {
if (array[i] == null) {
return true;
}
} else {
if (array[i].equals(element)) {
return true;
}
}
}
return false;
}

/**
* get list size
*
* @return
*/
@Override
public int size() {
return size;
}
}

源代码

主要注意以下几点:

  • 添加元素时 ,判断是否需要对 Array 进行扩容;
  • 删除元素时,判断是否需要对 Array 进行收缩;
  • remove 与 contains 接口,注意 element 为 null 的情况;

特点

  • 对数据进行遍历的时候,数据在连续的物理空间中进行存放,CPU 的内部缓存结构会缓存连续的内存片段,可以大幅降低读取内存的性能开销,所以查询比较快;
  • 删除线性表中的元素的时候,后面的元素会整体向前移动,所以删除的效率较低,插入类似,时间复杂度为 O (n);

参考资料