双向链表

概念介绍

顾名思义，如果你知道单向链表只能朝着一个方向遍历的话，那么双向链表就是可以向两个方向遍历。双向链表每个结点存在两个指针域，分别存储该结点的前驱结点引用和后继结点引用，从任意一个结点出发，都能通过前驱引用以及后继引用完成整个链表结点的访问。

所以不难看出，单向链表能干的事，双向链表也能干！但是正是因为这一特性，相比于单链表，双向链表在访问其他结点上带来方便的同时，将占用更多的资源，因此在使用的时候可以根据自己的场景来决定使用何种数据结构。

节点结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class DataNode{
    int date;
    DataNode pre;
    DataNode next;

    public DataNode(int num){
        this.date=num;
    }



    @Override
    public String toString() {
        return "DataNode{" +
                "date=" + date +
                '}';
    }
}

不难看出，双向链表只是在单链表的基础上加立一个前驱指针pre

用一个DoubleLinkedList类来表示双向链表和封装方法

代码全局

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class DoubleLinkedLIst {
    //头指针
    public DataNode head =new DataNode(0);

    //将一个节点加入队尾
    public void add(DataNode dataNode){}

    //按序加入，并且重复元素不加入
    public void addByorder(DataNode dataNode){}

    //遍历
    public void list(){}

    // 在不重复的链表中删除对应数据
    public void delete(int num) throws Exception {}

}

将一个节点加入队尾

1
2
3
4
5
6
7
8
9
public void add(DataNode dataNode){
    DataNode temp =head;
    while(temp.next!=null){
        temp=temp.next;
    }
    temp.next=dataNode;
    dataNode.pre=temp;

}

按序加入，并且重复元素不加入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public void addByorder(DataNode dataNode){
        DataNode temp =head;
        while(temp.next!=null && temp.next.date<dataNode.date){
            temp=temp.next;
        }
        if(temp.next==null){
            add(dataNode);
        } else if(temp.next.date==dataNode.date){
            return;
        }else{
            dataNode.next=temp.next;
            dataNode.pre=temp;
            temp.next.pre=dataNode;
            temp.next=dataNode;
        }
    }

遍历

1
2
3
4
5
6
7
8
public void list(){
        DataNode temp =head.next;
        while(temp!=null){
            System.out.println(temp.toString());
            temp=temp.next;
        }

    }

在不重复的链表中删除对应数据

1
2
3
4
5
6
7
8
9
10
11
public void delete(int num) throws Exception {
        DataNode temp =head.next;
        if(temp==null){
            throw new Exception();
        }
        while(temp.date!=num){
            temp=temp.next;
        }
        temp.next.pre=temp.pre;
        temp.pre.next=temp.next;
    }

简单的测试代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public static void main(String[] args) throws Exception {
        DataNode a1 =new DataNode(1);
        DataNode a2 =new DataNode(2);
        DataNode a3 =new DataNode(3);
        DataNode a4 =new DataNode(4);
        DataNode a5 =new DataNode(5);
        DataNode a6 =new DataNode(6);
        DoubleLinkedLIst d =new DoubleLinkedLIst();

        d.addByorder(a2);
        d.addByorder(a3);
        d.addByorder(a1);
        d.addByorder(a4);
        d.addByorder(a6);
        d.addByorder(a5);
        d.delete(5);

        d.list();

    }

测试结果：
结果1

约瑟夫环：

问题描述：

已知n个人（以编号1，2，3…n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。

解决思路

创建一个循环链表，当k为1时，直接从start节点输出n个节点。当k不为1时，创建temp指针指向start，删掉从start开始数的第k个节点并输出。然后temp向后移一位，再开始数，一直循环这个过程。当temp.next等于temp时结束循环，并输出此节点即可输出完整答案。

代码实现

Node类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Node{
    public int no ;
    public Node next;

    public Node(int num){
        this.no=num;
    }

    @Override
    public String toString() {
        return "node{" +
                "no=" + no +
                '}';
    }
}

solve 方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public static void solve(int num ,int cunt){
        //创建循环链表
        Node start =new Node(1);
        Node temp  =start;
        for(int i=2;i<=num;i++){
            temp.next =new Node(i);
            temp=temp.next;
        }
        temp.next=start;

        //遍历并输出结果
        temp=start;
        if(cunt==1){
            for(int i=1;i<=num;i++){
                System.out.println(temp.toString());
                temp=temp.next;
            }
        }else{
            while(temp.next!=temp){
                for(int i=0;i<cunt-2;i++){
                    temp=temp.next;
                }
                System.out.println(temp.next.toString());
                temp.next=temp.next.next;
                temp=temp.next;
            }
        }
        System.out.println(temp.toString());
}

main测试

1
2
3
4
5
6
7
8
9
10
11
public static void main(String[] args) {


        Scanner sc = new Scanner(System.in);
        System.out.print("请输入人数:");
        int people = sc.nextInt();
        System.out.print("请输入报数数目：");
        int cunt =sc.nextInt();
        sc.close();
        solve(people,cunt);
}

测试结果：
结果2