java数据结构（数组和链表的使用）

一.数组的数据结构

先声明一个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