线性表的顺序存储与实现

线性表的顺序存储就是使用一组地址连续的存储空间来依次存储线性表中元素以数据元素在计算机内存的地址相邻性表示数据元素之间的关系在，Java中可以使用数组来存储线性表中的数据元素, 数组就是一块连续的存储空间。

插入元素

删除元素

具体代码实现

/**
 * 通过数组实现线性表
 * @author 北京乐学网老崔
 */
public class MyArrayList implements MyList {
	private Object [] elements;		//定义数组保存数据元素
	private static final int DEFAULT_CAPACITY = 16; 	//数组的默认初始化容量
	private int size;			//保存数据元素的个数
	
	//构造方法
	public MyArrayList() {
		elements = new Object[DEFAULT_CAPACITY];
	}
	public MyArrayList(int initialCapacity) {
		elements = new Object[initialCapacity];
	}
	
	
	// 返回元素的个数
	@Override
	public int getSize() {
		return size;
	}

	@Override
	public boolean isEmpty() {
		// 判断线性表是否为空
		return size == 0 ;
	}

	// 在线性表的i位置插入元素e
	@Override
	public void insert(int i, Object e) {
		//判断索引值i是否越界
		if ( i < 0 || i > size ) {
			throw new IndexOutOfBoundsException(i+"越界");
		}
		//如果数组已满 , 对数组扩容
		if ( size >= elements.length) {
			expandSpace(); 		//数组扩容
		}
		//从i开始,把元素依次后移
		for( int j = size ; j > i ; j--	) {
			elements[j] = elements[j-1];					
		}		
		//把元素e存储到i位置
		elements[i] = e;
		//元素的个数增1
		size++;
	}

	// 数组扩容
	private void expandSpace() {
		//定义一个更大的数组, 默认按2倍大小扩容
		Object[] newElements = new Object[elements.length* 2]; 
		//把原来数据的内容复制到新的数组中
		for( int i = 0 ; i<elements.length; i++) {
			newElements[i] = elements[i];
		}
		//让原来的数组名指向新的数组
		elements = newElements;
	}
	
	// 判断当前线性表中是否包含元素e
	@Override
	public boolean contains(Object e) {
		return indexOf(e) >= 0 ;
	}

	// 返回元素e在线性表中的第一次出现的索引值, 如果不存在返回-1
	@Override
	public int indexOf(Object e) {
		//遍历数组
		if (e == null) {
			//线性表中,用户可能添加null
			for(int i = 0 ; i < size ; i++) {
				if (elements[i] == null) {
					return i;
				}
			}
		}else {
			for(int i = 0 ; i < size ; i++) {
				if (e.equals(elements[i])) {
					return i;
				}
			}
		}
		return -1;
	}

	// 在线性表中删除第一个与e相同的元素
	@Override
	public Object remove(Object e) {
		//获得e在线性表中的索引值
		int index = indexOf(e);
		if ( index < 0 ) {
			return null; 		//线性表中不存在元素e
		}
		return remove(index);
	}

	// 删除指定索引值的元素
	@Override
	public Object remove(int i) {
		//判断i是否越界
		if ( i < 0 || i >= size) {
			throw new IndexOutOfBoundsException(i+"越界");
		}
		//把要删除的元素保存起来
		Object old = elements[i]; 
		//把i+1开始的元素依次前移
		for(int j = i; j<size-1; j++) {
			elements[j] = elements[j+1];
		}
		//把最后的元素置 为null
		elements[size-1] = null;
		//修改元素的个数
		size--;
		//把删除的元素返回
		return old;
	}

	// 把索引值为i的元素替换为e
	@Override
	public Object replace(int i, Object e) {
		//判断索引值是否越界
		if ( i < 0 || i >= size) {
			throw new IndexOutOfBoundsException(i+"越界");
		}
		Object old = elements[i]; 		//保存原来 的值
		//替换
		elements[i] = e;
		//把原来的元素值返回
		return old;
	}

