# 無料学習の推奨事項:##記事ディレクトリ
#1. 単連結リストの概要
を node の形式で格納する
順序付きリストです。 、ただし、ノード は連続した である必要はありません。各ノードにはデータ フィールドと次のフィールドが含まれます。 データ ドメイン: データの保存に使用されます。
ヘッド ノードのないリンク リスト##に分割されます。 ＃。 
単一リンク リスト (先頭ノードなし)
#2. 単一リンク リストの実装
単一リンク リストを使用して実装 – 水滸伝ヒーロー ランキング管理。 1) ヒーローの
追加、削除、変更、確認を完了します2) 1 つ目の方法でヒーローを追加する場合、先頭に を直接末尾に追加します。リンクされたリスト
。3) 2 番目の方法では、ヒーローを追加するときに、ランキング に従って指定された位置にヒーロー
を挿入します (ランキングがすでに存在する場合、追加は失敗し、プロンプトが表示されます)。1. 単一リンクリストの作成 (追加)#1.1 末尾の追加
# #末尾を追加するというアイデア
①最初に、単一リンク リストの先頭を表すために使用される先頭ノードを作成します。 ②
その後、ノードが追加されるたびに、そのノードはリンク リストの最後に直接追加されます。末尾の追加とは、番号付けシーケンスに関係なく、現在のリンク リストの最後のノードを見つけ、最後のノードの次のノードが新しいノードを指すことを意味します。
コードの実装<div class="code" style="position:relative; padding:0px; margin:0px;"><pre class="brush:php;toolbar:false;"> // 添加方式1:尾添加
public void add(HeroNode heroNode) {
// 因为head头不能动,因此需要一个辅助变量(指针)temp
HeroNode temp = head;
while (true) {
// 如果遍历到链表的最后
if (temp.next == null) {
break;
}
// temp指针后移
temp = temp.next;
}
// 当退出循环时,temp指向链表的最后
temp.next = heroNode;
}</pre><div class="contentsignin">ログイン後にコピー</div></div>
ランキングによる追加のアイデア ①
②新しいノード.next=temp.next;
③temp.next=新しいノード;
#コードの実装
// 添加方式2:根据排名添加
public void addByOrder(HeroNode heroNode) {
HeroNode temp = head;// 借助辅助指针
boolean flag = false;// 添加的编号是否存在
while (true) {
if (temp.next == null) {// 遍历到结尾
break;
}
if (temp.next.no > heroNode.no) {// 位置找到,就在temp的后面插入
break;
} else if (temp.next.no == heroNode.no) {// 该编号已存在
flag = true;
break;
}
temp = temp.next;// 后移,遍历当前链表
}
if (flag) {
// 不能添加
System.out.printf("准备插入的英雄的编号%d已经存在，不能加入\n", heroNode.no);
} else {
// 插入到temp的后面
heroNode.next = temp.next;
temp.next = heroNode;
}
}2. 単一リンク リスト ノードの変更
変更のアイデア
①まずトラバーサルでノードを見つけます。
②temp.name =newHeroNode.name;, temp.nickname=newHeroNode.nickname;
コードの実装
<div class="code" style="position:relative; padding:0px; margin:0px;"><pre class="brush:php;toolbar:false;"> // 修改节点信息,根据节点的no属性修改其他信息
public void update(HeroNode newHeroNode) {
// 空链表无法修改节点信息
if (head.next == null) {
System.out.println("链表为空~");
return;
}
// 根据no排名找到需要修改的节点
HeroNode temp = head.next;
boolean flag = false;// flag表示是否找到需要修改的节点
while (true) {
if (temp == null) {
// 遍历到结尾
break;
}
if (temp.no == newHeroNode.no) {
// 找到
flag = true;
break;
}
temp = temp.next;// 后移
}
if (flag) {
temp.name = newHeroNode.name;
temp.nickname = newHeroNode.nickname;
} else {
System.out.printf("没有找到编号为%d的节点，不能修改\n", newHeroNode.no);
}
}</pre><div class="contentsignin">ログイン後にコピー</div></div>
3. 単一リンク リスト ノードの削除削除のアイデア
①必要なノードを見つける前のノードを削除します。
②temp.next=temp.next.next
③削除されたノードには、それを指す他の参照がなく、ガベージ コレクション メカニズムによってリサイクルされます。
#コードの実装#<div class="code" style="position:relative; padding:0px; margin:0px;"><pre class="brush:php;toolbar:false;"> public void delete(int no) {
HeroNode temp = head;
boolean flag = false;// 是否找到待删除节点
while (true) {
if (temp.next == null) {
// 遍历到结尾
break;
}
if (temp.next.no == no) {
// 找到了待删除节点的前一个节点
flag = true;
break;
}
temp = temp.next;// 后移
}
if (flag) {
// 可以删除
temp.next = temp.next.next;
} else {
System.out.printf("要删除的%d节点不存在\n", no);
}
}</pre><div class="contentsignin">ログイン後にコピー</div></div>#4. 単一リンク リストの完全な実装
#
package com.gql.linkedlist;/**
* 单链表
*
* @guoqianliang
*
*/public class SingleLinkedListDemo {
public static void main(String[] args) {
// 创建节点
HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");
// 创建单向链表
SingleLinkedList singleLinkedList = new SingleLinkedList();
// 加入
singleLinkedList.addByOrder(hero1);
singleLinkedList.addByOrder(hero4);
singleLinkedList.addByOrder(hero3);
singleLinkedList.addByOrder(hero2);
singleLinkedList.list();
// 测试修改节点
HeroNode newHeroNode = new HeroNode(2, "小卢", "玉麒麟~");
singleLinkedList.update(newHeroNode);
System.out.println("修改后的链表情况:");
singleLinkedList.list();
// 删除一个节点
singleLinkedList.delete(1);
singleLinkedList.delete(2);
singleLinkedList.delete(3);
singleLinkedList.delete(4);
System.out.println("删除后的链表情况:");
singleLinkedList.list();
}}//定义SingleLinkedList,管理英雄class SingleLinkedList {
// 初始化头结点,不存放具体数据
private HeroNode head = new HeroNode(0, "", "");
// 添加方式1:尾添加
// 思路:
// 1.找到当前链表的最后节点
// 2.将这个最后的节点的next指向新的节点
public void add(HeroNode heroNode) {
// 因为head头不能动,因此需要一个辅助变量(指针)temp
HeroNode temp = head;
while (true) {
// 如果遍历到链表的最后
if (temp.next == null) {
break;
}
// temp指针后移
temp = temp.next;
}
// 当退出循环时,temp指向链表的最后
temp.next = heroNode;
}
// 添加方式2:根据排名添加
public void addByOrder(HeroNode heroNode) {
HeroNode temp = head;// 借助辅助指针
boolean flag = false;// 添加的编号是否存在
while (true) {
if (temp.next == null) {// 遍历到结尾
break;
}
if (temp.next.no > heroNode.no) {// 位置找到,就在temp的后面插入
break;
} else if (temp.next.no == heroNode.no) {// 该编号已存在
flag = true;
break;
}
temp = temp.next;// 后移,遍历当前链表
}
if (flag) {
// 不能添加
System.out.printf("准备插入的英雄的编号%d已经存在，不能加入\n", heroNode.no);
} else {
// 插入到temp的后面
heroNode.next = temp.next;
temp.next = heroNode;
}
}
// 修改节点信息,根据节点的no属性修改其他信息
public void update(HeroNode newHeroNode) {
// 空链表无法修改节点信息
if (head.next == null) {
System.out.println("链表为空~");
return;
}
// 根据no排名找到需要修改的节点
HeroNode temp = head.next;
boolean flag = false;// flag表示是否找到需要修改的节点
while (true) {
if (temp == null) {
// 遍历到结尾
break;
}
if (temp.no == newHeroNode.no) {
// 找到
flag = true;
break;
}
temp = temp.next;// 后移
}
if (flag) {
temp.name = newHeroNode.name;
temp.nickname = newHeroNode.nickname;
} else {
System.out.printf("没有找到编号为%d的节点，不能修改\n", newHeroNode.no);
}
}
// 删除节点
// 思路:
// 1.找到需要删除节点的前一个节点
// 2.temp.next=temp.next.next
// 3.被删除的节点将会被垃圾回收机制回收
public void delete(int no) {
HeroNode temp = head;
boolean flag = false;// 是否找到待删除节点
while (true) {
if (temp.next == null) {
// 遍历到结尾
break;
}
if (temp.next.no == no) {
// 找到了待删除节点的前一个节点
flag = true;
break;
}
temp = temp.next;// 后移
}
if (flag) {
// 可以删除
temp.next = temp.next.next;
} else {
System.out.printf("要删除的%d节点不存在\n", no);
}
}
// 显示链表[遍历]
public void list() {
// 空链表直接返回
if (head.next == null) {
System.out.println("链表为空");
return;
}
// 仍然使用辅助变量(指针),进行循环
HeroNode temp = head.next;
while (true) {
if (temp == null) {
break;
}
System.out.println(temp);
// 将temp后移
temp = temp.next;
}
}}//定义HeroNode,每一个HeroNode就是一个节点class HeroNode {
public int no;// 排名
public String name;
public String nickname;// 昵称
public HeroNode next;// 指向下一个节点
// 构造器
public HeroNode() {
super();
}
public HeroNode(int no, String name, String nickname) {
super();
this.no = no;
this.name = name;
this.nickname = nickname;
}
// 重写toString
@Override
public String toString() {
return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]";
}}
上記 4 つの答え面接の質問は次のコードにあります
package com.gql.LinkedList;import java.util.Stack;/**
* 模拟单链表
*
* @author Hudie
* @Email:guoqianliang@foxmail.com
* @date 2020年7月16日下午6:47:42
*/public class SingleLinkedListDemo {
public static void main(String[] args) {
// 创建节点
HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");
// 创建单向链表
SingleLinkedList singleLinkedList = new SingleLinkedList();
// 加入
singleLinkedList.addByOrder(hero1);
singleLinkedList.addByOrder(hero4);
singleLinkedList.addByOrder(hero3);
singleLinkedList.addByOrder(hero2);
singleLinkedList.list();
// 测试修改节点
HeroNode newHeroNode = new HeroNode(2, "小卢", "玉麒麟~");
singleLinkedList.update(newHeroNode);
System.out.println("修改后的链表情况:");
singleLinkedList.list();
// 删除一个节点
singleLinkedList.delete(4);
System.out.println("删除后的链表情况:");
singleLinkedList.list();
//练习4:反向打印单链表
System.out.println("反向打印单链表:");
reversePrint(singleLinkedList.getHead());
//练习3:反转单链表
reversalList(singleLinkedList.getHead());
System.out.println("反转过后的单链表为:");
singleLinkedList.list();
// 练习1:获取单链表节点个数
System.out.println("单链表的有效个数为:");
System.out.println(getLength(singleLinkedList.getHead()));
int index = 2;
//练习2:获取单链表倒数第index给节点
System.out.println("倒数第"+ index +"个节点为:");
System.out.println(getLastKNode(singleLinkedList.getHead(),index));
}
/**
* @Description: 获取单链表节点个数 思路: while循环 + 遍历指针
*/
public static int getLength(HeroNode head) {
if (head.next == null) {
return 0;
}
int length = 0;
// 辅助指针
HeroNode p = head.next;
while (p != null) {
length++;
p = p.next;
}
return length;
}
/**
* @Description:
* 查找单链表中倒数第index个节点 index:表示倒数第index给节点
* 思路:
* 1.首先获取链表的长度length,可直接调用getLength
* 2.然后从链表第一个开始遍历,遍历(length-index)个
* 3.找不到返回null
*/
public static HeroNode getLastKNode(HeroNode head, int index) {
if (head.next == null) {
return null;
}
int length = getLength(head);
if (index <= 0 || index > length) {
return null;
}
HeroNode p = head.next;
for(int i = 0;i < length-index;i++){
p = p.next;
}
return p;
}
/**
* @Description:
* 反转单链表[带头节点]
* 思路:
* 1.先定义一个节点reversalHead = new HeroNode(0,"","");
* 2.遍历原来的链表,每遍历一个节点,就将其取出,并放在新的链表reversalHead的最前端
* 3.原来的链表的head.next = reversalHead;
*/
public static void reversalList(HeroNode head){
//链表为空或只有一个节点,无需反转,直接返回
if(head.next == null || head.next.next == null){
return;
}
//辅助指针p
HeroNode p = head.next;
HeroNode next = null;//指向辅助指针p的下一个位置
HeroNode reversalHead = new HeroNode(0,"","");
//遍历原来的链表,每遍历一个节点,就将其取出,并放在新的链表reversalHead的最前端
while(p != null){
next = p.next;
p.next = reversalHead.next;
reversalHead.next = p;
p = next;
}
head.next = reversalHead.next;
}
/**
* @Description:
* 反向打印单链表[带头节点]
* 思路1:单链表反转后打印(不建议,因为破坏了单链表的结构)
* 思路2:使用栈结构,利用栈先进后出的特点
*/
public static void reversePrint(HeroNode head){
if(head.next == null){
return;
}
Stack stack = new Stack();
HeroNode p = head.next;
while(p != null){
stack.push(p);
p = p.next;
}
//将栈中的节点进行打印
while(stack.size() > 0){
System.out.println(stack.pop());
}
}}// 定义SingleLinkedList,管理英雄,即链表的增删改查class SingleLinkedList {
// 初始化头结点,不存放具体数据
private HeroNode head = new HeroNode(0, "", "");
// 添加方式1:尾添加
// 思路:
// 1.找到当前链表的最后节点
// 2.将这个最后的节点的next指向新的节点
public void add(HeroNode heroNode) {
// 因为head头不能动,因此需要一个辅助变量(指针)temp
HeroNode temp = head;
while (true) {
// 如果遍历到链表的最后
if (temp.next == null) {
break;
}
// temp指针后移
temp = temp.next;
}
// 当退出循环时,temp指向链表的最后
temp.next = heroNode;
}
public HeroNode getHead() {
return head;
}
// 添加方式2:根据排名添加
public void addByOrder(HeroNode heroNode) {
HeroNode temp = head;// 借助辅助指针
boolean flag = false;// 添加的编号是否存在
while (true) {
if (temp.next == null) {// 遍历到结尾
break;
}
if (temp.next.no > heroNode.no) {// 位置找到,就在temp的后面插入
break;
} else if (temp.next.no == heroNode.no) {// 该编号已存在
flag = true;
break;
}
temp = temp.next;// 后移,遍历当前链表
}
if (flag) {
// 不能添加
System.out.printf("准备插入的英雄的编号%d已经存在，不能加入\n", heroNode.no);
} else {
// 插入到temp的后面
heroNode.next = temp.next;
temp.next = heroNode;
}
}
// 修改节点信息,根据节点的no属性修改其他信息
public void update(HeroNode newHeroNode) {
// 空链表无法修改节点信息
if (head.next == null) {
System.out.println("链表为空~");
return;
}
// 根据no排名找到需要修改的节点
HeroNode temp = head.next;
boolean flag = false;// flag表示是否找到需要修改的节点
while (true) {
if (temp == null) {
// 遍历到结尾
break;
}
if (temp.no == newHeroNode.no) {
// 找到
flag = true;
break;
}
temp = temp.next;// 后移
}
if (flag) {
temp.name = newHeroNode.name;
temp.nickname = newHeroNode.nickname;
} else {
System.out.printf("没有找到编号为%d的节点，不能修改\n", newHeroNode.no);
}
}
// 删除节点
// 思路:
// 1.找到需要删除节点的前一个节点
// 2.temp.next=temp.next.next
// 3.被删除的节点将会被垃圾回收机制回收
public void delete(int no) {
HeroNode temp = head;
boolean flag = false;// 是否找到待删除节点
while (true) {
if (temp.next == null) {
// 遍历到结尾
break;
}
if (temp.next.no == no) {
// 找到了待删除节点的前一个节点
flag = true;
break;
}
temp = temp.next;// 后移
}
if (flag) {
// 可以删除
temp.next = temp.next.next;
} else {
System.out.printf("要删除的%d节点不存在\n", no);
}
}
// 显示链表[遍历]
public void list() {
// 空链表直接返回
if (head.next == null) {
System.out.println("链表为空");
return;
}
// 仍然使用辅助变量(指针),进行循环
HeroNode temp = head.next;
while (true) {
if (temp == null) {
break;
}
System.out.println(temp);
// 将temp后移
temp = temp.next;
}
}}// 定义HeroNode,每一个HeroNode就是一个节点class HeroNode {
public int no;// 排名
public String name;
public String nickname;// 昵称
public HeroNode next;// 指向下一个节点
// 构造器
public HeroNode() {
super();
}
public HeroNode(int no, String name, String nickname) {
super();
this.no = no;
this.name = name;
this.nickname = nickname;
}
// 重写toString
@Override
public String toString() {
return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]";
}} 関連する学習の推奨事項:
Java の基礎
以上が単一リンクリスト(Linked List)関連のJava実装の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。
![[Web フロントエンド] Node.js クイック スタート](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
