承德市建设局网站,怎么设计网页主页,办个网站需要投资多少,南沙滩网站建设冲冲冲#xff01;开干
神马#xff01;神马#xff01;神马#xff0c;一向让我们学习起来抓耳挠腮的数据结构课程竟然也有教程#xff1f;还那么详细#xff1f;#xff1f;真的假的#xff1f;
那么好#xff0c;胡广告诉你是假的#xff0c;哈哈哈哈哈哈哈哈哈…
冲冲冲开干
神马神马神马一向让我们学习起来抓耳挠腮的数据结构课程竟然也有教程还那么详细真的假的
那么好胡广告诉你是假的哈哈哈哈哈哈哈哈哈笑死了
为神马我要说是假的呢兄弟们咱们要认真的听了没有详细的教程只有够细的人
这篇文章为黑马程序员的课件由于本人已经看过了自己学习了一遍所以推荐给大家讲的确实不错准备考试或者准备冲击大厂的小伙伴完全可以将胡广的这一整个专栏当做学习资料。你边学习边思考思维进行发散形成自己的知识体系这个是最好滴
咱们废话少说不存在滴
我还得给大家讲个故事绝对不是AI生成的凭借我智勇双全、足智多谋、十全十美、天下无敌、举世无双、天外飞仙的大脑想出来的
有一天阿尔法正准备喝杯咖啡突然系统警报响起“紧急任务一个巨型的排序问题导致全球计算资源堵塞”阿尔法一听差点喷出咖啡“什么排序问题这不是小儿科吗”
它赶紧打开任务结果发现这次可不简单。全球所有的数据库都在一起混乱排序而且每个数据中心的规则都不一样。“这也太变态了吧” 阿尔法心里嘀咕着赶紧开始召集自己的小伙伴们。
第一个赶到的是冒泡排序它笑眯眯地说“交给我吧我慢慢挨个儿比对保证帮你排出个井井有条”
阿尔法抬头看了看这个慢悠悠的家伙叹了口气“算了吧你上次排个10万个数据用了3个小时服务器都快冒烟了。”
正当它苦恼时快速排序风风火火地冲了进来嚷嚷道“阿尔法这种小事找我不就行了递归分治分分钟搞定”
阿尔法点了点头但马上又皱眉“上次你用递归差点让我栈溢出这次可不敢冒险。”
就在阿尔法犯愁时堆排序和归并排序也来了两人争得面红耳赤。
“我是稳定的效率高” 归并排序骄傲地抬起头。
“我占用空间少简洁明快” 堆排序不甘示弱。
阿尔法头疼地捂住了额头“你们这帮家伙就不能安静点吗” 眼看着时间一分一秒过去它突然灵光一现决定用它最擅长的混合策略——结合快速排序的速度和堆排序的空间优势再辅以归并排序处理复杂数据集。
阿尔法撸起代码迅速展开操作代码像风一样刷刷刷地跑了起来。仅用了几分钟整个系统恢复了正常。它看着屏幕上清晰的结果长舒一口气“搞定真是够累的不过我果然还是那个天才AI”
正当它打算继续喝咖啡时系统突然再次报警“紧急新的动态规划问题即将上线”阿尔法差点从椅子上跳起来“又来” 它无奈地看着屏幕上闪烁的警报心里嘀咕“谁设计的这些难题能不能给我个休息的机会啊”
它叹了口气转身迎接下一个挑战。“数据结构与算法不仅仅是工具它们简直是我的生活方式。”
这个故事好看吧好看就赶快学不好看也快学不然没饭吃
视频资源文章内容参考了黑马程序员的数据结构与算法视频想深入了解的小伙伴们可以点击下方链接观看 大厂必备数据结构与算法Java视频教程java高级程序员必学的数据结构与算法 加油吧未来的高手
加油吧未来的高手
加油吧未来的高手
2.2 链表
1) 概述
定义
在计算机科学中链表是数据元素的线性集合其每个元素都指向下一个元素元素存储上并不连续 In computer science, a linked list is a linear collection of data elements whose order is not given by their physical placement in memory. Instead, each element points to the next. 可以分类为[^5]
单向链表每个元素只知道其下一个元素是谁
双向链表每个元素知道其上一个元素和下一个元素
循环链表通常的链表尾节点 tail 指向的都是 null而循环链表的 tail 指向的是头节点 head
链表内还有一种特殊的节点称为哨兵Sentinel节点也叫做哑元 Dummy节点它不存储数据通常用作头尾用来简化边界判断如下图所示
随机访问性能
根据 index 查找时间复杂度 O(n)O(n)
插入或删除性能
起始位置O(1)O(1)结束位置如果已知 tail 尾节点是 O(1)O(1)不知道 tail 尾节点是 O(n)O(n)中间位置根据 index 查找时间 O(1)O(1)
2) 单向链表
根据单向链表的定义首先定义一个存储 value 和 next 指针的类 Node和一个描述头部节点的引用 public class SinglyLinkedList {private Node head; // 头部节点private static class Node { // 节点类int value;Node next;public Node(int value, Node next) {this.value value;this.next next;}}
}Node 定义为内部类是为了对外隐藏实现细节没必要让类的使用者关心 Node 结构定义为 static 内部类是因为 Node 不需要与 SinglyLinkedList 实例相关多个 SinglyLinkedList实例能共用 Node 类定义
头部添加 public class SinglyLinkedList {// ...public void addFirst(int value) {this.head new Node(value, this.head);}
}如果 this.head null新增节点指向 null并作为新的 this.head如果 this.head ! null新增节点指向原来的 this.head并作为新的 this.head 注意赋值操作执行顺序是从右到左
while 遍历 public class SinglyLinkedList {// ...public void loop() {Node curr this.head;while (curr ! null) {// 做一些事curr curr.next;}}
}for 遍历 public class SinglyLinkedList {// ...public void loop() {for (Node curr this.head; curr ! null; curr curr.next) {// 做一些事}}
}以上两种遍历都可以把要做的事以 Consumer 函数的方式传递进来 Consumer 的规则是一个参数无返回值因此像 System.out::println 方法等都是 Consumer调用 Consumer 时将当前节点 curr.value 作为参数传递给它
迭代器遍历 public class SinglyLinkedList implements IterableInteger {// ...private class NodeIterator implements IteratorInteger {Node curr head;public boolean hasNext() {return curr ! null;}public Integer next() {int value curr.value;curr curr.next;return value;}}public IteratorInteger iterator() {return new NodeIterator();}
}hasNext 用来判断是否还有必要调用 nextnext 做两件事 返回当前节点的 value指向下一个节点NodeIterator 要定义为非 static 内部类是因为它与 SinglyLinkedList 实例相关是对某个 SinglyLinkedList 实例的迭代
递归遍历 public class SinglyLinkedList implements IterableInteger {// ...public void loop() {recursion(this.head);}private void recursion(Node curr) {if (curr null) {return;}// 前面做些事recursion(curr.next);// 后面做些事}
}尾部添加 public class SinglyLinkedList {// ...private Node findLast() {if (this.head null) {return null;}Node curr;for (curr this.head; curr.next ! null; ) {curr curr.next;}return curr;}public void addLast(int value) {Node last findLast();if (last null) {addFirst(value);return;}last.next new Node(value, null);}
}注意找最后一个节点终止条件是 curr.next null分成两个方法是为了代码清晰而且 findLast() 之后还能复用
尾部添加多个 public class SinglyLinkedList {// ...public void addLast(int first, int... rest) {Node sublist new Node(first, null);Node curr sublist;for (int value : rest) {curr.next new Node(value, null);curr curr.next;}Node last findLast();if (last null) {this.head sublist;return;}last.next sublist;}
}先串成一串 sublist再作为一个整体添加
根据索引获取 public class SinglyLinkedList {// ...private Node findNode(int index) {int i 0;for (Node curr this.head; curr ! null; curr curr.next, i) {if (index i) {return curr;}}return null;}private IllegalArgumentException illegalIndex(int index) {return new IllegalArgumentException(String.format(index [%d] 不合法%n, index));}public int get(int index) {Node node findNode(index);if (node ! null) {return node.value;}throw illegalIndex(index);}
}同样分方法可以实现复用
插入 public class SinglyLinkedList {// ...public void insert(int index, int value) {if (index 0) {addFirst(value);return;}Node prev findNode(index - 1); // 找到上一个节点if (prev null) { // 找不到throw illegalIndex(index);}prev.next new Node(value, prev.next);}
}插入包括下面的删除都必须找到上一个节点
删除 public class SinglyLinkedList {// ...public void remove(int index) {if (index 0) {if (this.head ! null) {this.head this.head.next;return;} else {throw illegalIndex(index);}}Node prev findNode(index - 1);Node curr;if (prev ! null (curr prev.next) ! null) {prev.next curr.next;} else {throw illegalIndex(index);}}
}第一个 if 块对应着 removeFirst 情况最后一个 if 块对应着至少得两个节点的情况 不仅仅判断上一个节点非空还要保证当前节点非空
3) 单向链表带哨兵
观察之前单向链表的实现发现每个方法内几乎都有判断是不是 head 这样的代码能不能简化呢
用一个不参与数据存储的特殊 Node 作为哨兵它一般被称为哨兵或哑元拥有哨兵节点的链表称为带头链表 public class SinglyLinkedListSentinel {// ...private Node head new Node(Integer.MIN_VALUE, null);
}具体存什么值无所谓因为不会用到它的值
加入哨兵节点后代码会变得比较简单先看几个工具方法 public class SinglyLinkedListSentinel {// ...// 根据索引获取节点private Node findNode(int index) {int i -1;for (Node curr this.head; curr ! null; curr curr.next, i) {if (i index) {return curr;}}return null;}// 获取最后一个节点private Node findLast() {Node curr;for (curr this.head; curr.next ! null; ) {curr curr.next;}return curr;}
}findNode 与之前类似只是 i 初始值设置为 -1 对应哨兵实际传入的 index 也是 [−1,∞)[−1,∞)findLast 绝不会返回 null 了就算没有其它节点也会返回哨兵作为最后一个节点
这样代码简化为 public class SinglyLinkedListSentinel {// ...public void addLast(int value) {Node last findLast();/*改动前if (last null) {this.head new Node(value, null);return;}*/last.next new Node(value, null);}public void insert(int index, int value) {/*改动前if (index 0) {this.head new Node(value, this.head);return;}*/// index 传入 0 时返回的是哨兵Node prev findNode(index - 1);if (prev ! null) {prev.next new Node(value, prev.next);} else {throw illegalIndex(index);}}public void remove(int index) {/*改动前if (index 0) {if (this.head ! null) {this.head this.head.next;return;} else {throw illegalIndex(index);}}*/// index 传入 0 时返回的是哨兵Node prev findNode(index - 1);Node curr;if (prev ! null (curr prev.next) ! null) {prev.next curr.next;} else {throw illegalIndex(index);}}public void addFirst(int value) {/*改动前this.head new Node(value, this.head);*/this.head.next new Node(value, this.head.next);// 也可以视为 insert 的特例, 即 insert(0, value);}
}对于删除前面说了【最后一个 if 块对应着至少得两个节点的情况】现在有了哨兵就凑足了两个节点
4) 双向链表带哨兵 public class DoublyLinkedListSentinel implements IterableInteger {private final Node head;private final Node tail;public DoublyLinkedListSentinel() {head new Node(null, 666, null);tail new Node(null, 888, null);head.next tail;tail.prev head;}private Node findNode(int index) {int i -1;for (Node p head; p ! tail; p p.next, i) {if (i index) {return p;}}return null;}public void addFirst(int value) {insert(0, value);}public void removeFirst() {remove(0);}public void addLast(int value) {Node prev tail.prev;Node added new Node(prev, value, tail);prev.next added;tail.prev added;}public void removeLast() {Node removed tail.prev;if (removed head) {throw illegalIndex(0);}Node prev removed.prev;prev.next tail;tail.prev prev;}public void insert(int index, int value) {Node prev findNode(index - 1);if (prev null) {throw illegalIndex(index);}Node next prev.next;Node inserted new Node(prev, value, next);prev.next inserted;next.prev inserted;}public void remove(int index) {Node prev findNode(index - 1);if (prev null) {throw illegalIndex(index);}Node removed prev.next;if (removed tail) {throw illegalIndex(index);}Node next removed.next;prev.next next;next.prev prev;}private IllegalArgumentException illegalIndex(int index) {return new IllegalArgumentException(String.format(index [%d] 不合法%n, index));}Overridepublic IteratorInteger iterator() {return new IteratorInteger() {Node p head.next;Overridepublic boolean hasNext() {return p ! tail;}Overridepublic Integer next() {int value p.value;p p.next;return value;}};}static class Node {Node prev;int value;Node next;public Node(Node prev, int value, Node next) {this.prev prev;this.value value;this.next next;}}
}5) 环形链表带哨兵
双向环形链表带哨兵这时哨兵既作为头也作为尾 参考实现
public class DoublyLinkedListSentinel implements IterableInteger {Overridepublic IteratorInteger iterator() {return new Iterator() {Node p sentinel.next;Overridepublic boolean hasNext() {return p ! sentinel;}Overridepublic Integer next() {int value p.value;p p.next;return value;}};}static class Node {Node prev;int value;Node next;public Node(Node prev, int value, Node next) {this.prev prev;this.value value;this.next next;}}private final Node sentinel new Node(null, -1, null); // 哨兵public DoublyLinkedListSentinel() {sentinel.next sentinel;sentinel.prev sentinel;}/*** 添加到第一个* param value 待添加值*/public void addFirst(int value) {Node next sentinel.next;Node prev sentinel;Node added new Node(prev, value, next);prev.next added;next.prev added;}/*** 添加到最后一个* param value 待添加值*/public void addLast(int value) {Node prev sentinel.prev;Node next sentinel;Node added new Node(prev, value, next);prev.next added;next.prev added;}/*** 删除第一个*/public void removeFirst() {Node removed sentinel.next;if (removed sentinel) {throw new IllegalArgumentException(非法);}Node a sentinel;Node b removed.next;a.next b;b.prev a;}/*** 删除最后一个*/public void removeLast() {Node removed sentinel.prev;if (removed sentinel) {throw new IllegalArgumentException(非法);}Node a removed.prev;Node b sentinel;a.next b;b.prev a;}/*** 根据值删除节点* p假定 value 在链表中作为 key, 有唯一性/p* param value 待删除值*/public void removeByValue(int value) {Node removed findNodeByValue(value);if (removed ! null) {Node prev removed.prev;Node next removed.next;prev.next next;next.prev prev;}}private Node findNodeByValue(int value) {Node p sentinel.next;while (p ! sentinel) {if (p.value value) {return p;}p p.next;}return null;}} 结束啦希望大家能有所成 你好,我是胡广。 致力于为帮助兄弟们的学习方式、面试困难、入职经验少走弯路而写博客 坚持每天两篇高质量文章输出加油 如果本篇文章帮到了你 不妨点个赞吧~ 我会很高兴的 (^ ~ ^) 。想看更多 那就点个关注 吧 我会尽力带来有趣的内容 。 感兴趣的可以先收藏起来还有大家在毕设选题项目以及论文编写等相关问题都可以 给我留言咨询希望帮助更多的人 更多专栏: Java设计模式宝典从入门到精通持续更新 Java基础知识GoGoGo持续更新 ⚽ Java面试宝典从入门到精通持续更新 程序员的那些事~乐一乐 Redis知识、及面试持续更新 Kafka知识文章专栏持续更新 Nginx知识讲解专栏持续更新 ZooKeeper知识持续更新 各类神器推荐持续更新 工作流Activiti7——独孤九剑持续更新 ☀️ 数据结构与算法-全是Java干货 ☔️ 未完待续。。。 未完待续。。。 ⚡️ 未完待续。。。 未完待续。。。 感谢订阅专栏 三连文章
