algo/java/05_array/GenericArray.java at master · open-source-backup/algo · GitHub

History

163 lines (136 loc) · 3.81 KB

Raw

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

public class GenericArray<T> {

private T[] data;

private int size;

// 根据传入容量，构造Array

public GenericArray(int capacity) {

data = (T[]) new Object[capacity];

size = 0;

}

// 无参构造方法，默认数组容量为10

public GenericArray() {

this(10);

}

// 获取数组容量

public int getCapacity() {

return data.length;

}

// 获取当前元素个数

public int count() {

return size;

}

// 判断数组是否为空

public boolean isEmpty() {

return size == 0;

}

// 修改 index 位置的元素

public void set(int index, T e) {

checkIndex(index);

data[index] = e;

}

// 获取对应 index 位置的元素

public T get(int index) {

checkIndex(index);

return data[index];

}

// 查看数组是否包含元素e

public boolean contains(T e) {

for (int i = 0; i < size; i++) {

if (data[i].equals(e)) {

return true;

}

return false;

}

// 获取对应元素的下标, 未找到，返回 -1

public int find(T e) {

for ( int i = 0; i < size; i++) {

if (data[i].equals(e)) {

return i;

}

return -1;

}

// 在 index 位置，插入元素e, 时间复杂度 O(m+n)

public void add(int index, T e) {

checkIndex(index);

// 如果当前元素个数等于数组容量，则将数组扩容为原来的2倍

if (size == data.length) {

resize(2 * data.length);

}

for (int i = size - 1; i >= index; i--) {

data[i + 1] = data[i];

}

data[index] = e;

size++;

}

// 向数组头插入元素

public void addFirst(T e) {

add(0, e);

}

// 向数组尾插入元素

public void addLast(T e) {

add(size, e);

}

// 删除 index 位置的元素，并返回

public T remove(int index) {

checkIndexForRemove(index);

T ret = data[index];

for (int i = index + 1; i < size; i++) {

data[i - 1] = data[i];

}

size --;

data[size] = null;

// 缩容

if (size == data.length / 4 && data.length / 2 != 0) {

resize(data.length / 2);

}

return ret;

}

// 删除第一个元素

public T removeFirst() {

return remove(0);

}

// 删除末尾元素

public T removeLast() {

return remove(size - 1);

}

// 从数组中删除指定元素

public void removeElement(T e) {

int index = find(e);

if (index != -1) {

remove(index);

}

@Override

public String toString() {

StringBuilder builder = new StringBuilder();

builder.append(String.format("Array size = %d, capacity = %d \n", size, data.length));

builder.append('[');

for (int i = 0; i < size; i++) {

builder.append(data[i]);

if (i != size - 1) {

builder.append(", ");

}

builder.append(']');

return builder.toString();

}

// 扩容方法，时间复杂度 O(n)

private void resize(int capacity) {

T[] newData = (T[]) new Object[capacity];

for (int i = 0; i < size; i++) {

newData[i] = data[i];

}

data = newData;

}

private void checkIndex(int index) {

if (index < 0 || index > size) {

throw new IllegalArgumentException("Add failed! Require index >=0 and index <= size.");

}

private void checkIndexForRemove(int index) {

if(index < 0 || index >= size) {

throw new IllegalArgumentException("remove failed! Require index >=0 and index < size.");

}

algo/java/05_array/GenericArray.java at master · open-source-backup/algo · GitHub

Expand file tree

Breadcrumbs

GenericArray.java

Latest commit

History

Breadcrumbs

GenericArray.java

File metadata and controls