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

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

}

// 将数据元素 exOpMve 插入到线性表中 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]=elxOpMveementData[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

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

}

}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。