单向链表

1. 单向链表简介

单向链表是链表结构的一种, 它会将一块区域划分为两个部分, 一部分用来存储数据, 另一部分用来存储下一个数据的位置, 这样就构成了一个单向链表

2. 单向链表的算法实现

数据的操作最常见的就是增删改查, 所以这里自定义一个链表结构来实现这四个方法的算法,有的人看到算法可能会觉得很难, 但实际上算法并没有所想象的那么复杂, 算法都是来源于现实生活的, 只是用编程语言更为简单的将其实现

2.1 链表的结构

链表Link的所有数据都是存储在节点之中, 并且这个节点能够指向下一个节点, 所以说我们需要创建一个类Node, 这个类中至少要有两个属性, 一个用来存放数据data, 另一个用来指向下一个节点next

(1) Node类

回顾java中的LinkedList集合, 我们在操作这个集合的时候, 无论增删改查, 都是只考虑了数据而不

需要考虑节点和节点之间的关系. 所以说我们应该创建一个Link类用提供给使用者, 使用者只需要通过Link类来对数据进行操作, 而不需要关心其它,

并且Node节点是属于Link链表特有的, 不应当被其它类所操作, 所以Node类应该是Link的内部类

(2) data和next属性

data数据应当能够存储任何类型的数据, 所以应该是Object的, 而next属性能够指向下一个节点, 所以next就必须是Node类型

2.2 add方法

每当链表往里面添加一个数据的时候, 就是创建了一个新的节点,  所以在add方法中需要创建一个新的Node对象

这时我们的数据已经添加成功, 但是仅仅这样还不够, 因为每个Node节点之间没有任何联系, 这样连最基本的结构都不算, 更不用说链表了. 那么我们就必须考虑这些节点相互之间的关系问题,

数据和数据之间本身是不会有任何顺序的, 编程中所谓的有序只是人为的对数据进行了操作或封装,如果我们现实生活中, 有三个人”张三”, “李四”, “王五”, 我们想让他们站队该如何操作? 我们能否随便找一个人站第一, 其余两个人随便往第一个人的后面站?

这里有一个非常重要的概念-----first, 链表中的首节点非常的重要, 有了首节点就能够让我们对链表操作方便很多, 如果首节点不存在, 那么整个链表也不应该存在, 如上图所示, ”张三”就是这个首节点

而哪一个节点是首节点, Node本身是应该不知道的, Node应该只关心数据data和下一个Node的位置next, 而Link持有每一个Node节点, 所以到底谁是first, Link应该知道, 所以我们就要在Link中创建一个全局变量first, 用来记录首节点

我们可以将使用者第一次调用add()方法时所创建的节点作为首节点first

但是如果首节点已经存在了, 该怎么办? 在现实生活中, 如果我们让张三, 已经站好了, 此时来了李四, 那么李四站在什么位置, 只需要问问张三, 看看后面有没有人, 如果没有人, 那么就站在张三后面, 如果有人了, 那么继续向后走, 直到某个人后面是空的即可,并且谁后面是空的, 应该交给Node本身来判断

传递到下一个节点后, 让下一个节点继续判断后面是否为空, 如果为空, 就让新的节点放在当前节点的后面, 如果不为空, 就继续向后判断

此时, add方法已经实现完毕, 但是怎么知道是否添加成功? 接下来要实现get()方法, 如果能够获取到里面的每个元素, 那么就是添加成功

2.3 size()和get()方法

2.3.1 size()

对于size方法, 实现起来很简单, 只需要一个计数的变量, 当添加一个新的节点时, 让该计数器自增1, 当移除一个节点时, 该计数器自减1, 再定义一个size()方法将这个计数器返回即可.

2.3.2 get()方法

平时使用Java的LinkedList中的get方法, 需要传递一个下标, 根据下标来查找到对应位置的数据, 所以这个get方法参数应该能接收一个下标, 返回一个数据

接下来是相关算法实现, 在日常生活中我们要在一队人里面找到某个位置上的人, 我们可以让这支队伍的第一个人开始报数, 等报到我们要找到的那个数字时, 就是我们要找的目标

算法实现也是这样, 我一是要有目标位置, 二是要能够向下报数

此时get()方法基本完成, 可以和add()方法共同测试

2.4 set()方法

set()和get()方法很类似, 我们需要通过下标来找到需要修改的节点数据的位置, 再将新的data赋值给当前节点的data即可

此时, set()方法已经实现, 进行方法测试

2.5 remove()方法

如果我们要删除一个数据, 那么我们可以根据下标进行删除

加入我们一支队伍中, 要让某个人离队, 如果这个人是第一个人, 也就是首节点, 如果没有首节点我们操作链表会很不方便, 所以必须要有另一个人来代替他站在首节点的位置, 此时只需要首节点所记录的后面的那个人, 成为首节点即可

如果不是第一个人离队, 那么就继续向后查找, 直到找到目标位置, 让目标位置的人离队, 并且需要让目标位置的前一个人改变next, 改为指向目标位置的后面那个人

此时, remove方法基本实现, 在Test测试类中测试

3. 优化

我们的Link链表大体上实现了, 现在可以做少部分的优化

3.1 增加边界判断

我们现在的链表有很多都是基于下标的操作, 而在实际操作中, 当使用者传入一个不存在的下标位置时, 应该抛出下标越界异常,

对于下标的边界位置条件应当满足 大于0 小于等于size

此处拿get()方法举例:

分别对边界进行测试

3.2 将数据类型转换为泛型

如果不使用泛型, 那么可以往里面添加任何类型的数据, 添加起来很方便, 但是取的时候就不知道该用什么样的类型接收

所以我们可以将Node节点中的数据data的数据类型改为泛型的类型

