题目 输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。...示例 1： 输入：head = [1,3,2] 输出：[2,3,1] 限制： 0 <= 链表长度 <= 10000 第一次 //使用栈的特性先进后出 //复杂度O（n） public int[] reversePrint...] = result[i].val; count--; } return resultV2; } 第三种解决方案 //纯O（n）的复杂度
2.4 方法对比 LinkedList 实现了 Queue 接口，在新增、删除、查询等方面增加了很多新的方法，这些方法在平时特别容易混淆，在链表为空的情况下，返回值也不太一样，我们列一个表格，方便大家记录...： 方法含义 返回异常 返回特殊值 底层实现 新增 add(e) offer(e) 底层实现相同 删除 remove() poll(e) 链表为空时，remove 会抛出异常，poll 返回 null。...查找 element() peek() 链表为空时，element 会抛出异常，peek 返回 null。... // 索引位置变化 nextIndex--; return lastReturned.item; } 这里复杂点体现在需要判断 next 不为空和为空的场景...== lastReturned 的场景分析：从尾到头递归顺序，并且是第一次迭代，并且要删除最后一个元素的情况下 // 这种情况下，previous() 方法里面设置了 lastReturned
以下逐一举例：单向链表每个节点只包含一个指向下一个节点的指针，最后一个节点的指针为空（null）。...首先需要做的是把element作为值传入，创建Node项。先来实现第一个场景：向为空的列表添加一个元素。...如果是，就返回它的位置 } index++; // 就继续计数 current = current.next; //检查列表中下一个节点 } return -1; }; 如果列表为空，或是到达列表的尾部...如果没有找到值，就返回-1。检查链表是否为空如果列表中没有元素，isEmpty方法就返回true，否则返回false。...remove(element)：从列表中移除一项。indexOf(element)：返回元素在列表中的索引。如果列表中没有该元素则返回-1。
如果尾节点为空，则队列为空，将首尾节点都指向当前节点。 如果尾节点不为空，证明队列中有其他节点，则将当前尾节点的nextWaiter指向当前节点，将当前节点置为尾节点。...while方法会从首节点顺着等待队列往后寻找waitStatus!=-2的节点，将当前节点的nextWaiter置为空。...如果当前节点的前驱节点为空，代表当前节点为首节点，则将next设置为首节点； 如果不为空，则将前驱节点的nextWaiter指向后继节点。 如果后继节点为空，则直接将前驱节点设置为尾节点。...，返回false；如果当前节点有前驱节点，则证明它在AQS队列中，但是前驱节点为空，说明它是头节点，而头节点是不参与锁竞争的，也返回false。...; } 将等待队列的头结点从等待队列转移到AQS队列中，如果转移失败，说明该节点已被取消，直接返回false，然后将first指向新的头结点重新进行转移。
常见的链表类型有单向链表（单链表），双向链表和循环链表。 以下逐一举例： 单向链表 每个节点只包含一个指向下一个节点的指针，最后一个节点的指针为空（null）。...首先需要做的是把element作为值传入，创建Node项。 先来实现第一个场景：向为空的列表添加一个元素。...如果是，就返回它的位置 } index++; // 就继续计数 current = current.next; //检查列表中下一个节点 } return -1; }; 如果列表为空...如果没有找到值，就返回-1。 检查链表是否为空 如果列表中没有元素，isEmpty方法就返回true，否则返回false。...如果列表中没有该元素则返回-1。 removeAt(position)：从列表的特定位置移除一项。 isEmpty()：如果链表中不包含任何元素，返回true，如果链表长度大于0则返回false。
背景说明 一个系统可为其他系统提供能力或者直接为UI层提供数据，在设计系统测试方案时应考虑上游调用的各种场景，不仅考虑顺利且正向思维操作的场景，还应逆向的场景。...具体来说，例如一个简单的积分充值接口，积分币数量不可空。从系统本身来说，无充值数量此充值单据即无意义。而充值数量会作为积分消费、失效等接口调用的起始数据源依赖。...依次对 必传参数设置为空进行请求，此时接口不可调用成功，无数据生成，同时关注接口返回信息明确性，如果接口返回提示文案为“XX不可为空”一目了然，极大方便定位问题，提高效率。...03 流程节点限制 流程节点限制，即需严格遵守流程流转。当调用某就流程时，必须由上一节点调用。 为何需做流程节点限制？ 支付单系统的流程为流程1：创建、支付完成、支付后的使用，流程2：创建、取消。...测试不合理流程节点下的调用，包含单一流程和交叉流程，观察接口返回及数据状态。例如单据状态为创建时调用使用接口，单据状态为完成时调用取消接口。
链表按此结构对各节点的访问需从链表的头找起，后续节点的地址由当前节点给出。无论在表中访问哪个节点，都需要从链表的头开始，顺序向后查找。链表的尾节点由于无后续节点，其指针域为空，写作为NULL。...3.2 实现 [golang 双向链表] 节点定义 双向链表有两个指针，分别指向前一个节点和后一个节点 链表表头 prev 的指针为空，链表表尾 next 的指针为空 // 链表的一个节点 type ListNode...、表尾进行访问，定义了一个属性 len ，直接可以返回链表的长度，直接查询链表的长度就不用遍历时间复杂度从 O(n) 到 O(1)。...链表的长度 } // 创建一个空链表 func NewList() (list *List) { list = &List{ } return } // 返回链表头节点 func...// 从链表左边取出一个节点 func (l *List) LPop() (node *ListNode) { // 数据为空 if l.len == 0 { return
与siftUp()方法类似，siftDown()方法不断地比较当前节点和它的子节点，并交换它们的位置，直到当前节点小于等于最小的子节点或子节点都为空。...合并多个有序数组：可以将多个有序数组的第一个元素放入PriorityQueue中，并且每次从PriorityQueue中取出最小的元素，直到PriorityQueue为空。...E peek()：返回PriorityQueue中的第一个元素，如果PriorityQueue为空，则返回null。...E poll()：移除并返回PriorityQueue中的第一个元素，如果PriorityQueue为空，则返回null。...boolean remove(Object o)：从PriorityQueue中移除指定元素。 int size()：返回PriorityQueue中的元素个数。
在经典的生产者/消费者模型中，生产者们将生产的元素放入队列，而消费者们从队列获取元素消费 当队列已满，我们会手动阻塞生产者，直到消费者消费再来手动唤醒生产者 当队列为空，我们会手动阻塞消费者，直到生产者生产再来手动唤醒消费者...抛出异常NoSuchElementException 返回值: 队满offer返回false，队空poll返回null 阻塞等待: 队满时put会阻塞线程 或 队空时take会阻塞线程 超时阻塞等待:...**********保证入队、出队操作的原子性，使用两个等待队列存储等待的生产者、消费者，适用于在并发量不大的场景** LinkedBlockingQueue LinkedBlockingQueue从名称上来看...(); //入队的等待队列 private final Condition notFull = putLock.newCondition(); } 从字段中，我们可以知道它使用单向链表的节点...后续首节点会一直指向值为空的虚拟节点 而真实的队头节点实际上是这个虚拟节点的next节点 来看看入队操作 public boolean offer(E e, long timeout, TimeUnit
什么是二叉树 就像是自然界里的树一样，从树干上分出树杈，从树杈到树梢，只不过说二叉树指定的就是每次分出两个杈而已。...node.left = _helper(node.left, val) // 以当前节点左孩子为起点，返回新的左孩子节点 return node // 返回新的节点...val, 返回新的根节点 } } 查 根据二叉搜索树的特性从根节点开始比较，还是逐层进行递归，如果根据规则最后遇到了空节点，那说明这颗树里没有这个节点。...里面的两种场景，将另一边的孩子节点续上即可。...但如果把几种对应场景的应对思路理清楚后，看懂代码和写出对应的逻辑其实并太难。
让我们从底层实现开始深入了解这个强大的数据结构。 linkedList.jpg 底层数据结构 LinkedList的底层数据结构是双向链表。...往前遍历，找到对应索引的节点并返回。...如果要删除的元素是 null，则通过遍历链表找到第一个值为 null 的节点，然后调用 unlink(x) 方法删除该节点。删除成功后返回 true。...如果要删除的元素是 null，则通过遍历链表找到第一个值为 null 的节点，然后调用 unlink(x) 方法删除该节点。删除成功后返回 true。...使用场景 LinkedList适用于以下场景： 频繁的插入和删除操作： 由于链表的节点可以方便地插入和删除，适用于这类操作频繁的场景。
适用于集合元素先入先出和先入后出的场景，在队列源码中被频繁使用。...2.2 删除节点 节点删除的方式和添加类似，我们可以选择从头部删除，也可以选择从尾部删除，删除操作会把节点的值，前后指向节点都置为 null，帮助 GC 进行回收。...**从头部删除** ```java //从头删除节点 f 是链表头节点 private E unlinkFirst(Node f) { // 拿出头节点的值，作为方法的返回值 final...: next.prev; // 索引位置变化 nextIndex--; return lastReturned.item; } ``` 这里复杂点体现在需要判断 next 不为空和为空的场景...的场景分析：从尾到头递归顺序，并且是第一次迭代，并且要删除最后一个元素的情况下 // 这种情况下，previous() 方法里面设置了 lastReturned = next = last,所以
二叉树的遍历 5.1 定义 从根节点出发，按照某种次序访问二叉树中的所有结点，使得每个结点被访问1次 且 只被访问1次 5.2 遍历方式 二叉树的遍历方式包括： 前序遍历（深度优先遍历） 中序遍历 后序遍历...(root); // 步骤4：置当前结点的左孩子为当前节点 // 返回步骤1 root = root.getLeftNode...置当前结点的左孩子为当前节点 // 返回步骤1 root = root.getLeftNode(); }else...置当前结点的右孩子为当前节点 root = root.getRightNode(); // 返回步骤1 }...二叉树的类型 上述讲解的是基础的二叉树 根据不同的需求场景，二叉树分为许多类型，主要有： 下面，我将详细讲解各种二叉树的类型 6.1 线索二叉树 简介 示意图 特别注意 问：如何区别该指针
当队列为空时，head 和 tail 指向同一个节点，该节点的 item 域为 null。 ...poll 方法用于从队列的头部移除一个元素并返回它。...如果 p 是队列的头节点，则直接返回 p 的 item 值。如果 p 的 next 指针为 null，则说明队列已经为空，直接返回 null。...如果当前节点p是头节点，则直接更新头节点的指针。如果p的下一个节点q是null，则说明队列已经为空，直接返回null。...如果添加成功，则返回true，否则返回false。poll()：从队列中弹出一个元素。如果队列为空，则返回null。updateHead(Node h, Node p)：更新头节点指针。
队列中； PROPAGATE，值为-3，表示当前场景下后续的acquireShared能够得以执行； 值为0，表示当前节点在sync队列中，等待着获取锁。...enq(node); return node; } 将构造的同步节点加入到同步队列中 使用链表的方式把该Node节点添加到队列尾部，如果tail的前驱节点不为空（队列不为空），则进行CAS...unparkSuccessor(h); } // 如果头节点对应的线程是空状态，则设置“尾节点对应的线程所拥有的共享锁”为其它线程获取锁的空状态。...，该线程会从LockSupport.parkNanos(Object blocker,long nanos)方法返回）。...因此，在超 时非常短的场景下，同步器会进入无条件的快速自旋。
二叉树的遍历 5.1 定义 从根节点出发，按照某种次序访问二叉树中的所有结点，使得每个结点被访问1次 且 只被访问1次 5.2 遍历方式 二叉树的遍历方式包括： 前序遍历（深度优先遍历） 中序遍历 后序遍历...置当前结点的左孩子为当前节点 // 返回步骤1 root = root.getLeftNode(); }else...置当前结点的右孩子为当前节点 root = root.getRightNode(); // 返回步骤1 }...二叉树的类型 上述讲解的是基础的二叉树 根据不同的需求场景，二叉树分为许多类型，主要有： ? 下面，我将详细讲解各种二叉树的类型 6.1 线索二叉树 简介 ? 示意图 ?...作用 & 应用场景 ? 6.3 平衡二叉排序树（AVL树） 属于 二叉搜索树的一种特殊类型 特点 ? 具体介绍 ? 6.4 红黑树 属于 二叉搜索树的一种特殊类型 ?
，用于从根节点开始递归查找指定键值的节点。...在 _FindR 函数中，首先判断当前节点是否为空，如果为空则表示在当前路径上没有找到指定键值的节点，返回 false。...，用于从根节点开始递归删除指定键值的节点。...首先判断当前节点是否为空，如果为空则表示在当前路径上没有找到指定键值的节点，返回 false。 如果当前节点的键值小于要删除的键值 key，则递归调用 _EraseR 函数在右子树中删除。...copy 函数接收一个节点指针 root，用于递归复制以该节点为根的子树。 首先判断当前节点是否为空，如果为空则返回 nullptr。
如果队列为空则抛出异常 E remove(); // 检索并删除队列的头节点，返回值为删除的队列头节点 // ?...如果队列为空则返回 null E poll(); // 检查但不删除队列头节点 // ?如果队列为空则抛出异常 E element(); // 检查但不删除队列头节点 // ?...如果队列为空则返回 null E peek(); 总结一下 Queue 接口的方法，分为三个大类： 新增元素到队列容器中：add、offer 从队列容器中移除元素：remove、poll 查询队列头节点是否为空...队列入队如上图所示，head 中 item 永为空，last 中 next 永为空 LBQ#offer 也是入队方法，不同的是：如果队列元素已满，则直接返回 false，不阻塞线程 节点出队 LBQ#take...next 后继节点 if (first == null) // 如果后继节点为空，返回 null，否则返回后继节点的 item return null;
阻塞一段时间 一直阻塞 入队（队列满时） add offer返回false offer阻塞超时后返回false put 出队（队列空时） remove poll返回null poll阻塞超时后返回null...remove方法在BlockingQueue的注释里规定如果队列中元素为空，那么抛出空指针异常，而LinkedBlockingQueue在实现的时候，如果元素为空，它返回了false，为了接口中的描述，...遵循队列的FIFO原则，链表头匹配队列头，链表尾匹配队列尾，出队从链表头删除元素，入队从链表尾插入元素。...三、总结 本文通过 LinkedBlockingQueue 的源码，来介绍了下链表阻塞队列，当队列满和空的场景下，入队和出队时，队列有啥变化。...，让消费者慢慢消费；每应用到一个新的场景中，都是一个新的技术工具，所以学好队列，用处很大。
，它采用先进先出的规则对节点进行排序，当我们添加一个元素的时候，它会添加到队列的尾部，当我们获取一个元素时，它会返回队列头部的元素。...底层由单向链表组成，每个节点结构如下所示： 构造函数中，创建了一个空节点作为链表中的第一个Node节点 1.3.1> add 向容器中添加元素，源码如下所示： 关于t !...---- 1.5> BlockingQueue 阻塞队列常用方法 由于使用offer方法时，如果队列已经满了，那么则无法插入成功，会立即返回false；同样的，当我们调用poll方法的时候，如果队列中是空的...---- 1.5.2> LinkedBlockingQueue 构造函数，默认长度为2^31，大概21亿多 ---- ---- 【解释】 在构造函数中，创建一个空的节点，作为整个链表的头节点。...()方法用于那些需要有返回值的场景； runAsync()方法用于没有返回值的场景； 在这两个方法中，都分别有一个方法可以接收一个Executor参数。
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
ICP备案
实时音视频
对象存储
即时通信 IM
