JAVA数据结构：自定义ArrayList通过接口List实现数组
·
首先定义接口 List<E> ，以下是对每个方法的详细解释：
int size(): 返回列表中元素的数量。boolean isEmpty(): 判断列表是否为空，如果为空则返回true，否则返回false。boolean contains(Object o): 判断列表是否包含指定的元素，如果包含则返回true，否则返回false。Object[] toArray(): 将列表转换为一个数组。boolean add(E e): 将指定的元素添加到列表的末尾，并返回true。boolean remove(Object o): 从列表中移除指定的元素，如果成功移除则返回true，否则返回false。boolean containsAll(List<E> c): 判断列表是否包含另一个集合中的所有元素，如果是则返回true，否则返回false。boolean addAll(List<? extends E> c): 将另一个集合中的所有元素添加到列表的末尾，如果成功添加则返回true。boolean addAll(int index, List<? extends E> c): 在指定位置插入另一个集合中的所有元素。boolean removeAll(List<?> c): 移除列表中与另一个集合相同的所有元素。void clear(): 移除列表中的所有元素，使其为空。E get(int index): 返回指定位置的元素。E set(int index, E element): 将指定位置的元素替换为新的元素，并返回原来的元素。void add(int index, E element): 在指定位置插入一个元素。E remove(int index): 移除并返回指定位置的元素。int indexOf(Object o): 返回指定元素在列表中第一次出现的位置索引，如果不存在则返回-1。
这个接口定义了列表常用的操作，实现这个接口的类需要提供对应的方法实现，例如ArrayList或LinkedList。
public interface List<E> {
int size();
boolean isEmpty();
boolean contains(Object o);
Object[] toArray();
boolean add(E e);
boolean remove(Object o);
boolean containsAll(List<E> c);
boolean addAll(List<? extends E> c);
boolean addAll(int index, List<? extends E> c);
boolean removeAll(List<?> c);
void clear();
E get(int index);
E set(int index, E element);
void add(int index, E element);
E remove(int index);
int indexOf(Object o);
}
接下来定义 TArrayList，它实现了之前提到的 List 接口。以下是对代码的详细解释：
-
TArrayList类实现了List接口，并使用泛型来表示列表的元素类型。 -
类中的成员变量：
value: 用于存储列表元素的数组，初始长度为零。size: 当前列表中的元素个数。length: 表示数组当前的长度，即最大容量。DEFAULT_LENGTH: 默认的最大容量，设定为20。
private Object[] value = {};//长度为零的数组
private int size;//当下坐标，当前存储的元素个数
private int length;//表示数组当前的长度 最大容器
private static final int DEFAULT_LENGTH = 20;//默认最大容量
-
构造方法
TArrayList(int initiallength)：- 根据传入的
initiallength初始化数组长度，但不允许小于等于零。 - 如果
initiallength小于等于默认容量（20），则使用默认容量初始化数组。 - 否则，使用传入的
initiallength初始化数组。
- 根据传入的
public TArrayList (int initiallength){
if (initiallength <= 0){
throw new IllegalArgumentException("initiallength 不能小于0");
}
if (initiallength <= 20){
length = DEFAULT_LENGTH;
value = new Object[length];
size=0;
}
else{
length = initiallength;
value = new Object[length];
size=0;
}
}
-
方法实现：
size(): 返回当前列表中的元素个数。
public int size() {
return size;
}//元素个数
isEmpty(): 判断列表是否为空。
public boolean isEmpty() {
return size==0;
}//判空
contains(Object o): 判断列表是否包含指定元素。
public boolean contains(Object o) {
for (int i = 0; i < size; i++) {
if (value[i].equals(o)) {
return true;
}
}
return false;
}//是否包含指定元素
toArray(): 将列表转换为数组。
public Object[] toArray() {
return Arrays.copyOf(value, size);
}//列表转换为数组
add(Object o): 向列表末尾添加元素。
public boolean add(Object o) {
if(size==length){
int oldLength = length;
int newLength = oldLength+(oldLength>>1);
length = newLength;
Object[] newValues = new Object[length];
for (int i=0;i<oldLength;i++){
newValues[i]=value[i];
}
value=newValues;
System.out.println("扩容：" +length);
}
value[size++]=o;
return true;
}//向列表中添加元素
remove(Object o): 从列表中移除指定元素。
public boolean remove(Object o) {
for (int i = 0; i < size; i++) {
if (value[i]==o) {
value[i]=null;;
for( int x=i ;x<size;x++){
value[x]=value[x+1];
}
}
}
return true;
}//从列表中移除指定的元素
containsAll(List c): 判断列表是否包含另一个集合中的所有元素。
public boolean containsAll(List c) {
for (int i = 0; i < c.size(); i++) {
Object element = c.get(i);
boolean found = false;
for (int j = 0; j < size; j++) {
if (value[j] != null && value[j].equals(element)) {
found = true;
break;
}
}
if (!found) {
return false;
}
}
return true;
}
addAll(List c): 将另一个集合中的所有元素添加到列表末尾。
public boolean addAll(List c) {
int elementsToAdd = c.size();
if (size + elementsToAdd > DEFAULT_LENGTH) {
// 如果需要，调整数组大小
int newLength = Math.max(size + elementsToAdd, length * 2);
value = Arrays.copyOf(value, newLength);
length = newLength;
System.out.println("扩容："+length);
}
for (int i = 0; i < elementsToAdd; i++) {
value[size + i] = c.get(i);
}
size += elementsToAdd;
return true;
}
addAll(int index, List c): 在指定位置插入另一个集合中的所有元素。
public boolean addAll(int index, List c) {
if (index < 0 || index > size) {
throw new ArrayIndexOutOfBoundsException("Index is out of bounds. Index: " + index + ", Size: " + size);
}
int newSize = size + c.size();
// Ensure capacity
if (newSize > length) {
int newCapacity = Math.max(length * 2, newSize);
value = Arrays.copyOf(value, newCapacity);
length = newCapacity;
}
// Shift elements to make space for new elements
for (int i = size - 1; i >= index; i--) {
value[i + c.size()] = value[i];
}
// Insert elements from the given list at the specified index
for (int i = 0; i < c.size(); i++) {
value[index + i] = c.get(i);
}
size = newSize;
return true;
}
clear(): 移除列表中的所有元素。
public void clear() {
for(int i=0;i < size;i++){
value[i]=null;
}
size=0;
}
get(int index): 获取指定位置的元素。
public Object get(int index) {
if(index>=0&&index<size){
return value[index];
}else{
throw new ArrayIndexOutOfBoundsException("index 超过了范围 max:"+(size-1));
}
}
set(int index, Object element): 替换指定位置的元素。
public Object set(int index, Object element) {
value[index]=element;
return value[index];
}
add(int index, Object element): 在指定位置插入一个元素。
public void add(int index, Object element) {
for(int i=size;i>index;i--){
value[i]=value[i-1];
}
value[index]=element;
}
remove(int index): 移除指定位置的元素。
public Object remove(int index) {
if(index<0||index>size-1){
throw new ArrayIndexOutOfBoundsException("index 超过了范围 max:"+(size-1));
}else{
value[index]=null;
for(int i=index;i<size;i++){
value[i]=value[i+1];
}
}
return null;
}
indexOf(Object o): 获取第一个匹配元素的索引。
public int indexOf(Object o) {
for(int i=0;i<size;i++){
if(value[i]==o){
return i;
}
}
return -1;//没找到返回-1
}//获取第一个元素出现的下标
removeAll(List c): 移除列表中与另一个集合相同的所有元素。
public boolean removeAll(List c) {
for (int i=0;i<c.size();i++) {
Object element = c.get(i);
for(int j =0;j<size;j++){
if(value[j]==element){
value[j]=null;
for(int x=j;x<size;x++){
value[x]=value[x+1];
}
}
}
}
return false;
}
-
main方法：- 创建
TArrayList对象并进行一系列操作的演示，对实现的方法进行测试，包括添加、移除、查询等。
- 创建
public static void main(String[] args) {
TArrayList myList = new TArrayList(20);
for(int i=1;i<=10;i++){
myList.add(i);
}
for(int i=0;i<20;i++){
System.out.println(myList.value[i]);
}
//Object[] array = myList.toArray();
//for (Object element : array) {
//System.out.print(element + " ");
//}
//System.out.println(myList.size);
//System.out.println(myList.isEmpty());
//System.out.println(myList.contains(5));
//System.out.println(myList.contains(11));
//System.out.println(myList.get(9));
//System.out.println(myList.set(9,11));
//myList.add(10,11);
//for(int i=0;i<20;i++){
//System.out.println(myList.value[i]);
//}
//myList.remove(9);
//for(int i=0;i<20;i++){
//System.out.println(myList.value[i]);
//}
//System.out.println(myList.indexOf(5));
//myList.remove((Integer)5);
//for(int i=0;i<20;i++){
//System.out.println(myList.value[i]);
//}
//myList.clear();
//for(int i=0;i<20;i++){
//System.out.println(myList.value[i]);
//}
TArrayList List1 = new TArrayList(3);
for(int i=1;i<=3;i++){
List1.add(i);
}
for(int i=0;i<3;i++){
//System.out.println(List1.value[i]);
}
TArrayList List2 = new TArrayList(3);
for(int i=11;i<=13;i++){
List2.add(i);
}
//System.out.println(myList.containsAll(List1));
//System.out.println(myList.containsAll(List2));
//myList.addAll(List2);
//for(int i=0;i<20;i++){
//System.out.println(myList.value[i]);
//}
//myList.addAll(0,List2);
//for(int i=0;i<20;i++){
//System.out.println(myList.value[i]);
//}
//myList.removeAll(List1);
//for(int i=0;i<20;i++){
//System.out.println(myList.value[i]);
//}
}
数组是一种常见的数据结构，具有以下特点：
-
连续的内存空间： 数组中的元素在内存中是连续存储的，这使得对数组的随机访问和遍历操作非常高效。
-
相同数据类型： 数组中的元素必须是相同的数据类型，这是因为数组是一个固定大小的结构，每个元素占据相同的内存空间。
-
固定大小： 数组的大小是固定的，一旦创建，其大小通常不能动态改变。
-
随机访问： 由于元素的连续存储，可以通过索引直接访问数组中的任何元素，使得随机访问变得非常高效。
常见的数组操作包括：
-
访问元素： 通过索引可以快速访问数组中的任何元素。
-
插入元素： 在数组中插入元素可能需要将后续元素向后移动，这可能是一个耗时的操作。
-
删除元素： 删除数组中的元素同样可能需要将后续元素向前移动，同样可能是一个耗时的操作。
-
遍历： 遍历数组中的所有元素，执行特定的操作。
-
查找元素： 在数组中查找特定元素，可以使用线性查找或者二分查找等算法。
-
更新元素： 修改数组中特定位置的元素值。
需要注意的是，由于数组的固定大小，插入和删除元素可能涉及到移动大量元素的操作，因此在这些操作频繁进行的情况下，可能会考虑使用其他数据结构，如链表或动态数组。
更多推荐
21
0- 0
已为社区贡献1条内容
所有评论(0)