单向链表

1. 单向链表简介

单向链表是链表结构的一种, 它会将一块区域划分为两个部分, 一部分用来存储数据, 另一部分用来存储下一个数据的位置, 这样就构成了一个单向链表

2. 单向链表的算法实现

数据的操作最常见的就是增删改查, 所以这里自定义一个链表结构来实现这四个方法的算法,有的人看到算法可能会觉得很难, 但实际上算法并没有所想象的那么复杂, 算法都是来源于现实生活的, 只是用编程语言更为简单的将其实现

2.1 链表的结构

链表Link的所有数据都是存储在节点之中, 并且这个节点能够指向下一个节点, 所以说我们需要创建一个类Node, 这个类中至少要有两个属性, 一个用来存放数据data, 另一个用来指向下一个节点next

(1) Node类

回顾java中的LinkedList集合, 我们在操作这个集合的时候, 无论增删改查, 都是只考虑了数据而不

需要考虑节点和节点之间的关系. 所以说我们应该创建一个Link类用提供给使用者, 使用者只需要通过Link类来对数据进行操作, 而不需要关心其它,

并且Node节点是属于Link链表特有的, 不应当被其它类所操作, 所以Node类应该是Link的内部类

(2) data和next属性

data数据应当能够存储任何类型的数据, 所以应该是Object的, 而next属性能够指向下一个节点, 所以next就必须是Node类型

2.2 add方法

每当链表往里面添加一个数据的时候, 就是创建了一个新的节点,  所以在add方法中需要创建一个新的Node对象

这时我们的数据已经添加成功, 但是仅仅这样还不够, 因为每个Node节点之间没有任何联系, 这样连最基本的结构都不算, 更不用说链表了. 那么我们就必须考虑这些节点相互之间的关系问题,

数据和数据之间本身是不会有任何顺序的, 编程中所谓的有序只是人为的对数据进行了操作或封装,如果我们现实生活中, 有三个人”张三”, “李四”, “王五”, 我们想让他们站队该如何操作? 我们能否随便找一个人站第一, 其余两个人随便往第一个人的后面站?

这里有一个非常重要的概念-----first, 链表中的首节点非常的重要, 有了首节点就能够让我们对链表操作方便很多, 如果首节点不存在, 那么整个链表也不应该存在, 如上图所示, ”张三”就是这个首节点

而哪一个节点是首节点, Node本身是应该不知道的, Node应该只关心数据data和下一个Node的位置next, 而Link持有每一个Node节点, 所以到底谁是first, Link应该知道, 所以我们就要在Link中创建一个全局变量first, 用来记录首节点

我们可以将使用者第一次调用add()方法时所创建的节点作为首节点first

但是如果首节点已经存在了, 该怎么办? 在现实生活中, 如果我们让张三, 已经站好了, 此时来了李四, 那么李四站在什么位置, 只需要问问张三, 看看后面有没有人, 如果没有人, 那么就站在张三后面, 如果有人了, 那么继续向后走, 直到某个人后面是空的即可,并且谁后面是空的, 应该交给Node本身来判断

传递到下一个节点后, 让下一个节点继续判断后面是否为空, 如果为空, 就让新的节点放在当前节点的后面, 如果不为空, 就继续向后判断

此时, add方法已经实现完毕, 但是怎么知道是否添加成功? 接下来要实现get()方法, 如果能够获取到里面的每个元素, 那么就是添加成功

2.3 size()和get()方法

2.3.1 size()

对于size方法, 实现起来很简单, 只需要一个计数的变量, 当添加一个新的节点时, 让该计数器自增1, 当移除一个节点时, 该计数器自减1, 再定义一个size()方法将这个计数器返回即可.

2.3.2 get()方法

平时使用Java的LinkedList中的get方法, 需要传递一个下标, 根据下标来查找到对应位置的数据, 所以这个get方法参数应该能接收一个下标, 返回一个数据

接下来是相关算法实现, 在日常生活中我们要在一队人里面找到某个位置上的人, 我们可以让这支队伍的第一个人开始报数, 等报到我们要找到的那个数字时, 就是我们要找的目标

算法实现也是这样, 我一是要有目标位置, 二是要能够向下报数

此时get()方法基本完成, 可以和add()方法共同测试

2.4 set()方法

set()和get()方法很类似, 我们需要通过下标来找到需要修改的节点数据的位置, 再将新的data赋值给当前节点的data即可

此时, set()方法已经实现, 进行方法测试

2.5 remove()方法

如果我们要删除一个数据, 那么我们可以根据下标进行删除

加入我们一支队伍中, 要让某个人离队, 如果这个人是第一个人, 也就是首节点, 如果没有首节点我们操作链表会很不方便, 所以必须要有另一个人来代替他站在首节点的位置, 此时只需要首节点所记录的后面的那个人, 成为首节点即可

如果不是第一个人离队, 那么就继续向后查找, 直到找到目标位置, 让目标位置的人离队, 并且需要让目标位置的前一个人改变next, 改为指向目标位置的后面那个人

此时, remove方法基本实现, 在Test测试类中测试

3. 优化

我们的Link链表大体上实现了, 现在可以做少部分的优化

3.1 增加边界判断

我们现在的链表有很多都是基于下标的操作, 而在实际操作中, 当使用者传入一个不存在的下标位置时, 应该抛出下标越界异常,

对于下标的边界位置条件应当满足 大于0 小于等于size

此处拿get()方法举例:

分别对边界进行测试

3.2 将数据类型转换为泛型

如果不使用泛型, 那么可以往里面添加任何类型的数据, 添加起来很方便, 但是取的时候就不知道该用什么样的类型接收

所以我们可以将Node节点中的数据data的数据类型改为泛型的类型