Java数据存储（模拟ArrayList和LikedList）_Java

数据结构：提供一组数据的储存、检索的物理结构；对于数据而言，放的进去，取得出来
线性存储的结构：一对一
数组：必须是一段连续的内存空间，位置是固定的，提供了索引
链表：除了保存自己保存的数据之外，还要保存下一个节点的地址

对于数据要有增、删、改、查、遍历
在java中使用数据结构来完成数据的增删改查和遍历会非常麻烦；因此Java中引入了集合
集合
树形：一对多
图形：

模拟ArrayList 和LikedList

数组的结构
在这里插入图片描述
数组是连续的，只存放数据。但数组长度是固定的；
添加元素时要考虑数组长度，数组扩容；
在指定位置添加数据后要注意：指定位置之后的数据要往后移
在指定位置删除数据后要注意：指定位置之后的数据要往前移

//首先要抽象一个数据结构的接口 List public interface List{ int size; //记录数据结构的长度 //尾部添加数据 void add(Object obj); //指定位置插入数据 void add(int index,Object obj); //指定位置的删除 Object remove(int index); //指定位置的修改 void set(int index , Object obj); //获取指定位置的值 Object get(int index); //获取整个数据结构的长度 int size(); //使用迭代器遍历 Iterator iterator(); } //迭代器：Iterator ---> 遍历 //迭代器接口 public interface Iterator{ //是否还有下一个元素 boolean hasNext(); //获取下一个元素的值 Object next(); //删除尾部元素的方法 Object remove();//（可选） }

/**
 * 模拟一个连续性的线性存储结构
 * @author 1991094146
 *
 */ public class ArrayList implements List{ //使用数组来模拟连续性的存储结构 private Object[] data; //使用一个变量来记录数据结构的长度 private int size; //空参的构造器 public ArrayList() { this(10); } //单参的构造器 public ArrayList(int length) { data = new Object[length]; } public void add(Object obj) { add(size,obj); } public void add(int index, Object obj) { //判断一下index是否合法 if(index<0 || index>size) { System.out.println("输入的索引不合法"); return; } //判断数组是不是满了？ data = arrayFull(); //数据搬移 //倒着循环 for(int i=size;i>index;i--) { data[i] = data[i-1]; } data[index] = obj; size++; } //封装一个私有的方法供内部使用 private Object[] arrayFull() { if(size == data.length) { //满了之后要扩容 Object[] no = new Object[data.length+10]; for(int i=0;i<data.length;i++) { no[i] = data[i]; } //System.arraycopy(src, srcPos, dest, destPos, length); data = no; } return data; } 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; } public void set(int index, Object obj) { if(index<0 || index>=size) return; data[index] = obj; } public Object get(int index) { if(index<0 || index>=size) return null; return data[index]; } public int size() { return size; } //内部类实现迭代器接口方法 public Iterator iterator() { return new Iterator() { int position = -1; public Object remove() { //修改一下迭代的位置 if(position+1<=0) { return null; } return ArrayList.this.remove(position--); } public Object next() { return get(++position); } public boolean hasNext() { if(data[position+1] == null) { return false; }else { return true; } } }; } }

链表的结构
单项链表的结构
在这里插入图片描述

链表分为单向链表和双向链表
单项列表是没有下表的，节点分为两部分一部分存储数据，另一部分是下个节点的地址（堆区的地址）；注意：图中地址不是节点自己的地址；而是下一个节点的地址
链表每一次查询都需要从头节点向后寻址，所以要声明头节点；
链表进行数据的添加（插入）或者删除数据时；要注意节点中下个节点的地址；

eg：图中在节点1后面插入新节点；
1、需要先将节点2的地址（插入新节点前：节点1指向的下个节点的地址）放在新节点的地址区；
   确保新节点插入后，不会造成数据的丢失
2、将新节点的地址放在节点1的地址区；//绿线代表新的节点指向

/**
 * 抽象链表结构中的节点
 * @author 1991094146
 *
 */ public class Node { //原本保存的数据 private Object data; //指向下一个节点的地址 public Node next; public Node(Object data) { this.data = data; } public Node(Object data , Node next) { this.data = data; this.next = next; } //提供data的访问接口 public Object getData() { return data; } public void setData(Object data) { this.data = data; } }

/**
 * 以链表的结构来实现线性数据存储
 * @author 1991094146
 *
 */ public class LinkedList implements List{ //准备一个头节点 private Node head; //准备一个变量记录数据结构的长度 private int size; //构造器 public LinkedList() { head = new Node(null,null); } public void add(Object obj) { add(size,obj); } public void add(int index, Object obj) { //1、验证index if(index<0 || index>size) return; //2、找到要修改的节点 Node curr = head; //3、进行遍历查找 for(int i=0;i<index;i++) { curr = curr.next; } Node node = new Node(obj); node.next = curr.next; curr.next = node; size++; } public Object remove(int index) { //1、验证index if(index<0 || index>=size) return null; //2、找到要修改的节点 Node curr = head; Node pre = null; //3、进行遍历查找 for(int i=0;i<=index;i++) { pre = curr; curr = curr.next; } //保存要删除的节点的值 Object temp = curr.getData(); //修改地址指向 pre.next = curr.next; curr.next = null; size--; return temp; } public void set(int index, Object obj) { //1、验证index if(index<0 || index>=size) return; //2、找到要修改的节点 Node curr = head; //3、进行遍历查找 for(int i=0;i<=index;i++) { curr = curr.next; } curr.setData(obj); } public Object get(int index) { //1、验证index if(index<0 || index>=size) return null; //2、找到要修改的节点 Node curr = head; //3、进行遍历查找 for(int i=0;i<=index;i++) { curr = curr.next; } return curr.getData(); } public int size() { return size; } public Iterator iterator() { return new Iterator() { //定义迭代器的当前位置 int position = -1; public Object remove() { if(position+1<size) { //调用外部类的删除方法 return LinkedList.this.remove(position--); }else { return null; } } public Object next() { if(position+1 < size) { return get(++position); }else { return null; } } public boolean hasNext() { if(position+1 < size) { return true; }else { return false; } } }; } }