链表数据结构的定义、类型和操作... Kotlin 语言示例

terry 2年前 (2023-09-27) 阅读数 65 #数据结构与算法

1. 链表的定义

链表是一种递归数据结构，也是一种线性结构，但它并不是以线性方式存储数据order，而是在每个节点中存储一个指向下一个节点的指针（pointer）。简单来说，链表不像数组那样将数组存储在连续的内存地址空间中。它们可能不连续，因为每个节点都存储了下一个节点的引用（地址）

2. 链表的类型

单向链表

单向链表（也称为单向链表） ) ) 是一种链表。其特点是链表的链接方向是单向的，对链表的访问从头部开始，然后通过next指针读取下一个节点。

单链表的数据结构可以分为两部分：数据字段和指针字段。数据字段存储数据，指针字段指向下一个存储节点的地址。注意：单向链表只能在一个方向上遍历

classLinkedNode(var value: Int) {
    var next: LinkedNode? = null
}
复制代码

publicclassLinkedNode{
    int value;
    LinkedNode next; publicLinkedNode(int value){
        this.value = value;
    }
}
复制代码

双向链表

双向链表（也称为双向链表）是链表的一种。与单向链表的区别在于，它的每个节点都有两个指针指向直接后继节点和和和❀无因此，从双向链表中的任意一个节点，都可以方便地访问其前驱节点和后继节点。

双向链表的数据结构可以分为两部分：前一个指针字段、数据字段和后一个指针字段。 prev 指针域指向上一个存储节点的地址（即指向直接前驱节点），data 域存储数据，next 指针域指向下一个存储节点的地址（即指向下一个存储节点）到直接后继节点）。注：单链表可以两个方向遍历，即正序和倒序

classLinkedNode(var value: Int) {
    var prev: LinkedNode? = nullvar next: LinkedNode? = null
}
复制代码

publicclassLinkedNode{
    int value;
    LinkedNode prev; 
    LinkedNode next; publicLinkedNode(int value){
        this.value = value;
    }
}
复制代码

单向循环链表

单向循环链表，仅在单链表的基础上，它的最后一个节点不再为空，而是指向头节点并形成一个环。并且节点结构与单链表相同。因此，从单向循环链表中的任意一个节点，都可以找到任意其他节点。

双向循环链表

双向循环链表仅基于双向链表。 之前指向头节点的指针不再为空，而是直接指向尾节点；尾结的下一个。指针不再为空，而是直接指向头结点。

3。链表的特征

1。内存中并不存在连续的内存地址空间，它只是逻辑上的线性连续结构。每个节点都包含一个指向下一个节点的下一个指针（可以指向下一个节点或零）
2。链表在删除和添加节点方面非常高效，基本上是O(1)常量级别的时间效率。序列表中的删除和添加操作的时间效率是线性O(n)。因此，通常用于频繁删除和添加元素节点
3。要查找并获取链表中的第 K 个节点，往往需要实现遍历，因此通常需要 O(n) 的时间效率
4。链表的长度是可变的，这意味着在足够的内存空间内，链表的长度可以无限扩展。序列表一般是固定的，当长度超过时就会扩展。

4。基本链表操作

链表的构造

我们知道，一个节点类型变量就可以表示一个链表，只要每个对应节点的 next 指针能够指向下一个节点或者指向 null（表示链表的最后一个节点）

classLinkedNode(var value: Int) {
    var next: LinkedNode? = null
}
funmain(args: Array<String>) {
    val node1 = LinkedNode(value = 1)val node2 = LinkedNode(value = 2)val node3 = LinkedNode(value = 3)
    node1.next = node2
    node2.next = node3
}
复制代码

classLinkedNode(var value: Int) {
    var prev: LinkedNode? = nullvar next: LinkedNode? = null
}

funmain(args: Array<String>) {
    val node1 = LinkedNode(value = 1)val node2 = LinkedNode(value = 2)val node3 = LinkedNode(value = 3)
    
    node1.next = node2 
    node2.prev = node1 
    
    node2.next = node3 
    node3.prev = node2 
}
复制代码

在链表的头部插入一个节点

在链表的顶部插入一个节点是最简单的操作。一般的处理方法是，首先创建一个指向第一个节点的oldFirst，然后重新创建一个新节点，新节点的next指向oldFirst指向的节点，first指向新插入的节点。

funinsertToHead(head: LinkedNode): LinkedNode {
    var first: LinkedNode = head
    val oldFirst: LinkedNode = head
    first = LinkedNode(value = 6)
    first.next = oldFirst
    return first
}
复制代码

funinsertToHead(head: LinkedNode): LinkedNode {
    var first: LinkedNode = head
    val oldFirst: LinkedNode = head
    first = LinkedNode(value = 6)
    oldFirst.prev = first
    first.next = oldFirst
    return first
}
复制代码

