实现一个类似ArrayList的数据结构

简介: 实现一个类似ArrayList的数据结构

实现一个类似ArrayList的数据结构,可以帮助我们更深入地理解动态数组的原理和实现细节。在Java中,ArrayList是常用的动态数组实现,它可以根据需要动态地增长或缩减存储元素的空间,提供了便捷的操作方法。

 

自实现ArrayList的核心原理

 

自实现一个ArrayList主要涉及以下几个核心原理和步骤:

 

1. **动态数组的基本结构**:使用数组作为基本的存储结构,并实现动态扩展功能。当数组容量不足时,通过创建一个更大的数组并将原有元素拷贝过去来实现扩展。

 

2. **元素的添加和删除**:实现添加元素、获取元素、删除元素等基本操作。添加元素时,需要考虑数组容量是否足够;删除元素时,可能需要进行数组的整理和缩减容量的操作。

 

3. **迭代器的实现**:提供迭代器以支持对ArrayList中元素的遍历和操作。

 

4. **异常处理**:处理可能的越界访问等异常情况。

 

自实现ArrayList的代码示例

 

下面是一个简单的自实现ArrayList的代码示例,展示了基本的添加、获取、删除和迭代功能。

 

```java
import java.util.Arrays;
import java.util.Iterator;
import java.util.NoSuchElementException;
 
public class MyArrayList<E> implements Iterable<E> {
    private static final int DEFAULT_CAPACITY = 10;
    private Object[] elements;
    private int size;
 
    public MyArrayList() {
        elements = new Object[DEFAULT_CAPACITY];
        size = 0;
    }
 
    public MyArrayList(int initialCapacity) {
        if (initialCapacity < 0) {
            throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
        }
        elements = new Object[initialCapacity];
        size = 0;
    }
 
    public int size() {
        return size;
    }
 
    public boolean isEmpty() {
        return size == 0;
    }
 
    public void add(E e) {
        if (size == elements.length) {
            ensureCapacity(size + 1);
        }
        elements[size++] = e;
    }
 
    @SuppressWarnings("unchecked")
    public E get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        return (E) elements[index];
    }
 
    public E remove(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        @SuppressWarnings("unchecked")
        E oldValue = (E) elements[index];
        int numMoved = size - index - 1;
        if (numMoved > 0) {
            System.arraycopy(elements, index + 1, elements, index, numMoved);
        }
        elements[--size] = null; // Let gc do its work
        return oldValue;
    }
 
    private void ensureCapacity(int minCapacity) {
        int oldCapacity = elements.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1); // grow by 50%
        if (newCapacity < minCapacity) {
            newCapacity = minCapacity;
        }
        elements = Arrays.copyOf(elements, newCapacity);
    }
 
    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            private int cursor = 0;
 
            @Override
            public boolean hasNext() {
                return cursor != size;
            }
 
            @SuppressWarnings("unchecked")
            @Override
            public E next() {
                int i = cursor;
                if (i >= size) {
                    throw new NoSuchElementException();
                }
                cursor = i + 1;
                return (E) elements[i];
            }
        };
    }
 
    public static void main(String[] args) {
        MyArrayList<String> list = new MyArrayList<>();
        list.add("Apple");
        list.add("Banana");
        list.add("Orange");
 
        System.out.println("Elements in the list:");
        for (String fruit : list) {
            System.out.println(fruit);
        }
 
        System.out.println("Removing element at index 1: " + list.remove(1));
        System.out.println("Size of list after removal: " + list.size());
 
        System.out.println("Elements in the list after removal:");
        for (String fruit : list) {
            System.out.println(fruit);
        }
    }
}
```

 

解释和关键点说明

 

- **数组存储**:`elements`数组用于存储元素,初始化时默认容量为`DEFAULT_CAPACITY`(这里设定为10)。

- **添加元素**:`add(E e)`方法将元素添加到数组末尾,如果数组容量不足则通过`ensureCapacity`方法扩展数组。

- **获取元素**:`get(int index)`方法根据索引获取元素,注意边界检查。

- **删除元素**:`remove(int index)`方法删除指定索引位置的元素,将后续元素向前移动。

- **迭代器**:实现了`Iterable<E>`接口,使得可以使用增强的for循环和迭代器遍历列表中的元素。

