链表(Linked List) 介绍
链表是有序的列表, 但是它在内存中是存入如下
说明:
- 链表是以节点的方式来存储,是链式存储
- 每个节点包含data域:用于存放值, next域:指向下一个节点
- 如图: 发现链表的各个节点不一定是连续存储的
- 链表分带头节点的链表和没有带头节点的链表, 根据实际的需求来确定
- 单链表(带头节点)逻辑结构示意图如下
单链表的应用实例
需求
使用带head头的单向链表实现 - 水浒英雄排行榜管理,完成对英雄人物的增删改查操作, 注: 删除和修改,查找可以考虑独立完成
顺序添加节点
需求
/**
单向链表(带头节点) */ public class SingleLinkedListDemo {
public static void main(String[] args) {
SingleLinkedList singleLinkedList = new SingleLinkedList();// 顺序添加singleLinkedList.addHeroNode(new HeroNode(1, "宋江", "及时雨"));singleLinkedList.addHeroNode(new HeroNode(2, "卢俊义", "玉麒麟"));singleLinkedList.addHeroNode(new HeroNode(3, "吴用", "智多星"));singleLinkedList.addHeroNode(new HeroNode(4, "林冲", "豹子头"));singleLinkedList.showLinkedList();
}
}
/**
定义链表管理节点 */ class SingleLinkedList {
/**
定义头节点, 代表第一个节点,不要动 */ private final HeroNode head = new HeroNode(0, “”, “”);
/**
- 添加节点到链表, 不考虑编号顺序 *
@param next 要添加的节点 */ public void addHeroNode(HeroNode next) { HeroNode tailNode = getTailNode(head); // 在尾部的节点上添加一个节点 tailNode.next = next; }
public void showLinkedList() { showLinkedList(head); }
public void showLinkedList(HeroNode head) { System.out.println(head); if (head.next != null) {
showLinkedList(head.next);} }
/**
- 获取尾部节点 *
- @param headNode 头节点
- @return 尾部节点 */ public HeroNode getTailNode(HeroNode headNode) { return headNode.next == null ? headNode : getTailNode(headNode.next); }
}
/**
节点 / 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; }
@Override public String toString() { return “HeroNode{“ +
"no=" + no + ", name='" + name + '\'' + ", nickName='" + nickName + '\'' + '}';} }
<a name="ZZqKf"></a> ### 测试 ```java HeroNode{no=0, name='', nickName=''} HeroNode{no=1, name='宋江', nickName='及时雨'} HeroNode{no=2, name='卢俊义', nickName='玉麒麟'} HeroNode{no=3, name='吴用', nickName='智多星'} HeroNode{no=4, name='林冲', nickName='豹子头'}带排序的添加节点(插入)
需求
- 第二种方式在添加英雄时, 根据排名将英雄插入到指定位置(如果有这个排名, 则添加失败, 并给出提示)
思路分析示意图
代码实现
```java package com.dance.linkedlist;
/**
单向链表(带头节点) */ public class SingleLinkedListDemo {
public static void main(String[] args) {
SingleLinkedList singleLinkedList = new SingleLinkedList(); ...... // 带排序的添加 singleLinkedList.addHeroNodeByNo(new HeroNode(2, "卢俊义", "玉麒麟")); singleLinkedList.addHeroNodeByNo(new HeroNode(1, "宋江", "及时雨")); singleLinkedList.addHeroNodeByNo(new HeroNode(4, "林冲", "豹子头")); singleLinkedList.addHeroNodeByNo(new HeroNode(3, "吴用", "智多星")); singleLinkedList.showLinkedList();}
}
/**
定义链表管理节点 */ class SingleLinkedList {
……
/**
- 根据编号添加, 需要考虑编号排序问题
- 因为头节点不能动, 因此我们需要一个辅助指针来帮助我们寻找添加的位置
- 因为是单向链表,所以我们的辅助指针需要找到位于要添加节点的上一个节点, 否则没办法插入 *
@param heroNode 要添加的节点 */ public void addHeroNodeByNo(HeroNode heroNode) { try {
HeroNode addBeforeNode = getAddBeforeNode(head, heroNode); heroNode.next = addBeforeNode.next; addBeforeNode.next = heroNode;} catch (Exception e) {
System.out.println(e.getMessage());} }
……
public HeroNode getAddBeforeNode(HeroNode heroNode, HeroNode newVal) { if (heroNode.next == null || heroNode.next.no > newVal.no) {
return heroNode;} if (heroNode.next.no == newVal.no) {
throw new RuntimeException("插入数据失败, 编号已存在: " + heroNode.next);} return getAddBeforeNode(heroNode.next, newVal); }
}
/**
- 节点 */ class HeroNode { …… }
<a name="mJ8uQ"></a>
### 测试
```java
HeroNode{no=0, name='', nickName=''}
HeroNode{no=1, name='宋江', nickName='及时雨'}
HeroNode{no=2, name='卢俊义', nickName='玉麒麟'}
HeroNode{no=3, name='吴用', nickName='智多星'}
HeroNode{no=4, name='林冲', nickName='豹子头'}
节点信息修改
需求
- 先通过遍历找到该节点
- temp.name = newHeroNode.name ;temp.nickName = newHeroNode.nickName
代码实现
```java package com.dance.linkedlist;
/**
单向链表(带头节点) */ public class SingleLinkedListDemo {
public static void main(String[] args) {
SingleLinkedList singleLinkedList = new SingleLinkedList(); ...... // 带排序的添加 singleLinkedList.addHeroNodeByNo(new HeroNode(2, "卢俊义", "玉麒麟")); singleLinkedList.addHeroNodeByNo(new HeroNode(1, "宋江", "及时雨")); singleLinkedList.addHeroNodeByNo(new HeroNode(4, "林冲", "豹子头")); singleLinkedList.addHeroNodeByNo(new HeroNode(3, "吴用", "智多星")); // 修改节点信息 singleLinkedList.updateHeroNodeByNo(new HeroNode(2, "小卢", "倒茶")); singleLinkedList.showLinkedList();}
}
/**
定义链表管理节点 */ class SingleLinkedList {
……
/**
- 修改节点信息 *
@param source 源信息 */ public void updateHeroNodeByNo(HeroNode source){ try {
HeroNode target = getHeroNodeByNo(source.no); // 只允许修改 名称和昵称 target.name = source.name; target.nickName = source.nickName;} catch (Exception e) {
System.out.println(e.getMessage());}
}
……
public HeroNode getHeroNodeByNo(int no) { return getHeroNodeByNo(head, no); }
public HeroNode getHeroNodeByNo(HeroNode heroNode, int no){ if (heroNode == null){
throw new RuntimeException("没有找到对应的节点");} if(heroNode.no == no){
return heroNode;} return getHeroNodeByNo(heroNode.next, no); }
}
/**
- 节点 */ class HeroNode { …… }
<a name="CL6zi"></a>
### 测试
```java
HeroNode{no=0, name='', nickName=''}
HeroNode{no=1, name='宋江', nickName='及时雨'}
HeroNode{no=2, name='小卢', nickName='倒茶'}
HeroNode{no=3, name='吴用', nickName='智多星'}
HeroNode{no=4, name='林冲', nickName='豹子头'}
移除节点
需求
/**
单向链表(带头节点) */ public class SingleLinkedListDemo {
public static void main(String[] args) {
SingleLinkedList singleLinkedList = new SingleLinkedList(); ...... // 带排序的添加 singleLinkedList.addHeroNodeByNo(new HeroNode(2, "卢俊义", "玉麒麟")); singleLinkedList.addHeroNodeByNo(new HeroNode(1, "宋江", "及时雨")); singleLinkedList.addHeroNodeByNo(new HeroNode(4, "林冲", "豹子头")); singleLinkedList.addHeroNodeByNo(new HeroNode(3, "吴用", "智多星")); // 修改节点信息 singleLinkedList.updateHeroNodeByNo(new HeroNode(2, "小卢", "倒茶")); // 移除节点2,4 singleLinkedList.removeHeroNodeByNo(2); singleLinkedList.removeHeroNodeByNo(4); singleLinkedList.showLinkedList();}
}
/**
定义链表管理节点 */ class SingleLinkedList {
……
/**
- 根据编号移除节点
@param no 编号 */ public void removeHeroNodeByNo(int no){ HeroNode removeBeforeHeroNode = getRemoveBeforeHeroNode(no); removeBeforeHeroNode.next = removeBeforeHeroNode.next.next; }
……
public HeroNode getRemoveBeforeHeroNode(int no){ return getRemoveBeforeHeroNode(head, no); }
public HeroNode getRemoveBeforeHeroNode(HeroNode heroNode, int no){ if(heroNode == null){
throw new RuntimeException("没有找到要移除的节点");} if(heroNode.next.no == no){
return heroNode;} return getRemoveBeforeHeroNode(heroNode.next, no); }
}
/**
- 节点 */ class HeroNode { …… }
<a name="BaSG2"></a>
### 测试
```java
HeroNode{no=0, name='', nickName=''}
HeroNode{no=1, name='宋江', nickName='及时雨'}
HeroNode{no=3, name='吴用', nickName='智多星'}
单链表面试题(新浪, 百度, 腾讯)
求单链表中有效节点的个数
package com.dance.linkedlist;
/**
* 单向链表(带头节点)
*/
public class SingleLinkedListDemo {
public static void main(String[] args) {
SingleLinkedList singleLinkedList = new SingleLinkedList();
......
// 带排序的添加
singleLinkedList.addHeroNodeByNo(new HeroNode(2, "卢俊义", "玉麒麟"));
singleLinkedList.addHeroNodeByNo(new HeroNode(1, "宋江", "及时雨"));
singleLinkedList.addHeroNodeByNo(new HeroNode(4, "林冲", "豹子头"));
singleLinkedList.addHeroNodeByNo(new HeroNode(3, "吴用", "智多星"));
......
int nodeSize = singleLinkedList.getNodeSize();
System.out.println("链表中有效节点个数为"+ nodeSize);
}
}
/**
* 定义链表管理节点
*/
class SingleLinkedList {
......
public int getNodeSize(){
return getNodeSize(head);
}
/**
* 获取单链表的有效节点个数, (如果是带头节点,需要不统计头节点)
* @param heroNode 头节点
* @return 节点数据有效个数
*/
public int getNodeSize(HeroNode heroNode){
int count = 0;
if (heroNode.next == null){
return count;
}
HeroNode cursor = heroNode.next;
while (cursor != null){
count++;
cursor = cursor.next;
}
return count;
}
}
/**
* 节点
*/
class HeroNode {
......
}
执行结果:
链表中有效节点个数为4
查询单链表中的倒数第k个节点[新浪面试题]
package com.dance.linkedlist;
/**
* 单向链表(带头节点)
*/
public class SingleLinkedListDemo {
public static void main(String[] args) {
SingleLinkedList singleLinkedList = new SingleLinkedList();
......
// 带排序的添加
singleLinkedList.addHeroNodeByNo(new HeroNode(2, "卢俊义", "玉麒麟"));
singleLinkedList.addHeroNodeByNo(new HeroNode(1, "宋江", "及时雨"));
singleLinkedList.addHeroNodeByNo(new HeroNode(4, "林冲", "豹子头"));
singleLinkedList.addHeroNodeByNo(new HeroNode(3, "吴用", "智多星"));
......
int nodeSize = singleLinkedList.getNodeSize();
System.out.println("链表中有效节点个数为"+ nodeSize);
System.out.println("倒数第一个节点是:" + singleLinkedList.lastIndexOf(1));
System.out.println("倒数第二个节点是:" + singleLinkedList.lastIndexOf(2));
System.out.println("倒数第三个节点是:" + singleLinkedList.lastIndexOf(3));
System.out.println("倒数第四个节点是:" + singleLinkedList.lastIndexOf(4));
System.out.println("倒数第五个节点是:" + singleLinkedList.lastIndexOf(5));
}
}
/**
* 定义链表管理节点
*/
class SingleLinkedList {
......
/**
* 倒序查找
* @param k 倒数第k个
* @return k的元素
*/
public HeroNode lastIndexOf(int k){
// 如果k为负数或者头结点直接返回null
if(k <= 0){
return null;
}
int nodeSize = getNodeSize();
// 如果k大于有效节点数直接返回null
if(nodeSize < k){
return null;
}
// 通过有效节点数 - k 取到正向节点数
int index = nodeSize - k;
int start = 1;
HeroNode cursor = head.next;
// 循环正向节点数 获取k
while (start <= index){
start++;
cursor = cursor.next;
}
return cursor;
}
......
}
/**
* 节点
*/
class HeroNode {
......
}
执行结果:
链表中有效节点个数为4
倒数第一个节点是:HeroNode{no=4, name='林冲', nickName='豹子头'}
倒数第二个节点是:HeroNode{no=3, name='吴用', nickName='智多星'}
倒数第三个节点是:HeroNode{no=2, name='卢俊义', nickName='玉麒麟'}
倒数第四个节点是:HeroNode{no=1, name='宋江', nickName='及时雨'}
倒数第五个节点是:null
单链表的反转[腾讯面试题, 有点难度]
package com.dance.linkedlist;
/**
* 单向链表(带头节点)
*/
public class SingleLinkedListDemo {
public static void main(String[] args) {
SingleLinkedList singleLinkedList = new SingleLinkedList();
......
// 带排序的添加
singleLinkedList.addHeroNodeByNo(new HeroNode(2, "卢俊义", "玉麒麟"));
singleLinkedList.addHeroNodeByNo(new HeroNode(1, "宋江", "及时雨"));
singleLinkedList.addHeroNodeByNo(new HeroNode(4, "林冲", "豹子头"));
singleLinkedList.addHeroNodeByNo(new HeroNode(3, "吴用", "智多星"));
......
singleLinkedList.showLinkedList();
System.out.println("反转单链表");
singleLinkedList.reverse();
singleLinkedList.showLinkedList();
}
}
/**
* 定义链表管理节点
*/
class SingleLinkedList {
/**
* 定义头节点, 代表第一个节点,不要动
*/
public final HeroNode head = createHeadNode();
private HeroNode createHeadNode(){
return new HeroNode(0, "", "");
}
......
public void reverse(){
reverse(head);
}
/**
* 反转单向链表
* @param heroNode 头节点
*/
public void reverse(HeroNode heroNode){
// 如果当前链表为空 或者 有效节点数 为1 就不需要反转
if(heroNode.next == null || heroNode.next.next == null){
return;
}
// 0 -> 1 -> 2 -> 3 -> 4
// 0 -> 4 -> 3 -> 2 -> 1
// 定义辅助指针
HeroNode current = heroNode.next; // 1 -> 2 -> 3 -> 4
// 指向当前节点的下一个节点
HeroNode next = null; // null
// 定义新的头节点
HeroNode reverseHead = createHeadNode(); // 0
// 遍历原来的链表
// 每遍历一个节点,就将其取出,并放在新的链表reverseHead的最前端
while (current != null) {
// 保存当前节点的下一个节点
// 1: next = 2 -> 3 -> 4 -> null
// 5: next = 3 -> 4
// 9: next = 4
// 13: null
next = current.next;
// 将当前节点的下一个节点放到reverseHead的最前面
// 2: current = 1 -> null
// 6: current = 2 -> 1 -> null
// 10: current = 3 -> 2 -> 1 -> null
// 14: current = 4 -> 3 -> 2 -> 1 -> null
current.next = reverseHead.next;
// 将reverseHead 的下一个节点 设置为当前节点
// 3: reverseHead = 0 -> 1 -> null
// 7: reverseHead = 0 -> 2 -> 1 -> null
// 11: reverseHead = 0 -> 3 -> 2 -> 1 -> null
// 15: reverseHead = 0 -> 4 -> 3 -> 2 -> 1 -> null
reverseHead.next = current;
// 当前节点向后移动
// 4: current = 2 -> 3 -> 4
// 8: current = 3 -> 4
// 12: current = 4
// 16: current = null
current = next;
}
// 将head.next 指向 reverseHead.next ,实现单链表的反转
head.next = reverseHead.next;
}
}
/**
* 节点
*/
class HeroNode {
......
}
执行结果
HeroNode{no=0, name='', nickName=''}
HeroNode{no=1, name='宋江', nickName='及时雨'}
HeroNode{no=2, name='卢俊义', nickName='玉麒麟'}
HeroNode{no=3, name='吴用', nickName='智多星'}
HeroNode{no=4, name='林冲', nickName='豹子头'}
反转单链表
HeroNode{no=0, name='', nickName=''}
HeroNode{no=4, name='林冲', nickName='豹子头'}
HeroNode{no=3, name='吴用', nickName='智多星'}
HeroNode{no=2, name='卢俊义', nickName='玉麒麟'}
HeroNode{no=1, name='宋江', nickName='及时雨'}
逆向遍历单链表
思路分析图解
思路
- 上面的题的要求就是逆向打印单链表
- 方式1: 先将单链表进行反转操作,然后在遍历即可, 这样做的问题是会破坏原来的单链表结构,不建议
- 方式2: 可以;利用栈(stack)数据结构,将各个节点压入栈中,然后利用栈的先入后出的特点,就实现了逆向打印的效果
- 其实我还想到了一种方法,就是获取链表的有效节点数,然后通过有效节点数创建一个数组, 遍历链表将有效节点顺序放入数组,然后逆向遍历数组
栈的简单使用(后面详细写)
package com.dance.linkedlist;
import java.util.Stack;
public class TestStack {
public static void main(String[] args) {
Stack<String> strings = new Stack<>();
// 入栈
strings.push("1");
strings.push("2");
strings.push("3");
while (strings.size()>0) {
// 出栈 从栈顶 取出
String pop = strings.pop();
System.out.println(pop);
}
}
}
执行结果
3
2
1
使用栈实现逆向遍历
package com.dance.linkedlist;
import java.util.Stack;
/**
* 单向链表(带头节点)
*/
public class SingleLinkedListDemo {
public static void main(String[] args) {
SingleLinkedList singleLinkedList = new SingleLinkedList();
......
// 带排序的添加
singleLinkedList.addHeroNodeByNo(new HeroNode(2, "卢俊义", "玉麒麟"));
singleLinkedList.addHeroNodeByNo(new HeroNode(1, "宋江", "及时雨"));
singleLinkedList.addHeroNodeByNo(new HeroNode(4, "林冲", "豹子头"));
singleLinkedList.addHeroNodeByNo(new HeroNode(3, "吴用", "智多星"));
......
singleLinkedList.showLinkedList();
......
System.out.println("逆向打印单链表");
singleLinkedList.showReverseLinkedList();
}
}
/**
* 定义链表管理节点
*/
class SingleLinkedList {
......
/**
* 逆向打印链表
*/
public void showReverseLinkedList(){
showReverseLinkedList(head.next);
}
/**
* 逆向打印链表
* @param node 头节点
*/
public void showReverseLinkedList(HeroNode node){
Stack<HeroNode> stacks = new Stack<>();
heroNodeToStack(node, stacks);
showStack(stacks);
}
/**
* 打印栈
* @param stacks 栈
*/
public void showStack(Stack<HeroNode> stacks){
while (!stacks.isEmpty()){
System.out.println(stacks.pop());
}
}
/**
* 链表顺序压栈
* @param heroNode 头节点
* @param stack 栈
*/
public void heroNodeToStack(HeroNode heroNode, Stack<HeroNode> stack){
if(heroNode == null){
return;
}
stack.push(heroNode);
heroNodeToStack(heroNode.next,stack);
}
}
/**
* 节点
*/
class HeroNode {
......
}
执行结果
HeroNode{no=0, name='', nickName=''}
HeroNode{no=1, name='宋江', nickName='及时雨'}
HeroNode{no=2, name='卢俊义', nickName='玉麒麟'}
HeroNode{no=3, name='吴用', nickName='智多星'}
HeroNode{no=4, name='林冲', nickName='豹子头'}
逆向打印单链表
HeroNode{no=4, name='林冲', nickName='豹子头'}
HeroNode{no=3, name='吴用', nickName='智多星'}
HeroNode{no=2, name='卢俊义', nickName='玉麒麟'}
HeroNode{no=1, name='宋江', nickName='及时雨'}
合并两个有序的单链表, 合并之后的链表依然有序
这个我就只写思路了
思路:
- 创建两个带头的单向链表a,b
-
双向链表应用实例
双向链表的操作分析与实现
需求
单向链表和双向链表的区别
单向链表,查找的方向只能是一个方向,而双向链表可以向前和向后查找
- 单向链表,不能自我删除,需要靠辅助节点,而双向链表,则可以自我删除,所以前面我们单链表删除节点时,总是需要临时节点,临时节点是待删除节点的前一个节点
分析双向链表如何完成遍历,添加,修改和删除的思路
对上图的说明Head头结点
不存放具体的数据,作用就是代表单链表的头节点属性
pre : 用于存放当前节点的上一个节点的坐标
next : 用于存放当前节点的下一个节点的坐标
value: 值添加, 遍历所有节点
和单向链表一样,只是多了可以向前查找的节点而已, 直接遍历到next属性为null的节点,添加到他的后面即可
也就是value:2{下面用current表示}
current.next = 新节点
新节点.pre = current代码实现
我直接拿上面的单链表进行扩展了,就不重新写了, 可以直接集成单链表和HeroNode对象,重写自己需要重写的方法,然后只要处理好类型的上下转型就可以 ```java package com.dance.linkedlist;
import java.util.Stack;
/**
双向链表(带头节点) */ public class DoubleLinkedListDemo {
public static void main(String[] args) {
DoubleLinkedList doubleLinkedList = new DoubleLinkedList(); // 添加节点 doubleLinkedList.addHeroNode(new HeroNodeExt(2, "卢俊义", "玉麒麟")); doubleLinkedList.addHeroNode(new HeroNodeExt(1, "宋江", "及时雨")); doubleLinkedList.addHeroNode(new HeroNodeExt(4, "林冲", "豹子头")); doubleLinkedList.addHeroNode(new HeroNodeExt(3, "吴用", "智多星")); doubleLinkedList.showLinkedList();}
}
/**
定义链表管理节点 */ class DoubleLinkedList extends SingleLinkedList {
@Override protected HeroNode createHeadNode() {
return new HeroNodeExt(0,"","");}
@Override public void addHeroNode(HeroNode next) {
HeroNode tailNode = getTailNode(head); if(next instanceof HeroNodeExt){ HeroNodeExt current = (HeroNodeExt) next; tailNode.next = current; current.pre = tailNode; }else{ throw new RuntimeException("参数类型错误,不是 HeroNodeExt.class"); }} }
/**
节点 */ class HeroNodeExt extends HeroNode {
/**
当前节点的上一个节点 */ public HeroNode pre;
public HeroNodeExt(int no, String name, String nickName) { super(no, name, nickName); } }
执行结果 ```java HeroNode{no=0, name='', nickName=''} HeroNode{no=2, name='卢俊义', nickName='玉麒麟'} HeroNode{no=1, name='宋江', nickName='及时雨'} HeroNode{no=4, name='林冲', nickName='豹子头'} HeroNode{no=3, name='吴用', nickName='智多星'}修改节点信息
代码实现
修改节点信息和单链表的一样,直接调用父类的方法即可 ```java package com.dance.linkedlist;
import java.util.Stack;
/**
双向链表(带头节点) */ public class DoubleLinkedListDemo {
public static void main(String[] args) {
DoubleLinkedList doubleLinkedList = new DoubleLinkedList(); // 添加节点 doubleLinkedList.addHeroNode(new HeroNodeExt(2, "卢俊义", "玉麒麟")); doubleLinkedList.addHeroNode(new HeroNodeExt(1, "宋江", "及时雨")); doubleLinkedList.addHeroNode(new HeroNodeExt(4, "林冲", "豹子头")); doubleLinkedList.addHeroNode(new HeroNodeExt(3, "吴用", "智多星")); doubleLinkedList.showLinkedList(); // 修改节点内容 doubleLinkedList.updateHeroNodeByNo(new HeroNodeExt(2,"小卢","小玉")); doubleLinkedList.showLinkedList();}
}
……
执行结果
```java
HeroNode{no=0, name='', nickName=''}
HeroNode{no=2, name='卢俊义', nickName='玉麒麟'}
HeroNode{no=1, name='宋江', nickName='及时雨'}
HeroNode{no=4, name='林冲', nickName='豹子头'}
HeroNode{no=3, name='吴用', nickName='智多星'}
HeroNode{no=0, name='', nickName=''}
HeroNode{no=2, name='小卢', nickName='小玉'}
HeroNode{no=1, name='宋江', nickName='及时雨'}
HeroNode{no=4, name='林冲', nickName='豹子头'}
HeroNode{no=3, name='吴用', nickName='智多星'}
删除指定节点
代码实现
根据ID删除指定节点,重写父类的删除方法,根据NO查询指定节点可以调用父类的方法,然后通过转型移除节点
package com.dance.linkedlist;
import java.util.Stack;
/**
* 双向链表(带头节点)
*/
public class DoubleLinkedListDemo {
public static void main(String[] args) {
DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
// 添加节点
doubleLinkedList.addHeroNode(new HeroNodeExt(2, "卢俊义", "玉麒麟"));
doubleLinkedList.addHeroNode(new HeroNodeExt(1, "宋江", "及时雨"));
doubleLinkedList.addHeroNode(new HeroNodeExt(4, "林冲", "豹子头"));
doubleLinkedList.addHeroNode(new HeroNodeExt(3, "吴用", "智多星"));
doubleLinkedList.showLinkedList();
// 修改节点内容
doubleLinkedList.updateHeroNodeByNo(new HeroNodeExt(2,"小卢","小玉"));
doubleLinkedList.showLinkedList();
// 删除指定节点
doubleLinkedList.removeHeroNodeByNo(2);
doubleLinkedList.showLinkedList();
}
}
/**
* 定义链表管理节点
*/
class DoubleLinkedList extends SingleLinkedList {
......
@Override
public void removeHeroNodeByNo(int no) {
HeroNodeExt current = (HeroNodeExt) getHeroNodeByNo(no);
current.pre.next = current.next;
((HeroNodeExt)current.next).pre = current.pre;
}
}
......
执行结果
HeroNode{no=0, name='', nickName=''}
HeroNode{no=2, name='卢俊义', nickName='玉麒麟'}
HeroNode{no=1, name='宋江', nickName='及时雨'}
HeroNode{no=4, name='林冲', nickName='豹子头'}
HeroNode{no=3, name='吴用', nickName='智多星'}
HeroNode{no=0, name='', nickName=''}
HeroNode{no=2, name='小卢', nickName='小玉'}
HeroNode{no=1, name='宋江', nickName='及时雨'}
HeroNode{no=4, name='林冲', nickName='豹子头'}
HeroNode{no=3, name='吴用', nickName='智多星'}
HeroNode{no=0, name='', nickName=''}
HeroNode{no=1, name='宋江', nickName='及时雨'}
HeroNode{no=4, name='林冲', nickName='豹子头'}
HeroNode{no=3, name='吴用', nickName='智多星'}
双向链表按照编号顺序添加节点
直接写代码吧,其实就是需要处理一下pre和下一个节点为null,不设置Pre的问题
package com.dance.linkedlist;
import java.util.Stack;
/**
* 双向链表(带头节点)
*/
public class DoubleLinkedListDemo {
public static void main(String[] args) {
DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
// 添加节点
doubleLinkedList.addHeroNodeByNo(new HeroNodeExt(2, "卢俊义", "玉麒麟"));
doubleLinkedList.addHeroNodeByNo(new HeroNodeExt(1, "宋江", "及时雨"));
doubleLinkedList.addHeroNodeByNo(new HeroNodeExt(4, "林冲", "豹子头"));
doubleLinkedList.addHeroNodeByNo(new HeroNodeExt(3, "吴用", "智多星"));
doubleLinkedList.showLinkedList();
......
}
}
/**
* 定义链表管理节点
*/
class DoubleLinkedList extends SingleLinkedList {
......
@Override
public void addHeroNodeByNo(HeroNode heroNode) {
HeroNodeExt beforeNode = (HeroNodeExt)getHeroNodePosition(head, heroNode);
HeroNodeExt current = (HeroNodeExt) heroNode;
HeroNodeExt afterNode = (HeroNodeExt) beforeNode.next;
beforeNode.next = current;
current.pre = beforeNode;
current.next = afterNode;
if(afterNode != null) {
afterNode.pre = current;
}
}
......
}
......
执行结果
HeroNode{no=0, name='', nickName=''}
HeroNode{no=1, name='宋江', nickName='及时雨'}
HeroNode{no=2, name='卢俊义', nickName='玉麒麟'}
HeroNode{no=3, name='吴用', nickName='智多星'}
HeroNode{no=4, name='林冲', nickName='豹子头'}
单向环形链表应用场景
Josephu(约瑟夫, 约瑟夫环)问题
Josephu问题为: 设编号为1, 2,……n的n个人围坐一圈,约定编号为k(1<=k<=n)的人从1开始报数,数到m的那个人出列,他的下一位又从1开始报数,数到m的那个人又出列,依次类推,直到所有人出列为止,由此产生一个出队编号的序列
提示: 用一个不带头节点的单向环形列表来处理Josephu问题: 先构成一个有n个节点的单循环链表, 然后由k节点起从1开始计数, 记到m时,对应节点从 链表中删除,然后再从被删除节点的下一个节点又从1开始计数,直到最后一个节点从链表中删除,算法结束
单向环形链表介绍
其实就是不带头的单向链表,然后将最后节点的next指向第一个节点
Josephu问题思路图解
创建环形链表思路图解
构建一个单向的环形链表思路
- 先创建第一个节点,让first指向该节点,并形成环形
- 后面每创建一个新节点,就把新节点, 加入到已有的环形链表中即可
遍历环形链表
- 先让一个辅助指针(curBoy)指向first节点
然后通过循环遍历该链表,当curBoy.next = first时结束
小孩出圈的思路分析图
根据用户的输入生成一个小孩出圈的顺序
n = 5 , 即有5个人
k = 1 , 从第一个人开始报数
m = 2 , 数2下
需要创建一个辅助指针helper, 事先应该指向环形链表的最后这个节点
补充:小孩报数前,先让first和helper移动k-1次
- 当小孩报数时,让first和helper指针同时的移动m-1次
- 这时就可以将first指向的小孩节点出圈
- first = first.next
- helper.next = first
- 原来first指向的节点就没有任何引用了, 就会被下一次的GC回收
- 出圈的顺序为 : 2->4->1->5->3
Josephu问题代码实现
```java package com.dance.linkedlist;
public class JosephuDemo { public static void main(String[] args) { CircleSingleLinkedList singleLinkedList = new CircleSingleLinkedList(); // 添加5个小孩 singleLinkedList.addBoy(20); // singleLinkedList.show(); singleLinkedList.killBoy(3,2,20); } }
class CircleSingleLinkedList {
/**
* 第一个节点
*/
private Boy first = new Boy(-1);
public void addBoy(int nums) {
if (nums < 1) {
System.out.println("数量错误");
return;
}
// 辅助指针帮助创建循环链表
Boy curBoy = null;
// 使用for创建环形链表
for (int i = 1; i <= nums; i++) {
Boy boy = new Boy(i);
if (first.no == -1) {
// 将头节点设置为第一个小孩
first = boy;
// 将第一个小孩的下一个节点设置为自己 构成环形
first.next = first;
// 将当前节点设置为第一个小孩方便下一次添加
curBoy = first;
} else {
curBoy.next = boy;
boy.next = first;
curBoy = boy;
}
}
}
public void show() {
Boy current = first;
if (current.no == -1) {
System.out.println("数据为空");
} else {
// 打印第一个节点
System.out.println(current);
// 循环打印后续节点
while (current.next != first) {
System.out.println(current.next);
current = current.next;
}
}
}
/**
* 根据用户的输入, 计算出小孩出圈的顺序
*
* @param startNo 表示从第几个小孩开始数数
* @param countNum 表示数几下(包含自己)
* @param nums 表示最初有几个小孩在圈
*/
public void killBoy(int startNo, int countNum, int nums) {
if (checkParams(startNo, countNum, nums)) {
// 创建辅助指针,帮助完成小孩出圈
Boy helper = first;
// 需要创建一个辅助指针(变量)helper 事先应该指向环形链表的最后这个节点
helper = pointAfter(helper);
// 小孩报数之前先移动K - 1 次, 因为不一定是从第一个小孩开始数
for (int i = 0; i < startNo - 1; i++) {
// 头节点后移
first = first.next;
// 尾节点后移
helper = helper.next;
}
// 开始循环, 一直到圈中只有一个小孩
while (true) {
// 当头和尾都指向一个节点时,就只有一个节点了
if (helper == first) {
// 打印最后一个小孩
System.out.println(first);
break;
}
// 当小孩报数时, 让first和helper指针同时移动M - 1次,然后出圈
for (int i = 0; i < countNum - 1; i++) {
first = first.next;
helper= helper.next;
}
// 这时first指向的节点就要出圈的小孩
System.out.println(first);
// 设置helper的指针指向出圈小孩的下一个节点
helper.next = first.next;
first = first.next;
}
}
}
public boolean checkParams(int startNo, int countNum, int nums) {
if (first.no == -1) {
System.out.println("链表为空");
return false;
} else if (startNo < 1) {
System.out.println("不能从第0位开始数");
return false;
} else if (startNo > nums) {
System.out.println("开始位置不能大于总数");
return false;
}
return true;
}
public Boy pointAfter(Boy point) {
while (true) {
// 找到最后一个节点
if (point.next == first) {
return point;
}
point = point.next;
}
}
}
class Boy { /**
* 编号
*/
public int no;
/**
* 下一个节点
*/
public Boy next;
public Boy(int no) {
this.no = no;
}
@Override
public String toString() {
return "Boy{" +
"no=" + no +
'}';
}
}
执行结果
```java
Boy{no=4}
Boy{no=6}
Boy{no=8}
Boy{no=10}
Boy{no=12}
Boy{no=14}
Boy{no=16}
Boy{no=18}
Boy{no=20}
Boy{no=2}
Boy{no=5}
Boy{no=9}
Boy{no=13}
Boy{no=17}
Boy{no=1}
Boy{no=7}
Boy{no=15}
Boy{no=3}
Boy{no=19}
Boy{no=11}
若有收获，就点个赞吧
0 人点赞
