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

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

1顺序表新增

/**
 * 顺序表
 *
 * @author cjd
 *
 */
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;
  }
}

方法

/**
   * 单链表表
   *
   * @author cjd
   *
   */
  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<i;j++){
        p=p.next;
      }

      return p.data;
    }

    // 将数据元素 e 插入到单链表中 i 号位置
    public void add(int i, Object e) {

      //遍历结点
      Node p=head;//找到前一个结点，从head结点开始
      for(int j=0;j<i;j++){
        p=p.next;//移动指针到下一个结点
      }

      //新创建一个结点
      Node newNode = new Node();
      newNode.data=e;
      newNode.next=p.next;

      p.next=newNode;//指明新结点的直接后继结点

      // 个数+1
      size++;

    }

    // 将数据元素 e 插入到单链表末尾
    public void add(Object e) {
      this.add(size,e);//最后位新增
    }

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

      Node p=head.next;//找到前一个结点，从head结点开始
      StringBuilder stringBuilder= new StringBuilder("[");
      for (int i = 0; i < size; i++) {
        if (i == 0)
          stringBuilder.append("" + p.data);
        else
          stringBuilder.append("," + p.data);

        //移动指针到下一个结点
        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("实现单链表新增"+singlist.toString());

  }
}

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