单向链表及常见面试题和双向链表

发布时间:2022-08-19 12:36

单向链表

单向链表(单链表)是链表的一种,其特点是链表的链接方向是单向的,对链表的访问要通过顺序读取从头部开始;链表是使用指针进行构造的列表;又称为结点列表,因为链表是由一个个结点组装起来的;其中每个结点都有指针成员变量指向列表中的下一个结点;
链表是由结点构成,head指针指向第一个成为表头结点,而终止于最后一个指向NULL的指针。
单向链表及常见面试题和双向链表_第1张图片
小结上图:
(1)链表是以节点的方式存储,是链式存储
(2)每个节点包含data域,next域:指向下一个节点
(3)如图:发现链表的各个节点不一定是连续存储
(4)链表分带头节点的链表没有头节点的链表,根据实际的需求来确定

我们操作的习惯是让头节点为空,作用就是表示单链表的头。然后一次进行操作。

添加操作(创建):

  1. 先创建一个head头节点,作用就是表示单链表的头
  2. 后面我们每添加一个节点,就直接加入到链表的最后

遍历:
通过一个辅助变量(指针),帮助遍历整个链表

按照序号的顺序添加:

  1. 首先找到新添加节点的位子,是通过辅助变量(指针),通过遍历搞定
  2. 新的节点.next=temp.next
  3. 将temp.next=新的节点

修改节点:

  1. 首先找到需要修改的位子,是通过辅助变量(指针),通过遍历搞定
  2. 找到后,修改信息

删除节点:

  1. 我们先找到需要删除的节点的前一个节点
  2. temp.next=temp.next.next
  3. 被删除的节点,将不会有其他引用指向,会被垃圾回收机制回收



实现上述操作的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 void  show(){
        //判断链表是否为空
        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<temp.next.no){//位置找到,就在temp的后面插入
                break;
            }else if (node.no==temp.next.no){//说明添加的heronode已经存在了
                flag=true;  //说明编号存在
                break;
            }
            temp=temp.next;//后移,遍历当前链表
        }
        //判断flag的值
        if (flag){  //不能添加,说明编号已经存在
            System.out.println("准备插入的英雄的编号"+node.no+"已经存在,不能加入");
        }else {
            //插入到链表,temp的后面
            node.next=temp.next;
            temp.next=node;
        }
    }
    //删除节点
    public void delete(int no){
        if (head.next==null){
            System.out.println("链表为空");
            return;
        }
        HeroInfo temp=head;
        while (true){
            if (temp==null){
                return;
            }
            if (temp.next.no==no){
                temp.next=temp.next.next;
                break;
            }
            temp=temp.next;
        }
    }
    //修改信息
    public void update(HeroInfo node){
        if (head.next==null){
            System.out.println("链表为空");
            return;
        }
        HeroInfo temp=head;
        while (true){
            if (temp==null){
                return;
            }
            if (temp.no==node.no){
                temp.name=node.name;
                temp.nickname=node.nickname;
            }
            temp=temp.next;
        }
    }

}
//定义heroinfo,每个heroinfo就是一个节点
class HeroInfo{
    public  int no;
    public  String name;
    public String nickname;
    public HeroInfo next; //指向下一个节点
    //构造器
    public HeroInfo(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 + '\'' +
                '}';
    }
}


单链表的常见面试题:

(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个 4  3次   倒数第二个   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<HeroInfo> 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<String> 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<temp.next.no){//位置找到,就在temp的后面插入
                break;
            }else if (node.no==temp.next.no){//说明添加的heronode已经存在了
                flag=true;  //说明编号存在
                break;
            }
            temp=temp.next;//后移,遍历当前链表
        }
        //判断flag的值
        if (flag){  //不能添加,说明编号已经存在
            System.out.println("准备插入的英雄的编号"+node.no+"已经存在,不能加入");
        }else {
            //插入到链表,temp的后面
            node.next=temp.next;
            temp.next=node;
        }
    }
    public void  show(){
        //判断链表是否为空
        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;
        }
    }
}

双向链表

使用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 void  show(){
        //判断链表是否为空
        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{
    public  int no;
    public  String 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 + '\'' +
                '}';
    }
}

ItVuer - 免责声明 - 关于我们 - 联系我们

本网站信息来源于互联网,如有侵权请联系:561261067@qq.com

桂ICP备16001015号