数据结构与算法笔记（2）链表

链表

单链表

1. 链表是有序的列表，以节点的方式来存储，是链式存储。
2. 每个节点包含data域，next域。
3. 链表的各个检点不一定是连续存储。
4. 链表分有头节点的链表和没有头节点的链表，根据实际的需求确定。

代码实现：

package cn.Retur0;

public class SingleLinkedList {
    public static void main(String[] args) {
        LinkedList ll = new LinkedList();

        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);

//        ll.add(node1);
//        ll.add(node4);
//        ll.add(node2);
//        ll.add(node3);

        ll.addByOrder(node1);
        ll.addByOrder(node3);
        ll.addByOrder(node4);
        ll.addByOrder(node2);

        ll.show();

        ll.delete(3);

        ll.show();
    }
}

// 管理类
class LinkedList {
    // 初始化一个头结点
    private Node head = new Node(0);

    // 添加节点到链表尾方法
    public void add(Node node) {
        Node temp = head;
        while (temp.next != null) {
            // 如果不是最后一个节点，将temp后移
            temp = temp.next;
        }
        // 退出while时，temp就指向了量表的最后。
        temp.next = node;
    }

    // 按照data值大小顺序插入node
    public void addByOrder(Node node) {
        Node temp = head;
        boolean flag = false; // 标志添加的编号是否存在

        // 因为是单链表，要找的temp时要添加位置的前一个节点
        while (temp.next != null) {
            if (temp.next.data > node.data)
                break;
            if (temp.next.data == node.data) {
                flag = true;
                break;
            }
            temp = temp.next;
        }

        if (flag) {
            System.out.println("data值" + node.data + "重复");
        } else {
            // 如果不重复，添加
            node.next = temp.next;
            temp.next = node;
        }
    }

    // 删除节点
    public void delete(int data) {
        Node temp = head;
        boolean flag = false;
        while (temp != null) {
            if (temp.next == null)
                break;
            if (temp.next.data == data) {
                flag = true;
                break;
            }
            temp = temp.next;
        }

        if (flag) {
            temp.next = temp.next.next;
        } else {
            System.out.println("节点不存在");
        }
    }

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

// 定义node
class Node {
    public int data;
    public Node next;

    public Node(int data) {
        this.data = data;
    }

    @Override
    public String toString() {
        return "Node{" +
                "data=" + data +
                '}';
    }
}

双向链表

管理单项链表的缺点分析：

1. 单链表查找的方向智能式一个方向，而双向链表可以向前或向后查找。
2. 单链表不能自我删除，需要靠辅助节点。而双向链表可以自我删除。

环形链表与约瑟夫问题

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

构建一个单向的环形链表：

1. 先创建第一个节点，让first指向改建点，并形成环形。
2. 后面我们每创建一个新节点，就把该节点加入到已有的环形链表中。

代码实现：

package cn.Retur0.linkedlist;

public class Josepfu {
    public static void main(String[] args) {
        CircleSinglyLinkedList c = new CircleSinglyLinkedList(5);
        c.count(1,2,5);
    }
}

// 创建环形单向链表
class CircleSinglyLinkedList {
    // 创建first节点，当前没有编号
    private Boy first = null;

    public CircleSinglyLinkedList(int nums) {
        // 校验nums
        if (nums < 1)
            throw new RuntimeException("nums的值不正确");

        // 创建环形链表
        Boy cur = null; // 辅助指针
        for (int i = 1; i <= nums; i++) {
            Boy boy = new Boy(i);
            //如果是第一个boy
            if (i == 1) {
                first = boy;
                first.setNext(first);
                cur = first;
            } else {
                cur.setNext(boy);
                boy.setNext(first);
                cur = boy;
            }
        }
    }

    // 根据用户的输入，计算出圈的顺序

    /**
     * @param startNo  从第几个boy开始数
     * @param countNum 数几下
     * @param nums 一共几个boy
     */
    public void count(int startNo, int countNum, int nums) {
        // 数据校验
        if (first == null || startNo < 1 || startNo > nums) {
            throw new RuntimeException("参数输入有误");
        }

        // 先将first定位到startNo
        for(int i=0; i<startNo-1; i++){
            first = first.getNext();
        }

        // 创建辅助指针，这个指针一直在first后面
        Boy helper = first;
        while (helper.getNext() != first) {
            helper = helper.getNext();
        }

        // 报数开始，让first和helper同时移动m-1次，然后出圈
        while(true){
            if(helper == first)// 说明圈中只有一个节点
                break;
            // 让first和helper同时移动m-1次
            for(int i=0; i<countNum-1; i++){
                first = first.getNext();
                helper = helper.getNext();
            }
            // 这时first指向的就是要出圈的boy
            System.out.println(first.getNo()+"出圈");
            // 出圈
            first = first.getNext();
            helper.setNext(first);
        }
        System.out.println("最后的boy"+first.getNo());
    }

    // 遍历
    public void show() {
        if (first == null)
            throw new RuntimeException("没有boy");
        // 使用辅助指针完成遍历
        Boy cur = first;
        while (true) {
            System.out.println(cur.getNo());
            // 这个判断跳出的条件不能放在while后面，因为要先打印，再判断
            if (cur.getNext() == first)
                break;
            cur = cur.getNext();
        }
    }
}

// 节点类
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;
    }
}