arraydeque是更优选择，因其底层为循环数组、o(1)出入队、无节点开销、gc压力小；linkedlist仅在需removefirstoccurrence等特有方法时适用。
Java里BFS用LinkedList还是ArrayDeque？
直接说结论：ArrayDeque是更优选择，除非你要用removeFirstOccurrence这类LinkedList特有方法。它底层是循环数组，入队出队都是O(1)，没有节点对象开销，GC压力小；而LinkedList每个元素都多一个Node包装，BFS动辄上万节点时内存和速度差距明显。
常见错误是照着老教程写new LinkedList()当队列——这没错，但不是最优。尤其在LeetCode刷题或高频图遍历场景下，ArrayDeque能稳定快10%~20%。
-
ArrayDeque不支持null元素，BFS中若节点可能为null（比如树的空子节点），得提前判空再入队 -
LinkedList实现了Queue和Deque，但BFS只用到单端入、单端出，没必要为双端能力买单 - 别用
PriorityQueue代替——那是Dijkstra或A*的节奏，BFS要的是严格层序，它不保证FIFO
如何避免BFS重复访问同一节点？
核心就一条：入队前检查是否已访问过，而不是出队时才标记。否则同一节点可能被多次加入队列，导致超时或逻辑错乱（比如最短路径算错）。
典型场景是无向图遍历或网格走迷宫：visited数组/集合必须和入队动作强绑定。用boolean[][]比HashSet快，坐标可直接映射；如果是复杂对象节点，确保equals/hashCode正确实现。
立即学习“Java免费学习笔记（深入）”；
- 错误写法：
queue.offer(node);然后在while循环里if (visited[node]) continue;——此时node可能已重复入队多次 - 正确顺序：
if (!visited[node]) { visited[node] = true; queue.offer(node); } - 对树结构可省略
visited，但图结构必须有，哪怕是有向图——存在环或多路径到达同一节点
Queue.poll()返回null意味着什么？
只说明队列为空，不代表BFS结束或出错。它本身不是异常信号，而是你控制循环的自然出口。但很多人误把它当异常处理，加了不必要的try-catch或日志报警。
使用场景很明确：BFS主循环就是while ((node = queue.poll()) != null)，或者更常见的while (!queue.isEmpty()) + queue.poll()。前者简洁，后者语义更清晰，且避免null值干扰（比如你真要存null占位，那就只能用后者）。
-
poll()和remove()区别：前者空队列返回null，后者抛NoSuchElementException——BFS里永远选poll() - 别用
element()或peek()来驱动循环，它们不移除元素，会导致死循环 - 如果用
ArrayDeque，注意它不接受null，所以poll()返回null只可能是队列空，不会是存了null
层级信息怎么从BFS队列里安全抽出来？
不能靠计数器硬数，也不能每次循环重建队列。标准解法是记录当前层剩余节点数，用内层for跑完一层再更新层数。
原因很简单：BFS天然按层扩展，但Queue接口不暴露长度变化过程。靠queue.size()动态变，必须在每层开始前“拍快照”，否则边出边入会让size失真。
- 初始化：
int level = 0;，进入while前int size = queue.size(); - 内层循环：
for (int i = 0; i ，里面正常<code>poll()和offer() - for结束后
level++，再取新size进下一轮——这样level和实际层数完全对齐 - 别在for里调
queue.size()判断，那会把下一层新入的节点也算进来
这事看着小，但LeetCode上“二叉树的层序遍历”或“最小基因变化”类题，90%的WA都栽在这一步的层数错位上。
