【数据结构和算法】001 单链表 LinkedList
2020-03-29 16:06:26来源:博客园 阅读 ()
【数据结构和算法】001 单链表 LinkedList
小朋友,你是否有很多问号?为什么?别人都在看漫画,而我在学画画,对着钢琴说话...
一、单链表(LinkedList)介绍和内存布局
链表是有序的列表,它在内存中的实际存储结构如下:
看上去虽然无序,但ta是靠每个链表节点元素的 地址 和 next域 来分清首尾相连的顺序,如下图所示,由头指针指向第一个元素,进而第二个、三个...
链表的逻辑结构:
二、单链表创建、遍历实现以及单链表节点增、删、改、查操作
1、创建、新增、遍历显示
模型如下:1)head节点 2)中间节点 3)尾结点
每个节点的next域指向下一个节点的对象地址,尾结点为空
新建所需实体类:
package ...; /** * @Author: ldk * @Date: 2020/3/29 21:18 * @Describe: */ public class HeroNode { public int no; public String name; public String nickName; public HeroNode next;//指向下一个节点 //构造节点对象 public HeroNode(int no, String name, String nickName) { this.no = no; this.name = name; this.nickName = nickName; } //重写toString() @Override public String toString() { return "HeroNode{" + "no=" + no + ", name='" + name + '\'' + ", nickName='" + nickName + '\'' + '}'; }
//GetSet方法自行脑补....
}
创建 SingleLinkedList 类,编写 添加 和 遍历 的方法 并 创建main方法测试:
package ...; /** * @Author: ldk * @Date: 2020/3/29 21:25 * @Describe: */ public class LinkedListTest { public static void main(String[] args) { HeroNode h1 = new HeroNode(1, "张三", "小三"); HeroNode h2 = new HeroNode(2, "李四", "小四"); HeroNode h3 = new HeroNode(3, "王五", "小五"); HeroNode h4 = new HeroNode(4, "赵六", "小六"); SingleLinkedList singleLinkedList = new SingleLinkedList(); singleLinkedList.add(h1); singleLinkedList.add(h2); singleLinkedList.add(h3); singleLinkedList.add(h4); singleLinkedList.detail(); } static class SingleLinkedList { //创建头结点 private HeroNode head = new HeroNode(0, "", ""); //节点添加方法 public void add(HeroNode heroNode) { //拿到头结点 HeroNode temp = head; //找到最后一个节点,把next域指向要添加的节点 while (true) { if (temp.next == null) { break; } temp = temp.next; } temp.next = heroNode; } //显示链表【遍历】 public void detail() { if (head.next == null) { System.out.println("链表为空!"); return; } //获取一个临时指针 HeroNode temp = head.next; while (true) { if (temp.next == null){ System.out.println(temp.toString()); System.out.println("就这么多了~~"); break; } System.out.println(temp.toString()); temp = temp.next; } } } }
运行结果:
2、按顺序插入节点
上面的测试是从1,2,3,4依次插入,那么,链表本身是有序的,我们能不能按照no字段乱序插入实现自动递增排序,且从重复元素不再重复插入,
意思就是,插入顺序改成1432,但链表内部结构依然是1234
代码只需稍微对add()方法修改一下:
//按照字段no 升序插入 public void add2(HeroNode heroNode) { //获取指针 HeroNode temp = head; while (true) { if (temp.next == null) { break; } else if (temp.next.no == heroNode.no) { System.out.println("该节点已经存在~"); return; } else if (temp.next.no > heroNode.no) { break; } temp = temp.next; } heroNode.next = temp.next; temp.next = heroNode; }
凌乱且重复的插入顺序:
有序的打印结果:
依然是1234的顺序,而且重复的元素不再插入 ~
其余增删改查有时间可以做自己思考一下,这里不再赘述。
三、单链表新浪、腾讯、百度面试题
解答暂时值分析思路,代码后期慢慢填补:
1)思路:从头结点的下一个开始,一直遍历,每遍历一个即+1,直到.next为空,此所得即为链表长度
2)思路:依然是遍历,从第一个一直遍历到第length-k的下一个即为k
代码(后补):
3)思路:有点难度,但也是很清晰的。
分为母链和子链,母链双指针,子链单指针
母链拆一个节点拼接到子链头部后第一个,以此类推,得到的全新子链即为反转链:
代码(后补):
4)思路:同4,反转后,打印即可。
5)思路:以其中一个链表为母链,另一个为子链,遍历子链,挨个插入母联即可。
2020-03-29 21:02:13
原文链接:https://www.cnblogs.com/dk1024/p/12594782.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- DES/3DES/AES 三种对称加密算法实现 2020-06-11
- 数据结构:用实例分析ArrayList与LinkedList的读写性能 2020-06-04
- 终于有人把最适合学习算法的书单找出来了,面试必备! 2020-06-03
- 基础排序算法(附加java实现) 2020-06-02
- 终于有人把最适合学习算法的书单找出来了,面试必备! 2020-05-29
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash