单向链表 单向链表（单链表）是链表的一种，其特点是链表的链接方向是单向的，对链表的访问要通过顺序读取从头部开始；链表是使用指针进行构造的列表；又称为结点列表，因为链表是由一个个结点组装起来的；其中每个结点都有指针成员变量指向列表中的下一个结点；
链表是由结点构成，head指针指向第一个成为表头结点，而终止于最后一个指向NULL的指针。
文章图片
小结上图：
（1）链表是以节点的方式存储，是链式存储
（2）每个节点包含data域，next域：指向下一个节点
（3）如图：发现链表的各个节点不一定是连续存储
（4）链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定
我们操作的习惯是让头节点为空，作用就是表示单链表的头。然后一次进行操作。
添加操作（创建）：
- 先创建一个head头节点，作用就是表示单链表的头
- 后面我们每添加一个节点，就直接加入到链表的最后
通过一个辅助变量（指针），帮助遍历整个链表
按照序号的顺序添加：
- 首先找到新添加节点的位子，是通过辅助变量（指针），通过遍历搞定
- 新的节点.next=temp.next
- 将temp.next=新的节点
- 首先找到需要修改的位子，是通过辅助变量（指针），通过遍历搞定
- 找到后，修改信息
- 我们先找到需要删除的节点的前一个节点
- temp.next=temp.next.next
- 被删除的节点，将不会有其他引用指向，会被垃圾回收机制回收
实现上述操作的Demo：
使用head头的单向链表实现水浒英雄传排行的管理
（1）要对英雄增删改查
（2）第一种添加，直接添加到尾部
（3）第二种添加，根据排名添加
package SingleLinkList;
public class HeroRank {
public static void main(String[] args) {
SingleList s=new SingleList();
s.addBy(new HeroInfo(1,"松江","及时雨"));
s.addBy(new HeroInfo(3,"yyyzl","天才"));
s.addBy(new HeroInfo(2,"李逵","黑旋风"));
s.update(new HeroInfo(3,"lizhuzhu","hahah"));
s.delete(1);
s.show();
}
}
//定义SingleList来管理英雄
class SingleList{
//初始化头节点，我们希望头节点不要动，不存放具体的数据
private HeroInfo head=new HeroInfo(0,"","");
public HeroInfo getHead() {
return head;
}
//添加节点到单向链表
//思路，考虑找不到当前编号顺序时
//1.找到该节点的最后一个节点
//2.找到最后这个节点的next指向新的节点
public void add(HeroInfo node){
//因为head节点不能动，所以我们需要一个辅助遍历temp
HeroInfo temp=head;
//遍历链表
while (true){
//找到链表的最后
if (temp.next==null){
break;
}
//如果没到最后，将temp后移
temp=temp.next;
}
//当退出while循环时，temp就指向了链表的最后
temp.next=node;
}
//遍历
public voidshow(){
//判断链表是否为空
if (head.next==null){
System.out.println("链表为空");
return;
}
//因为head节点不能动，所以我们需要一个辅助遍历temp
HeroInfo temp=head.next;
while (true){
if (temp==null) {
break;
}
//输出节点的信息
System.out.println(temp);
//将temp后移
temp=temp.next;
}
}
//第二种方式添加英雄，根据英雄插入到指定的位置
//（如果已经存在给出错误提示）
public void addBy(HeroInfo node){
//因为head节点不能动，所以我们需要一个辅助遍历temp
//因为是单链表，因为我们找的temp是位于添加位置的前一个节点，否则插入不了
HeroInfo temp=head;
boolean flag=false;
//flag标志添加的编号是否已经存在，默认为flase
while (true){
if (temp.next==null){//说明temp已经在链表的最后
break;
}
if (node.no单链表的常见面试题： （1）求单链表的长度
（2）查找单链表种的倒数第k个节点
（3）单链表的反转
（4）从尾到头打印单链表（内含Stack简单运用）
（5）合并两个有序的单链表，合并之后的链表依然有序
package SingleLinkList;
import org.junit.Test;
import java.util.Stack;
/*
（1）求单链表的长度
（2）查找单链表种的倒数第k个节点
（3）单链表的反转
（4）从尾到头打印单链表
（5）合并两个有序的单链表，合并之后的链表依然有序
*/
public class InterviewTest {public static void main(String[] args) {
Test1 i=new Test1();
i.addBy(new HeroInfo(1,"松江","及时雨"));
i.addBy(new HeroInfo(3,"yyyzl","天才"));
i.addBy(new HeroInfo(2,"李逵","黑旋风"));
//System.out.println(i.test1());
//i.test2(3);
//i.test3();
//i.show();
//i.stackTest();
//i.test4();
}
}
class Test1{
private HeroInfo head=new HeroInfo(0,"","");
//求单链表的长度
//思路：循环一遍不断++
public int test1(){
if (head.next==null){
System.out.println("链表为空");
return 0;
}
HeroInfo temp=head.next;
int length=0;
while (true){
if (temp==null){
return length;
}
length++;
temp=temp.next;
}
}
//查找单链表种的倒数第k个节点
//思路：先循环一共多少个，然后循环index-k次长度为3倒数第1个 43次倒数第二个2次3
public void test2(int no){
if (head.next==null){
System.out.println("链表为空");
return;
}
HeroInfo temp=head.next;
int index=test1();
for (int i = 1;
i < index-no+2;
i++) {
if (temp==null){
return;
}
if (i==index-no+1){
System.out.println(temp.name+" "+temp.nickname);
}
temp=temp.next;
}
}
//单链表的反转
//思路：1.定义一个新节点；
// 2.遍历原先的链表，每遍历一个，将其取出，放在新链表的最前端
// 3.将原先的链表的head.next指向新链表的.next
public void test3(){
//如果当前链表为空，或者只有一个节点，无需反转，直接返回
if (head.next==null || head.next.next==null){
return;
}
HeroInfo reverseHead=new HeroInfo(0,"","");
HeroInfo cur=head.next;
//当前的辅助节点
HeroInfo next=null;
//指向当前辅助节点的下一个节点
//每次遍历一个节点，就将它取出，放在新链表的头部
while (cur!=null){
next=cur.next;
//当前辅助节点的下一个节点
cur.next=reverseHead.next;
//cur的下一个节点指向新链表的头部
reverseHead.next=cur;
cur=next;
//让辅助节点后移
}
//head.next指向reverseHead.next，实现反转
head.next=reverseHead.next;
}
//从尾到头打印单链表
//思路：遍历一遍数组，边遍历边push进栈（先进后出的特性）中，然后循环打印就行
public void test4(){
if (head.next==null){
System.out.println("链表为空");
return;
}
HeroInfo temp=head.next;
Stack s=new Stack<>();
while (true){
if (temp==null){
break;
}
s.push(temp);
temp=temp.next;
}
while (s.size()>0){
System.out.println(s.pop());
}
}//栈的操作
public void stackTest(){
Stack> stack=new Stack<>();
stack.push("111");
stack.push("222");
stack.push("333");
while (stack.size()>0){
System.out.println(stack.pop());
}
}
//合并两个有序的单链表，合并之后链表依然有序
//思路：两个链表都添加进那个有序的public void addBy(HeroInfo node){
//因为head节点不能动，所以我们需要一个辅助遍历temp
//因为是单链表，因为我们找的temp是位于添加位置的前一个节点，否则插入不了
HeroInfo temp=head;
boolean flag=false;
//flag标志添加的编号是否已经存在，默认为flase
while (true){
if (temp.next==null){//说明temp已经在链表的最后
break;
}
if (node.no双向链表 使用head头的双向链表实现水浒英雄传排行的管理
使用单向链表的缺点分析：
（1）单向链表，查找的方向只能是一个方向，而双向链表可以向前或者向后查找
（2）单向链表不能自我删除，需要靠辅助节点，而双向链表，则可以自我删除，所以前面我们单链表删除时的节点，总是找到temp，temp是待删节点的前一个节点来删除的
遍历：
方式和单链表一样，只是可以向前，也可以向后查找
添加：（默认添加到双向链表的最后）
（1）先找到双向链表的最后这个节点
（2）temp.next=newHeroNode
（3）newHeroNode.pre=temp
修改：
思路、原理都和单向链表一样
删除：
（1）因为是双向链表，因此，我们可以实现自我删除某个节点
（2）直接找到要删除的这个节点，比如temp
（3）temp.pre.next=temp.next
（4）temp.next.pre=temp.pre
【单向链表及常见面试题和双向链表】代码实现：
public class DoubleLinkedListDemo {
public static void main(String[] args) {
DoubleLinkedList d=new DoubleLinkedList();
d.add(new HeroInfo1(1,"松江","及时雨"));
d.add(new HeroInfo1(3,"yyyzl","天才"));
d.add(new HeroInfo1(2,"李逵","黑旋风"));
d.update(new HeroInfo1(2,"lizhuzhu","hahah"));
d.delete(1);
d.show();
}
}
class DoubleLinkedList{
private HeroInfo1 head=new HeroInfo1(0,"","");
public void add(HeroInfo1 node){
//因为head节点不能动，所以我们需要一个辅助遍历temp
HeroInfo1 temp=head;
//遍历链表
while (true){
//找到链表的最后
if (temp.next==null){
break;
}
//如果没到最后，将temp后移
temp=temp.next;
}
//当退出while循环时，temp就指向了链表的最后
//形成一个双向链表
temp.next=node;
node.pre=temp;
}
public voidshow(){
//判断链表是否为空
if (head.next==null){
System.out.println("链表为空");
return;
}
//因为head节点不能动，所以我们需要一个辅助遍历temp
HeroInfo1 temp=head.next;
while (true){
if (temp==null) {
break;
}
//输出节点的信息
System.out.println(temp);
//将temp后移
temp=temp.next;
}
}
public void update(HeroInfo1 node){
if (head.next==null){
return;
}
HeroInfo1 temp=head.next;
boolean flag=false;
while (true){
if (temp==null){
return;
}
if (temp.no==node.no){
flag=true;
break;
}
temp=temp.next;
}
if (flag){
temp.name= node.name;
temp.nickname=node.nickname;
}else {
System.out.println("您的节点没找到哦");
}
}
public void delete(int no){
if (head.next==null){
return;
}
HeroInfo1 temp=head.next;
boolean flag=false;
while (true){
if (temp==null){
break;
}
if (temp.no==no){
flag=true;
break;
}
temp=temp.next;
}
if (flag){
temp.pre.next=temp.next;
if (temp.next!=null){
temp.next.pre=temp.pre;
}
}else {
System.out.println("没找到该节点哦");
}
}
}
//定义heroinfo1，每个heroinfo1就是一个节点
class HeroInfo1{
publicint no;
publicString name;
public String nickname;
public HeroInfo1 next;
//指向下一个节点
public HeroInfo1 pre;
//指向前一个节点
//构造器
public HeroInfo1(int no, String name, String nickname) {
this.no = no;
this.name = name;
this.nickname = nickname;
}
//为了显示，我们重写了tostring方法
@Override
public String toString() {
return "HeroInfo{" +
"no=" + no +
", name='" + name + '\'' +
", nickname='" + nickname + '\'' +
'}';
}
}推荐阅读
- java|10道经典链表面试题
- 数据结构|链表常见面试题
- 数据结构|常见的链表面试题
- 数据结构|数据结构之链表+常见面试题
- 程序人生|学习C++需要看哪些书籍（这是我花了两年时间准备的书单）
- 2022/6/29学习总结
- c++|红黑树，插入和删除，基于C++的实现
- Java初级学习笔记|Java语法之多线程（线程的创建，线程的状态，线程安全）的使用
- 数据结构|【数据结构】约瑟夫环（单向循环链表的应用）——C语言