投稿
  1. 极客之音首页
  2. 技术随笔

数据结构之链表

飞熊 • • 技术随笔 • 阅读 270

勤奋不是嘴上说说而已，而是实际的行动，在勤奋的苦度中持之以恒，永不退却。业精于勤，荒于嬉；行成于思，毁于随。在人生的仕途上，我们毫不迟疑地选择勤奋，她是几乎于世界上一切成就的催产婆。只要我们拥着勤奋去思考，拥着勤奋的手去耕耘，用抱勤奋的心去对待工作，浪迹红尘而坚韧不拔，那么，我们的生命就会绽放火花，让人生的时光更加的闪亮而精彩。

导读：本篇文章讲解 数据结构之链表，希望对大家有帮助，欢迎收藏，转发！站点地址：www.bmabk.com，来源：原文

数据结构之链表

链表（Linked List）介绍

链表是有序的列表，但是它在内存中是存储如下：

image-20220118213708139

小结:

  1. 链表是以节点的方式来存储,是链式存储
  2. 每个节点包含 data 域， next 域：指向下一个节点.
  3. 如图：发现链表的各个节点不一定是连续存储.
  4. 链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定

单链表(带头结点) 逻辑结构示意图如下单链表(带头结点) 逻辑结构示意图如下

image-20220118213844177

单链表应用举例

使用带head头的单向链表实现 –水浒英雄排行榜管理完成对英雄人物的增删改查操作， 注: 删除和修改

添加节点

第一种方法在添加英雄时，直接添加到链表的尾部

思路分析示意图：

image-20220118214238061

第二种方式在添加英雄时，根据排名将英雄插入到指定位置(如果有这个排名，则添加失败，并给出提示)

思路分析示意图：

image-20220118214443726

修改节点

思路：

  1. 先通过遍历找到该节点
  2. temp.name = newHeroNode.name; temp.nickname = newHeroNode.nickname;

删除节点

思路分析示意图：

image-20220118215005481

代码

package cn.tedu.linkedlist;

import java.util.Stack;

/**
 * @ClassName SingleLinkedListDemo
 * @Description
 * @Author keke
 * @Time 2022/1/5 23:36
 * @Version 1.0
 */
public class SingleLinkedListDemo {

    public static void main(String[] args) {
        // 先创建节点
        HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");
        HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
        HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
        // 创建一个链表
        SingleLinkedList singleLinkedList = new SingleLinkedList();

        // 加入
        singleLinkedList.add(hero1);
        singleLinkedList.add(hero4);
        singleLinkedList.add(hero2);
        singleLinkedList.add(hero3);
        // 测试修改节点的代码
        HeroNode newHeroNode = new HeroNode(2, "小卢", "玉麒麟~~");
        singleLinkedList.update(newHeroNode);
        // 显示
        singleLinkedList.list();
        singleLinkedList.delete(1);
        singleLinkedList.delete(4);
        singleLinkedList.list();
        System.out.println("有效节点的个数：" + getLength(singleLinkedList.getHead()));
        HeroNode result = findLastIndexNode(singleLinkedList.getHead(), 1);
        System.out.println(result);
    }
}

/**
 * 定义 SingleLinkedList 管理英雄
 */
class SingleLinkedList {
    // 先初始化一个头节点，头节点不要动，不存放具体数据
    private HeroNode head = new HeroNode(0, "", "");

    public HeroNode getHead() {
        return head;
    }

    /**
     * 添加节点到单向链表
     * 当不考虑编号顺序时，找到当前链表的最后节点，将最后这个节点的 next 指向新的节点
     */
    public void add(HeroNode heroNode) {
        // 因为 head 节点不能动，因此需要一个辅助变量 temp
        HeroNode temp = head;
        // 遍历链表，找到最后
        while (true) {
            // 找到链表最后
            if (temp.next == null) {
                break;
            }
            // 如果没有找到最后，将 temp 后移
            temp = temp.next;
        }
        // 当退出 while 循环时， temp 就指向了链表的最后
        // 将最后这个节点的 next，指向新的节点
        temp.next = heroNode;
    }

