数据结构与算法之美——单链表复习
2022/1/29 17:34:54
本文主要是介绍数据结构与算法之美——单链表复习,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
1、课程内容
详情可参考“极客时间”上的《数据结构与算法之美》课程:07 | 链表(下):如何轻松写出正确的链表代码? (geekbang.org)
2、课后练习
代码:
结点
package dataStruct; /** * @ClassName Node * @Version 1.0 * @Author Wulc * @Date 2022-01-28 10:54 * @Description 链表结点 */ public class Node<T> { //数据信息 public T data; //下一个节点引用 public Node next; public Node(T data) { this.data = data; } //添加节点 public void add(T data) { if (this.next == null) { this.next = new Node(data); } else { this.next.add(data); } } //添加节点 public void add(Node node) { if (this.next == null) { this.next = node; } else { this.next.add(node); } } }
链表:
package dataStruct; import java.util.ArrayList; import java.util.List; /** * @ClassName ListNode * @Version 1.0 * @Author Wulc * @Date 2022-01-28 10:54 * @Description 链表 */ public class ListNode<T> { //根结点位置 public int foot; //链表长度 public int length; //当前结点 public Node root; //头结点 public Node head; public ListNode() { this.head = new Node("Head"); } //判断链表是否为空 public boolean isEmpty() { if (length == 0 || this.root == null) { return true; } else { return false; } } //判断链表是否包含某个数值 public boolean contain(T data) { Node cur = this.head.next; while (cur != null) { if (cur.data.equals(data)) { return true; } cur = cur.next; } return false; } //判断链表是否包含某个结点 public boolean contain(Node node) { Node cur = this.head.next; while (cur != null) { if (cur == node) { return true; } cur = cur.next; } return false; } //获取链表的长度 public int size() { return this.length; } //添加结点 public void addNode(T data) { if (this.isEmpty()) { this.root = new Node(data); //头结点的下一个结点为链表的第一个结点 this.head.next = this.root; } else { this.root.add(data); } this.length++; } //添加结点 public void addNode(Node node) { if (this.isEmpty()) { this.root = node; //头结点的下一个结点为链表的第一个结点 this.head.next = this.root; } else { this.root.add(node); } this.length++; } //输出链表 public Object[] print() { Object obj[] = new Object[this.length]; int i = 0; //从第一个链表结点开始遍历 this.root = this.head.next; while (this.root != null) { obj[i++] = this.root.data; this.root = this.root.next; } this.root = this.head.next; return obj; } //单链表反转:只要把链表上每个结点的next指针指向其前驱结点即可完成单链表反转 public void reserve() { Node pre = null, next = null; this.root = this.head.next; while (this.root != null) { next = this.root.next; if (next == null) { //确保头结点的next指向链表的第一个结点 this.head.next = this.root; } this.root.next = pre; pre = this.root; this.root = next; } } //链表中环的检测一:快慢指针法,慢指针和快指针如果相遇了,则有环,如果不相遇则无环 public boolean ifHasLoopV() { //p1是慢指针,一次步进一格 Node p1 = this.head.next; //p2是快指针,一次步进二格 Node p2 = this.head.next.next; int i = 0; while (p1 != null && p2 != null) { if (p1 == p2) { return true; } if (p2.next.next == null) { return false; } p1 = p1.next; p2 = p2.next.next; } return true; } //链表中环的检测一:足迹法,遍历链表,如果重复遍历了某个结点,则有环 public boolean ifHasLoopV1() { List<Node> list = new ArrayList<>(); Node cur = this.head.next; while (cur != null) { if (list.contains(cur)) { return true; } list.add(cur); cur = cur.next; } return false; } //两个有序的链表合并(降序),将当前链表与参数链表合并成一个新的链表 public ListNode mergeSortedLinkList(ListNode listNode) { ListNode tListNode = new ListNode(); this.root = this.head.next; while (this.root != null && listNode.root != null) { if (this.root.data.toString().compareTo(listNode.root.data.toString()) < 0) { tListNode.addNode(new Node(this.root.data)); this.root = this.root.next; } else { tListNode.addNode(new Node(listNode.root.data)); listNode.root = listNode.root.next; } } while (this.root != null) { tListNode.addNode(new Node(this.root.data)); this.root = this.root.next; } while (listNode.root != null) { tListNode.addNode(new Node(listNode.root.data)); listNode.root = listNode.root.next; } return tListNode; } //删除链表倒数第 n 个结点:快慢指针法 public void removeLastN(int n) { if (n == length) { this.head.next = this.root.next; this.length--; } if (n < length) { Node p1 = this.head; Node p2 = this.head; int i = 0; while (i < n) { p2 = p2.next; i++; } while (p2 != null) { p1 = p1.next; p2 = p2.next; if (p2.next == null) { this.root = p1; //删除倒数第n个结点 this.root.next = p1.next.next; this.length--; break; } } } } //求链表的中间结点 public Node getMiddleNode() { int i = 0; this.root = this.head.next; if (this.length % 2 == 1) { while (i++ < this.length / 2) { this.root = this.root.next; } } else { while (i++ < this.length / 2 - 1) { this.root = this.root.next; } } return this.root; } }
3、总结
因为临近过年,比较闲,于是就用公司给的点数去买了极客时间上的《数据结构与算法之美》的课程。旨在巩固一下基础,提升代码能力和逻辑思维能力。
除了大二上数据结构课程时手动写过一些链表,之后在做课设,毕设,以及实际开发中,几乎没怎么用过链表。在java中链表结构常见的也就是LinkedList、LinkedHashMap、LinkedHashSet这些。比较笼统的来说加了Linked说明底层的结构添加了链表。
具体一点来说
比如LinkedList和ArrayList
LinkedList的底层数据结构是链表,没有固定大小,无需扩容。插入,删除速度快。
ArrayList的底层数据结构是数组,数组默认长度为10,当存储容量达到三分之二时,自动扩容1.5倍空间(即申请一个原来大小1.5倍的空间,并把原来里面的内容全部拷贝到新的空间去)。因此ArrayList对插入删除操作不太友好,但得益于底层的数组结构有下标索引加成,因此查询速度快。
LinkedHashMap和HashMap
LinkedHashMap是继承自HashMap,但多了一个“双向链表”。因为多了一个“双向链表”,因此LinkedHashMap可以按照元素的插入顺序进行输出(只是输出顺序可以按照插入顺序进行输出),但LinkedHashMap和HashMap的存储结构元素顺序都是一样的,都是按照key进行升序排序,因为LinkedHashMap的put方法同HashMap的put方法。
HashMap的结构是散列表+链表,如下:
HashMap.put()底层实现
LinkedHashMap.put其实和HashMap.put()底层实现原理一样,只不过LinkedHashMap多了一个双向链表存放entry了。
LinkedHashSet和HashSet
首先说明一下HashSet中的值是不可重复的,HashSet底层其实也是用HashMap存储元素的。因为HashSet的add方法调用了HashMap的put方法,HashSet.add的值就是HashMap.put的key,因为HashMap的key不能重复,所以HashSet.add的值就不会重复了。
HashMap保存数据时会根据key去计算一个hashCode值用于决定在散列表中的存储位置,hash值是系统计算的,有一定随机性的,因此HashSet.add的值(相当于hashMap中的key)保存在内存中也是根据hashCode的值无序存放的。
当然这里有个问题就是既然hashSet的值是以key的形式存在hashMap中,但是hashMap中的key是有序的,而hashSet以hashMap key存放在hashMap中的值是无序的?其实这个问题很好解释,就是hashSet只是借用了hashMap的存储结构,但不会去使用到hashMap中相应的key排序优化的算法。因此在hashSet中还是根据hash code进行索引的。
LinkedHashSet继承HashSet,底层使用父类HashSet的LinkedHashMap来保存所有元素,因此LinkedHashSet和LinkedHashMap一样可以按照输入顺序有序输出。
4、参考资料
一文读懂链表反转(迭代法和递归法) - 你是风儿 - 博客园
java实现单链表_congge-CSDN博客_java链表实现
常见链表操作-链表中环的检测(JAVA实现)_wanf425的专栏-CSDN博客_链表中环的检测
搞定面试官(Java)—LinkedList插入更快?ArrayList遍历更快? - 知乎
迭代器是什么 - html中文网
HashSet添加元素过程_cai_ing的博客-CSDN博客_hashset添加元素
浅谈LinkedHashSet(哈希链表)_橙子的博客-CSDN博客_linkedhashset数据结构
java的LinkedHashSet是怎样实现存取有序的, 底层原理是什么_百度知道 (baidu.com)
这篇关于数据结构与算法之美——单链表复习的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-01后台管理开发学习:新手入门指南
- 2024-11-01后台管理系统开发学习:新手入门教程
- 2024-11-01后台开发学习:从入门到实践的简单教程
- 2024-11-01后台综合解决方案学习:从入门到初级实战教程
- 2024-11-01接口模块封装学习入门教程
- 2024-11-01请求动作封装学习:新手入门教程
- 2024-11-01登录鉴权入门:新手必读指南
- 2024-11-01动态面包屑入门:轻松掌握导航设计技巧
- 2024-11-01动态权限入门:新手必读指南
- 2024-11-01动态主题处理入门:新手必读指南