java数据结构(数组和链表的使用)
程序员文章站
2022-07-10 18:26:52
一.数组的数据结构先声明一个List接口,声明一下线性数据结构的规则package day11;/** * 声明一个线性的数据结构的规则 * * @author Acer * */public interface List {// 尾部添加void add(Object obj);// 指定位置添加void add(int index, Object obj);// 指定位置删除Object remove(int index);// 获取指定位置上的数...
一.数组的数据结构
先声明一个List接口,声明一下线性数据结构的规则
package day11; /**
* 声明一个线性的数据结构的规则
*
* @author Acer
*
*/ public interface List { // 尾部添加 void add(Object obj); // 指定位置添加 void add(int index, Object obj); // 指定位置删除 Object remove(int index); // 获取指定位置上的数据 Object get(int index); // 修改指定位置上的数据 void set(int index, Object obj); // 返回该数据结构的长度 int size(); // 获得当前数据结构的迭代器 Iterator iterator(); }
创建迭代器接口
package day11; /**
* 自定义数据结构的单向迭代器
* @author Acer
*
*/ public interface Iterator { // 判断有没有下个元素 boolean hasNext(); //获取下一个元素 Object next(); //从尾部删除一个元素 Object remove(); }
创建一个ArrayList类,实现接口
package day11; public class ArrayList implements List { private Object[] data; private int size; // 提供两个构造器 public ArrayList() { this(10); } public ArrayList(int length) { data = new Object[length]; } @Override//尾部添加 public void add(Object obj) { add(size,obj); } @Override//指定位置添加 public void add(int index, Object obj) { // 先来判断index输入是否合法 if (index < 0 || index > size) { System.out.println("下标输入不合法"); return; } // 判断一下是否满了 /*
* if(size == data.length) {
* Object[] no = new Object[data.length];
* for(int i=0;i<data.length;i++) {
* no[i] = data[i]; } data = no;
* }*/ * // 此处方法重复使用多次,故封装为私有方法 // 调用封装的方法 data = arrayFull(); // 移动数据式倒着来的 for (int i = size - 1; i > index; i--) { data[i + 1] = data[i]; } data[index] = obj; size++; } // 私有方法判断数组是否满了 private Object[] arrayFull() { if (size == data.length) { Object[] no = new Object[data.length]; for (int i = 0; i < data.length; i++) { no[i] = data[i]; } data = no; } return data; } @Override//指定位置删除 public Object remove(int index) { if (index < 0 || index > size) return null; // 数据搬移 Object temp = data[index]; for (int i = index; i < size - 1; i++) { data[i] = data[i + 1]; } data[size - 1] = null; size--; return temp; } @Override//获取指定位置上的数据 public Object get(int index) { // 判断输入的index是否合法 if (index < 0 || index > size) return null; return data[index]; } @Override//修改指定位置上的数据 public void set(int index, Object obj) { if (index < 0 || index > size) return; data[index] = obj; } @Override//返回该数据结构的长度 public int size() { return size; } @Override//获取当前数据结构的迭代器 public Iterator iterator() { return new Iterator() { int position = -1; @Override//从尾部删除一个元素 public Object remove() { if(position+1<size) { return ArrayList.this.remove(position--); } return null; } @Override//获取下一个元素 public Object next() { if(position+1<size) { return get(++position); } return null; } @Override//判断有没有下个元素 public boolean hasNext() { // System.out.println(position); // if(data[position+1] == null) { if(position+1>size){ position++; return false; }else { position++; return true; } } }; } }
创建一个测试类进行相关功能的测试
package day11; import com.briup.day06.Student; public class ListTest { public static void main(String[] args) { List al = new ArrayList(); al.add("hello"); al.add("world"); al.add("tom"); al.add(1, new Student("Jerry")); al.add(2, 20); // System.out.println(al.remove(2)); // System.out.println(al.size()); //使用迭代器 Iterator it = al.iterator(); while(it.hasNext()) { System.out.println(it.next()); } } }
二.链表的数据结构
抽象一个链表中单个节点的类
package day11; /**
* 抽象一个链表中单个节点的类
*
* @author Acer
*
*/ public class Node { // 节点中保存的数据 private Object data; // 指向下一个节点的地址 public Node next; // 单参构造器 public Node(Object data) { this.data = data; } // 全参构造器 public Node(Object data, Node next) { super(); this.data = data; this.next = next; } // get和set方法 public Object getData() { return data; } public void setData(Object data) { this.data = data; } }
创建链表的数据结构,依然实现接口
package day11; /**
* 链表结构的数据结构
*
* @author Acer
*
*/ public class LinkedTest implements List { // 定义一个空的头节点 private Node head; // 用来记录数据结构的大小 private int size; public LinkedTest() { head = new Node(null, null); } @Override // 尾部添加 public void add(Object obj) { add(size,obj); } @Override // 指定位置上添加 public void add(int index, Object obj) { if (index < 0 || index > size) return; // 使用临时变量,将head值赋予它 Node curr = head; // 找到index的位置,只能从头节点向后去遍历 for (int i = 0; i < index; i++) { curr = curr.next; } // 准备一个新添加进来的节点 Node node = new Node(obj); // 准备地址重新定向 node.next = curr.next; curr.next = node; size++; } @Override // 指定位置删除 public Object remove(int index) { // 1.验证合法性 if (index < 0 || index > size) return null; // 2.遍历取到当前节点和当前节点的上一个节点 Node curr = head; Node pre = null; for (int i = 0; i <= index; i++) { pre = curr; curr = curr.next; } //3.确认curr就是我们要删除的节点 //pre就是我们要删除节点的上一个节点 //保存删除节点的数据 Object temp = curr.getData(); //修改地址指向 pre.next = curr.next; curr.next = null; size--; return temp; } @Override // 获取指定位置上的数据 public Object get(int index) { // 1.验证合法性 if (index < 0 || index > size) return null; // 2.遍历取到当前节点 Node curr = head; for (int i = 0; i <= index; i++) { curr = curr.next; } // 最后得到的curr就是要取的当前节点 return curr.getData(); } @Override // 修改指定位置上的数据 public void set(int index, Object obj) { // 1.验证合法性 if (index < 0 || index > size) return; // 2.遍历取到当前节点 Node curr = head; for (int i = 0; i <= index; i++) { curr = curr.next; } // 3.curr就是要修改的节点 curr.setData(obj); } @Override // 返回该数据结构的长度 public int size() { return size; } @Override // 获取当前数据结构的迭代器 public Iterator iterator() { return new Iterator() { int position = -1; @Override public Object remove() { if(position+1<size) { return LinkedTest.this.remove(position--); } return null; } @Override public Object next() { if(position+1<size) { return get(++position); } return null; } @Override public boolean hasNext() { if(position+1<size) { return true; } return false; } }; } }
这里可以继续使用之前的测试类,只需要把new对象的ArrayList改为LinkedTest即可
package day11; import com.briup.day06.Student; public class ListTest { public static void main(String[] args) { List al = new LinkedTest(); al.add("hello"); al.add("world"); al.add("tom"); al.add(1, new Student("Jerry")); al.add(2, 20); System.out.println(al.remove(2)); System.out.println(al.size()); // System.out.println(al.get(2)); //使用迭代器 Iterator it = al.iterator(); while(it.hasNext()) { System.out.println(it.next()); } } }
这里就可以对链表的数据结构的相关功能进行测试
本文地址:https://blog.csdn.net/lanaiwanqiQAQ/article/details/107900154
推荐阅读
-
Java中的增强for循环和break continue的使用 以及流程控制训练
-
JavaEE基础day02 1.定义Java中的变量 四类八种 2.变量定义和使用的注意事项 3.数据类型的转换、强制数据类型转换4.算数运算符、比较运算符、逻辑运算符、赋值运算符、三元运算符
-
Java实现求子数组和的最大值算法示例
-
Java使用条件语句和循环结构的详细介绍
-
Java使用IO流实现音频的剪切和拼接
-
java序列化和serialVersionUID的使用方法实例
-
Java时间类Date类和Calendar类的使用详解
-
java使用链表来模拟栈的入栈出栈操作实例代码
-
java和c#使用hessian通信的方法
-
Java的wait(), notify()和notifyAll()使用心得