一.线性表
实现思路：我们平常使用的ArrayList集合便是一个顺序表,我们只需要通过阅读并且研究源码,便可以自己来实现一个顺序表了。
下面是我的具体代码
import java.util.Arrays;
import javax.management.RuntimeErrorException;
/*
* 这是一个顺序表
*/
public class Sequence_table<E>{
//该变量是顺序表的初始容量
private static final int List_Init_Size=100;
//底层数组
private static Object[] array;
//顺序表的真实数据量
private int size;
//默认的依次扩充顺序表的大小
private static final int default_sizecount=10;
/*
* 初始化一个顺序表----通过构造方法实现初始化
*/
public Sequence_table(){
this(List_Init_Size);
}
public Sequence_table(int Init_Size) {
if(Init_Size > 0) {
this.array=new Object[Init_Size];
size=0;
}
else if(Init_Size==0) {
this.array=new Object[]{};
size=0;
}
else {
throw new RuntimeErrorException(null, "参数"+Init_Size+"不合法");
}
}
/*
* 该方法用于将顺序表的容量缩减为当前所占用的真正空间
*/
public void trimToSize() {
if(size<array.length) {
array=(size==0)?new Object[]{}:Arrays.copyOf(array,size);
}
}
/*
* 增加当前顺序表的容量,当然需要在原本的容量不足的情况下才可以
*/
public void ensureCapacity(int TheLong) {
if(TheLong>=1&&(size==array.length)) {
array=Arrays.copyOf(array,array.length+TheLong);
}
if(TheLong<1) {
throw new RuntimeErrorException(null, "参数"+TheLong+"不合法");
}
return;
}
/*
* 获取当前线性表的大小
*/
public int size() {
return size;
}
/*
* 向线性表中添加数据
*/
public boolean add(E e) {
this.ensureCapacity(default_sizecount);
array[size]=e;
size++;
return true;
}
/*
* 该方法用于检查索引是否合法
*/
public void checkIndex(int index) {
if(index>=0&&index<=size) {
size++;
if(size==array.length)
this.ensureCapacity(default_sizecount);
else
size--;
}
else throw new RuntimeErrorException(null, "参数"+index+"不合法");
}
/*
* 向线性表中的指定位置插入数据
*/
public void add(int index, E e) {
checkIndex(index);
for(int i=size;i<=index;i--) {
array[i]=array[i-1];
if(i==index) {
array[i]=e;
}
}
size++;
}
/*
* 删除线性表中的数据
*/
public void remove(int index) {
checkIndex(index);
for(int i=index;i<size;i++) {
array[i]=array[i+1];
}
size--;
}
/*
* 获取线性表中的数据
*/
public Object get(int index) {
checkIndex(index);
return array[index];
}
/*
* 修改线性表中的数据
*/
public void change(int index,E value) {
checkIndex(index);
array[index]=value;
}
}
二.单链表
实现思路：在java中每new一个新的对象就会在内存中创建出一片地址,将下一个对象存入上一个对象中便实现了单链表
具体代码如下：
import java.util.Arrays;
import javax.management.RuntimeErrorException;
/*
* java实现单链表
* 命名基本上会模仿c语言中的命名
* 比如说Node(节点)之类的
*/
class Node{
Node next=null; //存储着下一个节点的地址
int data;//数据域
public Node(int data) {
this.data=data;
}
}
public class Link_List{
private Node headNode=null;//头节点
private Node tailNode=null;//尾节点
private Node recordNode=null;//该节点用于记录
private int size; //单链表的当前容量
/*
* 初始化一个单链表
*/
public Link_List() {
headNode=new Node(0);
size=1;
}
/*
* 返回单链表当前容量
*/
public int size() {
return size-1;
}
/*
* 向单链表中添加节点,使用尾插法,不断改变尾节点的值,达到不断添加的效果
*/
public void add(int data) {
if(headNode.next==null) {
headNode.next=new Node(data);
tailNode=headNode.next; //给尾节点赋值
size++;
}
else {
tailNode.next=new Node(data);
tailNode=tailNode.next;
size++;
}
}
/*
* 向单链表中插入数据
*/
public void add(int index,int data) {
if(index<0||index>size) {
throw new RuntimeErrorException(null, "参数"+index+"不合法");
}
else {
if(index==size-1) {
this.add(data);
return;
}
recordNode=headNode.next;
for(int i=1;i<index;i++) {
recordNode=recordNode.next;
}
Node a=new Node(data);
if(index==0) {
headNode.next=a;
a.next=recordNode;
size++;
return;
}
Node b=recordNode.next;
recordNode.next=a;
a.next=b;
size++;
return;
}
}
/*
* 获取单链表中所有的值
*/
public int[] getAll() {
int[] a=new int[size];
recordNode=headNode.next;
for(int i=1;i<a.length;i++) {
a[i]=recordNode.data;
recordNode=recordNode.next;
}
a=Arrays.copyOfRange(a,1,10);
return a;
}
/*
* 删除单链表的某个节点
*/
public void delete(int index) {
if(index<1||index>size) {
throw new RuntimeErrorException(null, "参数"+index+"不合法");
}
else {
recordNode=headNode;
for(int i=1;i<=index-1;i++) {
recordNode=recordNode.next;
}
if(index==size-1) {
recordNode.next=null;
size--;
return;
}
recordNode.next=(recordNode.next).next;
size--;
}
}
/*
* 获取单链表中某个节点的值
*/
public int get(int index) {
if(index<0||index>size) {
throw new RuntimeErrorException(null, "参数"+index+"不合法");
}
else {
recordNode=headNode;
for(int i=0;i<index;i++) {
recordNode=recordNode.next;
}
return recordNode.data;
}
}
}