首页 > 代码库 > 每日一记--2014.10.11（2）

每日一记--2014.10.11（2）

2024-07-26 16:07:23   216人阅读

今天终于进展到了第三章，好好读了读链表

其实对于linkedlist来说，它的remove也会是O(N)，因为对于删除这个动作确实是常数时间的，但是对于定位到被删除元素的位置就需要有线性时间的开销了

今天参照书上的把ArrayList类编了编，定名为MyArrayListM

  1 package myarraylist;  2   3 import java.util.Iterator;  4 import java.util.NoSuchElementException;  5   6 public class MyArrayListM<AnyType> implements Iterable<AnyType>{  7     private static final int DEFAULT_SIZE=10;  8     private int theSize;  9     private AnyType[] items; 10      11     MyArrayListM(){ 12         theSize=0; 13         ensureCapacity(DEFAULT_SIZE); 14     } 15     public int size(){ 16         return theSize; 17     } 18     public boolean isEmpty(){ 19         return theSize==0; 20     } 21     public void trimToSize(){ 22         ensureCapacity(size()); 23     } 24     public AnyType get(int idx){ 25         if(idx<0|idx>size()) 26             throw new ArrayIndexOutOfBoundsException(); 27         return items[idx]; 28     } 29     public AnyType set(int idx,AnyType element){ 30         if(idx<0|idx>size()) 31             throw new ArrayIndexOutOfBoundsException(); 32         AnyType old = items[idx]; 33         items[idx]=element; 34         return old; 35     } 36     public void add(AnyType element){ 37         add(size(),element); 38     } 39     public void add(int idx,AnyType element){ 40         if(idx<0|idx>size()) 41             throw new ArrayIndexOutOfBoundsException(); 42         if(items.length==size()) 43             ensureCapacity(size()*2); 44         for(int i=size();i>idx;i--){//改变一下i的取值，可以减少使用一个临时的数组 45             items[i]=items[i-1]; 46         } 47         items[idx]=element; 48          49         theSize++;//嗯嗯，这个忘记了 50     } 51      52     public AnyType remove(int idx){ 53         if(idx<0|idx>size()) 54             throw new ArrayIndexOutOfBoundsException();  55         AnyType removed =items[idx]; 56         for(int i=idx;i<size()-1;i++){ 57             items[i]=items[i+1]; 58         } 59         theSize--; 60         return removed; 61          62     } 63     @SuppressWarnings("unchecked") 64     private void ensureCapacity(int cap) { 65         if(cap<size()) 66             return; 67         AnyType[] old = items; 68         items = (AnyType[]) new Object[cap]; 69         for(int i=0;i<size();i++){ 70             items[i]=old[i]; 71         } 72          73     } 74     public Iterator<AnyType> iterator(){ 75         return new ArrayListIterator(); 76     } 77     private class ArrayListIterator implements Iterator<AnyType> {//ArrayListIterator之后不能加<AnyType>,否则报错 78         int current =0; 79         @Override 80         public boolean hasNext() { 81             return current <size(); 82         } 83  84         @Override 85         public AnyType next() { 86             if(!hasNext()) 87                 throw new NoSuchElementException(); 88             return items[current++]; 89          90         } 91  92         @Override 93         public void remove() { 94             // TODO Auto-generated method stub 95             MyArrayListM.this.remove(current--); 96         } 97          98     } 99     100 101 }

 

每日一记--2014.10.11（2）


联系
我们