線(xiàn)性表的順序存儲(chǔ)與實(shí)現(xiàn)

線(xiàn)性表的順序存儲(chǔ)就是使用一組地址連續(xù)的存儲(chǔ)空間來(lái)依次存儲(chǔ)線(xiàn)性表中元素以數(shù)據(jù)元素在計(jì)算機(jī)內(nèi)存的地址相鄰性表示數(shù)據(jù)元素之間的關(guān)系在，Java中可以使用數(shù)組來(lái)存儲(chǔ)線(xiàn)性表中的數(shù)據(jù)元素, 數(shù)組就是一塊連續(xù)的存儲(chǔ)空間。

插入元素

刪除元素

具體代碼實(shí)現(xiàn)

/**
 * 通過(guò)數(shù)組實(shí)現(xiàn)線(xiàn)性表
 * @author 北京動(dòng)力節(jié)點(diǎn)老崔
 */
public class MyArrayList implements MyList {
	private Object [] elements;		//定義數(shù)組保存數(shù)據(jù)元素
	private static final int DEFAULT_CAPACITY = 16; 	//數(shù)組的默認(rèn)初始化容量
	private int size;			//保存數(shù)據(jù)元素的個(gè)數(shù)
	
	//構(gòu)造方法
	public MyArrayList() {
		elements = new Object[DEFAULT_CAPACITY];
	}
	public MyArrayList(int initialCapacity) {
		elements = new Object[initialCapacity];
	}
	
	
	// 返回元素的個(gè)數(shù)
	@Override
	public int getSize() {
		return size;
	}

	@Override
	public boolean isEmpty() {
		// 判斷線(xiàn)性表是否為空
		return size == 0 ;
	}

	// 在線(xiàn)性表的i位置插入元素e
	@Override
	public void insert(int i, Object e) {
		//判斷索引值i是否越界
		if ( i < 0 || i > size ) {
			throw new IndexOutOfBoundsException(i+"越界");
		}
		//如果數(shù)組已滿(mǎn) , 對(duì)數(shù)組擴(kuò)容
		if ( size >= elements.length) {
			expandSpace(); 		//數(shù)組擴(kuò)容
		}
		//從i開(kāi)始,把元素依次后移
		for( int j = size ; j > i ; j--	) {
			elements[j] = elements[j-1];					
		}		
		//把元素e存儲(chǔ)到i位置
		elements[i] = e;
		//元素的個(gè)數(shù)增1
		size++;
	}

	// 數(shù)組擴(kuò)容
	private void expandSpace() {
		//定義一個(gè)更大的數(shù)組, 默認(rèn)按2倍大小擴(kuò)容
		Object[] newElements = new Object[elements.length* 2]; 
		//把原來(lái)數(shù)據(jù)的內(nèi)容復(fù)制到新的數(shù)組中
		for( int i = 0 ; i<elements.length; i++) {
			newElements[i] = elements[i];
		}
		//讓原來(lái)的數(shù)組名指向新的數(shù)組
		elements = newElements;
	}
	
	// 判斷當(dāng)前線(xiàn)性表中是否包含元素e
	@Override
	public boolean contains(Object e) {
		return indexOf(e) >= 0 ;
	}

	// 返回元素e在線(xiàn)性表中的第一次出現(xiàn)的索引值, 如果不存在返回-1
	@Override
	public int indexOf(Object e) {
		//遍歷數(shù)組
		if (e == null) {
			//線(xiàn)性表中,用戶(hù)可能添加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;
	}

	// 在線(xiàn)性表中刪除第一個(gè)與e相同的元素
	@Override
	public Object remove(Object e) {
		//獲得e在線(xiàn)性表中的索引值
		int index = indexOf(e);
		if ( index < 0 ) {
			return null; 		//線(xiàn)性表中不存在元素e
		}
		return remove(index);
	}

	// 刪除指定索引值的元素
	@Override
	public Object remove(int i) {
		//判斷i是否越界
		if ( i < 0 || i >= size) {
			throw new IndexOutOfBoundsException(i+"越界");
		}
		//把要?jiǎng)h除的元素保存起來(lái)
		Object old = elements[i]; 
		//把i+1開(kāi)始的元素依次前移
		for(int j = i; j<size-1; j++) {
			elements[j] = elements[j+1];
		}
		//把最后的元素置 為null
		elements[size-1] = null;
		//修改元素的個(gè)數(shù)
		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]; 		//保存原來(lái) 的值
		//替換
		elements[i] = e;
		//把原來(lái)的元素值返回
		return old;
	}

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

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

	//重寫(xiě)toString()
	@Override
	public String toString() {
		// 把線(xiàn)性表中每個(gè)元素連接起來(lái), 遍歷數(shù)組中已添加的元素
		StringBuilder sb = new StringBuilder();
		sb.append("[");
		for( int i = 0 ;  i<size ; i++ ) {
			sb.append(elements[i] );
			//數(shù)據(jù)之間使用逗號(hào)分隔
			if (i < size - 1) {
				sb.append(",");
			}
		}
		
		sb.append("]");		
		return sb.toString();
	}
}

/**
 * 測(cè)試MyArrayList
 * @author 北京動(dòng)力節(jié)點(diǎn)老崔
 */
public class MyArrayListTest {

	public static void main(String[] args) {
		// 1) 創(chuàng)建一個(gè)MyArrayList對(duì)象
		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) 把線(xiàn)性表中的內(nèi)容打印輸出
		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 );
	}
	

}

順序存儲(chǔ)的特點(diǎn)

優(yōu)點(diǎn):

順序存儲(chǔ)是使用數(shù)組實(shí)現(xiàn)的, 數(shù)組可以通過(guò)索引值快速訪問(wèn)每個(gè)元素。