眨眼间，我们就上到了数据结构，从数组到队列，数据结构中的基本内容也快讲完，在数组的学习中，我们首先是学习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中实现动态数组链表的关键概念、操作以及其实现方式...
Java数据结构是编程中至关重要的组成部分，它们定义了如何有效地存储和操作数据。在这个话题中，我们将重点关注两种常见的数据结构——链表和数组，并探讨它们如何被用来实现栈这一特定的抽象数据类型。 栈是一种...
Java 数组链表效率对比 Java 中的数组和链表是两种常用的数据结构，它们都可以用来存储和操作数据。然而，在实际开发中，选择合适的数据结构和遍历方式对程序的性能和效率有着非常重要的影响。下面我们将对 Java 中...
Java中的数组和链表是两种常见的线性数据结构，各有优缺点，适用于不同的场景。下面我们将详细探讨这两种数据结构的区别。 **数组（Array）** 数组是一种在内存中连续存储相同类型元素的数据结构。它的主要特点...
本项目“java模拟实现数组链表树图等数据结构”旨在帮助初学者通过实际操作来理解这些基本数据结构及其工作原理。 首先，数组是最基础的数据结构，它是一个有序的元素集合，元素可以通过索引来访问。在Java中，数组...
本压缩包"基于JAVA实现的常用数据结构代码"包含了多个关键的数据结构实现，包括复杂度分析、动态数组、链表、栈、队列以及二叉搜索树。以下是这些数据结构的详细说明： 1. **复杂度**：在计算机科学中，复杂度分为...
Java中的栈是一种重要的数据结构，它遵循“后进先出”（LIFO）的原则，常用于处理临时存储和撤销操作等问题。栈的操作主要包括以下几个基本运算： 1. **判断栈是否为空**：`isEmpty()`方法检查栈中是否还有元素，...
本资源主要讲解了Java面试编程题中的数组和链表相关知识点，涵盖了Java编程语言中数组和链表的基本概念、算法和数据结构等方面的知识。 一、数组相关知识点 1. 、二维数组的概念和性质：在 Java 中，二维数组是一...
Java数据结构 线性表，链表，哈希表是常用的数据结构，在进行Java开发时，JDK已经为我们提供了一系列相应的类来实现基本的数据结构
本篇文章将深入探讨如何使用Java数组来模拟实现链表数据结构，以此来增强对链表理解的同时，也能看到数组在特殊场景下的运用。 链表是由一系列节点（或称为元素）组成的线性数据结构，每个节点包含数据和指向下一个...
本资源提供了Java实现的数据结构代码，包括栈、动态数组、队列、链表和二叉树，这些都是计算机科学中最基础且重要的数据结构。 1. **栈（Stack）**：栈是一种“后进先出”（LIFO）的数据结构，常用于表达式求值、...
Java基础-模拟HashMap集合（基于数组和链表） 在本文中，我们将详细介绍如何模拟Java的HashMap集合，使用数组和链表来实现Hash表的存储。我们将从基本概念开始，逐步深入到HashMap的实现细节中。 什么是HashMap？ ...
在Java编程语言中，数组和链表是两种基础且重要的数据结构。它们各自有独特的特点和使用场景，尤其是在处理大量数据时，理解它们的工作原理和性能特性至关重要。本压缩包文件"数组的扩容和链表结构.zip"包含了关于...
本课件资源提供了全面的数据结构学习材料，涵盖了链表、栈、队列、数组、串、树等基本数据结构，对于理解和掌握这些知识至关重要。 1. 链表：链表是一种动态数据结构，它的元素（节点）不连续存储，而是通过指针...
链表是一种动态数据结构，每个节点包含数据和指向下一个节点的引用。与数组相比，链表在插入和删除操作上更高效，因为不需要移动元素。Java中的链表主要由`java.util.LinkedList`类表示，它同时实现了`List`接口，...
数组集合是一种基本的数据结构，在Java中被广泛使用。它具有以下特点： 1. **有序性**：数组集合中的元素按照一定的顺序排列，这使得我们可以通过索引直接访问特定位置的元素。 2. **快速访问**：由于数组在内存中...
Java中的链表是一种重要的数据结构，它克服了数组在存储和操作上的局限性。链表不依赖于内存中连续的存储空间，而是通过节点间的引用（即指针）连接各个数据元素，使得插入和删除操作更为高效。在链表中，每个节点...
Java 数据结构在计算机科学和编程中起着至关重要的作用。本文将介绍顺序表、链表、栈、队列、堆、二叉树、常见排序算法、Map 和 Set 的基本概念、实现代码及其应用场景。这些数据结构和算法是编写高效程序的基础，...