数据结构-队列，栈，哈希表，List，Vector
文章目录常见的数据结构有哪些Vector队列和栈、列表的区别队列和栈属于列表吗?链表和列表的对比linkedList是单向链表还是双向链表?单向链表有哪些应用?哈希表为什么不用哈希表来做索引?hashmap的底层原理是什么?哈希表会重复吗?那么hashmap会重复吗?java实现部分栈和队列的实现Stack(栈)LinkedList(链表、堆栈)ArrayDeque其他哈希表相关文档数据结构是一个大课题。常见的数据结构有哪些数组 #列表 # List系列VectorArrayListLinkedList栈 # 虽然经常说堆栈但是这两个是两个概念。队列 #树图堆哈希表Vectorvector是list的一个实现类。奇怪吧看英文翻译怎么也联想不到它和list有关系。这涉及到历史原因vector最早被表示为一维动态数组。vector # 英文翻译为向量、矢量计算机中表示一维动态数组这就比较搭了。队列和栈、列表的区别—数据结构操作和访问列表通用数据结构支持任意位置的插入、删除和访问操作。元素可通过索引直接访问动态调整大小。队列线性结构仅允许在队尾插入Enqueue和在队头删除Dequeue操作遵循先进先出FIFO原则。 栈线性结构仅允许在一端栈顶进行插入Push和删除Pop操作遵循后进先出LIFO原则。队列和栈属于列表吗?不属于。链表和列表的对比维度列表链表存储结构通常由数组实现元素存储在连续的内存位置。元素存储在动态分配的节点中节点之间通过指针连接。检索支持通过索引直接访问元素时间复杂度通常为O(1)即常数时间。不支持通过索引直接访问元素访问任意元素需要从头节点或尾节点开始遍历时间复杂度为O(n)n为节点数。存储结构在内存使用上如果列表大小固定则效率较高但如果需要频繁扩容则可能涉及额外的内存分配和数据复制影响效率。在内存使用上较为灵活但由于节点指针的开销整体内存效率可能低于列表。插入和删除效率在列表中间或前端插入、删除元素时需要移动后续元素以保持列表的连续性时间复杂度为O(n)。在列表末尾插入元素时由于数组尾部通常有预留空间或动态扩容机制效率相对较高。在链表开头或结尾插入、删除元素时只需修改指针的指向时间复杂度为O(1)。linkedList是单向链表还是双向链表?单向链表有哪些应用?linkedList是双向链表。单向链表有哪些应用?就没这么用的单向链表一般只是在教学时说明概念实际做的时候双向链表也不复杂没人会做单向链表这么蹩脚的功能。哈希表为什么不用哈希表来做索引?答就没人这么用。# 0分正确答案哈希表的检索方式是等值查询不支持范围查询和索引。hashmap的底层原理是什么?这是一道数据结构题坑很多。要点1、hashmap的实现方式。JDK1.7及之前数组 单向链表拉链法解决冲突。JDK1.8及之后数组 链表/红黑树链表长度≥8且数组长度≥64时树化≤6时退化。2、哈希表的设计原理负载因子、扩容、时间复杂度等。负载因子已存储元素数量/哈希表容量 # 默认值0.75当插入元素后如果负载因子大于预设值哈希表会进行扩容。扩容通常创建一个更大如原容量的2倍的新数组并重新分配所有元素。当元素减少时负载因子低于预设的下限例如0.25或0.1时哈希表可能进行缩容以节省空间。哈希表会重复吗?那么hashmap会重复吗?哈希表理论上可以重复。hashmap不会重复不是说生成hash时不会重复而是如果重复了就替换该值为最新对象所以从使用角度来说hashmap是不会重复的。java实现部分栈和队列的实现1、最原始的栈是stack# 有缺点、性能低、本质上是一个锁2、最原始的队列是LinkedList# 兼容队列和栈的功能3、推荐的栈和队列是ArrayDeque# 兼容队列和栈的功能Stack(栈)已不推荐使用主要有两点1、强行改变入栈规则2、所有方法都加了synchronized性能差坑点示例强行改变入栈规则。Slf4jpublicclassStackDemo{publicstaticvoidmain(String[]args){StackStringstacknewStack();stack.push(A);stack.push(B);stack.push(C);log.info(stack{},JSON.toJSONString(stack));Stringbottomstack.get(0);System.out.println(强行拿到栈底元素bottom);// 输出: A!stack.add(0,违规插入);log.info(stack{},JSON.toJSONString(stack));}}LinkedList(链表、堆栈)有人可能感到奇怪LinkedList不是链表吗怎么放到这里来了?linkedList的两大业务场景1、作为链表 # 解决list增删效率低的问题2、因为双向链表天然支持在两端进行增删操作所以被java收编实现了Deque接口也就是说兼容了栈和队列的能力ArrayDeque注意这个词Deque(double-ended queue)(双端队列)。其他哈希表相关文档HashMap是如何实现的(底层原理)以及面试 常见问题 # 场景比较全深入解析双向链表LinkedList的实现与应用 # 说的比较详细