JAVA模拟新增顺序表及单链表

最近在回顾大学学的数据结构，这里给大家用java模拟顺序表和单链表的新增

1顺序表新增

public class ArrayList {
  private Object[] elementData; // 底层是一个数组，目前还没有确定长度

  private int size; // 不是数组分配了几个空间，而是元素的个数

  public ArrayList() {
    this(4);
  }

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

  // 返回线性表的大小，即数据元素的个数。
  public int size() {
    return size;
  }

  // 返回线性表中序号为 i 的数据元素@Override
  public Object get(int i) {
    return elementData[i];
  }

  // 将数据元素 e 插入到线性表中 i 号位置
  public void add(int i, Object e) {
    // 扩容 elementData = Arrays.copyOf(elementData, elementData.length*2);
    if (size == elementData.length) {//数组满了，就扩容
      Object[] elementDatanew = new Object[elementData.length * 2];//新创建一个新的数组，长度是旧数组2倍
      for (int j = 0; j < elementData.length; j++) {
 elementDatanew[j] = elementData[j];//将旧数组的数据拷贝到新数组
      }
      elementData = elementDatanew;//让elementData指向新数组
    }
    
    //最后位后移
    for(int j=size;j>i;j--){
      elementData[j]=elementData[j-1];
    }
    
    // 给数组赋值
    elementData[i] = e;
    // 元素个数+1
    size++;

  }

  // 将数据元素 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();
  }

}

测试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("实现顺序表新增"+list.toString());
  }
}

2单链表新增

实体类

public class Node {
  Object data;//要存储的数据
  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;
  }
}

方法

  public class SinglelinkedList {
    private Node head = new Node();//头结点，不存储数据，为了编程方便
    private int size;//一共有几个结点

    
    // 表的大小，即数据元素的个数。
    public int size() {
      return size;
    }

    // 返回单链表中序号为 i 的数据元素
    public Object get(int i) {
      //遍历结点
      Node p=head;//找到前一个结点，从head结点开始
      for(int j=0;j

测试类

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("实现单链表新增"+singlist.toString());
    
    
  }
}

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持考高分网。