数据结构01-自定义ArrayList

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
package A01.LSQ;
public interface MyList<E>
{
// 新增数据
E add(E data);
// 插入数据
E add(int index, E data);
// 容器大小
int size();
// 根据下标取出数据
E get(int index);
// 根据下标删除数据
boolean remove(int index);
// 删除指定数据，如果有多个则删除下标最小的
boolean remove(E data);
// 修改数据
E set(int index, E data);
}

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
package A01.LSQ;
import java.util.Iterator;
import java.util.NoSuchElementException;
public class MyArrayList<E> implements MyList<E>, Iterable<E>
{
// 保存数据的数组
private E[] arr;
// 数组长度
private int len;
// 线性表大小
private int size;
// 数组每次的增量
private final int addSize;
public MyArrayList()
{
this(10);
}
public MyArrayList(int len)
{
this(10, 10);
}
public MyArrayList(int len, int addSize)
{
this.len = len;
this.addSize = addSize;
arr = (E[]) new Object[len];
size = 0;
}
@Override
public E add(E data)
{
return add(size, data);
}
@Override
public E add(int index, E data)
{
if (index < 0 || index > size)
throw new IndexOutOfBoundsException("数组越界");
if (size == len)
{
addArrSize(len + addSize);
}
for (int i = size; i > index; i--)
{
arr[i] = arr[i - 1];
}
arr[index] = data;
size++;
return data;
}
@Override
public int size()
{
return size;
}
@Override
public E get(int index)
{
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException("数组越界");
return arr[index];
}
@Override
public boolean remove(int index)
{
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException("数组越界");
for (int i = index; i < size; i++)
{
arr[i] = arr[i + 1];
}
size--;
return true;
}
@Override
public boolean remove(E data)
{
for (int i = 0; i < size; i++)
{
if (data.equals(arr[i]))
{
return remove(i);
}
}
return false;
}
@Override
public E set(int index, E data)
{
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException("数组越界");
arr[index] = data;
return data;
}
public void addArrSize(int len)
{
E[] temp = (E[]) new Object[len];
for (int i = 0; i < size; i++)
{
temp[i] = arr[i];
}
arr = temp;
this.len = len;
}
// 实现增强for循环的内部类
@Override
public Iterator<E> iterator()
{
return new MyArrayListIterator();
}
private class MyArrayListIterator implements Iterator<E>
{
private int current = 0;
@Override
public void remove()
{
MyArrayList.this.remove(--current);
}
@Override
public boolean hasNext()
{
return current < size;
}
@Override
public E next()
{
if(!hasNext())
throw new NoSuchElementException();
return arr[current++];
}
}
}