    /**
     * 第二种方式在添加英雄时，根据排名将英雄插入到指定位置  (如果有这个排名，则添加失败，并给出提示)
     *
     * @param heroNode
     */
    public void addByOrder(HeroNode heroNode) {
        // 因为头节点不能动，因此仍然通过一个辅助指针来帮助找到添加的位置
        // 因为单链表，找的 temp 是位于添加位置的前一个节点，否则插入不了
        HeroNode temp = head;
        // 标识添加的编号是否存在，默认为 false
        boolean flag = false;
        while (true) {
            // 说明 temp 已经在链表的最后
            if (temp.next == null) {
                break;
            }
            // 位置找到了，就在 temp 的后面插入
            if (temp.next.no > heroNode.no) {
                break;
            } else if (temp.next.no == heroNode.no) {
                // 说明希望添加的 heroNode 的编号已然存在
                flag = true;
                break;
            }
            // 后移，遍历当前链表
            temp = temp.next;
        }
        // 判断 flag
        if (flag) {
            // 不能添加，说明编号存在
            System.out.println("准备插入的英雄的编号：" + heroNode.no + "已经存在，不能加入");
        } else {
            // 插入到链表中，temp 的后面
            heroNode.next = temp.next;
            temp.next = heroNode;
        }
    }

    /**
     * 修改节点的信息，根据 no 编号来修改，即 no 编号不能修改
     * 1.根据 newHeroNode 的 no 来修改即可
     */
    public void update(HeroNode newHeroNode) {
        // 判断是否为空
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        // 找到需要修改的节点，根据 no 编号
        // 定义一个辅助变量
        HeroNode temp = head.next;
        // 表示是否找到该节点
        boolean flag = false;
        while (true) {
            if (temp == null) {
                // 已经遍历完链表
                break;
            }
            if (temp.no == newHeroNode.no) {
                // 找到了
                flag = true;
                break;
            }
            temp = temp.next;
        }
        // 根据 flag 判断是否找到要修改的节点
        if (flag) {
            temp.name = newHeroNode.name;
            temp.nickname = newHeroNode.nickname;
        } else {
            // 没有找到
            System.out.println("没有找到编号 " + newHeroNode.no + " 的节点，不能修改");
        }
    }

    /**
     * 删除节点
     * 1.head 不能动，因此需要一个辅助节点找到待删除节点的前一个节点
     * 2.说明在比较时，是 temp.nex.no 和需要删除的节点的 no 比较
     *
     * @param no
     */
    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 = temp.next;
        }
        if (flag) {
            // 可以删除
            temp.next = temp.next.next;
        } else {
            System.out.printf("要删除的 %d 节点不存在\n", no);
        }
    }

    /**
     * 显示链表
     */
    public void list() {
        // 判断链表是否为空
        if (head.next == null) {
            throw new RuntimeException("链表为空");
        }
        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(int no, String name, String nickname) {
        this.no = no;
        this.name = name;
        this.nickname = nickname;
    }

    /**
     * 为了显示方法
     *
     * @return
     */
    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickname='" + nickname + '\'' +
                '}';
    }
}

单链表面试题

求单链表中有效节点的个数

代码：

/**
 * 获取到单链表中有效节点的个数(如果是带头节点的链表，需要不统计头节点)
 * @param head 链表的头节点
 * @return 返回的是有效节点的个数
 */
public static int getLength(HeroNode head) {
    // 空链表
    if (head.next == null) {
        return 0;
    }
    int length = 0;
    // 定义一个辅助变量，指令没有统计头节点
    HeroNode cur = head.next;
    while (cur != null) {
        length++;
        cur = cur.next;
    }
    return length;
}

第 K 个节点

代码:

/**
 * 查找单链表的倒数第 k 个节点 [sina]
 * 1.编写一个方法，接收 head 节点，同时接收一个 index
 * 2.index 表示是倒数第 index 个节点
 * 3.先把链表从头到尾遍历，得到链表的总长度 getLength
 * 4.得到 size 后，从链表的第一个开始遍历 (size - index) 个，就可以得到
 * 5.如果找到了，则返回该节点，否则返回 null
 */
public static HeroNode findLastIndexNode(HeroNode head, int index) {
    // 判断链表如果为空，返回 null
    if (head.next == null) {
        return null;
    }
    // 第一次遍历得到链表的长度(节点个数)
    int size = getLength(head);
    // 第二次遍历 size - index 位置，就是倒数的第 k 个节点
    // 先做一个 index 的校验
    if (index <= 0 || index > size) {
        return null;
    }
    // 定义辅助变量，for循环定位到倒数的 index
    HeroNode cur = head.next;
    for (int i = 0; i < size - index; i++) {
        cur = cur.next;
    }
    return cur;
}

