Java动态数组的实现过程

终是梦幻 發表於 2026-1-8 14:26:50

<div id="navCategory"><h5 class="catalogue">目录</h5><ul class="first_class_ul"><li>1. 基础结构设计</li><li>2. 核心功能实现</li><ul class="second_class_ul"><li>2.1 基本操作</li><ul class="third_class_ul"><li>获取元素个数和容量</li><li>获取和设置元素</li></ul><li>2.2 添加元素</li><ul class="third_class_ul"></ul><li>2.3 插入元素</li><ul class="third_class_ul"></ul><li>2.4 删除元素</li><ul class="third_class_ul"></ul><li>2.5 扩容机制</li><ul class="third_class_ul"></ul></ul><li>3. 性能分析</li><ul class="second_class_ul"><li>时间复杂度</li><ul class="third_class_ul"></ul><li>空间复杂度</li><ul class="third_class_ul"></ul></ul><li>4. 实现特点</li><ul class="second_class_ul"></ul><li>5. 改进建议</li><ul class="second_class_ul"></ul><li>总结</li><ul class="second_class_ul"></ul></ul></div><p>在本文中，我们将深入探讨如何实现一个简单的动态数组（类似于Java中的ArrayList）。通过这个实现，我们可以更好地理解动态数组的工作原理和核心操作。</p>
<p class="maodian"></p><h2>1. 基础结构设计</h2>
<p>首先，让我们看看类的基本结构：</p>
<div class="jb51code"><pre class="brush:java;">public class MyList {
private int[] arr;    // 底层数组
private int capacity = 10; // 数组容量
private int size = 0; // 当前元素个数
private int extendRatio = 2; // 扩容倍数
}
</pre></div>
<p>这个实现包含了四个关键的成员变量：</p>
<ul><li><code>arr</code>: 存储实际数据的底层数组</li><li><code>capacity</code>: 数组的容量</li><li><code>size</code>: 当前实际存储的元素数量</li><li><code>extendRatio</code>: 扩容时的倍数</li></ul>
<p class="maodian"></p><h2>2. 核心功能实现</h2>
<p class="maodian"></p><h3>2.1 基本操作</h3>
<p class="maodian"></p><h4>获取元素个数和容量</h4>
<div class="jb51code"><pre class="brush:java;">public int size() {
return size;
}

public int capacity() {
return capacity;
}
</pre></div>
<p class="maodian"></p><h4>获取和设置元素</h4>
<div class="jb51code"><pre class="brush:java;">public int get(int index) {
if (index < 0 || index >= size) {
   throw new IndexOutOfBoundsException();
}
return arr;
}

public void set(int index, int num) {
if (index < 0 || index >= size) {
   throw new IndexOutOfBoundsException();
}
arr = num;
}
</pre></div>
<p class="maodian"></p><h3>2.2 添加元素</h3>
<div class="jb51code"><pre class="brush:java;">public void add(int item) {
if (size == capacity) {
   extendCapacity();
}
arr = item;
size++;
}
</pre></div>
<p class="maodian"></p><h3>2.3 插入元素</h3>
<div class="jb51code"><pre class="brush:java;">public void insert(int index, int item) {
if (index < 0 || index >= size) {
   throw new IndexOutOfBoundsException();
}
if (size == capacity) {
   extendCapacity();
}
// 将index后的元素都向后移动一位
for (int i = size - 1; i >= index; i--) {
   arr = arr;
}
arr = item;
size++;
}
</pre></div>
<p class="maodian"></p><h3>2.4 删除元素</h3>
<div class="jb51code"><pre class="brush:java;">public int remove(int index) {
if (index < 0 || index >= size) {
   throw new IndexOutOfBoundsException();
}
int num = arr;
// 将index后的元素都向前移动一位
for (int i = index; i < size - 1; i++) {
   arr = arr;
}
size--;
return num;
}
</pre></div>
<p class="maodian"></p><h3>2.5 扩容机制</h3>
<div class="jb51code"><pre class="brush:java;">private void extendCapacity() {
// 新建一个长度为原数组 extendRatio 倍的新数组，并将原数组复制到新数组
arr = Arrays.copyOf(arr, extendRatio);
// 更新列表容量
capacity = arr.length;
}
</pre></div>
<p class="maodian"></p><h2>3. 性能分析</h2>
<p class="maodian"></p><h3>时间复杂度</h3>
<ul><li>访问元素 (get/set): O(1)</li><li>在末尾添加元素 (add): 平均O(1)</li><li>插入元素 (insert): O(n)</li><li>删除元素 (remove): O(n)</li></ul>
<p class="maodian"></p><h3>空间复杂度</h3>
<ul><li>初始空间复杂度: O(1)</li><li>扩容后的空间复杂度: O(n)</li></ul>
<p class="maodian"></p><h2>4. 实现特点</h2>
<ul><li><strong>动态扩容</strong>：当数组空间不足时，会自动扩容为原来的2倍。</li><li><strong>边界检查</strong>：所有的操作都会进行严格的边界检查，防止数组越界。</li><li><strong>数据搬移</strong>：在插入和删除操作时，需要移动元素，这是数组实现的一个缺点。</li></ul>
<p class="maodian"></p><h2>5. 改进建议</h2>
<ol><li>考虑添加收缩机制，当数组使用率过低时减少容量</li><li>可以支持泛型，使其能够存储任意类型的数据</li><li>优化扩容机制，使用更灵活的扩容策略</li><li>添加迭代器支持，提供更方便的遍历方式</li></ol>
<p class="maodian"></p><h2>总结</h2>
<p>这个简单的动态数组实现展示了数据结构中最基本的一些概念：动态扩容、边界检查、元素操作等。通过理解这些基础实现，我们可以更好地理解Java中ArrayList等集合类的工作原理。</p>
<p>以上为个人经验，希望能给大家一个参考，也希望大家多多支持琼殿技术社区。</p>

                        <div class="art_xg">
                           <b>您可能感兴趣的文章:</b><ul><li>Java ArrayList的基本概念和作用及动态数组的机制与性能</li><li>使用Java实现在Excel中添加动态数组公式</li><li>Java中的动态数组和栈Vector Stack使用区别介绍</li><li>Java动态数组ArrayList实现动态原理</li><li>ArrayList源码探秘之Java动态数组的实现</li><li>Java ArrayList集合详解(Java动态数组)</li></ul>
                        </div>

                     </div>

頁: [1]

琼殿技术论坛's Archiver

Java动态数组的实现过程