/**
 * 順序表
 * 
 * @author cjd
 *
 */
public class ArrayList {
  private Object[] elementData; // 底層是一個(gè)數(shù)組，目前還沒有確定長(zhǎng)度

  private int size; // 不是數(shù)組分配了幾個(gè)空間，而是元素的個(gè)數(shù)

  public ArrayList() {
    this(4);
  }

  public ArrayList(int initialCapacity) {
    elementData = new Object[initialCapacity];
  }

  // 返回線性表的大小，即數(shù)據(jù)元素的個(gè)數(shù)。
  public int size() {
    return size;
  }

  // 返回線性表中序號(hào)為 i 的數(shù)據(jù)元素@Override
  public Object get(int i) {
    return elementData[i];
  }

  // 將數(shù)據(jù)元素 e 插入到線性表中 i 號(hào)位置
  public void add(int i, Object e) {
    // 擴(kuò)容 elementData = Arrays.copyOf(elementData, elementData.length*2);
    if (size == elementData.length) {//數(shù)組滿了，就擴(kuò)容
      Object[] elementDatanew = new Object[elementData.length * 2];//新創(chuàng)建一個(gè)新的數(shù)組，長(zhǎng)度是舊數(shù)組2倍
      for (int j = 0; j < elementData.length; j++) {
        elementDatanew[j] = elementData[j];//將舊數(shù)組的數(shù)據(jù)拷貝到新數(shù)組
      }
      elementData = elementDatanew;//讓elementData指向新數(shù)組
    }
    
    //最后位后移
    for(int j=size;j>i;j--){
      elementData[j]=elementData[j-1];
    }
    
    // 給數(shù)組賦值
    elementData[i] = e;
    // 元素個(gè)數(shù)+1
    size++;

  }

  // 將數(shù)據(jù)元素 e 插入到線性表末尾
  public void add(Object e) {
    this.add(size,e);//最后位新增
    

  }

  

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

}

public class test {
  public static void main(String[] args) {
    ArrayList list=new ArrayList();
    list.add(1);
    list.add(2);
    list.add(3);
    list.add(4);
    list.add(5);
    list.add(6);
    list.add(3,9);
    System.out.println("實(shí)現(xiàn)順序表新增"+list.toString());
  }
}

public class Node {
  Object data;//要存儲(chǔ)的數(shù)據(jù)
  Node next;
  public Node(Object data, Node next) {
    super();
    this.data = data;
  }
  public Node() {
    super();
  }
  public Object getData() {
    return data;
  }
  public void setData(Object data) {
    this.data = data;
  }
  public Node getNext() {
    return next;
  }
  public void setNext(Node next) {
    this.next = next;
  }
}

/**
   * 單鏈表表
   * 
   * @author cjd
   *
   */
  public class SingleLinkedList {
    private Node head = new Node();//頭結(jié)點(diǎn)，不存儲(chǔ)數(shù)據(jù)，為了編程方便
    private int size;//一共有幾個(gè)結(jié)點(diǎn)

    
    // 表的大小，即數(shù)據(jù)元素的個(gè)數(shù)。
    public int size() {
      return size;
    }

    // 返回單鏈表中序號(hào)為 i 的數(shù)據(jù)元素
    public Object get(int i) {
      //遍歷結(jié)點(diǎn)
      Node p=head;//找到前一個(gè)結(jié)點(diǎn)，從head結(jié)點(diǎn)開始
      for(int j=0;j<i;j++){
        p=p.next;
      }
      
      return p.data;
    }

    // 將數(shù)據(jù)元素 e 插入到單鏈表中 i 號(hào)位置
    public void add(int i, Object e) {
      
      //遍歷結(jié)點(diǎn)
      Node p=head;//找到前一個(gè)結(jié)點(diǎn)，從head結(jié)點(diǎn)開始
      for(int j=0;j<i;j++){
        p=p.next;//移動(dòng)指針到下一個(gè)結(jié)點(diǎn)
      }
      
      //新創(chuàng)建一個(gè)結(jié)點(diǎn)
      Node newNode = new Node();
      newNode.data=e;
      newNode.next=p.next;
      
      p.next=newNode;//指明新結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)
      
      // 個(gè)數(shù)+1
      size++;

    }

    // 將數(shù)據(jù)元素 e 插入到單鏈表末尾
    public void add(Object e) {
      this.add(size,e);//最后位新增
    }

    

    public String toString() {
      if (size == 0) {
        return "[]";
      }

      Node p=head.next;//找到前一個(gè)結(jié)點(diǎn)，從head結(jié)點(diǎn)開始
      StringBuilder stringBuilder= new StringBuilder("[");
      for (int i = 0; i < size; i++) {
        if (i == 0)
          stringBuilder.append("" + p.data);
        else
          stringBuilder.append("," + p.data);
        
        //移動(dòng)指針到下一個(gè)結(jié)點(diǎn)
        p=p.next;
      }
      stringBuilder.append("]");
      return stringBuilder.toString();
    }

  }

public class test {
  public static void main(String[] args) {
  
    
    SingleLinkedList singlist=new SingleLinkedList();
    singlist.add(1);
    singlist.add(2);
    singlist.add(3);
    singlist.add(4);
    singlist.add(5);
    singlist.add(6);
    singlist.add(3,9);
    System.out.println("實(shí)現(xiàn)單鏈表新增"+singlist.toString());
    
    
  }
}