数据结构与算法 | 线性表 —— 顺序表

线性表

定义

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

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

分类

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

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

顺序表

定义

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

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

实现

顺序表的存放数据的特点和数组一样,所以我们这里采用数组来实现,这里我们来用数组来简单实现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
package one.wangwei.algorithms.datastructures.list.interfaces;

/**
* 线性表接口
*
* @param <T>
* @author wangwei
* @date 2018/04/27
*/
public interface IList<T> {

/**
* 添加元素
*
* @param element
* @return
*/
public boolean add(T element);

/**
* 移除元素
*
* @param element
* @return
*/
public boolean remove(T element);

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

/**
* 设置index上的元素
*
* @param index
* @param element
* @return
*/
public T set(int index, T element);

/**
* 清空list集合
*/
public void clear();

/**
* 判断是否包含某个元素
*
* @param element
*/
public boolean contains(T element);

/**
* 集合大小
*
* @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
package one.wangwei.algorithms.datastructures.list.impl;

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

import java.util.Arrays;

/**
* list集合
*
* @param <T>
* @author wangwei
* @date 2018/04/27
*/
public class MyArrayList<T> implements IList<T> {

/**
* 默认大小
*/
private static final int DEFAULT_SIZE = 10;

private int size = 0;
/**
* 初始化一个默认数组
*/
private transient T[] array = (T[]) new Object[DEFAULT_SIZE];

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

/**
* 添加元素
*
* @param index
* @param element
* @return
*/
private boolean add(int index, T element) {
// 扩容
if (size >= array.length) {
grow();
}
if (index == size) {
array[size] = element;
} else {
System.arraycopy(array, index, array, index + 1, size - index);
array[index] = element;
}
size++;
return true;
}

/**
* 扩容
*/
private void grow() {
int growSize = size + (size << 1);
array = Arrays.copyOf(array, growSize);
}

/**
* 缩减
*/
private void shrink() {
int shrinkSize = array.length >> 1;
array = Arrays.copyOf(array, shrinkSize);
}

/**
* 移除第一个匹配的元素
*
* @param element
* @return
*/
@Override
public boolean remove(T element) {
if (element == null) {
for (int i = 0; i < size; i++) {
if (array[i] == null) {
remove(i);
return true;
}
}
} else {
for (int i = 0; i < size; i++) {
if (array[i].equals(element)) {
remove(i);
return true;
}
}
}
return false;
}

/**
* 删除 index 位置上元素
*
* @param index
* @return
*/
@Override
public T remove(int index) {
if (index < 0 || index >= size) {
throw new ArrayIndexOutOfBoundsException("Index: " + index + ", Size: " + size);
}
T element = array[index];
if (index != --size) {
System.arraycopy(array, index + 1, array, index, size - index);
}
array[size] = null;
int shrinkSize = array.length >> 1;
if (shrinkSize >= DEFAULT_SIZE && shrinkSize > size) {
shrink();
}
return element;
}

/**
* 设置索引值
*
* @param index
* @param element
* @return
*/
@Override
public T set(int index, T element) {
if (index < 0 || index >= size) {
throw new ArrayIndexOutOfBoundsException("Index: " + index + ", Size: " + size);
}
T oldElement = array[index];
array[index] = element;
return oldElement;
}

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

/**
* 检查是否包含某个元素
*
* @param element
*/
@Override
public boolean contains(T element) {
if (element == null) {
for (int i = 0; i < size; i++) {
if (array[i] == null) {
return true;
}
}
} else {
for (int i = 0; i < size; i++) {
if (element.equals(array[i])) {
return true;
}
}
}
return false;
}

/**
* 集合大小
*
* @return
*/
@Override
public int size() {
return size;
}
}

查看源代码

特点

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

参考资料

请我喝杯咖啡吧~