数据结构-链表

数组与链表

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);
}