美文网首页
数据结构-链表

数据结构-链表

作者: acc8226 | 来源:发表于2021-07-31 21:33 被阅读0次

    链表结构

    链表结构五花八门,今天我重点给你介绍三种最常见的链表结构,它们分别是:单链表、双向链表和循环链表。我们首先来看最简单、最常用的单链表。

    单链表

    我们习惯性地把第一个结点叫作头结点,把最后一个结点叫作尾结点。其中,头结点用来记录链表的基地址。有了它,我们就可以遍历得到整条链表。而尾结点特殊的地方是:指针不是指向下一个结点,而是指向一个空地址 NULL,表示这是链表上最后一个结点。

    针对链表的插入和删除操作,我们只需要考虑相邻结点的指针改变,所以对应的时间复杂度是 O(1)。链表随机访问的性能没有数组好,需要 O(n) 的时间复杂度。

    循环链表

    循环链表是一种特殊的单链表。实际上,循环链表也很简单。它跟单链表唯一的区别就在尾结点。我们知道,单链表的尾结点指针指向空地址,表示这就是最后的结点了。而循环链表的尾结点指针是指向链表的头结点。从我画的循环链表图中,你应该可以看出来,它像一个环一样首尾相连,所以叫作“循环”链表。

    从我画的图中可以看出来,双向链表需要额外的两个空间来存储后继结点和前驱结点的地址。所以,如果存储同样多的数据,双向链表要比单链表占用更多的内存空间。虽然两个指针比较浪费存储空间,但可以支持双向遍历,这样也带来了双向链表操作的灵活性。那相比单链表,双向链表适合解决哪种问题呢?从结构上来看,双向链表可以支持 O(1) 时间复杂度的情况下找到前驱结点,正是这样的特点,也使双向链表在某些情况下的插入、删除等操作都要比单链表简单、高效。

    头结点即为第一个节点
    尾节点指向空地址

    带哨兵的节点有利于简化代码,推荐使用

    双向链表

    循环链表是一种特殊的单链表。实际上,循环链表也很简单。它跟单链表唯一的区别就在尾结点。我们知道,单链表的尾结点指针指向空地址,表示这就是最后的结点了。而循环链表的尾结点指针是指向链表的头结点。从我画的循环链表图中,你应该可以看出来,它像一个环一样首尾相连,所以叫作“循环”链表。

    双向循环链表

    了解了循环链表和双向链表,如果把这两种链表整合在一起就是一个新的版本:双向循环链表。

    双向链表的示例【待添加】

    必练操作

    接口定义

    package com.s1.array;
    
    public interface IList {
    
        void print();
    
        // 往尾部添加
        void add(Integer data);
    
        void addFirst(Integer data);
    
        void addLast(Integer data);
    
        // 指定位置添加元素(有效范围内)
        void add(int position, Integer data);
        
        // 往尾部删除
        Object remove();
    
        // 删除首元素
        Object removeFirst();
    
        // 删除尾元素
        Object removeLast();
    
        // 删除指定下标的元素
        Object remove(int index);
        
        // 删除指定数据的元素
        Object remove(Object obj);  
            
        // 改1 : 找到下标,然后更改
        boolean updateByPosition(int position, Integer value);
        
        // 改2 : 找到原数据,然后更改
        boolean updateByData(Integer oldData, Integer newData);
        
        void clear();   
    }
    
    • 实现单链表【可选 循环链表、双向链表】,支持增删操作
    • 单链表反转链
    • 表中环的检测
    • 两个有序的链表合并
    • 删除链表倒数第 n 个结点
    • 求链表的中间结点

    思考题:基于链表的 LRU 算法

    LRU 思路一

    1. 如果此数据之前已经被缓存在链表中了,我们遍历得到这个数据对应的结点,并将其从原来的位置删除,然后再插入到链表的头部。
    2. 如果此数据没有在缓存链表中,又可以分为两种情况:
      如果此时缓存未满,则将此结点直接插入到链表的头部;
      如果此时缓存已满,则链表尾结点删除,将新的数据结点插入链表的头部。

    或者 思路二

        /**
         * 如果不存在 
         *   队列未满则插入 tail
         *   队列已满移除head并从插入 tail         
         * 如果存在 则从中取出并从插入 tail
         */ 
    
    package com.s2.link;
    
    public class LRULinkedList extends LinkedList {
        
        private static final int DEFAULT_LENGTH = 10;
        
        private final int length;
        
        private int used = 0;
    
        public LRULinkedList() {
            this(DEFAULT_LENGTH);
        }
        
        public LRULinkedList(int length) {
            this.length = length;
        }
        
        protected boolean isFull () {
            return this.used == this.length;
        }
        
        @Override
        public void add(Integer data) {
            /**
             * 如果不存在 
             *   队列未满则插入 tail
             *   队列已满移除head并从插入 tail         
             * 如果存在 则从中取出并从插入 tail
             */ 
            Object removeNode = this.remove(data);
            if (removeNode == null && this.isFull()) {
                this.removeFirst();     
            }
            this.addLast(data);
        }
        
        @Override
        public Object remove(Object obj) {
            Object removeObject = super.remove(obj);
            if (removeObject != null) {
                this.used--;
            }       
            return removeObject;
        }
        
        @Override
        public Object removeFirst() {
            Object removeObject = super.removeFirst();
            if (removeObject != null) {
                this.used--;
            }       
            return removeObject;
        }
        
        @Override
        public void addLast(Integer data) {
            super.addLast(data);
            used++;
        }
    }
    

    思考题:判断是否为回文串

    找到中间节点。根据奇偶个数。
    如果是奇数个则中分开。
    如果是偶数个,则认为中点有两个,继续分开。
    然后分别拿到两端的 head 指针就行循环,如果遇到节点的数据不一致则认定不是回文串。若循环结束则认为该串是回文串。

    代码片段

        // 判断是否为回文 
        public boolean palindrome() {
            // 根据快慢指针找到中间节点, 但是不知道总结点个数是奇还是偶数
            if (this.headNode == null) {
                return false;
            }
            if (this.headNode.next == null) {
                return true;
            }
            // 大于两个节点
            Node slow = this.headNode;
            Node fast = this.headNode;
            while (fast.next != null && fast.next.next != null) {
                slow = slow.next;
                fast = fast.next.next;
            }
            
            //  slow  fast
            //  1     2
            //  1     2   3
            System.out.println("slow " + slow);
            System.out.println("fast " + fast);
            
            Node leftNode;
            Node rightNode;
            // 总奇数个, 一个重点
            if (fast.next == null) {
                rightNode = slow.next;
                this.inverseLinkList(slow);
                leftNode = slow.next;
            } 
            //  总偶数个数,两个中点 
            else {
                rightNode = slow.next;
                this.inverseLinkList(slow);
                leftNode = slow;
            }           
            return this.TFResult(leftNode, rightNode);
        }
    

    我的代码
    https://gitee.com/kaiLee/struct/tree/master/src/main/java/com/s2

    参考

    06 | 链表(上):如何实现LRU缓存淘汰算法? https://time.geekbang.org/column/article/41013

    07 | 链表(下):如何轻松写出正确的链表代码? https://time.geekbang.org/column/article/41149

    algo: 数据结构和算法必知必会的50个代码实现
    https://gitee.com/TheAlgorithms/algo

    相关文章

      网友评论

          本文标题:数据结构-链表

          本文链接:https://www.haomeiwen.com/subject/ztbdsltx.html