单链表的反转【腾讯面试题】

思路分析图解：

image-20220118220251156

image-20220118220452450

代码：

/**
 * 单链表的反转 [tencent]
 */
public static void reverseList(HeroNode head) {
    // 如果当前链表为空，或者只有一个节点，无序反转，直接返回
    if (head.next == null || head.next.next == null) {
        return;
    }
    // 定义一个辅助指针，帮助遍历原来的链表
    HeroNode cur = head.next;
    // 指向当前节点 cur 的下一个节点
    HeroNode next = null;
    HeroNode reverseHead = new HeroNode(0, "", "");
    // 遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表 reverseHead 的最前端.
    while (cur != null){
        // 先暂时保存当前节点的下一个节点，后面需要使用
        next = cur.next;
        // 将 cur 的下一个节点指向新的链表的最前端
        cur.next = reverseHead.next;
        // 将 cur 连接到新的链表上
        reverseHead.next = cur;
        // 让 cur 后移
        cur = next;
    }
    // 将 head.next 指向 reverseHead.next，实现单链表的反转
    head.next = reverseHead.next;
}

从尾到头打印单链表 【百度，要求方式1：反向遍历 。 方式2：Stack栈】

思路分析图解：

image-20220118220653361

代码：

/**
 * 从尾到头打印单链表 [baidu，方式：Stack 栈]
 */
public static void reversePrint(HeroNode head){
    if (head.next == null) {
        return;
    }
    // 创建一个栈，将各个节点压入栈
    Stack<HeroNode> stack = new Stack<>();
    HeroNode cur = head.next;
    // 将列表所有节点压入栈
    while (cur != null){
        stack.push(cur);
        // cur 后移，这样就可以压入下一个节点
        cur = cur.next;
    }
    // 将栈中的节点进行打印，pop 出栈
    while (stack.size() > 0){
        // stack 的特点是先进后出
        System.out.println(stack.pop());
    }
}

双向链表应用举例

使用带head头的双向链表实现 –水浒英雄排行榜

管理单向链表的缺点分析:

  1. 单向链表，查找的方向只能是一个方向，而双向链表可以向前或者向后查找。

  2. 单向链表不能自我删除，需要靠辅助节点 ，而双向链表，则可以自我删除，所以前面我们单链表删除时节点，总是找到temp,temp是待删除节点的前一个节点

image-20220118221521636

分析 双向链表的遍历，添加，修改，删除的操作思路===》代码实现

  • 遍历 方和 单链表一样，只是可以向前，也可以向后查找

  • 添加 (默认添加到双向链表的最后)

    • 先找到双向链表的最后这个节点
    • temp.next = newHeroNode
    • newHeroNode.pre = temp;

  • 修改 思路和 原来的单向链表一样.

  • 删除

    • 因为是双向链表，因此，我们可以实现自我删除某个节点
    • 直接找到要删除的这个节点，比如temp
    • temp.pre.next = temp.next
    • temp.next.pre = temp.pre;

代码实现：

package cn.tedu.linkedlist;

/**
 * @ClassName DoubleLinkedListDemo
 * @Description
 * @Author keke
 * @Time 2022/1/17 21:54
 * @Version 1.0
 */
public class DoubleLinkedListDemo {

    public static void main(String[] args) {
        System.out.println("双向链表的测试：");
        HeroNode2 hero1 = new HeroNode2(1, "宋江", "及时雨");
        HeroNode2 hero2 = new HeroNode2(2, "卢俊义", "玉麒麟");
        HeroNode2 hero3 = new HeroNode2(3, "吴用", "智多星");
        HeroNode2 hero4 = new HeroNode2(4, "林冲", "豹子头");
        // 创建一个双向链表
        DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
        doubleLinkedList.add(hero1);
        doubleLinkedList.add(hero2);
        doubleLinkedList.add(hero3);
        doubleLinkedList.add(hero4);

        doubleLinkedList.list();

        // 修改
        HeroNode2 newHeroNode = new HeroNode2(4, "公孙胜", "入云龙");
        doubleLinkedList.update(newHeroNode);
        System.out.println("修改后的链表情况：");
        doubleLinkedList.list();
        // 删除
        doubleLinkedList.delete(3);
        System.out.println("删除后的链表情况：");
        doubleLinkedList.list();
    }
}


/**
 * 创建一个 双向链表的类
 */
class DoubleLinkedList{

