Java数据结构和算法(四) 链表

逆流者 2021年02月21日 22次浏览

链表(Linked List)介绍

链表是有序的列表,但是它在内存中是存储如下:
在这里插入图片描述

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

单向链表

单链表(带头结点) 逻辑结构示意图:
在这里插入图片描述

代码演示

package datastructure.linked;

/**
 * @author wsh
 * @date 2020-09-03 10:48
 */
public class SingleLinkedListDemo {

    public static void main(String[] args) {
        // 1、准备工作
        // 1.1 创建节点
        Node node1 = new Node(1, "第1个节点");
        Node node2 = new Node(2, "第2个节点");
        Node node3 = new Node(3, "第3个节点");
        Node node4 = new Node(4, "第4个节点");
        // 1.2 创建链表
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        // 2、测试添加
        // 2.1 随意添加节点
        singleLinkedList.add(node1);
        singleLinkedList.add(node4);
        singleLinkedList.add(node3);
        singleLinkedList.add(node2);
        System.out.println("随意添加节点显示:");
        singleLinkedList.list();
        singleLinkedList.removeAll();

        // 2.2 顺序添加节点
        singleLinkedList.addByOrder(node1);
        singleLinkedList.addByOrder(node4);
        singleLinkedList.addByOrder(node3);
        singleLinkedList.addByOrder(node2);
        System.out.println("顺序添加节点显示:");
        singleLinkedList.list();
        // 3、测试修改
        singleLinkedList.update(new Node(3, "第三个节点~~"));
        System.out.println("修改链表节点后显示:");
        singleLinkedList.list();
        // 4、测试删除
        singleLinkedList.delete(2);
        System.out.println("删除链表一个节点后显示:");
        singleLinkedList.list();
        singleLinkedList.delete(1);
        singleLinkedList.delete(4);
        singleLinkedList.delete(3);
        System.out.println("陆续删除链表中所有节点后显示:");
        singleLinkedList.list();

    }
}

/**
 * 单向链表
 */
class SingleLinkedList {

    /**
     * 初始化头节点,不放数据,不能动
     */
    private Node head = new Node(0, "");

    /**
     * 添加节点
     *
     * @param node 要添加的节点
     */
    public void add(Node node) {
        // temp 表示最后一个节点
        Node temp = head;
        while (temp.next != null) {
            // 没有到链表最后,将temp后移,继续找
            temp = temp.next;
        }
        // 链表最后
        temp.next = node;
    }

    /**
     * 添加节点(根据id顺序添加)
     *
     * @param node 要添加的节点
     */
    public void addByOrder(Node node) {
        // temp 实际要代表我们要添加位置的前一个节点
        Node temp = head;
        // 需要添加的编号是否存在,默认不存在
        boolean flag = false;

        while (true) {
            if (temp.next == null) {
                // 链表最后
                break;
            }
            if (temp.next.id > node.id) {
                break;
            } else if (temp.next.id == node.id) {
                flag = true;
                break;
            }
            // 将temp后移,继续遍历
            temp = temp.next;
        }
        if (flag) {
            System.out.printf("插入的节点 %d 已存在,不能添加!\n", node.id);
        } else {
            node.next = temp.next;
            temp.next = node;
        }
    }

    /**
     * 修改链表中的节点,注意,id不变,它是节点确定的标志
     * @param node 要修改的节点
     */
    public void update(Node node) {
        // 判断链表是否为空
        if (head.next == null) {
            System.out.println("链表为空!");
            return;
        }
        // 辅助变量
        Node temp = head.next;
        boolean isExist = false;
        while (temp != null) {
            if (temp.id == node.id) {
                isExist = true;
                break;
            }
            temp = temp.next;
        }
        if (isExist) {
            temp.name = node.name;
        } else {
            System.out.printf("链表中不存在编号 %d 的节点\n", node.id);
        }
    }

    /**
     * 删除节点
     * @param id 要删除节点的ip
     */
    public void delete(int id) {
        Node temp = head;
        // 是否找到要删除的几点
        boolean flag = false;
        while (temp.next != null) {
            if (temp.next.id == id) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            temp.next = temp.next.next;
        } else {
            System.out.printf("要删除的 %d 节点不存在\n", id);
        }
    }

