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)));

  }

}
-----------------------------------