`
Inmethetiger
  • 浏览: 111268 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

ArrayList的实现方式

阅读更多

 

      这里我想说说我对这个数据结构的理解。之前一直被theSize,size(),theItems.length几个点搞混。现在有点小明白。在java环境下,新建立数组并用int[] a = new int[10]。这样初始化的时候,数组的长度a.length=10。但是全部都是为null。而在上面的线性表中的size,返回的是a数组包含元素的个数,与a.length没有关系。

调试的情况如附件所示:theSize是线性表这个对象的一个属性。表示的是这个对象中的itemElement的个数。而theItem.length则是itemElem的长度,里面的值都是为null。

 

还有增加和删除。

增加为什么是

 

	public void add(int idx, AnyType x) {
		int objectSize = theItems.length;
		if (theItems.length == size())
			ensureCapacity(size() * 2 + 1);
		for (int i = theSize; i > idx; i--)
			theItems[i] = theItems[i - 1];

		theItems[idx] = x;
		theSize++;
	}

 而不是theItems[i+1]=theItems[i]?在当前条件下(i>index)。如果改为这种。那么,比如有theItems[]={0,1,2,3,4,5,6,null,null}、然后在add(4,100)。则执行的时候会是 theItems[8]=theItem[7]。虽然theItems.length=10。数组没有越界。但是却是在null之后插入。而使用上面的情况下则是theItem[7]=theItem[6]。刚好是最后一个元素的下一个空间。

 

删除也同样如此。而且要注意,i<size-1。而不是i<size。如果小于size的话。也会出问题。

 

归根到底,主要是size表示的是元素个数。而i或者index表示的是索引。而数组索引是从0开始的。就像a[0]的index=0而size=1一样。

 

 

 

 

 

 

 

import java.util.Iterator;
import java.util.NoSuchElementException;

public class MyArrayList<T> implements Iterable<T> {

	// 默认大小
	private static final int DEFAULT_CAPACITY = 10;
	// 长度
	private int theSize;
	// 数据
	private T[] theItems;

	// 构造函数
	public MyArrayList() {
		this(DEFAULT_CAPACITY);
	}

	// 构造函数
	@SuppressWarnings("unchecked")
	public MyArrayList(int size) {
		theItems = (T[]) new Object[size];
	}

	// 清除
	public void clear() {
		theSize = 0;
		ensureCapacity(DEFAULT_CAPACITY);
	}

	// 大小
	public int size() {
		return theSize;
	}

	// 是否为空
	public boolean isEmpty() {
		return size() == 0;
	}

	// 扩展数组大小
	public void trimToSize() {
		ensureCapacity(size());
	}

	// 查找
	public T get(int index) {
		if (index < 0 || index >= size())
			throw new ArrayIndexOutOfBoundsException();
		return theItems[index];
	}

	// 修改
	public T set(int index, T newVal) {
		if (index < 0 || index >= size())
			throw new ArrayIndexOutOfBoundsException();
		T old = theItems[index];
		theItems[index] = newVal;
		return old;
	}

	// 增加
	public void add(int index, T t) {
		// 如果数组的长度等于存储元素的长度,则扩展数组长度
		if (theItems.length == size())
			ensureCapacity(size() * 2 + 1);
		// 移动
		for (int i = theSize; i > index; i--) {
			theItems[i] = theItems[i - 1];
		}
		theItems[index] = t;
		theSize++;
	}

	// 增加
	public boolean add(T t) {
		System.out.println("size():" + size());
		add(size(), t);
		return true;
	}

	// 删除
	public T remove(int index) {
		T removeItem = theItems[index];
		for (int i = index; i < size() - 1; i++) {
			theItems[i] = theItems[i + 1];
		}
		theSize--;
		return removeItem;
	}

	// 添加空间
	public void ensureCapacity(int newCapcity) {
		if (newCapcity < theSize)
			return;
		T[] old = theItems;
		theItems = (T[]) new Object[newCapcity];
		for (int i = 0; i < size(); i++) {
			theItems[i] = old[i];
		}
	}

	// 迭代
	@Override
	public Iterator<T> iterator() {
		return new ArrayListIterator();
	}

	private class ArrayListIterator implements Iterator<T> {

		private int current = 0;

		public boolean hasNext() {
			return current < size();
		}

		public T next() {
			if (!hasNext()) {
				throw new NoSuchElementException();
			}
			return theItems[current++];
		}

		@Override
		public void remove() {
			MyArrayList.this.remove(--current);
		}

	}
}

 



  
  
  • 大小: 38.8 KB
分享到:
评论

相关推荐

    ArrayList的一个C++类模板实现

    在这个ArrayList实现中,第一层散列可能是用来快速定位元素的位置,而第二层散列可能是为了处理散列冲突,确保每个元素都有一个唯一的索引。这种双层散列结构可以显著减少查找和插入的时间复杂度,使其接近O(1)。 ...

    Java ArrayList实现的快排,归并排序,堆排序

    本篇将重点讲解如何利用ArrayList实现快速排序(Quick Sort)、归并排序(Merge Sort)和堆排序(Heap Sort)这三种经典的排序算法,并探讨它们的原理、优缺点以及在实际应用中的选择。 **快速排序(Quick Sort)**...

    JavaScript 实现基础 ArrayList 功能

    虽然JavaScript原生不支持ArrayList,但我们可以利用数组(Array)对象来实现类似的功能。下面将详细介绍如何使用JavaScript来实现基础的ArrayList功能,并探讨在没有参数重载(overload)的情况下如何处理方法的...

    用ArrayList实现用户信息的添加,删除,更新,查询

    以上就是使用ArrayList实现用户信息管理的基本操作。然而,对于大型项目或频繁的增删改查操作,可能需要考虑使用更高效的数据结构,如HashMap(基于键值对,查找速度更快)或数据库来进行数据管理。在实际应用中,...

    JSP_使用_Session_ArrayList_实现购物车程序

    根据给定的信息,本文将详细解释如何在Java Server Pages (JSP)中使用`HttpSession`和`ArrayList`来实现一个简单的购物车程序。...这种实现方式虽然简单,但对于理解和学习基本的Web开发技术非常有帮助。

    Java员工管理系统,ArrayList存储

    本项目聚焦于使用Java编程语言实现一个基于ArrayList的员工管理系统。ArrayList是Java集合框架中的一种动态数组,它提供了方便的数据存储和操作功能,特别适合用于小型数据集的存储。 在Java中,ArrayList类位于`...

    ArrayList LinkedList Vector区别

    ArrayList、LinkedList、Vector 是 Java 中常用的数据结构实现类,它们都实现了 List 接口,但它们在存储方式、性能、线程安全性等方面有着不同特点。 首先,ArrayList 和 Vector 都是采用数组方式存储数据的,这种...

    模拟java ArrayList Iterator

    ArrayList提供了一种高效的方式来管理大量的元素,并且提供了迭代器(Iterator)来遍历这些元素,使得我们可以在不暴露底层实现细节的情况下访问和修改列表中的元素。这个资源的目的是通过模拟Java ArrayList的...

    arrayList排序

    ArrayList是Java编程语言中常用的集合类之一,它继承自AbstractList并实现了List接口。ArrayList以对象数组的形式存储数据,提供了动态增长的能力,便于增删改查操作。在处理大量数据时,排序是常见的需求,本篇文章...

    c版的arraylist

    虽然不如Java中的`ArrayList`那么方便,但它提供了一种灵活的方式来管理和操作动态数据集,对于C程序员来说是一个有价值的工具。通过学习和理解这个实现,开发者可以更好地理解和运用C语言的数据结构和内存管理技巧...

    用C语言模拟ArrayList

    通过这种方式,我们实现了C语言中的ArrayList。需要注意的是,虽然C语言没有内置的ArrayList,但我们可以利用动态内存分配和结构体来创建自己的实现,从而获得与高级语言相似的功能。在实际应用中,我们还需要考虑...

    ArrayList集合工具类

    在JavaScript开发中,虽然没有直接对应的ArrayList类,但我们可以借鉴其概念和操作方式来实现类似的功能。 ArrayList的特点包括: 1. 底层实现:ArrayList使用了动态数组(Array)作为底层数据结构。这意味着它的...

    C++ArrayList

    下面将详细介绍C++实现ArrayList类的关键知识点。 首先,`ArrayList`的核心是动态内存管理。在C++中,我们通常使用`new`运算符来动态分配内存,创建一个可变大小的数组。为了方便管理和释放内存,我们还需要使用`...

    ArrayList LinkList和vector的区别

    ArrayList、LinkList和Vector是Java中三个常用的集合类,它们都实现了List接口,但是在实现方式和性能上有所不同。 ArrayList ArrayList是使用数组方式存储数据的,数组元素数大于实际存储的数据,以便增加和插入...

    Android:ArrayList学习实例

    在Android开发中,ArrayList是一个非常基础且常用的集合类,它继承自Java的AbstractList,并实现了List接口。ArrayList主要用于存储和管理有序的元素序列,它的核心特点是动态扩容,可以在运行时根据需要自动增加...

    Java中ArrayList的removeAll方法详解

    在比较两种实现方式时,我们可以看到,优化的removeAll方法的执行速度远远超过了原始的removeAll方法。这是因为优化的方法使用了HashSet的contains方法,该方法的时间复杂度为O(1),far less than O(n)。同时,优化...

    ArrayList深度剖析与简单实用

    在Java中,创建ArrayList最基础的方式是通过`new ArrayList();`。 2. **ArrayList的重要方法和属性** - **构造器**:ArrayList提供了三个构造器,分别是无参构造器(默认容量16)、接受ICollection参数的构造器...

    ArrayList源码分析

    ArrayList实现了`Iterator`接口,提供了一种安全的遍历方式,即迭代器模式。通过`iterator()`方法获取迭代器,可以顺序访问ArrayList的所有元素,且在遍历过程中能方便地进行删除操作。 6. **线程安全性** ...

    Vector 与ArrayList区别

    如果程序只需要单线程访问,或者可以通过其他方式实现线程安全(例如使用 `Collections.synchronizedList` 包装 `ArrayList`),那么 `ArrayList` 更合适。 **2. 数据增长的影响** - **初始化容量**:为了提高...

Global site tag (gtag.js) - Google Analytics