亲宝软件园·资讯

展开

数据结构---链表及约瑟夫环问题带来的思考

白露非霜 人气:0

链表和数组一样也是线性表的一种。和数组不同,它不需要再内存中开辟连续的空间。

链表通过指针将一组零散的内存块连接在一起。我们把内存块称为链表的“结点”(是节点还是结点,结点连接起来打个结所以叫“结点”?开个玩笑),也就是说这些结点可以在内存的任意地方,只要有其他的结点的指针指向这个位置就可以。

链表又分为单向链表,双向链表,循环链表

 

单向链表

 

 

循环链表:最后一个节点指向第一个结点

 

 

 

双向链表:比单向链表多了一个前驱指针,指向前面一个结点

 

 

 

 

从上面的结构和内存中的储存结构来看,就可以发现链表相比数组来说,随机查询效率是O(n),只有从头结点开始查找;但是它的插入修改效率比数组高,找到位置之后只需要修改下指针指向,而不需要进行后续元素的迁移。理论上来说是无限容量,不像数组满了还需要扩容,扩容还要重新申请内存,然后迁移数据,链表只需要在内存找个一小块空地,放好数据,让前面那个指向这里就是了。

我们也可以看到双向链表比单向链表更灵活,因为通过一个结点可以找到前后两个结点。但是多了个指针所占空间肯定比单向链表大。

 

 

Java中LinkedList就是一个双向链表。

 

 

 

 

简单实现一个单向链表

 

package com.nijunyang.algorithm.link;

/**
 * Description:
 * Created by nijunyang on 2020/3/31 22:09
 */
public class MyLinkedList<E> {
    private Node<E> head;
    private int size = 0;

    /**
     * 头部插入O(1)
     * @param data
     */
    public void insertHead(E data){
        Node newNode = new Node(data);
        newNode.next = head;
        head = newNode;
        size++;
    }

    public void insert(E data,int position){
        if(position == 0) {
            insertHead(data);
        }else{
            Node cur = head;
            for(int i = 1; i < position ; i++){
                cur = cur.next;        //一直往后遍历
            }
            Node newNode = new Node(data);
            //
            newNode.next = cur.next;        //新加的点指向后面 保证不断链
            cur.next = newNode;            //把当前的点指向新加的点
            size++;
        }

    }


    public void deleteHead(){
        head = head.next;
        size--;
    }

    public void delete(int position){
        if(position == 0) {
            deleteHead();
        }else{
            Node cur = head;
            for(int i = 1; i < position ; i ++){
                cur = cur.next;  //找到删除位置的前一个结点
            }
            cur.next = cur.next.next; //cur.next 表示的是删除的点,后一个next就是我们要指向的
            size--;
        }

    }

    public int size( ){
        return size;
    }

    public String toString( ){
        if (size == 0) {
            return "[]";
        }
        StringBuilder sb = new StringBuilder();
        sb.append('[');
        Node<E> node = head;
        sb.append(node.value);
        int counter = 0;
        for (;;) {
            if (++counter == size) {
                break;
            }
            sb.append(",");
            node = node.next;
            sb.append(node.value);


        }
        sb.append(']');
        return sb.toString();
    }

    public static void main(String[] args) {
        MyLinkedList myList = new MyLinkedList();
        myList.insertHead(5);
        System.out.println(myList);
        myList.insertHead(7);
        System.out.println(myList);
        myList.insertHead(10);
        System.out.println(myList);
        myList.delete(0);
        System.out.println(myList);
        myList.deleteHead();
        System.out.println(myList);
        myList.insert(11, 1);
        System.out.println(myList);

    }

    private static class Node<E>{

        E value;        //值
        Node<E> next;        //下一个的指针

        public Node() {
        }

        public Node(E value) {
            this.value = value;
        }
    }
}

 

 

 

 约瑟夫环问题:

说到链表就要提一个下约瑟夫环问题:N个人围成一圈,第一个人从1开始报数,报M的被杀掉,下一个人接着从1开始报,循环反复,直到剩下最后一个。看到这个就想到用循环链表来实现,无限remove知道链表只剩下一个为止。

