墙裂推荐（javahashtable）javahashmap红黑树，Java入门教程-数据结构简介（链表/队列/栈/哈希表），java链表和队列，

1.1.1. 链表（了解）

链表结构（火车和火车车厢）：

1)：单向链表，只能从头遍历到尾/只能从尾遍历到头。

2)：双向链表，既可以从头遍历到尾,又可以从尾遍历到头。

通过引用来表示上一个节点和下一个节点的关系。

单向链表：

双向链表：

对LinekdList操作的性能分析：

双向链表可以直接获取自己的第一个和最后一个节点。

如果新增的元素在第一个或最后一个位置，那么操作只有1次。

如果删除第一个元素：操作一次

如果删除最后一个元素：操作一次

如果删除中间的元素：

找到元素节点平均操作：(1+N)/2次

找到节点之后做删除操作: 1次

平均：(N+1)/2次

平均:(N+1)/2次

结论：

ArrayList：查询、更改较快，新增和删除较慢。

LinkedList：查询、更改较慢，新增和删除较快。

一般的，在开发中数据都是存储在数据库中，我们一般主要用来查询，所以ArrayList使用较多。

1.1.2. 队列（了解）

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。

进行插入操作的端称为队尾，进行删除操作的端称为队头。

单向队列(Queue)：先进先出(FIFO)，只能从队列尾插入数据，只能从队列头删除数据。

双向队列(Deque)：可以从队列尾/头插入数据，只能从队列头/尾删除数据。

结论：最擅长操作头和尾。

1.1.3. 栈（了解）

栈（stack）又名堆栈，它是一种运算受限的线性表，后进先出(LIFO)，和手枪弹夹类似。

栈结构仅允许在表的一端进行插入和删除运算，这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈中插入新元素又称作入栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素。从一个栈中删除元素又称作出栈，表示把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素（LIFO）。

1.1.4. 哈希表（了解）

一般的，数组中元素在数组中的索引位置是随机的，元素的取值和元素的位置之间不存在确定的对应关系。因此，在数组中查找特定的值时，需要把查找值和一系列的元素进行比较。

此时的查询效率依赖于查找过程中所进行的比较次数，如果比较次数较多，查询效率还是不高。

如果元素的值（value）和在数组中的索引位置（index）有一个确定的对应关系，我们把这种关系称之为哈希（hash）。则元素值和索引对应的公式为: index = hash(value)。也就是说，通过给定元素值，只要调用hash(value)方法，就能找到数组中取值为value的元素的位置。

比如，图中的hash算法公式为：index = value / 10 - 1。

在往哈希表中存储对象时，该hash算法就是对象的hashCode方法。

注：这里仅仅是假设算法公式是这样的，真实的算法公式我们可以不关心。

本系列教程为叩丁狼Java基础班内部教材，若要获得最好的学习效果，需要配合对应教学视频一起学习。需要完整教学视频，请私信作者。