眨眼间，我们就上到了数据结构，从数组到队列，数据结构中的基本内容也快讲完，在数组的学习中，我们首先是学习ArrayList做了一个简单的长度可变的数组，利用两个数组中的交换数据做到了每次增量为1的可变数组，然而和ArrayList相比较，我们的可变数组的计算速度耗时过长，为了将数组的时间缩短，提高数组的效率，我们设置了增量，初始容量和数量，每次数组中放入数据超过数组本身的容量是就自动扩容一定的增量，让数组节约了每次开辟内存空间的时间，提高效率，代码如下：
简单长度可变数组
public class MyList<E> {
// 定义一个初始长度为0的数组来存放数据
private Object[] src = new Object[0];
// 添加数据 Element
public void add(E s) {
// 定义一个新数组，长度是原始数组长度+1
Object[] dest = new Object[src.length + 1];
// 将原数组的值拷贝到新数组中
for(int i=0;i<src.length;i++){
dest[i]=src[i];
}
// 将新数组放到dest数组的最后一个位置
dest[src.length] = s;
// 将dest赋值给src
src = dest;
}
// 根据下标取出数据
public E get(int index) {
return (E)src[index];
}
// 将指定位置的数据修改为指定的值
public void modify(int index, E s) {
src[index] = s;
}
// 删除指定位置的数据
public void delete(int index) {
// 如果下标参数不合法，就抛出一个越界的异常对象
if (index < 0 || index >= src.length) {
// 创建异常对象
IndexOutOfBoundsException ex = new IndexOutOfBoundsException(
"下标越界！index:" + index + ",size：" + size());
// 抛出异常对象
throw ex;
}
String[] dest = new String[src.length - 1];
System.arraycopy(src, 0, dest, 0, index);
System.arraycopy(src, index + 1, dest, index, src.length - index - 1);
src = dest;
}
// 在指定位置插入指定数据
public void insert(int index, E s) {
// 如果下标参数不合法，就抛出一个越界的异常对象
if (index < 0 || index >= src.length) {
// 创建异常对象
IndexOutOfBoundsException ex = new IndexOutOfBoundsException(
"下标越界！index:" + index + ",size：" + size());
// 抛出异常对象
throw ex;
}
Object[] dest = new Object[src.length + 1];
// 如果下标<index，就拷贝到对应的下标位置
System.arraycopy(src, 0, dest, 0, index);
// 如果下标>=index，就拷贝到新数组下标+1的位置
System.arraycopy(src, index, dest, index + 1, src.length - index);
dest[index] = s;
src = dest;
}
// 获得数据个数
public int size() {
return src.length;
}
}
带增量的长度可变数组
public class MyList2<E> {
private int rongliang;// 初始容量
private int zengliang;// 增量
private int num;// 数量【元素个数】
// 定义一个初始长度为0的数组来存放数据
private Object[] src;
public MyList2() {
this(10, 10);
}
public MyList2(int rongliang) {
this(rongliang, 10);
}
public MyList2(int rongliang, int zengliang) {
this.rongliang = rongliang;
this.zengliang = zengliang;
src = new Object[rongliang];
}
// 添加数据 Element
public void add(E s) {
// 如果数量>=数组长度，就扩容
if (num >= src.length) {
// 增加数组容量
Object[] dest = new Object[src.length + zengliang];
// 将原数组的数据拷贝到新数组
System.arraycopy(src, 0, dest, 0, src.length);
src = dest;
}
// 将数据放到src数组第一个为null的位置
src[num++] = s;
}
// 根据下标取出数据
public E get(int index) {
if (index < 0 || index >= num) {
throw new IndexOutOfBoundsException("下标越界.index:" + index
+ ",size:" + num);
}
return (E) src[index];
}
// 将指定位置的数据修改为指定的值
public void modify(int index, E s) {
if (index < 0 || index >= num) {
throw new IndexOutOfBoundsException("下标越界.index:" + index
+ ",size:" + num);
}
src[index] = s;
}
// 删除指定位置的数据
public void delete(int index) {
if (index < 0 || index >= num) {
throw new IndexOutOfBoundsException("下标越界.index:" + index
+ ",size:" + num);
}
System.arraycopy(src, index+1, src, index, num-index);
num--;
//减小容量的策略
if(src.length-num>=zengliang){
Object[] dest = new Object[src.length-zengliang];
System.arraycopy(src, 0, dest, 0, num);
src=dest;
}
}
// 在指定位置插入指定数据
public void insert(int index, E s) {
if (index < 0 || index >= num) {
throw new IndexOutOfBoundsException("下标越界.index:" + index
+ ",size:" + num);
}
// 如果数量>=数组长度，就扩容
if (num >= src.length) {
// 增加数组容量
Object[] dest = new Object[src.length + zengliang];
// 将原数组的数据拷贝到新数组
System.arraycopy(src, 0, dest, 0, src.length);
src = dest;
}
// 将下标>=index的数据向后移动一个位置
System.arraycopy(src, index, src, index + 1, num - index);
src[index] = s;
num++;
}
// 获得数据个数
public int size() {
return num;
}
}
调用数组
public class Demo {
public static void main(String[] args) {
//在创建对象的时候明确类型
MyList2<Integer> list = new MyList2<Integer>(10,1000);
list.add(10);
list.add(20);
list.add(30);
list.add(40);
list.add(50);
list.delete(0);
for(int i=0;i<list.size();i++){
int t = list.get(i);
System.out.println(t);
}
}
众所周知，数组的查询速度很快，但要论插入和删除操作还是链表更为有利，链表的内存地址是不连续的，长度可变，线性结构，我们利用泛型做一个简单的链表，代码如下：
public class MyLinkList<E> {
// 定义一个长度为0的链表,用来存放数据
Node head = null;
private Node last = null;
private int num = 0;// 元素个数
public void add(E e) {
// 创建一个结点对象
Node n = new Node(e);
// 如果链表中还没有结点，那么这个结点就是第一个结点
if (head == null) {
head = n;
} else {
// 如果链表中已经有结点了，那么这个结点就应该放在链表的尾部
last.next = n;
}
last = n;
num++;
}
// 在指定位置插入数据
public void insert(int index, E e) {
if (index < 0 || index >= num) {
throw new IndexOutOfBoundsException("下标越界,index:" + index
+ ",size:" + num);
}
// 创建新结点
Node n = new Node(e);
if (index == 0) {// 将n作为新的头结点
n.next = head;
head = n;
} else {
// 获得下标为index的结点以及下标为index-1的结点
Node n2 = getNode(index);
Node n3 = getNode(index - 1);
n3.next = n;
n.next = n2;
}
num++;
}
public void delete(int index) {
if (index < 0 || index >= num) {
throw new IndexOutOfBoundsException("下标越界,index:" + index
+ ",size:" + num);
}
if(index==0){
Node n=head;
head=head.next;
n.next=null;
n=null;
}else{
Node n1 = getNode(index-1);
Node n = getNode(index);
Node n2 = getNode(index+1);
n1.next=n2;
n.next=null;
}
num--;
}
public void modify(int index, E e) {
if (index < 0 || index >= num) {
throw new IndexOutOfBoundsException("下标越界,index:" + index
+ ",size:" + num);
}
Node n = getNode(index);
n.e = e;
}
// 根据索引获得对应位置结点中的元素
public E get(int index) {
if (index < 0 || index >= num) {
throw new IndexOutOfBoundsException("下标越界,index:" + index
+ ",size:" + num);
}
Node n = getNode(index);
return n.e;
}
// 根据索引获得结点的方法
private Node getNode(int index) {
int t = 0;
Node n = head;
while (t < index) {
n = n.next;
t++;
}
return n;
}
// 获得元素的个数
public int size() {
return num;
}
// 根据头结点获得所有的结点数据
protected void getAllNode(Node n) {
// 获得结点中的元素数据
while (n != null) {
E e = n.e;
System.out.println(e);
n = n.next;
}
}
// 内部结点类
private class Node {
E e;// 结点中的元素
Node next;// 下一个结点的引用
public Node(E e) {
this.e = e;
}
}
}
调用链表
public class Demo {
public static void main(String[] args) {
MyLinkList<String> list = new MyLinkList<String>();
list.add("AA");
list.add("BB");
list.add("CC");
list.add("DD");
list.modify(2, "FF");
list.insert(4, "FF");
list.delete(0);
for(int i=0;i<list.size();i++){
String s = list.get(i);
System.out.println(s);
}
}
}
栈是线性结构，长度可变的，数据要先进后出，最先进去的数据一定是最后出来的，可以利用数组和链表实现，代码如下：
利用数组实现栈
public class MyStack<E> {
// 定义一个初始长度为0的数组来缓存数据
Object[] src = new Object[0];
// 将数据压入栈中
public void push(E e) {
Object[] dest = new Object[src.length + 1];
// 将原数组的数据拷贝到新数组
System.arraycopy(src, 0, dest, 0, src.length);
// 将新数据放到新数组的最后一个位置
dest[src.length] = e;
// 将src指向新数组
src = dest;
}
// 查看栈顶的数据
public E get() {
// 栈顶的就是数组的最后一个数据
E e = (E) src[src.length - 1];
return e;
}
// 弹出栈顶的数据
public E poll() {
// 栈顶的就是数组的最后一个数据
E e = (E) src[src.length - 1];
// 定义一个新数组长度是原数组长度-1
Object[] dest = new Object[src.length - 1];
// 将原数组中不包含最后一个的数据拷贝到新数组
System.arraycopy(src, 0, dest, 0, dest.length);
// 将src指向新数组
src = dest;
return e;
}
// 判断栈是否为空
public boolean isEmpty() {
return src.length == 0;
}
}
利用链表实现栈
public class MyStackLink<E> {
// 定义一个长度是0的链表
Node head = null;
int length;// 结点个数
// 将数据压入栈中
public void push(E e) {
// 创建结点对象
Node n = new Node(e);
// 每次都将新的结点作为新的头结点
n.next = head;
head = n;
length++;
}
// 查看栈顶的数据
public E get() {
return head == null ? null : head.e;
}
// 弹出栈顶的数据
public E poll() {
if (head == null) {
return null;
}
// 如果头结点存在，就取出并移除头结点
Node n = head;
head = n.next;
n.next = null;
length--;
return n.e;
}
// 获得栈的大小
public boolean isEmpty() {
return length == 0;
}
// 链式结构的结点类
private class Node {
E e;
Node next;
public Node(E e) {
this.e = e;
}
}
}
调用栈：
public class Demo {
public static void main(String[] args) {
// MyStackLink<String> stack = new MyStackLink<String>();
Stack<String> stack = new Stack<String>();
//将数据压入栈
stack.push("AA");
stack.push("BB");
stack.push("CC");
stack.push("DD");
while(!stack.isEmpty()){
String s = stack.pop();
System.out.println(s);
}
//查看栈顶的数据
String s = stack.get();
System.out.println(s);
//弹出栈顶的数据
String s1 = stack.poll();
System.out.println(s1);
s = stack.get();
System.out.println(s);
}
}
相关推荐
数据结构的定义 数据结构是计算机存储、组织数据的方式，用于高效地访问和修改数据。...Java提供了丰富的数据结构库，包括数组、链表、栈、队列等，这些数据结构为程序员提供了处理各种问题的工具和方法。
java数组和链表数据结构的区别 数组和链表.pdf
Java数组链表效率-Java数组和链表三种遍历效率对比 数组和链表.pdf
基于JAVA实现的常用数据结构代码，JAVA实现复杂度、动态数组、链表、栈、队列、二叉搜索树等
Java栈的实例-数组和链表两种方法 数组和链表.pdf
Java数据结构 线性表，链表，哈希表是常用的数据结构，在进行Java开发时，JDK已经为我们提供了一系列相应的类来实现基本的数据结构
java数组和链表底层-链表的底层原理和实现 数组和链表.pdf
在队列的代码中，引用了链表的代码
Java基础-模拟HashMap集合（基于数组和链表） 数组和链表.pdf
java面试编程题（数组和链表相关） 数组和链表.pdf
自己写的一个小项目。用数组模拟实现java的数据结构，性能还行。和源码思路比较接近。可以看看，有助于初学者了解数据结构与算法。
Java用数组和链表的方式简单实现HashMap的增删改功能 数组和链表.pdf
Java数组+链表简单实现HashMap的put和get 数组和链表.pdf
NULL 博文链接：https://redhacker.iteye.com/blog/1923208
Java集合，HashMap底层实现和原理（1.7数组+链表与1.8+的数组+链表+红黑树） 数组和链表.pdf
java实现数据结构，数组，链表，二叉树，图以及各种高级排序
数据结构 Java 数组 链表 栈 队列 树
java中链表和数组的区别？ 数组和链表.pdf
多种语言包括java、python、c语言、go语言、php等来实现的数据结构的源码，包含数组、 链表、栈、队列、递归、排序、二分查找、散列表、二叉树、堆、图、回溯、分治、动态规划的实现方法。非常适合学习数据结构的小...