之前去力扣上面做的时候就用循环链表实现了下,验证是可以过的,但是代码提交之后显示超时,过不了。仔细分析之后之后发现循环链表实现,时间线复杂度是O(n*m),如果数据大了,必定是个问题。然后就换了,数组(ArrayList)来实现,每次移除之后大小减一,通过取模size来实现循环报数的效果。会发现数组实现的,时间复杂度仅仅是O(n),两种方式代码如下:

 

package com.nijunyang.algorithm.link;

import java.util.ArrayList;

/**
 * Description:
 * Created by nijunyang on 2020/3/30 21:49
 */
public class Test {

    public static void main(String[] args){
        long start = System.currentTimeMillis();
        int result = yuesefuhuan_link(70866, 116922);
        long end = System.currentTimeMillis();
        System.out.println(result);
        System.out.println("链表耗时:" + (end - start));
        System.out.println("-------------------------");

        start = System.currentTimeMillis();
        result = yuesefuhuan_arr(70866, 116922);
        end = System.currentTimeMillis();
        System.out.println(result);
        System.out.println("数组耗时:" + (end - start));
    }

    /**
     * 数组约瑟夫环
     */
    public static int yuesefuhuan_arr(int n, int m) {
        int size = n;
        ArrayList<Integer> list = new ArrayList<>(size);
        for (int i = 0; i < size; i++) {
            list.add(i);
        }
        int index = 0;
        while (size > 1) {
            //取模可以回到起点
            index = (index + m - 1) % size;
            list.remove(index);
            size--;
        }
        return list.get(0);
    }


    /**
     * 循环链表约瑟夫环力扣超时
     * @param n
     * @param m
     * @return
     */
    public static int yuesefuhuan_link(int n, int m) {
        if (n == 1) {
            return n - 1;
        }

        Node<Integer> headNode = new Node<>(0);
        Node<Integer> currentNode = headNode;
        //尾结点
        Node<Integer> tailNode = headNode;

        for (int i = 1; i < n; i++) {
            Node<Integer> next = new Node<>(i);
            currentNode.next = next;
            currentNode = next;
            tailNode = currentNode;

        }
        //成环
        tailNode.next = headNode;

        //保证第一次进去的时候指向头结点
        Node<Integer> remove = tailNode;
        Node<Integer> preNode = tailNode;
        int counter = n;
        while (true) {
            for (int i = 0; i < m; i++) {
                //一直移除头结点则,前置结点不动
                if (m != 1) {
                    preNode = remove;
                }
                remove = remove.next;
            }
            preNode.next = remove.next;
            if (--counter == 1) {
                return preNode.value;
            }
        }
    }

    static class Node<E>{
        E value;
        Node next;
        public Node() {
        }
        public Node(E value) {
            this.value = value;
        }
    }
}

 

运行之后看下结果对比,我的机器CPU还算可以I7-8700,内存16G,结果都是一样的说明我们的两种算法都是正确的,但是耗时的差别就很大很大了

 

 

链表耗时30多秒,数组耗时86毫秒,,差不多400倍的差距。

之前也说到数据在内存中是连续的,可以借助CPU的缓存机制预读数据,而链表每次还需要根据指针去寻找。其次就是两种方式时间复杂度是不一样的,我们上面的用的数据70866, 116922。O(n*m)和O(n)差距有多大。所以说不同算法对程序的性能影响还是很大的,这应该就是体现了“算法之美”了吧。提到这个问题,最先想到的可能就是循环链表来解决,最后却发现,循环链表并不是一个很好的解决方式。这就像我们平时写代码,需求下来的时候想着怎样怎样去实现,但是最后上线版本中,肯定改了又改的版本,有些方案可能整体换血都可能。再者就是从这个问题中就看出了算法的重要性。当然在力扣上面还有一种反推法实现的,比数组实现的代码更少,性能更高,感兴趣的自己搜,这里就不列出来对比了。

 

加载全部内容

相关教程
猜你喜欢
用户评论