    /**
     * 显示链表
     */
    public void list() {
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        Node temp = head.next;
        while (temp != null) {
            System.out.println(temp);
            temp = temp.next;
        }
    }

    /**
     * 清空链表
     */
    public void removeAll() {
        head.next = null;
        System.out.println("-------清空链表---------");
    }

}

class Node {

    public int id;
    public String name;
    public Node next;

    public Node(int id, String name) {
        this.id = id;
        this.name = name;
    }

    @Override
    public String toString() {
        return "Node{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }
}

测试结果:

随意添加节点显示:
Node{id=1, name='第1个节点'}
Node{id=4, name='第4个节点'}
Node{id=3, name='第3个节点'}
Node{id=2, name='第2个节点'}
-------清空链表---------
顺序添加节点显示:
Node{id=1, name='第1个节点'}
Node{id=2, name='第2个节点'}
Node{id=3, name='第3个节点'}
Node{id=4, name='第4个节点'}
修改链表节点后显示:
Node{id=1, name='第1个节点'}
Node{id=2, name='第2个节点'}
Node{id=3, name='第三个节点~~'}
Node{id=4, name='第4个节点'}
删除链表一个节点后显示:
Node{id=1, name='第1个节点'}
Node{id=3, name='第三个节点~~'}
Node{id=4, name='第4个节点'}
陆续删除链表中所有节点后显示:
链表为空

单链表面试题

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

/**
 * 获取有效节点的个数
 *
 * @param head 头节点
 * @return 个数
 */
public static int getLength(Node head) {
    if (head.next == null) {
        return 0;
    }
    int length = 0;
    // temp 辅助几点,不计算头节点
    Node temp = head.next;
    while (temp != null) {
        length++;
        temp = temp.next;
    }
    return length;
}

2、查找单链表中的倒数第 k 个结点

/**
 * 查找单链表中的倒数第 k 个结点
 * @param head 头节点
 * @param index 倒第几个
 * @return 倒第 几个 节点
 */
public static Node findLastIndexNode(Node head, int index) {
    if (head.next == null) {
        return null;
    }
    // 1. 获取链表的总长度
    int size = getLength(head);
    // 校验合法性
    if (index <= 0 || index > size) {
        return null;
    }
    // 辅助变量,使用for循环,定位到倒第index个节点
    Node cur = head.next;
    for (int i = 0; i < size - index; i++) {
        cur = cur.next;
    }
    return cur;
}

3、单链表反转

/**
* 单链表反转
 */
public static Node reverse(Node head) {
    if (head.next == null) {
        return null;
    }
    Node cur = head.next;
    // next 指向当前节点的下一个节点
    Node next = null;
    // 遍历原来的链表,没遍历一个节点,就将其取出,放在新的链表 reverseHead 的最前端
    Node reverseHead = new Node(0, "");
    while (cur != null) {
        // 暂时存下当前节点的下一个节点
        next = cur.next;
        // 将cur的下一个节点指向新的链表的最前端
        cur.next = reverseHead.next;
        // 将当前的cur 连接到新的链表上
        reverseHead.next = cur;
        // 当前cur后移
        cur = next;
    }
    // 最终实现单链表的反转
    head.next = reverseHead.next;
    return head;
}

4、从尾到头打印单链表

/**
 * 从尾到头打印单链表,使用栈(Stack)先进后出
 */
public static void reversePrint(Node head) {
    if (head.next == null) {
        return;
    }
    // 创建一个栈
    Stack<Node> stack = new Stack<>();
    Node cur = head.next;
    // 将节点压入栈中
    while (cur != null) {
        stack.push(cur);
        cur = cur.next;
    }
    // 将栈中的节点进行出栈打印
    while (stack.size() > 0) {
        System.out.println(stack.pop());
    }
}

双向链表

和单向链表的对比:

