線性表的順序存儲與實現

線性表的順序存儲就是使用一組地址連續的存儲空間來依次存儲線性表中元素以數據元素在計算機內存的地址相鄰性表示數據元素之間的關系在，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 );
	}
	

}

順序存儲的特點

優點:

順序存儲是使用數組實現的, 數組可以通過索引值快速訪問每個元素。

缺點:

在插入/刪除元素時, 需要移動大量的元素。

當線性表長度變化較大時, 很難確定存儲空間的容量。

應用場景:

適合存儲的元素,插入/刪除操作比較少, 主要是查詢操作。