java線性表之順序表實現，java線性順序實現

java線性表之順序表實現，java線性順序實現

仿照arrayList寫了一個簡化版的線性表,主要為了用來研究arrayList在實現什麼操作的情況下比較節省性能,樓主文采很差,直接上代碼.

import java.util.Arrays;

public class SequenceList<T> {
	private final int DEFAULT_SIZE = 16;
	// 保存數組的長度
	private int capacity;
	// 定義一個數組用於保存順序線性表的元素
	private Object[] elementData;
	// 保存順序表中元素的當前個數
	private int size = 0;

	// 以默認數組長度創建空順序線性表
	public SequenceList() {
		capacity = DEFAULT_SIZE;
		elementData = new Object[capacity];
	}

	// 以一個初始化元素創建順序線性表
	public SequenceList(T element) {
		this();
		elementData[0] = element;
		size++;
	}

	/**
	 * 以指定長度的數組來創建順序線性表
	 * 
	 * @param element
	 *            指定順序線性表中第一個元素
	 * @param initSize
	 *            指定順序線性表底層數組的長度
	 */
	public SequenceList(T element, int initSize) {
		capacity = 1;
		// 把capacity設為大於initSize的最小的2的n次方
		while (capacity < initSize) {
			capacity <<= 1;
		}
		elementData = new Object[capacity];
		elementData[0] = element;
		size++;
	}

	// 獲取順序線性表的大小
	public int length() {
		return size;
	}

	// 獲取順序線性表中索引為i處的元素
	public T get(int i) {
		if (i < 0 || i > size - 1) {
			throw new IndexOutOfBoundsException("線性表索引越界");
		}
		return (T) elementData[i];
	}

	// 查找順序線性表中指定元素的索引
	public int locate(T element) {
		for (int i = 0; i < size; i++) {
			if (elementData[i].equals(element)) {
				return i;
			}
		}
		return -1;
	}

	// 向順序線性表的指定位置插入一個元素
	public void insert(T element, int index) {
		if (index < 0 || index > size) {
			throw new IndexOutOfBoundsException("線性表索引越界");
		}
		ensureCapacity(size + 1);
		// 將指定索引處之後的所有元素向後移動一格
		System.arraycopy(elementData, index, elementData, index + 1, size - index);
		elementData[index] = element;
		size++;
	}

	// 在線性順序表的開始處添加一個元素
	public void add(T element) {
		insert(element, size);
	}

	// 很麻煩，而且性能很差
	private void ensureCapacity(int minCapacity) {
		// 如果數組的原有長度小於目前所需的長度
		if (minCapacity > capacity) {
			// 不斷地將capacity * 2，直到capacity大於minCapacity
			while (capacity < minCapacity) {
				capacity <<= 1;
			}
			elementData = Arrays.copyOf(elementData, capacity);
		}
	}

	// 刪除順序線性表中指定索引處的元素
	public T delete(int index) {
		if (index < 0 || index > size - 1) {
			throw new IndexOutOfBoundsException("線性表索引越界");
		}
		T oldValue = (T) elementData[index];
		int numMoved = size - index - 1;
		if (numMoved > 0) {
			System.arraycopy(elementData, index + 1, elementData, index, numMoved);
		}
		// 清空最後一個元素
		elementData[--size] = null;
		return oldValue;
	}

	// 刪除順序線性表中最後一個元素
	public T remove() {
		return delete(size - 1);
	}

	// 判斷順序線性表是否為空表
	public boolean empty() {
		return size == 0;
	}

	// 清空線性表
	public void clear() {
		// 將底層數組所有元素賦為null
		Arrays.fill(elementData, null);
		size = 0;
	}

	public String toString() {
		if (size == 0) {
			return "[]";
		} else {
			StringBuilder sb = new StringBuilder("[");
			for (int i = 0; i < size; i++) {
				sb.append(elementData[i].toString() + ", ");
			}
			int len = sb.length();
			return sb.delete(len - 2, len).append("]").toString();
		}
	}
}

順序表使用數組儲存數據,所以對於隨機的訪問有很好的性能支持,不管是訪問線性表上的哪一個元素都可以直接使用elementData[i]直接得到,但是對於添加元素會很消耗性能,主要是在隨機插入元素的時候可能要將後面的元素整體向後移一位,還有數組長度不夠的時候需要創建原數組2倍的新數組然後將數據整體搬家到新數組,然後釋放掉原數組這兩點上非常消耗性能,所以arrayList的使用通常是沒有復雜的插入操作,更多的是對數據的取操作,而LinkedList(鏈表)在這些使用的性能方面正好相反.