链表是数据结构中最基础的内容，链表在存储结构上分成两种：数组形式储存，链式存储。
相比c语言需要的结构体，在java中由于有了面向对象编程，将指针‘藏’了起来，不需要分配内存。
所以只需要创建一个对象数组，为了能让链表更加实用，方便存储非基本类型的对象，所以使用了泛型。
菱形运算符<>中放你自己写的或者基本类型，比如你创建了一个Stdent类，想用链表将很多学生的信息存起来。
就可以myArrayList<Student> a=new myArrayList();这个链表就都存Student类的对象了。
数组链表的源码：
import java.util.Arrays; /**
* @author 李正阳
* @param <E> 泛型：所存储的对象
*/
public class myArrayList<E> implements List<E> {
/**
* DEFAULT_SIZE 数组链表储存的最大值
* elementData 存储元素的数组
* capacity当前数组链表可以存储的个数（为了扩容存在）
* size当前链表存储的个数
*/
private final int DEFAULT_SIZE = 16;
private Object[] elementData;
private int capacity;
public int size; /**
* 初始化数组栈
*/
public myArrayList() {
elementData = new Object[DEFAULT_SIZE];
size = 0;
capacity=DEFAULT_SIZE;
} /**
* 在数组链表的最后添加元素
* @param data 添加的元素
* @return true 添加成功 false 添加失败
*/
@Override
public boolean add(E data) {
if(isFull()) {
relloc();
elementData[size] = data;
size++;
}else {
elementData[size] = data;
size++;
}
return true;
} /**
* 判满函数
* @return true 满 false 未满
*/
@Override
public boolean isFull() {
if (size == DEFAULT_SIZE-1) {
return true;
} else {
return false;
}
}
/**
* 判空函数
* @return true 空 false 未空
*/
@Override
public boolean isEmpty() {
if (size ==0) {
return true;
} else {
return false;
}
} /**
* 删除元素
* @param number 删除元素在数组中的位置
* @return
*/
@Override
public E remove(int number){ E temp;
if (number == size) {
temp = (E) elementData[size - 1];
size--;
} else if(number<size) {
temp = (E) elementData[number - 1];
for (int i = number; i < size; i++) {
elementData[i] = elementData[i + 1];
}
size--;
}else {
throw new ArrayIndexOutOfBoundsException();
}
return temp; } /**
* 删除数组最后的元素
* @return 删除那个元素
*/
@Override
public E remove(){
E temp;
temp = (E) elementData[size-1];
size--;
return temp;
} /**
* 设置某一个位置元素
* @param i 在数组的位置
* @param data 替换的元素
*/
@Override
public void set(int i,E data){
if(i<=size) {
elementData[i - 1] = data;
}else {
throw new ArrayIndexOutOfBoundsException();
}
} /**
* 取得数组中某个位置的元素
* @param i 数组的位置
* @return 这个位置的对象
*/
@Override
public E get(int i){
E temp;
if(i<=size) {
temp = (E) elementData[i - 1];
return temp;
}else {
throw new ArrayIndexOutOfBoundsException();
}
} /**
* 判断一条链表是否为回文
* @return false 否 true 是
*/
@Override
public boolean isPalindrome() {
if(!isEmpty()) {
for (int i = 0, j = size - 1; i < size - 1; i++, j--) {
if (String.valueOf(elementData[i]).equals(String.valueOf(elementData[j]))) {
} else {
return false;
}
}
return true;
}else {
throw new NullPointerException();
}
} /**
* 输出链表中所有元素
*/
@Override
public void traver() {
for (int i=0;i<size;i++){
System.out.print(elementData[i]+" ");
}
} /**
* 扩容将数组扩容为两倍
*/
private void relloc(){
capacity=DEFAULT_SIZE*2;
elementData=Arrays.copyOf(elementData,DEFAULT_SIZE*2);
}
}
List接口：
/**
* @author 李正阳
* @param <E> 泛型
*/
public interface List<E> {
public boolean add(E data) ; /**
* 链式不需要这个方法
*/
default boolean isFull() {
return false;
}
public boolean isEmpty() ;
public E remove(int number);
public E remove();
public void set(int i,E data);
public E get(int i);
public boolean isPalindrome();
public void traver();
}
数据结构（一点五）链式顺序表
https://www.cnblogs.com/lzy321/p/10371767.html