  • 单向链表,查找的方向只能是一个方向,而双向链表可以向前或者向后查找。
  • 单向链表不能自我删除,需要靠辅助节点 ,而双向链表,则可以自我删除,所以前面我们单链表删除时节点,总是找到 temp,temp 是待删除节点的前一个节点。

代码演示:

package datastructure.linked;

/**
 * @author wsh
 * @date 2020-09-03 10:48
 */
public class DoubleLinkedListDemo {

    public static void main(String[] args) {
        System.out.println("双向链表测试:");
        // 1、准备工作
        // 1.1 创建节点
        Node2 node1 = new Node2(1, "第1个节点");
        Node2 node2 = new Node2(2, "第2个节点");
        Node2 node3 = new Node2(3, "第3个节点");
        Node2 node4 = new Node2(4, "第4个节点");
        // 1.2 创建链表
        DoubleLinkedList linkedList = new DoubleLinkedList();
        // 2、测试添加
        linkedList.add(node1);
        linkedList.add(node4);
        linkedList.add(node3);
        linkedList.add(node2);
        System.out.println("添加节点显示:");
        linkedList.list();
        // 3、修改
        linkedList.update(new Node2(3, "修改节点3"));
        System.out.println("修改后的链表显示:");
        linkedList.list();
        // 4、删除
        linkedList.delete(2);
        System.out.println("删除后链表显示:");
        linkedList.list();
    }
}

/**
 * 单向链表
 */
class DoubleLinkedList {

    /**
     * 初始化头节点,不放数据,不能动
     */
    private Node2 head = new Node2(0, "");

    public Node2 getHead() {
        return head;
    }

    /**
     * 添加节点
     *
     * @param node 要添加的节点
     */
    public void add(Node2 node) {
        // temp 表示最后一个节点
        Node2 temp = head;
        while (temp.next != null) {
            // 没有到链表最后,将temp后移,继续找
            temp = temp.next;
        }
        // 链表最后
        temp.next = node;
        node.pre = temp;
    }

    /**
     * 修改链表中的节点,注意,id不变,它是节点确定的标志
     *
     * @param node 要修改的节点
     */
    public void update(Node2 node) {
        // 判断链表是否为空
        if (head.next == null) {
            System.out.println("链表为空!");
            return;
        }
        // 辅助变量
        Node2 temp = head.next;
        boolean isExist = false;
        while (temp != null) {
            if (temp.id == node.id) {
                isExist = true;
                break;
            }
            temp = temp.next;
        }
        if (isExist) {
            temp.name = node.name;
        } else {
            System.out.printf("链表中不存在编号 %d 的节点\n", node.id);
        }
    }

    /**
     * 删除节点
     * 双向链表可以自我删除
     * @param id 要删除节点的ip
     */
    public void delete(int id) {
        Node2 temp = head.next;
        // 是否找到要删除的几点
        boolean flag = false;
        while (temp != null) {
            if (temp.id == id) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            // 这里实现了自我删除
            temp.pre.next = temp.next;
            // 这里要判断下,不判断,如果temp是最后一个节点会出现空指针
            if (temp.next != null) {
                temp.next.pre = temp.pre;
            }
        } else {
            System.out.printf("要删除的 %d 节点不存在\n", id);
        }
    }

    /**
     * 显示链表
     */
    public void list() {
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        Node2 temp = head.next;
        while (temp != null) {
            System.out.println(temp);
            temp = temp.next;
        }
    }

}

class Node2 {

    public int id;
    public String name;
    public Node2 pre;
    public Node2 next;

    public Node2(int id, String name) {
        this.id = id;
        this.name = name;
    }

    @Override
    public String toString() {
        return "Node2{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }
}

测试结果:

双向链表测试:
添加节点显示:
Node2{id=1, name='第1个节点'}
Node2{id=4, name='第4个节点'}
Node2{id=3, name='第3个节点'}
Node2{id=2, name='第2个节点'}
修改后的链表显示:
Node2{id=1, name='第1个节点'}
Node2{id=4, name='第4个节点'}
Node2{id=3, name='修改节点3'}
Node2{id=2, name='第2个节点'}
删除后链表显示:
Node2{id=1, name='第1个节点'}
Node2{id=4, name='第4个节点'}
Node2{id=3, name='修改节点3'}

单向环形链表

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

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

分析

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

代码演示

package datastructure.linked;

/**
 * @author wsh
 * @date 2020/9/7 4:30 下午
 */
public class Josephu {

