数据结构－用二维数组构造列表

package com.data.struct;

/**
 * 二位数组实现列表
 * 第一行表示next
 * 第二行表示value
 * 第三行表示prev
 * @author Administrator
 *
 */
public class ArrayNodeList {
	private int[][]storage;
	private int head;
	private int free;
	
	public ArrayNodeList(int size){
		storage=new int[3][size];
		head=-1;
		free=0;
		for(int i=0;i<size-1;i++){
			storage[0][i]=i+1;
		}
		storage[0][size-1]=-1;
		
	}
	/**
	 * 获取某个位置的值
	 * @param index
	 * @return
	 */
	public int getValue(int index){
		return storage[1][index];
	}
	/**
	 * 分配内存
	 * @return
	 * @throws Exception
	 */
	private int locateObject()throws Exception{
		if(free==-1){
			throw new Exception("out of space");
		}else{
			int x=free;
			free=storage[0][free];
			return x;
		}
		
	}
	/**
	 * 释放内存
	 * @param x
	 */
	private void freeObject(int x){
		storage[0][x]=free;
		free=x;
	}
	/**
	 * 打印
	 */
	public void print(){
		int x=head;
		while(x!=-1){
			System.out.print(storage[1][x]+" ");
			x=storage[0][x];
		}
		System.out.println();
	}
	/**
	 * 搜索值为k的为位置
	 * @param k
	 * @return
	 */
	public int search(int k){
		int x=head;
		while(x!=-1&&storage[1][x]!=k){
			x=storage[0][x];
		}
		return x;
	}
	/**
	 * 插入值为value的数据
	 * @param value
	 * @throws Exception
	 */
	public void insert(int value)throws Exception{
		int x=locateObject();
		storage[0][x]=head;
		storage[1][x]=value;
		storage[2][x]=-1;
		if(head!=-1){
			storage[2][head]=x;
		}
		head=x;
	}
	/**
	 * 删除位置为index的数据
	 * @param index
	 * @throws Exception
	 */
	public void delete(int index)throws Exception{
		if(storage[2][index]!=-1){
			storage[0][storage[2][index]]=storage[0][index];
		}else{
			head=storage[0][index];
		}
		if(storage[0][index]!=-1){
			storage[2][storage[0][index]]=storage[2][index];
		}
		freeObject(index);
	}
	public static void main(String[] args)throws Exception {
		ArrayNodeList list=new ArrayNodeList(10);
		list.print();
		list.insert(10);
		list.insert(20);
		list.print();
		list.delete(1);
		list.print();
		list.insert(30);
		list.insert(40);
		list.print();
		//list.delete(2);
		//list.print();
		System.out.println(list.getValue(list.search(30)));

	}

}