JAVA模擬新增順序表及單鏈表

更新時(shí)間：2020年07月09日 09:05:06 作者：咔咔kk

這篇文章主要介紹了JAVA模擬新增順序表及單鏈表,文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下

最近在回顧大學(xué)學(xué)的數(shù)據(jù)結(jié)構(gòu)，這里給大家用java模擬順序表和單鏈表的新增

1順序表新增

/**
 * 順序表
 * 
 * @author cjd
 *
 */
public class ArrayList {
  private Object[] elementData; // 底層是一個(gè)數(shù)組，目前還沒(méi)有確定長(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();
  }

}

測(cè)試mian

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

2單鏈表新增

實(shí)體類

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

  }

測(cè)試類

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

以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章: