数据结构-链表
本文介绍数据结构中单链表的结构、插入删除和随机访问效率、双向链表和循环链表的结构、链表实现 LRU 缓存,以及手写链表和常见的算法题

# 数据结构-链表

# 数组与链表

  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);
}
Comment here, be cool~

Copyright © 2020 CadeCode

Theme 2zh powered by VuePress

本页访问次数 0

Loading