    public static void main(String[] args) {
        CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
        // 圈中小孩总数
        int nums = 20;
        circleSingleLinkedList.add(nums);
        System.out.println("圈中所有小孩:");
        circleSingleLinkedList.showChild();
        // 从第几个小孩开始报数
        int startNo = 3;
        // 报几下数
        int countNum = 4;
        System.out.printf("圈中共有 %d 个小孩,从第 %d 个小孩开始报数,报 %d 下出圈\n", nums, startNo, countNum);
        circleSingleLinkedList.countChild(startNo, countNum, nums);
    }
}

class CircleSingleLinkedList {
    private Child first = null;

    /**
     * 构建环形链表
     *
     * @param nums 小孩数
     */
    public void add(int nums) {
        if (nums < 1) {
            System.out.println("nums的值不正确!");
            return;
        }
        Child cur = null;
        for (int i = 1; i <= nums; i++) {
            Child child = new Child(i);

            if (i == 1) {
                first = child;
                first.setNext(first);
                cur = first;
            } else {
                cur.setNext(child);
                child.setNext(first);
                cur = child;
            }
        }
    }

    /**
     * 显示环形链表
     */
    public void showChild() {
        if (first == null) {
            System.out.println("没有小孩");
            return;
        }
        Child curChild = first;
        while (true) {
            System.out.printf("小孩编号 %d \n", curChild.getId());
            if (curChild.getNext() == first) {
                break;
            }
            curChild = curChild.getNext();

        }

    }

    /**
     * 根据入参,计算小孩出圈的顺序
     *
     * @param startNo  从第几个小孩开始数数
     * @param countNum 数几下
     * @param nums     一共多少个小孩
     */
    public void countChild(int startNo, int countNum, int nums) {
        if (first == null || startNo < 1 || startNo > nums) {
            System.out.println("参数错误");
            return;
        }
        Child helper = first;
        // 把辅助节点指向环形链表的最后一个节点
        while (helper.getNext() != first) {
            helper = helper.getNext();
        }
        // 小孩报数前,把first和helper 移动到第一个报数小孩上
        for (int i = 0; i < startNo - 1; i++) {
            first = first.getNext();
            helper = helper.getNext();
        }

        // 圈中有两个或两个以上小孩
        // helper == first 表示圈中只有一个小孩
        while (helper != first) {
            for (int i = 0; i < countNum - 1; i++) {
                first = first.getNext();
                helper = helper.getNext();
            }
            System.out.printf("小孩 %d 出圈\n", first.getId());
            first = first.getNext();
            helper.setNext(first);
        }
        System.out.printf("最后留在圈中的小孩编号 %d\n", first.getId());
    }
}

/**
 * 小孩
 */
class Child {
    private int id;
    private Child next;

    public Child(int id) {
        this.id = id;
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public Child getNext() {
        return next;
    }

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

测试结果:

圈中所有小孩:
小孩编号 1 
小孩编号 2 
小孩编号 3 
小孩编号 4 
小孩编号 5 
小孩编号 6 
小孩编号 7 
小孩编号 8 
小孩编号 9 
小孩编号 10 
小孩编号 11 
小孩编号 12 
小孩编号 13 
小孩编号 14 
小孩编号 15 
小孩编号 16 
小孩编号 17 
小孩编号 18 
小孩编号 19 
小孩编号 20 
圈中共有 20 个小孩,从第 3 个小孩开始报数,报 4 下出圈
小孩 6 出圈
小孩 10 出圈
小孩 14 出圈
小孩 18 出圈
小孩 2 出圈
小孩 7 出圈
小孩 12 出圈
小孩 17 出圈
小孩 3 出圈
小孩 9 出圈
小孩 16 出圈
小孩 4 出圈
小孩 13 出圈
小孩 1 出圈
小孩 15 出圈
小孩 8 出圈
小孩 5 出圈
小孩 11 出圈
小孩 20 出圈
最后留在圈中的小孩编号 19