摘要:一前言最近在回顾数据结构与算法,有部分的算法题用到了栈的思想,说起栈又不得不说链表了。
一、前言
最近在回顾数据结构与算法,有部分的算法题用到了栈的思想,说起栈又不得不说链表了。数组和链表都是线性存储结构的基础,栈和队列都是线性存储结构的应用~
本文主要讲解单链表的基础知识点,做一个简单的入门~如果有错的地方请指正
二、回顾与知新说起链表,我们先提一下数组吧,跟数组比较一下就很理解链表这种存储结构了。
2.1回顾数组数组我们无论是C、Java都会学过:
数组是一种连续存储线性结构,元素类型相同,大小相等
数组的优点:
存取速度快
数组的缺点:
事先必须知道数组的长度
插入删除元素很慢
空间通常是有限制的
需要大块连续的内存块
插入删除元素的效率很低
2.2链表说明看完了数组,回到我们的链表:
链表是离散存储线性结构
n个节点离散分配,彼此通过指针相连,每个节点只有一个前驱节点,每个节点只有一个后续节点,首节点没有前驱节点,尾节点没有后续节点。
链表优点:
空间没有限制
插入删除元素很快
链表缺点:
存取速度很慢
链表相关术语介绍,我还是通过上面那个图来说明吧:
确定一个链表我们只需要头指针,通过头指针就可以把整个链表都能推导出来了~
链表又分了好几类:
单向链表
一个节点指向下一个节点
双向链表
一个节点有两个指针域
循环链表
能通过任何一个节点找到其他所有的节点,将两种(双向/单向)链表的最后一个结点指向第一个结点从而实现循环
操作链表要时刻记住的是:
节点中指针域指向的就是一个节点了!
三、Java实现链表算法:
遍历
查找
清空
销毁
求长度
排序
删除节点
插入节点
ps:我将head节点定义在成员变量上:
private static Node head = new Node();
首先,我们定义一个类作为节点
数据域
指针域
为了操作方便我就直接定义成public了。
public class Node { //数据域 public Integer data; //指针域,指向下一个节点 public Node next; public Node() { } public Node(int data) { this.data = data; } public Node(int data, Node next) { this.data = data; this.next = next; } }3.1创建链表(增加节点)
向链表中插入数据:
找到尾节点进行插入
即使头节点.next为null,不走while循环,也是将头节点与新节点连接的(我已经将head节点初始化过了,因此没必要判断头节点是否为null)~
/** * 向链表添加数据 * * @param value 要添加的数据 */ public static void addData(int value) { //初始化要加入的节点 Node newNode = new Node(value); //临时节点 Node temp = head; // 找到尾节点 while (temp.next != null) { temp = temp.next; } // 已经包括了头节点.next为null的情况了~ temp.next = newNode; }3.2遍历链表
上面我们已经编写了增加方法,现在遍历一下看一下是否正确~~~
从首节点开始,不断往后面找,直到后面的节点没有数据:
/** * 遍历链表 * * @param head 头节点 */ public static void traverse(Node head) { //临时节点,从首节点开始 Node temp = head.next; while (temp != null) { if (temp.data != null) { System.out.println("关注公众号Java3y:" + temp.data); } //继续下一个 temp = temp.next; } }
结果:
3.3插入节点插入一个节点到链表中,首先得判断这个位置是否是合法的,才能进行插入~
找到想要插入的位置的上一个节点就可以了~
/** * 插入节点 * * @param head 头指针 * @param index 要插入的位置 * @param value 要插入的值 */ public static void insertNode(Node head, int index, int value) { //首先需要判断指定位置是否合法, if (index < 1 || index > linkListLength(head) + 1) { System.out.println("插入位置不合法。"); return; } //临时节点,从头节点开始 Node temp = head; //记录遍历的当前位置 int currentPos = 0; //初始化要插入的节点 Node insertNode = new Node(value); while (temp.next != null) { //找到上一个节点的位置了 if ((index - 1) == currentPos) { //temp表示的是上一个节点 //将原本由上一个节点的指向交由插入的节点来指向 insertNode.next = temp.next; //将上一个节点的指针域指向要插入的节点 temp.next = insertNode; return; } currentPos++; temp = temp.next; } }3.4获取链表的长度
获取链表的长度就很简单了,遍历一下,每得到一个节点+1即可~
/** * 获取链表的长度 * @param head 头指针 */ public static int linkListLength(Node head) { int length = 0; //临时节点,从首节点开始 Node temp = head.next; // 找到尾节点 while (temp != null) { length++; temp = temp.next; } return length; }3.5删除节点
删除某个位置上的节点其实是和插入节点很像的, 同样都要找到上一个节点。将上一个节点的指针域改变一下,就可以删除了~
/** * 根据位置删除节点 * * @param head 头指针 * @param index 要删除的位置 */ public static void deleteNode(Node head, int index) { //首先需要判断指定位置是否合法, if (index < 1 || index > linkListLength(head) + 1) { System.out.println("删除位置不合法。"); return; } //临时节点,从头节点开始 Node temp = head; //记录遍历的当前位置 int currentPos = 0; while (temp.next != null) { //找到上一个节点的位置了 if ((index - 1) == currentPos) { //temp表示的是上一个节点 //temp.next表示的是想要删除的节点 //将想要删除的节点存储一下 Node deleteNode = temp.next; //想要删除节点的下一个节点交由上一个节点来控制 temp.next = deleteNode.next; //Java会回收它,设置不设置为null应该没多大意义了(个人觉得,如果不对请指出哦~) deleteNode = null; return; } currentPos++; temp = temp.next; } }3.6对链表进行排序
前面已经讲过了8种的排序算法了【八种排序算法总结】,这次挑简单的冒泡排序吧(其实我是想写快速排序的,尝试了一下感觉有点难.....)
/** * 对链表进行排序 * * @param head * */ public static void sortLinkList(Node head) { Node currentNode; Node nextNode; for (currentNode = head.next; currentNode.next != null; currentNode = currentNode.next) { for (nextNode = head.next; nextNode.next != null; nextNode = nextNode.next) { if (nextNode.data > nextNode.next.data) { int temp = nextNode.data; nextNode.data = nextNode.next.data; nextNode.next.data = temp; } } } }3.7找到链表中倒数第k个节点
这个算法挺有趣的:设置两个指针p1、p2,让p2比p1快k个节点,同时向后遍历,当p2为空,则p1为倒数第k个节点
/** * 找到链表中倒数第k个节点(设置两个指针p1、p2,让p2比p1快k个节点,同时向后遍历,当p2为空,则p1为倒数第k个节点 * * @param head * @param k 倒数第k个节点 */ public static Node findKNode(Node head, int k) { if (k < 1 || k > linkListLength(head)) return null; Node p1 = head; Node p2 = head; // p2比怕p1快k个节点 for (int i = 0; i < k - 1; i++) p2 = p2.next; // 只要p2为null,那么p1就是倒数第k个节点了 while (p2.next != null) { p2 = p2.next; p1 = p1.next; } return p1; }3.8删除链表重复数据
这里之前有问题,大家可以到:https://blog.csdn.net/ifollow...
进行参考
3.9查询链表的中间节点这个算法也挺有趣的:一个每次走1步,一个每次走两步,走两步的遍历完,然后走一步的指针,那就是中间节点
/** * 查询单链表的中间节点 */ public static Node searchMid(Node head) { Node p1 = head; Node p2 = head; // 一个走一步,一个走两步,直到为null,走一步的到达的就是中间节点 while (p2 != null && p2.next != null && p2.next.next != null) { p1 = p1.next; p2 = p2.next.next; } return p1; }3.10通过递归从尾到头输出单链表
/** * 通过递归从尾到头输出单链表 * * @param head 头节点 */ public static void printListReversely(Node head) { if (head != null) { printListReversely(head.next); if (head.data != null) { System.out.println(head.data); } } }3.11反转链表
/** * 实现链表的反转 * * @param head 链表的头节点 */ public static Node reverseList(Node head) { Node pre = null; Node cur = head; while (cur != null) { Node next = cur.next; cur.next = pre; pre = cur; cur = next; } return pre; } // 翻转完,使用下面的代码进行遍历吧: public static void traverse4Reverse(Node head) { //临时节点,从首节点开始 Node temp = head; while (temp != null) { if (temp.data != null) { System.out.println("关注公众号Java3y:" + temp.data); } //继续下一个 temp = temp.next; } }
反转链表参考自:
http://www.cnblogs.com/hanxue112253/p/8533426.html
四、最后理解链表本身并不难,但做相关的操作就弄得头疼,head.next next next next ....(算法这方面我还是薄弱啊..脑子不够用了.....)写了两天就写了这么点东西...
操作一个链表只需要知道它的头指针就可以做任何操作了
添加数据到链表中
遍历找到尾节点,插入即可(只要while(temp.next != null),退出循环就会找到尾节点)
遍历链表
从首节点(有效节点)开始,只要不为null,就输出
给定位置插入节点到链表中
首先判断该位置是否有效(在链表长度的范围内)
找到想要插入位置的上一个节点
将原本由上一个节点的指向交由插入的节点来指向
上一个节点指针域指向想要插入的节点
获取链表的长度
每访问一次节点,变量++操作即可
删除给定位置的节点
首先判断该位置是否有效(在链表长度的范围内)
找到想要插入位置的上一个节点
将原本由上一个节点的指向后面一个节点
对链表进行排序
使用冒泡算法对其进行排序
找到链表中倒数第k个节点
设置两个指针p1、p2,让p2比p1快k个节点,同时向后遍历,当p2为空,则p1为倒数第k个节点
删除链表重复数据
操作跟冒泡排序差不多,只要它相等,就能删除了~
查询链表的中间节点
这个算法也挺有趣的:一个每次走1步,一个每次走两步,走两步的遍历完,然后走一步的指针,那就是中间节点
递归从尾到头输出单链表
只要下面还有数据,那就往下找,递归是从最后往前翻。
反转链表
有递归和非递归两种方式,我觉得是挺难的。可以到我给出的链接上查阅~
PS:每个人的实现都会不一样,所以一些小细节难免会有些变动,也没有固定的写法,能够实现对应的功能即可~
参考资料:
http://www.cnblogs.com/whgk/p/6589920.html
https://www.cnblogs.com/bywallance/p/6726251.html
如果文章有错的地方欢迎指正,大家互相交流。习惯在微信看技术文章,想要获取更多的Java资源的同学,可以关注微信公众号:Java3y
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/71055.html
摘要:线程不安全底层数据结构是链表。的默认初始化容量是,每次扩容时候增加原先容量的一半,也就是变为原来的倍删除元素时不会减少容量,若希望减少容量则调用它不是线程安全的。 前言 声明,本文用得是jdk1.8 前一篇已经讲了Collection的总览:Collection总览,介绍了一些基础知识。 现在这篇主要讲List集合的三个子类: ArrayList 底层数据结构是数组。线程不安全 ...
摘要:接口在类库中有很多具体的实现。接口的意义是为各种具体的集合提供了最大化的统一操作方式。集合类框架的基本接口代表一组对象,每一个对象都是他的子元素不包含重复元素的有序的,可以包含重复元素将映射到的对象,不能重复。 写在之前: 这篇文章是自己面试过程中,总结出来的关于Java集合类的总结。每次面试之前来出来看看,速度快,也能很迅速的回忆一些细节问题。发布这篇文章,不仅仅是希望大家临阵磨枪,...
摘要:面试总结最近两周面试了几家公司高级工程师的职位,主要有宜信网信金融阿里高德口袋购物。目前有部分公司已经面试通过,两家在等消息。今天趁热把常见面试内容总结一下。可以用来完成统一命名服务状态同步服务集群管理分布式应用配置项等管理工作。 面试总结 最近两周面试了几家公司Java高级工程师的职位,主要有宜信、网信金融、阿里高德、口袋购物。目前有部分公司已经面试通过,两家在等消息。今天趁热把常见...
摘要:实现移除给定的元素要移除的元素返回值表示移除成功方法说明移除单向链表中某个位置的元素。的前端乐园原文链接寒假前端学习学习数据结构与算法二链表 本系列的第一篇文章: 学习JavaScript数据结构与算法(一),栈与队列第二篇文章:学习JavaScript数据结构与算法(二):链表第三篇文章:学习JavaScript数据结构与算法(三):集合第四篇文章:学习JavaScript数据结构与...
阅读 1263·2023-04-25 15:21
阅读 2645·2021-11-24 10:23
阅读 3383·2021-10-11 10:59
阅读 3221·2021-09-03 10:28
阅读 1709·2019-08-26 13:45
阅读 2290·2019-08-26 12:11
阅读 898·2019-08-26 12:00
阅读 1689·2019-08-26 10:44