便捷网站建设价格,怎么建立一个公司的网站,炫酷的网站设计,石家庄新钥匙做网站目录 引出手动实现ArrayList定义接口MyListT写ArrayList的实现类增加元素删除元素 写测试类进行测试数组插入数据? 总结 引出 1.ArrayList的结构分析#xff0c;可迭代接口#xff0c;是List的实现#xff1b; 2.数组增加元素和删除元素的分析#xff0c;何时扩容… 目录 引出手动实现ArrayList定义接口MyListT写ArrayList的实现类增加元素删除元素 写测试类进行测试数组插入数据? 总结 引出 1.ArrayList的结构分析可迭代接口是List的实现 2.数组增加元素和删除元素的分析何时扩容如何扩容 3.插入数据的复杂度O(N) 4.数组特点查找和修改容易O(1)增加和删除复杂O(N)
手动实现ArrayList 定义接口MyListT
package com.tianju.book.jpa.mlist;/*** 手工打造ArrayList*/
public interface MyListT {/*** 增加一个元素涉及到容量的变化*/void add(T t);/*** 根据索引删除元素* param index 要删除元素的索引超过索引索引不存在*/void remove(int index);/*** 根据索引修改一个元素* param index 要修改的索引* param t 修改的值*/void set(int index,T t);/*** 根据索引获取元素* param index 索引* return 获取的元素*/T get(int index);int size();String toString();}写ArrayList的实现类
增加元素
如果放不下怎么办如何扩容扩容后如何操作 扩容每次为原来的1.5倍 如果放不下就扩容 扩容后把原来的数据一个一个再放回去 删除元素 源码分析 删除头部尾部中间——最一般的就是中间元素被删除此时需要跳过被删除的元素把没有被删除的放回去 package com.tianju.book.jpa.mlist;public class MyArrayListT implements MyListT {private int size; // 不写初始值为0private Object[] elementData new Object[5]; // 自己的ArrayList的默认大小是5Overridepublic void add(T t) {// 如果放不下就要扩容if (size1elementData.length){// 位运算右移相当于除以2所以新的长度是原来的1.5倍int newLen elementData.length (elementData.length1);// 这里相当于新建一个数组把原来的一个一个放进去然后把elementData指向新的数组
// elementData Arrays.copyOf(elementData, newLen); // arrays工具类的实现Object[] newElementData new Object[newLen];for(int i0;ielementData.length;i){newElementData[i] elementData[i];}elementData newElementData;System.out.println(扩容后长度elementData.length);}elementData[size] t;//把新的元素放过来size size 1; // 新的size比原来加1}Overridepublic void remove(int index) {// 删除怎么搞// 删除头部尾部中间// 这里采用新建一个数组跳过要删除的那个元素一个一个再放回去Object[] newElementData new Object[elementData.length]; // 和原来大小一样int j 0; // 新的索引for (int i0;isize;i){if (iindex){System.out.println(index跳过: elementData[i]);continue;}newElementData[j] elementData[i];j; // 跳过被删除的那个索引}elementData newElementData; // 再指向新的数组size--; // 删除元素后size-1}Overridepublic void set(int index, T t) {// 修改的复杂度为O(1)if (indexsize){throw new IndexOutOfBoundsException(索引越界);}elementData[index] t;}Overridepublic T get(int index) {// 根据索引获取元素的复杂度也为O(1)// 需要判断索引是不是超了if (indexsize){throw new IndexOutOfBoundsException(索引越界);}return (T) elementData[index];}Overridepublic int size() {return this.size;}Overridepublic String toString(){String str [;for (int i 0;isize;i){str elementData[i] ,;}str ];return str;}
}
写测试类进行测试
package com.tianju.book.jpa.mlist;import java.util.ArrayList;
import java.util.List;public class MyListTest {public static void main(String[] args) {MyListString myList new MyArrayList();System.out.println(myList.size());myList.add(Peter001);myList.add(Peter002);myList.add(Peter003);myList.add(Peter004);System.out.println(myList.size());myList.add(Peter005);System.out.println(目前List中元素的数量myList.size());System.out.println(myList);System.out.println(*******删除一个元素*******);myList.remove(1);System.out.println(myList);System.out.println(删除元素后list长度myList.size());myList.add(shirley);System.out.println(新增shirley元素后listmyList);System.out.println(长度myList.size());System.out.println(*******修改一个元素*******);myList.set(0, zgg);System.out.println(myList);System.out.println(*******查询一个元素*******);String s myList.get(2);System.out.println(索引为2的元素为s);System.out.println(索引越界的情况);System.out.println(myList.get(10));ListString strings new ArrayList();System.out.println(strings.size());}
} 数组插入数据? 插人和删除的花费却潜藏着昂贵的开销这要看插入和删除发生在什么地方。最坏的情形下在位置0的插入即在表的前端插入首先需要将整个数组后移一个位置以空出空间来而删除第一个元素则需要将表中的所有元素前移一个位置因此这两种操作的最坏情况为O(N)。
平均来看这两种操作都需要移动表的一半的元素因此仍然需要线性时间。另一方面如果所有的操作都发生在表的高端那就没有元素需要移动而添加和删除则只花费O(1)时间。
存在许多情形在这些情形下的表是通过在高端进行插入操作建成的其后只发生对数组的访问即只有findKth操作。在这种情况下数组是表的一种恰当的实现。然而如果发生对表的一些插入和删除操作特别是对表的前端进行那么数组就不是一种好的选择。另一种数据结构链表(linked list)。 总结
1.ArrayList的结构分析可迭代接口是List的实现 2.数组增加元素和删除元素的分析何时扩容如何扩容 3.插入数据的复杂度O(N) 4.数组特点查找和修改容易O(1)增加和删除复杂O(N)