    // 先初始化一个头节点，头节点不要动，不存放具体的数据
    private HeroNode2 head = new HeroNode2(0, "", "");

    /**
     * 返回头节点
     */
    public HeroNode2 getHead(){
        return head;
    }

    /**
     * 遍历双向链表
     */
    public void list() {
        // 判断链表是否为空
        if (head.next == null) {
            throw new RuntimeException("链表为空");
        }
        HeroNode2 temp = head.next;
        while (true) {
            // 判断是否到最后
            if (temp == null) {
                break;
            }
            // 输出节点信息
            System.out.println(temp);
            // 将 temp 后移
            temp = temp.next;
        }
    }

    public void add(HeroNode2 heroNode) {
        // 因为 head 节点不能动，因此需要一个辅助变量 temp
        HeroNode2 temp = head;
        // 遍历链表，找到最后
        while (true) {
            // 找到链表最后
            if (temp.next == null) {
                break;
            }
            // 如果没有找到最后，将 temp 后移
            temp = temp.next;
        }
        // 当退出 while 循环时， temp 就指向了链表的最后
        // 形成一个双向链表
        temp.next = heroNode;
        heroNode.pre = temp;
    }

    /**
     * 修改一个节点的内容，可以看到双向链表的节点内容修改和单向链表一样
     * 只是节点类型改成 HeroNode2
     * @param newHeroNode
     */
    public void update(HeroNode2 newHeroNode) {
        // 判断是否为空
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        // 找到需要修改的节点，根据 no 编号
        // 定义一个辅助变量
        HeroNode2 temp = head.next;
        // 表示是否找到该节点
        boolean flag = false;
        while (true) {
            if (temp == null) {
                // 已经遍历完链表
                break;
            }
            if (temp.no == newHeroNode.no) {
                // 找到了
                flag = true;
                break;
            }
            temp = temp.next;
        }
        // 根据 flag 判断是否找到要修改的节点
        if (flag) {
            temp.name = newHeroNode.name;
            temp.nickname = newHeroNode.nickname;
        } else {
            // 没有找到
            System.out.println("没有找到编号 " + newHeroNode.no + " 的节点，不能修改");
        }
    }

    /**
     * 从双向链表中删除节点
     * 1.对于双向链表，可以直接找到要删除的这个节点
     * 2.找到后，自我删除即可
     */
    public void delete(int no) {
        // 判断当前链表是否为空
        if (head.next == null) {
            throw new RuntimeException("链表为空，无法删除");
        }
        HeroNode2 temp = head.next;
        // 标识是否找到待删除节点
        boolean flag = false;
        while (true) {
            // 已经找到链表的最后
            if (temp == null) {
                break;
            }
            if (temp.no == no) {
                // 找到待删除节点
                flag = true;
                break;
            }
            // temp 后移
            temp = temp.next;
        }
        if (flag) {
            // 可以删除
            temp.pre.next = temp.next;
            // 有问题？
            // 如果是最后一个节点，就不需要执行下面这句话，否则出现空指针
            if (temp.next != null) {
                temp.next.pre = temp.pre;
            }
        } else {
            System.out.printf("要删除的 %d 节点不存在\n", no);
        }
    }
}

/**
 * 定义一个 HeroNode2，每个 HeroNode2 对象就是一个节点
 */
class HeroNode2 {
    public int no;
    public String name;
    public String nickname;

    /**
     * 指向下一个节点，默认为 null
     */
    public HeroNode2 next;

    /**
     * 指向前一个节点，默认为 null
     */
    public HeroNode2 pre;

    public HeroNode2(int no, String name, String nickname) {
        this.no = no;
        this.name = name;
        this.nickname = nickname;
    }

    /**
     * 为了显示方法
     *
     * @return
     */
    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickname='" + nickname + '\'' +
                '}';
    }
}

Josephu(约瑟夫、约瑟夫环) 问题

Josephu 问题为：设编号为1，2，… n的n个人围坐一圈，约定编号为k（1<=k<=n）的人从1开始报数，数到m 的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。

提示：用一个不带头结点的循环链表来处理Josephu 问题：先构成一个有n个结点的单循环链表，然后由k结点起从1开始计数，计到m时，对应结点从链表中删除，然后再从被删除结点的下一个结点又从1开始计数，直到最后一个结点从链表中删除算法结束。

image-20220118221950637

单向环形链表介绍

image-20220118222046966

实现