	// 返回指定位置的元素
	@Override
	public Object get(int i) {
		// 判断索引值是否越界
		if (i < 0 || i >= size) {
			throw new IndexOutOfBoundsException(i + "越界");
		}
		return elements[i];
	}

	// 在指定的元素前插入一个元素
	@Override
	public boolean insertBefore(Object p, Object e) {
		//确定元素p在线性表中的位置
		int index = indexOf(p);
		if ( index < 0 ) {
			return false; 		//p元素不存在, 插入不成功
		}
		//插入元素
		insert(index, e);
		return true;
	}
	// 在指定的元素后插入一个元素
	@Override
	public boolean insertAfter(Object p, Object e) {
		// 确定元素p在线性表中的位置
		int index = indexOf(p);
		if (index < 0) {
			return false; 	// p元素不存在, 插入不成功
		}
		// 插入元素
		insert(index+1, e);
		return true;
	}

	//重写toString()
	@Override
	public String toString() {
		// 把线性表中每个元素连接起来, 遍历数组中已添加的元素
		StringBuilder sb = new StringBuilder();
		sb.append("[");
		for( int i = 0 ;  i<size ; i++ ) {
			sb.append(elements[i] );
			//数据之间使用逗号分隔
			if (i < size - 1) {
				sb.append(",");
			}
		}
		
		sb.append("]");		
		return sb.toString();
	}
}

/**
 * 测试MyArrayList
 * @author 北京乐学网老崔
 */
public class MyArrayListTest {

	public static void main(String[] args) {
		// 1) 创建一个MyArrayList对象
		MyArrayList list1 = new MyArrayList();
		
		//2) 判断是否为空
		System.out.println( list1.isEmpty() );	//true
		System.out.println( list1.getSize());	//0
		
		//3)添加元素
		list1.insert(0, "aa");
		list1.insert(1, "bb");
		list1.insert(0, "cc");
		System.out.println( list1.isEmpty() );	//false
		System.out.println( list1.getSize());	//3
		
		//4) 把线性表中的内容打印输出
		System.out.println( list1 ); //[cc,aa,bb]
		
		//5) 判断是否存在
		System.out.println( list1.indexOf("cc"));	//0
		System.out.println( list1.indexOf("bb"));	//2
		System.out.println( list1.indexOf("dd"));	//-1
		System.out.println( list1.contains("aa"));	//true
		System.out.println( list1.contains("xx"));	//false
		
		//6)删除
		list1.remove("dd");				//删除不存在的元素,
		System.out.println(list1 );		//[cc,aa,bb]
		list1.remove("bb");
		System.out.println(list1 );		//[cc,aa]
		list1.remove(0);
		System.out.println(list1 );		//[aa]
		
		//7)替换
		list1.insert(0, "xx");
		list1.insert(0, "oo");
		list1.insert(0, "yy");
		System.out.println( list1 ); 		//[yy,oo,xx,aa]
		list1.replace(0, "YY");
		System.out.println( list1 ); 	 	//[YY,oo,xx,aa]
		
		//8)返回指定索引的元素
		System.out.println( list1.get(0));	//YY
		System.out.println( list1.get(1));	//oo
//		System.out.println( list1.get(33));	//java.lang.IndexOutOfBoundsException: 33越界
		
		//9)在指定元素的前面/后面插入另外的元素
		list1.insertBefore("oo", "JJ");
		System.out.println( list1 );
		list1.insertAfter("oo", "jj");
		System.out.println( list1 );
		list1.insertAfter("TT", "BB");
		System.out.println( list1 );
	}
	

}

顺序存储的特点

优点:

顺序存储是使用数组实现的, 数组可以通过索引值快速访问每个元素。

缺点:

在插入/删除元素时, 需要移动大量的元素。

当线性表长度变化较大时, 很难确定存储空间的容量。

应用场景:

适合存储的元素,插入/删除操作比较少, 主要是查询操作。