手写定长数组

有个背景场景如下:

一天划分为1440分钟,每分钟记录一个数据块,然后用一个数据结构存储着1440个数据块,随着时间的推移,每过一分钟,向这个数据结构中添加一块,并移除最前的那个;其次就是我希望根据当前的时间,可以获取往前n分钟的数据块

简单来说,上面的需求解析如下:

  • 一个数组,容量为1440
  • 频繁的新增和删除
  • 随机的访问

后面两个就限制了ArrayList和LinkedList的使用场景了,所以为了满足这个场景,然后写了一个简单的数据结构

I. 滑动定长数组

来两个偏移量,将数组看成一个循环的结构,一个Start,一个End,分别记录开始和结束,直接在End处添加数据,每次删start处的数据;定位则计算与End或者Start的偏移量来做,超简单的实现如下:

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
 @SuppressWarnings("unchecked")
public static class DArray<T> {
private Object[] arys;
private int size;
private int start;
private int end;
@Getter
private int capacity;

public DArray(int size) {
this.size = size;
this.arys = new Object[size];
start = 0;
end = start;
capacity = 0;
}

public void add(T obj) {
arys[end] = obj;
end = (++end) % size;
++capacity;
}


public T remove() {
if (capacity == 0) {
return null;
}

Object obj = arys[start];
arys[start] = null;
start = (++start) % size;
--capacity;
return (T) obj;
}

public T index(int index) {
return (T) arys[(start + index) % size];
}
}

II. 其他

一灰灰Bloghttps://liuyueyi.github.io/hexblog

一灰灰的个人博客,记录所有学习和工作中的博文,欢迎大家前去逛逛

声明

尽信书则不如,已上内容,纯属一家之言,因个人能力有限,难免有疏漏和错误之处,如发现bug或者有更好的建议,欢迎批评指正,不吝感激

扫描关注

QrCode