Implémentation Java d'une liste à chaînage unique (Liste chaînée) liée
Recommandations d'apprentissage gratuites : Tutoriel Java Basic
Répertoire d'articles
- 1. Introduction à la liste à chaînage unique
- 2. Mise en œuvre d'une liste à chaînage unique
-
- 1. 🎜>
- 1.1 Ajouter à la fin
- 1.2 Ajouter par classement
- 3. . Suppression des nœuds de liste à lien unique
- 4. Mise en œuvre complète de la liste à lien unique
- 1. Introduction à la liste à chaînage unique
La liste à chaînage unique est un
, à la manière de , mais avec des nœuds
, chacun le nœud comprend un champ de données et un champ suivant.有序列表节点链式存储信息 : utilisé pour stocker des données. 不一定连续
- : pointe vers le nœud suivant. La liste chaînée
data域next域 est divisée en
. 
Liste chaînée unique (nœud principal)带头节点的链表不带头节点的链表
- Liste chaînée unique (sans nœud principal)
-
-
2. Implémentation d'une liste chaînée unique
Exigences : Utilisez avec l'en-tête pour implémenter – Gestion du classement des héros de la marge d'eau.
1) Complétez le héros2) La première méthode consiste à ajouter le héros,
单向链表. 3) Dans la deuxième méthode, lors de l'ajout d'un héros, ajoutez le héros
en fonction du classement (si le classement existe déjà, l'ajout échouera et une invite sera donnée)增删改查直接添加到链表的尾部
1 .Création (ajout) d'une liste à chaînage unique插入到指定位置
1.1 Ajout de queue
L'idée d'ajout de queue
🎜>①
②先创建一个head头节点，作用就是表示单链表的头。然后每添加一个节点，就直接加入到链表的最后。L'ajout de queue signifie : quelle que soit la séquence de numérotation, trouver le dernier nœud de la liste chaînée actuelle et pointer le suivant de le dernier nœud vers le nouveau nœud.
Mise en œuvre du code // 添加方式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;
}
Idées d'ajout par classement
①
②先通过辅助变量(temp指针)找到新添加的节点的位置。
③新节点.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;
}
}
Idées de modification
①
②通过遍历先找到该节点。, temp.name =newHeroNode.name;temp.nickname=newHeroNode.nickname;
// 修改节点信息,根据节点的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);
}
}
Idées de suppression
①
②找到需要删除的节点的前一个节点。
③temp.next=temp.next.next被删除的节点，将不会有其它引用指向，会被垃圾回收机制回收。
Mise en œuvre du code 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);
}
}
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 + "]";
}}
Les réponses aux quatre questions d'entretien ci-dessus sont placées dans le code ci-dessous
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 + "]";
}} 
Recommandations d'apprentissage associées :
Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!
Outils d'IA chauds
Undresser.AI Undress
Application basée sur l'IA pour créer des photos de nu réalistes
AI Clothes Remover
Outil d'IA en ligne pour supprimer les vêtements des photos.
Undress AI Tool
Images de déshabillage gratuites
Clothoff.io
Dissolvant de vêtements AI
AI Hentai Generator
Générez AI Hentai gratuitement.
Article chaud
Outils chauds
Bloc-notes++7.3.1
Éditeur de code facile à utiliser et gratuit
SublimeText3 version chinoise
Version chinoise, très simple à utiliser
Envoyer Studio 13.0.1
Puissant environnement de développement intégré PHP
Dreamweaver CS6
Outils de développement Web visuel
SublimeText3 version Mac
Logiciel d'édition de code au niveau de Dieu (SublimeText3)
Nombre parfait en Java
Aug 30, 2024 pm 04:28 PM
Guide du nombre parfait en Java. Nous discutons ici de la définition, comment vérifier le nombre parfait en Java ?, des exemples d'implémentation de code.
Weka en Java
Aug 30, 2024 pm 04:28 PM
Guide de Weka en Java. Nous discutons ici de l'introduction, de la façon d'utiliser Weka Java, du type de plate-forme et des avantages avec des exemples.
Numéro de Smith en Java
Aug 30, 2024 pm 04:28 PM
Guide du nombre de Smith en Java. Nous discutons ici de la définition, comment vérifier le numéro Smith en Java ? exemple avec implémentation de code.
Questions d'entretien chez Java Spring
Aug 30, 2024 pm 04:29 PM
Dans cet article, nous avons conservé les questions d'entretien Java Spring les plus posées avec leurs réponses détaillées. Pour que vous puissiez réussir l'interview.
Break or Return of Java 8 Stream Forach?
Feb 07, 2025 pm 12:09 PM
Java 8 présente l'API Stream, fournissant un moyen puissant et expressif de traiter les collections de données. Cependant, une question courante lors de l'utilisation du flux est: comment se casser ou revenir d'une opération FOREAK? Les boucles traditionnelles permettent une interruption ou un retour précoce, mais la méthode Foreach de Stream ne prend pas directement en charge cette méthode. Cet article expliquera les raisons et explorera des méthodes alternatives pour la mise en œuvre de terminaison prématurée dans les systèmes de traitement de flux. Lire plus approfondie: Améliorations de l'API Java Stream Comprendre le flux Forach La méthode foreach est une opération terminale qui effectue une opération sur chaque élément du flux. Son intention de conception est
Horodatage à ce jour en Java
Aug 30, 2024 pm 04:28 PM
Guide de TimeStamp to Date en Java. Ici, nous discutons également de l'introduction et de la façon de convertir l'horodatage en date en Java avec des exemples.
Programme Java pour trouver le volume de la capsule
Feb 07, 2025 am 11:37 AM
Les capsules sont des figures géométriques tridimensionnelles, composées d'un cylindre et d'un hémisphère aux deux extrémités. Le volume de la capsule peut être calculé en ajoutant le volume du cylindre et le volume de l'hémisphère aux deux extrémités. Ce tutoriel discutera de la façon de calculer le volume d'une capsule donnée en Java en utilisant différentes méthodes. Formule de volume de capsule La formule du volume de la capsule est la suivante: Volume de capsule = volume cylindrique volume de deux hémisphères volume dans, R: Le rayon de l'hémisphère. H: La hauteur du cylindre (à l'exclusion de l'hémisphère). Exemple 1 entrer Rayon = 5 unités Hauteur = 10 unités Sortir Volume = 1570,8 unités cubes expliquer Calculer le volume à l'aide de la formule: Volume = π × r2 × h (4
Comment exécuter votre première application Spring Boot dans Spring Tool Suite?
Feb 07, 2025 pm 12:11 PM
Spring Boot simplifie la création d'applications Java robustes, évolutives et prêtes à la production, révolutionnant le développement de Java. Son approche "Convention sur la configuration", inhérente à l'écosystème de ressort, minimise la configuration manuelle, allo
