02-手写链表、栈、队列——不依赖任何集合框架

老程序员回炉补基础二手写链表、栈、队列——不依赖任何集合框架很多程序员用了多年ArrayList、LinkedList却说不出链表插入一个节点需要几步操作。我用 Java 从零实现了三种基础数据结构没有用java.util里的任何一个集合类。一、双向链表Doubly Linked List学习时间2023年8月10日~12日这是我补基础时写的第一个数据结构。节点设计publicclassmNodeT{privateTdata;privateStringname;privatemNodeTpre;// 前驱指针privatemNodeTnext;// 后继指针publicmNode(Tdata){this.datadata;}publicmNode(Stringname,Tdata){this.namename;this.datadata;}// getter/setter 省略...}我选择了双向链表而不是单链表因为双向链表的插入和删除操作更完整也更贴近实际应用。JDK 的LinkedList底层也是双向链表。链表实现publicclassmLinkT{privatemNodeTheadernull;// 头节点privatemNodeTcurrnull;// 当前节点游标publicmLink(Tdata){headernewmNodeT(data);currheader;}// 追加节点publicvoidappend(mNodeTn){curr.setNext(n);n.setPre(curr);currn;// 游标移动到新节点}// 在当前节点前插入publicvoidinsert(mNodeTn){mNodeTprecurr.getPre();if(prenull){headern;n.setNext(curr);curr.setPre(n);}else{pre.setNext(n);n.setNext(curr);n.setPre(pre);curr.setPre(n);}}// 删除当前节点publicvoidremove(){mNodeTprecurr.getPre();mNodeTnextcurr.getNext();if(next!null){next.setPre(pre);currnext;}else{currpre;}if(pre!null){pre.setNext(next);}else{headercurr;}}}设计上的架构师习惯我引入了一个curr游标记录当前操作位置。这样链表就有了当前位置的概念append()在当前节点后面追加insert()在当前节点前面插入remove()删除当前节点这不是教科书上的标准实现但更贴近实际使用场景。很多时候我们需要一个光标在链表中移动而不是每次都从头开始遍历。核心操作图解删除节点最复杂的操作删除前 [A] - [B] - [C] ↑ curr 删除后 [A] - [C] ↑ curr移向 next需要处理三种边界情况删除的是中间节点最普通删除的是头节点pre null需要更新header删除的是尾节点next nullcurr回退到pre二、栈Stack学习时间2023年10月11日节点设计publicclasssNoteT{privateTdata;privatesNoteTnext;publicsNote(Tdata){this.datadata;}// getter/setter 省略...}栈实现publicclassmStackT{privatesNoteTtopnull;// 入栈publicvoidpush(sNoteTn){if(topnull){topn;}else{n.setNext(top);topn;}}// 出栈publicsNoteTpop(){sNoteTtemptop;if(top!null)toptop.getNext();temp.setNext(null);returntemp;}// 判空publicbooleanisNull(){returntopnull;}}我的理解栈是**后进先出LIFO**的数据结构用单链表就能实现而且只需要维护一个top指针push新节点指向当前 toptop 更新为新节点pop取出 toptop 后移一位实现非常简洁但栈的威力在于它的应用场景函数调用栈表达式求值浏览器的前进/后退在后续的树遍历中我用栈来模拟递归非递归中序遍历三、队列Queue学习时间2023年8月11日节点设计publicclassqNodeT{privateTdata;privateqNodeTnext;publicqNode(Tdata){this.datadata;}// getter/setter 省略...}队列实现publicclassmQueueT{privateqNodeTheadernull;// 队头出队端privateqNodeTtailnull;// 队尾入队端privateLongmaxSizeLong.MAX_VALUE;privateLongcurrSize0L;// 入队publicvoidinQueue(qNodeTn)throwsException{if(currSizemaxSize){thrownewException(队列已满!);}if(headernull){headern;tailn;}else{tail.setNext(n);tailn;}currSize;}// 出队publicqNodeToutQueue()throwsException{if(headernull){thrownewException(空队列!);}qNodeTtempheader;headerheader.getNext();currSize--;temp.setNext(null);returntemp;}publicLonggetCurrSize(){returncurrSize;}}我的理解队列是**先进先出FIFO**的数据结构需要维护两个指针header和tailinQueue在 tail 端追加tail 后移outQueue从 header 端取出header 后移我加了一个maxSize限制可以初始化为有界队列。这是一个架构师职业病——在生产环境中无界队列是 OOM 的常见元凶所以习惯性地做了容量限制。队列在后续代码中的复用这个手写的队列在后面的代码中被大量复用图的 BFS广度优先搜索用队列逐层遍历顶点树的层序遍历用队列按层输出节点拓扑排序入度为0的顶点入队逐个出队处理这验证了一个道理基础数据结构是上层算法的基石。三种数据结构对比结构操作特点核心指针典型应用双向链表双向遍历、插入、删除header currLRU缓存、浏览器历史栈后进先出LIFOtop函数调用栈、递归模拟队列先进先出FIFOheader tailBFS、任务调度从这些基础结构看架构选型作为架构师理解这些底层结构直接影响技术选型为什么ArrayList的随机访问是 O(1)而LinkedList是 O(n)因为数组有连续内存索引计算链表需要从头遍历。为什么LinkedList的头插入是 O(1)而ArrayList是 O(n)因为链表只需要改指针数组需要移动后面所有元素。为什么消息队列用队列而不是栈因为消息需要按顺序消费后进先出会导致老消息饿死。为什么递归会 StackOverflow因为函数调用栈是有限的每次递归都会压栈不退出就会溢出。这些问题的答案不在任何框架的文档里而在数据结构的基础知识里。下一篇预告《老程序员回炉补基础三二叉树——从递归遍历到非递归实现》