- **动态扩展**:`ensureCapacity(int minCapacity)`方法负责数组容量的动态扩展,保证足够的存储空间。

 

这个示例演示了如何基于数组实现一个简单的动态数组,具备基本的添加、获取、删除和迭代功能。自实现ArrayList的过程不仅可以加深对数据结构的理解,还能够理解Java集合框架中ArrayList的设计原理和优化策略。

目录
相关文章
|
5月前
|
Java
【Java集合类面试二十六】、介绍一下ArrayList的数据结构?
ArrayList是基于可动态扩展的数组实现的,支持快速随机访问,但在插入和删除操作时可能需要数组复制而性能较差。
|
2月前
|
存储 Java 索引
Java中的数据结构:ArrayList和LinkedList的比较
【10月更文挑战第28天】在Java编程世界中,数据结构是构建复杂程序的基石。本文将深入探讨两种常用的数据结构:ArrayList和LinkedList,通过直观的比喻和实例分析,揭示它们各自的优势与局限,帮助你在面对不同的编程挑战时做出明智的选择。
|
3月前
|
Java C++ 索引
让星星⭐月亮告诉你,LinkedList和ArrayList底层数据结构及方法源码说明
`LinkedList` 和 `ArrayList` 是 Java 中两种常见的列表实现。`LinkedList` 基于双向链表,适合频繁的插入和删除操作,但按索引访问元素效率较低。`ArrayList` 基于动态数组,支持快速随机访问,但在中间位置插入或删除元素时性能较差。两者均实现了 `List` 接口,`LinkedList` 还额外实现了 `Deque` 接口,提供了更多队列操作。
32 3
|
3月前
|
存储 缓存 索引
从底层数据结构和CPU缓存两方面剖析LinkedList的查询效率为什么比ArrayList低
本文详细对比了ArrayList和LinkedList的查询效率,从底层数据结构和CPU缓存两个方面进行分析。ArrayList基于动态数组,支持随机访问,查询时间复杂度为O(1),且CPU缓存对其友好;而LinkedList基于双向链表,需要逐个节点遍历,查询时间复杂度为O(n),且CPU缓存对其帮助不大。文章还探讨了CPU缓存对数组增删操作的影响,指出缓存主要作用于读取而非修改。通过这些分析,加深了对这两种数据结构的理解。
53 2
|
3月前
|
设计模式 安全 容器
数据结构第一篇【探究List和ArrayList之间的奥秘 】
数据结构第一篇【探究List和ArrayList之间的奥秘 】
29 5
|
4月前
|
存储 Java 程序员
【数据结构】初识集合&深入剖析顺序表(Arraylist)
Java集合框架主要由接口、实现类及迭代器组成,包括Collection和Map两大类。Collection涵盖List(有序、可重复)、Set(无序、不可重复),Map则由键值对构成。集合通过接口定义基本操作,具体实现由各类如ArrayList、HashSet等提供。迭代器允许遍历集合而不暴露其实现细节。List系列集合元素有序且可重复,Set系列元素无序且不可重复。集合遍历可通过迭代器、增强for循环、普通for循环及Lambda表达式实现,各有适用场景。其中ArrayList实现了动态数组功能,可根据需求自动调整大小。
43 11
|
3月前
|
算法 Java 测试技术
数据结构 —— Java自定义代码实现顺序表,包含测试用例以及ArrayList的使用以及相关算法题
文章详细介绍了如何用Java自定义实现一个顺序表类,包括插入、删除、获取数据元素、求数据个数等功能,并对顺序表进行了测试,最后还提及了Java中自带的顺序表实现类ArrayList。
43 0
|
7月前
|
存储 Java API
Java数据结构之ArrayList(如果想知道Java中有关ArrayList的知识点,那么只看这一篇就足够了!)
Java数据结构之ArrayList(如果想知道Java中有关ArrayList的知识点,那么只看这一篇就足够了!)
Java数据结构之ArrayList(如果想知道Java中有关ArrayList的知识点,那么只看这一篇就足够了!)
|
7月前
|
存储 Java 索引
【Java】LinkedList vs. ArrayList:Java中的数据结构选择
【Java】LinkedList vs. ArrayList:Java中的数据结构选择
36 3
|
2月前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
241 9