추천 무료 학습: Basic Java Tutorial
Article Directory
1. 단일 연결 리스트 소개
단일 연결 리스트는
체인 형태로 정보를 저장하는 순서 리스트입니다. code>는 노드 code> 형식이지만, 노드는 반드시 연속적일 필요는 없습니다. 각 노드에는 데이터 필드와 다음 필드가 포함됩니다. 有序列表，以节点的方式链式存储信息，但节点不一定连续，每一个节点包括data域和next域。
data域：用来存放数据。next域：指向下一个节点。
链表分为带头节点的链表和不带头节点的链表。
二、单链表的实现
需求：使用带head头的
单向链表实现–水浒英雄排行榜管理。
1)完成对英雄的增删改查
2)第一种方法在添加英雄时，直接添加到链表的尾部。
3)第二种方式在添加英雄时，根据排名将英雄插入到指定位置(如果已有这个排名，则添加失败，并给出提示)
1.单链表的创建(添加)
1.1尾添加
尾添加的思路
①先创建一个head头节点，作用就是表示单链表的头。
②然后每添加一个节点，就直接加入到链表的最后。
尾添加即：不考虑编号顺序，找到当前链表的最后节点，将最后这个节点的next指向新的节点。
代码实现
// 添加方式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;
}1.2按排名添加
按排名添加的思路
①先通过辅助变量(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;
}
}2.单链表节点的修改
修改的思路
①通过遍历先找到该节点。
②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);
}
}3.单链表节点的删除
删除的思路
①找到需要删除的节点的前一个节点。
②temp.next=temp.next.next
③被删除的节点，将不会有其它引用指向，会被垃圾回收机制回收。데이터 필드: 데이터를 저장하는 데 사용됩니다. 
다음 필드: 다음 노드를 가리킵니다.
링크된 목록은 다음과 같습니다. 헤드 노드가 있는 연결 목록과 헤드 노드가 없는 연결 목록으로 나뉩니다.
단일 연결 목록(리드 노드)
단일 연결 목록(헤드 노드 없음)
2. 단일 연결 리스트 구현
단일 연결 리스트를 사용하여 구현 - 물마진 영웅 순위 관리. 🎜🎜1.1 tail 추가 아이디어 🎜🎜🎜🎜🎜🎜🎜①1) 영웅의
추가, 삭제, 수정 및 확인을 완료합니다 2) 첫 번째 방법은 영웅 추가 시연결된 목록 끝에 직접 추가하는 것입니다. 영웅. 3) 두 번째 방법은 영웅을 추가할 때 순위에 따라지정된 위치에 영웅을 삽입합니다. (순위가 이미 존재하는 경우 추가가 실패하고 프롬프트가 표시됩니다.) 1. 연결 리스트의 단일 생성(추가)
먼저 헤드를 나타내는 헤드 노드를 생성합니다. 단일 연결 리스트. 🎜 ②노드가 추가될 때마다 연결리스트 끝에 바로 추가됩니다. 🎜🎜꼬리 추가는 번호 매기기 순서에 관계없이 현재 연결 목록의 마지막 노드를 찾고 마지막 노드의 다음 노드를 새 노드로 가리킨다는 의미입니다. 🎜🎜🎜코드 구현🎜🎜 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);
}
}먼저 보조 변수(임시 포인터)를 통해 새로 추가된 노드의 위치를 찾습니다. 🎜 ②새 node.next=temp.next;🎜 ③temp.next=새 노드;🎜🎜
🎜🎜🎜코드 구현🎜🎜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 + "]";
}}순회를 통해 먼저 노드를 찾습니다. 🎜 ②temp.name =newHeroNode.name;, temp.nickname=newHeroNode.nickname;🎜🎜🎜코드 구현🎜🎜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 + "]";
}} 삭제해야 할 노드 이전의 노드를 찾아보세요. 🎜 ②temp.next=temp.next.next🎜 ③삭제된 노드에는 다른 참조가 없으며 가비지 수집 메커니즘에 의해 재활용됩니다. 🎜🎜🎜🎜코드 구현🎜🎜rrreee🎜🎜4. 단일 연결 목록의 완전한 구현🎜🎜rrreee🎜🎜실행 결과🎜🎜🎜🎜🎜🎜3개의 단일 연결 표면 테스트 문제🎜🎜🎜🎜 🎜 위 인터뷰 4개 질문과 답변은 아래 코드에 있습니다🎜rrreee🎜🎜🎜관련 학습 권장사항: 🎜🎜🎜java basics🎜🎜🎜🎜위 내용은 단일 연결 리스트(Linked List) 관련 Java 구현의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!
![[웹 프런트엔드] Node.js 빠른 시작](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
