数据结构---顺序表以及ArrayList源码分析

分手后的思念是犯贱 2024-04-18 14:09 137阅读 0赞

顺序表的顺序存储是指在内存中用地址连续的一块内存存储空间顺序存放线性表的各元素。

只要知道顺序表的首地址和每个数据元素所占地址单元的个数就可以求出第i个数据元素的地址。所以对于顺序表来说查改比较快。

通常使用一维数组数组来存储。

在java中简单实现：

public class ListDemo {
    	private final int MAXSIZE=100;
    	private Object data[];
    	int last;
    	
    	int  defaultLength=20;
    	public ListDemo(int length) {
    		data = new Object[length];
    		last=0;
    	}
    	
    	public ListDemo() {
    		data = new Object[defaultLength];
    		last=0;
    	}
    }

进行简单的增删改查操作：

/*
    	 * 判断是否容量是否足够，如果不够扩容（2倍）
    	 */
    	public void add(Object obj) {
    		if (last < data.length) {
    			data[last++] = obj;
    		} else {
    			data = Arrays.copyOf(data, data.length * 2, Object[].class);
    			data[last++] = obj;
    		}
    	}
    
    	/*
    	 * 判断index是否合法，删除时数组整体向左移动
    	 */
    	public void delete(int index) {
    		if (index >= 0 && index <= last) {
    			for (int i = index; i < last - 1; i++) {
    				data[i] = data[i + 1];
    			}
    			last--;
    		} else {
    			System.err.println("下标不合法");
    		}
    	}
    	
    	/*
    	 * 查找
    	 */
    	public Object search(int index) {
    		if(index<last) {
    			return data[index];
    		}else {
    			return null;
    		}
    	} 
    	
    	/*
    	 * 修改
    	 */
    	public void update(Object obj,int index) {
    		if(index<last) {
    			data[index] = obj;
    		}else {
    			System.err.println("下标不合法");
    		}
    	}

下面分析一下ArrayList源码（部分）：

属性：
      //默认容量
      private static final int DEFAULT_CAPACITY = 10;
      //空集合
      private static final Object[] EMPTY_ELEMENTDATA = {};
      //默认空集合
      private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
      //数据存储数组，不参与序列化
      transient Object[] elementData;
      //容量
      private int size;
      //最大容量
      private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
      构造方法：
      /*
      *指定长度的构造方法
      */
       public ArrayList(int initialCapacity) {
            if (initialCapacity > 0) {
                this.elementData = new Object[initialCapacity];
            } else if (initialCapacity == 0) {
                this.elementData = EMPTY_ELEMENTDATA;
            } else {
                throw new IllegalArgumentException("Illegal Capacity: "+
                                                   initialCapacity);
            }
        }
        /*
        *空的构造方法
        */
         public ArrayList() {
            this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
        }
        /*
        *将其他Collection转化为ArrayList的构造方法
        */
         public ArrayList(Collection<? extends E> c) {
            elementData = c.toArray();
            if ((size = elementData.length) != 0) {
                if (elementData.getClass() != Object[].class)
                    elementData = Arrays.copyOf(elementData, size, Object[].class);
            } else {
                this.elementData = EMPTY_ELEMENTDATA;
            }
        } 
    
    增删改查的方法：
        /*
        *查找方法
        */
        public E get(int index) {
            //检查index是否非法
            rangeCheck(index);
            return elementData(index);
        }
        /*
        *更新方法
        */
         public E set(int index, E element) {
            rangeCheck(index);
    
            E oldValue = elementData(index);
            elementData[index] = element;
            return oldValue;
        }
        //如果index非法抛出异常
        private void rangeCheck(int index) {
            if (index >= size)
                throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        }
        //获取指定index的元素
         @SuppressWarnings("unchecked")
        E elementData(int index) {
            return (E) elementData[index];
        }
        /*
        *添加方法
        */
         public boolean add(E e) {
             //检查容量是否够
            ensureCapacityInternal(size + 1);  
            elementData[size++] = e;
            return true;
        }
        /*
        *下面这些是首先检查是不是空数组添加元素，如果空数组添加元素，那么初始这个数组长度为默认值
        *如果并不是空数组，先检查扩容后会不会超过最大容量，如果没有那么进行扩容1.5倍
        */
        private void ensureCapacityInternal(int minCapacity) {
            ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
        }
        private static int calculateCapacity(Object[] elementData, int minCapacity) {
            //判断是不是空数组
             if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
                return Math.max(DEFAULT_CAPACITY, minCapacity);
            }
            return minCapacity;
        }
    
        private void ensureExplicitCapacity(int minCapacity) {
            modCount++;
    
            // overflow-conscious code
            if (minCapacity - elementData.length > 0)
                grow(minCapacity);
        }
        //扩容函数
         private void grow(int minCapacity) {
            // overflow-conscious code
            int oldCapacity = elementData.length;
            int newCapacity = oldCapacity + (oldCapacity >> 1);
            if (newCapacity - minCapacity < 0)
                newCapacity = minCapacity;
            if (newCapacity - MAX_ARRAY_SIZE > 0)
                newCapacity = hugeCapacity(minCapacity);
            // minCapacity is usually close to size, so this is a win:
            elementData = Arrays.copyOf(elementData, newCapacity);
        }
        //检测扩容后会不会超过最大值
        private static int hugeCapacity(int minCapacity) {
            if (minCapacity < 0) // overflow
                throw new OutOfMemoryError();
            return (minCapacity > MAX_ARRAY_SIZE) ?
                Integer.MAX_VALUE :
                MAX_ARRAY_SIZE;
        }
        
        /*
        *删除函数（通过index删除）
        *然后数组数组整体左移（这里进行了一个是不是尾元素判断）
        */
         public E remove(int index) {
             //检查待删除下标是否合法
            rangeCheck(index);
            modCount++;
            //获取待删除的元素
            E oldValue = elementData(index);
            int numMoved = size - index - 1;
            if (numMoved > 0)
                System.arraycopy(elementData, index+1, elementData, index,
                                 numMoved);
            elementData[--size] = null; // clear to let GC do its work
            return oldValue;
        }
        /*
        *删除函数（通过对象来删除）
        *查找到object对应的index
        *下面的函数主要是通过fastRemove()来删除的
        */
          public boolean remove(Object o) {
            if (o == null) {
                for (int index = 0; index < size; index++)
                    if (elementData[index] == null) {
                        fastRemove(index);
                        return true;
                    }
            } else {
                for (int index = 0; index < size; index++)
                    if (o.equals(elementData[index])) {
                        fastRemove(index);
                        return true;
                    }
            }
            return false;
        }
        //真正执行删除的函数，与通过index删除的index相同
        private void fastRemove(int index) {
            modCount++;
            int numMoved = size - index - 1;
            if (numMoved > 0)
                System.arraycopy(elementData, index+1, elementData, index,
                                 numMoved);
            elementData[--size] = null; // clear to let GC do its work
        }
        
        /*
        *删除范围
        */
          protected void removeRange(int fromIndex, int toIndex) {
            modCount++;
            int numMoved = size - toIndex;
            System.arraycopy(elementData, toIndex, elementData, fromIndex,
                             numMoved);
    
            // clear to let GC do its work
            int newSize = size - (toIndex-fromIndex);
            for (int i = newSize; i < size; i++) {
                elementData[i] = null;
            }
            size = newSize;
        }