删除表格顶部的节点

fundeleteToHead(head: LinkedNode): LinkedNode? {
    var first: LinkedNode? = head
    first = first?.next
    return first
}
复制代码

fundeleteToHead(head: LinkedNode): LinkedNode? {
    var first: LinkedNode? = head
    first = first?.next
    first?.prev = nullreturn first
}
复制代码

在表格末尾插入节点

funinsertToTail(head: LinkedNode): LinkedNode? {
    var last = getTailNode(head) val oldLast = last
    last = LinkedNode(value = 4)
    oldLast?.next = last
    return head
}
复制代码

funinsertToTail(head: LinkedNode): LinkedNode? {
    var last = getTailNode(head) val oldLast = last
    last = LinkedNode(value = 4)
    oldLast?.next = last
    last.prev = oldLast
    return head
}
复制代码

在其他地方插入节点

funinsertToOther(head: LinkedNode): LinkedNode? {
    val current = getInsertPrevNode(head) val newNode = LinkedNode(value = 6)
    newNode.next = current?.next
    current?.next = newNodereturn head
}
复制代码

funinsertToOther(head: LinkedNode): LinkedNode? {
    val current = getInsertPrevNode(head) val newNode = LinkedNode(value = 6)
    newNode.next = current?.next
    newNode.prev = current 
    current?.next = newNode
    current?.next?.prev = newNode return head
}
复制代码

删除其他地方的节点

fundeleteToOther(head: LinkedNode): LinkedNode? {
    val current = getInsertPrevNode(head) 
    current?.next = current?.next?.next
    return head
}
复制代码

fundeleteToOther(head: LinkedNode): LinkedNode? {
    val current = getDeletePrevNode(head) 
    current?.next = current?.next?.next
    current?.next?.prev = current
    return head
}
复制代码

检查链表的❝大小

fungetLength(head: LinkedNode?): Int {
    var len = 0var current = head
    while (current != null){
        len++
        current = 
    }
    
    return len
}
复制代码

5. 链表实现堆栈和队列数据结构

1。链表实现堆栈结构

由于堆栈是一个表，因此任何实现表的方法都可以实现堆栈。显然，Java中常用的ArrayList和LinkedList集合都支持栈操作。

单链表也可以实现栈。入栈操作是通过在链表顶部插入来实现的，出栈操作是通过删除链表顶部元素来实现的。 top操作只需要返回top元素的值即可。？旋转也是常见的考点，反向链表也会作为题目的一部分，例如回文链表问题等。

2。实施过程
3.代码说明

funreverseLinkedList(head: LinkedNode?): LinkedNode? {
    var prev: LinkedNode? = nullvar current: LinkedNode? = head
    var next: LinkedNode? = head

    while (current != null) {
        next = 
         = prev
        prev = current
        current = next
    }
    
    return prev
}
复制代码

7.链表中经典的快慢指针问题

快慢指针问题是链表中非常经典的问题。快慢指针问题一般用于解决链表中的中间节点以及链表是否包含环以及环在链表中的条目位置问题。

如果使用快慢指针的问题是判断链表是否包含环，我们更希望快慢指针之间的相对距离恰好是环的长度，（即慢指针刚刚进入环，快指针刚刚绕环。绕一圈，两个指针正好相遇。）这样，两个指针就相遇了。这样，我们将数字作为每一步的速度差除以循环长度。但我们不知道环的具体长度，所以只能取每一步的速度差。能被环的长度整除的数字是1（1可以被任何数字整除），所以我们拿着快速指针，一次走2步。，慢指针一次走一步。事实上，只要两者的速度差为1，甚至可以一次快指针走3步，慢指针走2步。这样一来，只要在戒指之内，他们就一定会相遇。

1。快慢指针和链表调用的问题

publicbooleanhasCycle(ListNode head){
        if(head == null || head.next == null) returnfalse;
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null &&  != null){
            slow = slow.next;
            fast = .next;if(slow == fast){returntrue;
            }
        }
        
        returnfalse;
    }
复制代码

2。快慢指针寻找中间节点的问题

从快慢指针追赶的原理可以看出，如果快指针和慢指针同时从链表顶部开始（链表链表不包含环）节点开始交叉。如果快指针每次遍历的步数是慢指针的两倍，则可以实现如果快遍历到链表末尾，那么慢指针此时应该处于链表的中间节点位置链表（具体题可参考：LeetCode 876题）。

public ListNode middleNode(ListNode head){
        if(head == null) returnnull;
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null &&  != null){
            slow = slow.next;
            fast = .next;
        }
        
        return slow;
    }