思路分析示意图：

image-20220118222203171

image-20220118222323096

image-20220118222356578

代码:

package cn.tedu.linkedlist;

/**
 * @ClassName Josepfu
 * @Description
 * @Author keke
 * @Time 2022/1/17 22:56
 * @Version 1.0
 */
public class Josepfu {

    public static void main(String[] args) {
        CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
        circleSingleLinkedList.addBoy(5);
        circleSingleLinkedList.showBoy();
        circleSingleLinkedList.countBoy(1, 2, 5);
    }
}

/**
 * 创建一个环形单向链表
 */
class CircleSingleLinkedList{

    /**
     * 创建一个 first 节点，当前没有编号
     */
    private Boy first = new Boy(-1);

    /**
     * 添加小孩节点，构建成环形链表
     */
    public void addBoy(int nums){
        // nums 做一个数据校验
        if (nums < 1){
            throw new RuntimeException("nums 的值不正确");
        }
        // 辅助指针，帮助构建环形链表
        Boy curBoy = null;
        // 使用 for 循环创建环形链表
        for (int i = 1; i <= nums; i++) {
            // 根据编号，创建小孩节点
            Boy boy = new Boy(i);
            // 如果是第一个小孩
            if (i == 1) {
                first = boy;
                // 构成环
                first.setNext(first);
                // 让 curBoy 指向第一个小孩
                curBoy = first;
            }else {
                curBoy.setNext(boy);
                boy.setNext(first);
                curBoy = boy;
            }
        }
    }

    /**
     * 遍历当前环形链表
     */
    public void showBoy(){
        // 判断链表是否为空
        if (first == null){
            throw new RuntimeException("没有任何小孩");
        }

        // 因为 first 不能动，因此使用辅助指针完成遍历
        Boy curBoy = this.first;
        while (true){
            System.out.println("小孩的编号：" + curBoy.getNo());
            // 说明已经遍历完毕
            if (curBoy.getNext() == first){
                break;
            }
            // curBoy 后移
            curBoy = curBoy.getNext();
        }
    }

    /**
     * 根据用户的输入，计算小孩出圈的顺序
     * @param startNo 表示从第几个小孩开始数数
     * @param countNum 表示数几下
     * @param nums 表示最初有多少小孩在圈中
     */
    public void countBoy(int startNo, int countNum, int nums){
        // 数据校验
        if (first == null || startNo < 1 || startNo > nums){
            throw new RuntimeException("参数输入有误");
        }
        // 创建一个辅助指针，帮助完成小孩出圈
        Boy helper = first;
        // 事先应该指向环形链表的最后这个节点
        while (true){
            // 说明 helper 指向最后小孩节点
            if (helper.getNext() == first){
                break;
            }
            helper = helper.getNext();
        }
        // 小孩报数前，先让 first 和 helper 移动 k - 1 次
        for (int i = 0; i < startNo - 1; i++) {
            first = first.getNext();
            helper = helper.getNext();
        }
        // 当小孩报数时，让 first 和 helper 指针同时移动 m - 1 次，然后出圈
        // 这里是一个循环操作，直到圈中只有一个节点
        while (true){
            // 说明圈中只有一个节点
            if (helper == first){
                break;
            }
            // 让 first 和 helper 移动 countNum - 1 次
            for (int i = 0; i < countNum - 1; i++) {
                first = first.getNext();
                helper = helper.getNext();
            }
            // 这时 first 指向的节点，就是要出圈的小孩节点
            System.out.println("小孩：" + first.getNo() + "出圈");
            // 这时将 first 指向的小孩节点出圈
            first = first.getNext();
            helper.setNext(first);
        }
        System.out.println("最后留在圈中的小孩编号：" + first.getNo());
    }
}

/**
 * 创建一个 Boy 类，表示一个节点
 */
class Boy{

    /**
     * 编号
     */
    private int no;

    /**
     * 指向下一个节点，默认为空
     */
    private Boy next;

    public Boy(int no) {
        this.no = no;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public Boy getNext() {
        return next;
    }

    public void setNext(Boy next) {
        this.next = next;
    }
}

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。

文章由极客之家整理，本文链接：https://www.bmabk.com/index.php/post/141904.html

赞 (0)
飞熊的头像飞熊bm
0 0

相关推荐

发表回复

登录后才能评论
极客之家——专业性很强的中文编程技术网站，欢迎收藏到浏览器，订阅我们！