arraylist.java

java 实现常用数据结构（链表

/**
 *
 *
 *
 */
 
 package dreamer.util;
 
 public class ArrayList<T> implements List<T>
 {
 	private static final int INIT_SIZE = 1024;
 	private static final int INCREMENT = 256;
 	private Object [] list;
 	private int size;
 	private int len;
 	
 	public ArrayList()
 	{
 		list = new Object[INIT_SIZE];
 		size = INIT_SIZE;
 		len = 0;
 	}
 	
 	private void extend()
 	{
 		Object [] tmpList = new Object[size+INCREMENT];
 		for(int i=0;i<len;i++)
 		{
 			tmpList[i] = list[i];
 		}
 		list = tmpList;
 	}
 	
 	public boolean add(T elem)
 	{
 		if(len>=size)
 			extend();
 		list[len] = elem;
 		len++;
 		return true;
 	}
 	
 	public void add(int index,T elem)throws IndexSlopOverException
 	{
 		if(index<0 || index>=len)
 			throw new IndexSlopOverException();
 		if(len>=size)
 			extend();
 		for(int i=len-1;i>=index;i--)
 		{
 			list[i+1] = list[i];
 		}
 		list[index] = elem;
 		len++;
 	}
 	
 	public T remove(int index)throws IndexSlopOverException
 	{
 		if(index<0 || index>=len)
 			throw new IndexSlopOverException();
 		T elem = (T)list[index];
 		for(int i=index+1;i<len;i++)
 		{
 			list[i-1] = list[i];
 		}
 		len--;
 		return elem;
 	}
 	
 	public boolean remove(T elem)throws IndexSlopOverException
 	{
 		if(len==0)
 			throw new IndexSlopOverException();
 		int i = 0;
 		final int LIST_LENGTH = len;
 		while(i<len)
 		{
 			if(list[i].equals(elem))
 			{
 				for(int j=i+1;j<len;j++)
 				{
 					list[j-1] = list[j];
 				}
 				len--; 				
 			}
 			else
 				i++;
 		}
 		if(len == LIST_LENGTH)
 			return false;
 		return true;
 	}
 	
 	public void set(int index,T elem)throws IndexSlopOverException
 	{
 		if(index<0 || index>=len)
 			throw new IndexSlopOverException();
 		list[index] = elem;
 	}
 	
 	public T get(int index)throws IndexSlopOverException
 	{
 		if(index<0 || index>=len)
 			throw new IndexSlopOverException();
 		T elem = (T)list[index];
 		return elem;
 	}
 	
 	public boolean contains(T elem)
 	{
 		if(indexOf(elem)==-1)
 			return false;
 		return true;
 	}
 	
 	public int indexOf(T elem)
 	{
 		for(int i=0;i<len;i++)
 		{
 			if(list[i].equals(elem))
 				return i;
 		}
 		return -1;
 	}
 	
 	public int size()
 	{
 		return len;
 	}
 	
 	public Object [] toArray()
 	{
 		if(len==0)
 			return null;
 		Object [] array = new Object[len];
 		for(int i=0;i<len;i++)
 		{
 			array[i] = list[i];
 		}
 		return array;
 	}
 	
 	public boolean isEmpty()
 	{
 		if(len==0)
 			return true;
 		return false;
 	}
 	
 	public void clear()
 	{
 		list = new Object[INIT_SIZE];
 		size = INIT_SIZE;
 		len = 0;
 	}
 }