一、物理结构
数组
数组是存储相同数据类型的元素的一种有序数据结构，通过下标进行存储。查找的时间复杂度为O(1)，而删除和添加的时间复杂度为O(n)。
其代码实现如下：
public class MyArray {
private int[] array;
private int size;
public MyArray(int capacity){
this.array = new int[capacity];
size = 0;
}
/**
* 1.数组插入元素
* @param index 插入的位置
* @param element 插入的元素
*/
public void insert(int index, int element) throws Exception {
//如果越界的话
if(index<0||index>size){
throw new IndexOutOfBoundsException();
}
//如果达到上限，就扩容
if(size>=array.length){
resize();
}
//从中间插入时，数组元素从右向左移动
for (int i = size - 1; i >= index ; i--) {
array[i+1] = array[i];
}
array[index] = element;
size++;
}
/**
* 2.删除指定元素
* @param index 指定下标
*/
public void delete(int index){
if(index<0||index>=size){
throw new IndexOutOfBoundsException();
}
//如果是删除中间某一个数的话
for (int i = index; i < size -1 ; i++) {
array[i] = array[i+1];
}
size--;
}
/**
* 数组扩容
*/
public void resize(){
int[] arrayNew = new int[array.length*2];
System.arraycopy(array,0,arrayNew,0,array.length);
array = arrayNew;
}
/**
* 输出数组
*/
public void output(){
for(int i=0; i<size; i++){
System.out.println(array[i]);
}
}
public static void main(String[] args) throws Exception {
MyArray myArray = new MyArray(4);
//刚开始插入的时候，要从0 的位置开始插入
myArray.insert(0,3);
myArray.insert(1,7);
myArray.insert(2,9);
myArray.insert(3,5);
myArray.insert(1,6);
myArray.insert(5,8);
myArray.delete(2);
myArray.output();
}
}
链表
链表则是通过指针来连接节点的一种数据结构。在空间利用方面，是随机存储，相较于顺序存储的数组有着很大的灵活性。其中双向链表作为链表的一种，一个元素首和尾都分别指向于其他元素。链表的删除和添加的时间复杂度为O(1),查找的时间复杂度为O(n)。
链表的实现代码如下：
/**
* 节点
*/
public static class Node{
int data;
Node next;
Node(int data){
this.data = data;
}
}
public Node head;
public Node last;
public int size;
/**
* 获取某一个节点
*/
public Node get(int index){
if(index<0||index>size){
throw new IndexOutOfBoundsException("链表越界");
}
Node node = head;
for (int i = 0; i < index; i++) {
node = node.next;
}
return node;
}
/**
* 打印链表
*/
public void output(){
Node node = head;
for (int i = 0; i < size; i++) {
System.out.println(node.data +" ");
node = node.next;
}
}
/**
* 添加节点
*/
public void insert(int index,int data){
//如果越界的话
if(index<0||index>size){
throw new IndexOutOfBoundsException();
}
Node nodeAdd = new Node(data);
if(size==0){
head = nodeAdd;
last = nodeAdd;
}else {
if (index == 0) {
nodeAdd.next = head;
head = nodeAdd;
} else if (index == size) {
last.next = nodeAdd;
last = nodeAdd;
} else {
Node preNode = get(index - 1);
nodeAdd.next = preNode.next;
preNode.next = nodeAdd;
}
}
size++;
}
/**
* 删除节点
* @return
*/
public Node delete(int index){
if(index<0||index>=size){
throw new IndexOutOfBoundsException();
}
Node nodeDel = head;
if(size==0){
head = null;
last = null;
}else {
if(index == 0){
head = head.next;
}else if(index == size-1){
nodeDel = last;
Node nodeLa = get(index - 1);
last = nodeLa;
nodeLa.next = null;
}else {
nodeDel = get(index);
Node nodePre = get(index - 1);
nodePre.next = nodeDel.next;
}
}
size--;
return nodeDel;
}
public static void main(String[] args) {
MyLinkedList linkedList = new MyLinkedList();
linkedList.insert(0,1);
linkedList.insert(1,2);
linkedList.insert(2,3);
linkedList.insert(3,4);
linkedList.delete(1);
linkedList.output();
}
}
二、逻辑数据结构
例如栈、队列、和散列表等。都是基于数组和链表的数据结构。
栈
既可以使用数组，也可以使用队列实现。添加方式：尾部添加，删除方式：尾部删除。即：先入后出
队列
同样也是既可以使用数组，也可以使用队列实现。先入先出。
当使用数组来作为物理结构时，为了提高队列空间的利用率，产生了循环队列。
/**
* 队列特点，先进先出
* 这里的代码是循环队列，指可以循环利用空间。
*/
public class MyQueue {
private int[] array;
private int front;
private int rear;
public MyQueue(int capacity) {
this.array = new int[capacity];
}
/**
* 入队
* @param data
*/
public void enQueue(int data){
if((rear+1)%array.length==front){
throw new IndexOutOfBoundsException("队列已满");
}
array[rear] = data;
rear = (rear+1)%array.length;
}
/**
* 出队
* @return
*/
public int deQueue(){
if(rear == front){
throw new NullPointerException("队列已空");
}
int element = array[front];
front = (front+1)%array.length;
return element;
}
/**
* 打印队列
*/
public void printQueue(){
for (int i = front; i != rear; i = (i+1)%array.length) {
System.out.println(array[i]);
}
}
public static void main(String[] args) {
MyQueue myQueue = new MyQueue(10);
myQueue.enQueue(2);
myQueue.enQueue(5);
myQueue.deQueue();
myQueue.enQueue(7);
myQueue.enQueue(4);
myQueue.printQueue();
myQueue.deQueue();
}
}
散列表/哈希表（HashTable）
在java中，hashmap的实现结合了数组，链表，以及红黑树多种数据结构。
哈希表并不直接通过下标来进行标识，而是通过哈希函数将key转化为对应的下标，并将value储存在对应下标之下。而当一个下标对应多个value时，则使用链表来拓展，这种解决哈希冲突的方案称为链表法。
而ThreadLocal使用的是开放寻址法，即当对应下标中已经存在value的话，则按顺序寻找其他空间，存储新的value。