• 链表


    链表

    数组与链表

    1. 同为线性表存储结构
    2. 数组在一段连续的空间上,链表将分散的内存块连接起来使用

    单链表

    SinglyLinkedList

    结构

    1. 结点:存储链表的每一个内存块
    2. 后继指针:每个结点除了存储数据外,还要记录下一个内存块的地址
    3. 头结点:第一个结点,记录基址
    4. 尾结点:最后一个结点,指向 null

    插入删除

    1. 与数组相比,链表的插入删除不需要搬移数据,时间复杂度为 O(1)

    2. 插入:在结点 p 后插入 结点 x

      x.next = p.next;
      p.next = x;
      
    3. 删除:删除结点 p 后续第一个结点

      if(p.next != null) {
          p.next=p.next.next;
      }
      

    随机访问

    1. 链表的数据不是连续存储的,无法使用类似于数组的寻址方法进行随机访问,而是要从头遍历,直到找到相应结点
    2. LinkedList 内部使用双向链表结构,用 get( ) 随机访问时,需要从头部正向或反向遍历,效率低下

    双向链表、循环链表

    DoublyLinkedList、CircularLinkedList

    1. 双向链表:每个结点除了后继指针外,还存储了前驱指针 previous

    2. 循环链表:尾部结点指向头部结点,适合处理环形结构的数据

    3. 双向循环链表:结合了双向链表和循环链表的特点

    4. 双向链表比单链表灵活,删除性能更高

      删除给定指针指向的结点时,单链表需要遍历找到该结点的前驱结点,双链表可以直接获取前驱结点

      这是一种用空间换时间的设计思想

    链表实现 LRU 缓存

    链表实现 最近最久未使用淘汰算法

    维护一个单链表,越靠近链表尾部的结点,是越早之前访问的,当有新数据被访问时,从头遍历单链表

    1. 如果数据在链表中,遍历得到对应结点,删除该节点,再插入到头部
    2. 如果数据不在链表中
      • 链表未满时,直接插头部
      • 链表已满时,删除尾部结点,再插入头部

    手写链表

    public class SinglyList {
        // 哨兵结点
        ListNode head = new ListNode(0);
    
        // 在 pre 结点后插入 add 结点
        public void add(ListNode pre, ListNode add) {
            add.next = pre.next;
            pre.next = add;
        }
    
        // 删除 node 后第一个结点
        public void remove(ListNode node) {
            if (node.next != null) {
                node.next = node.next.next;
            }
        }
    
        public String toString() {
            String str = "head->";
            ListNode temp = head;
            while (temp.next != null) {
                str += temp.next + " ";
                temp = temp.next;
            }
            return str;
        }
    }
    
    public class ListNode {
        ListNode next;
        int value;
    
        public ListNode(int value) {
            this.value = value;
        }
    
        @Override
        public String toString() {
            return value + "";
        }
    }
    
    public class SinglyListTest {
        public static void main(String[] args) {
            ListNode node1 = new ListNode(1);
            ListNode node2 = new ListNode(2);
            ListNode node3 = new ListNode(3);
            ListNode node4 = new ListNode(4);
    		// 创建单链表加入结点
            SinglyList list = new SinglyList();
    
            list.add(list.head, node1);
            list.add(node1, node2);
            list.add(node2, node3);
            list.add(node3, node4);
    		// 打印
            System.out.println(list);
        }
    }
    

    print

    head->1 2 3 4
    
    1. 理解指针的含义:指向变量的内存地址
    2. 警惕指针丢失:插入节点时,注意操作顺序
    3. 利用哨兵结点简化编程
      • 当链表中没有结点时,插入操作不能简单使用上文中的方法,当链表只有一个结点时,删除操作也需要特殊处理
      • 引入哨兵结点,无论链表是否为空,head 指向哨兵结点, 插入删除操作可以统一代码逻辑
      • 把有哨兵的链表称为带头链表
    4. 注意边界条件处理:留意链表为空时、只有一个结点时、只有两个结点时、处理头尾结点时,能否正常工作
    5. 多练习常见的链表操作

    单链表反转

    public static void reverse(SinglyList list) {
        SinglyList result = new SinglyList();
        ListNode temp = list.head;
        while (temp.next != null) {
            temp = temp.next;
            result.add(result.head, new ListNode(temp.value));
        }
        System.out.println(result);
    }
    

    求中间结点

    快慢指针法,结点数分奇偶两种情况

    public static void middle(SinglyList list) {
        ListNode quick = list.head, slow = list.head;
        boolean isEven = true;//结点是否为偶数个
        while (quick.next != null) {
            if (quick.next.next != null) quick = quick.next.next;//偶数
            else {//奇数
                quick = quick.next;
                isEven = false;
            }
            slow = slow.next;
        }
        if (isEven) System.out.println(slow + "," + slow.next);
        else System.out.println(slow);
    }
    

    删除倒数第 n 个结点

    public static void delete(SinglyList list, int n) {
        ListNode p = list.head;
        int len = 0;
        while (p.next != null) {
            p = p.next;
            len++;
        }
        p = list.head;
        for (int i = 0; i < len - n; i++) {
            p = p.next;
        }
        list.remove(p);
        System.out.println(list);
    }
    

    环的检测

    快慢指针法,快慢指针重复则有环

    也可以使用一个 Set 去装结点,判断是否重复

    public static void circle(SinglyList list) {
        ListNode quick = list.head, slow = list.head;
        while (true) {
            quick = quick.next.next;
            if (quick == null) {
                System.out.println("have no circle");
                break;
            }
            slow = slow.next;
            if (quick == slow) {
                System.out.println("have circle");
                break;
            }
        }
    }
    

    两个有序链表合并

    带头链表遍历时需要注意起始结点

    public static void merge(SinglyList l1, SinglyList l2) {
        SinglyList result = new SinglyList();
        ListNode tail = result.head;
        ListNode head1 = l1.head;
        ListNode head2 = l2.head;
        while (head1.next != null || head2.next != null) {
            if (head1.next != null && head2.next != null) {
                if (head1.next.value < head2.next.value) {
                    head1 = head1.next;
                    result.add(tail, new ListNode(head1.value));
                    tail = tail.next;
                } else {
                    head2 = head2.next;
                    result.add(tail, new ListNode(head2.value));
                    tail = tail.next;
                }
            }
            if (head1.next == null && head2.next != null) {
                head2 = head2.next;
                result.add(tail, new ListNode(head2.value));
                tail = tail.next;
            }
            if (head1.next != null && head2.next == null) {
                head1 = head1.next;
                result.add(tail, new ListNode(head1.value));
                tail = tail.next;
            }
        }
        System.out.println(result);
    }
    
  • 相关阅读:
    CStringArray序列化处理
    【转】C++ Incorrect Memory Usage and Corrupted Memory(模拟C++程序内存使用崩溃问题)
    【转】Native Thread for Win32 C- Creating Processes(通俗易懂,非常好)
    【转】Native Thread for Win32 B-Threads Synchronization(通俗易懂,非常好)
    【转】Native Thread for Win32 A- Create Thread(通俗易懂,非常好)
    【转】关于OnPaint的工作机制
    Window发声函数Beep、MessageBeep
    Sqlite
    VC++ Splash Window封装类CSplash
    通过代码注册COM、DLL组件
  • 原文地址:https://www.cnblogs.com/pgjett/p/12295019.html
一二三 - 开发者的网上家园