学习第八天---链表

1. 链表基础概念
   • 逻辑与存储结构：在数据结构领域，数据元素之间存在不同的逻辑关系，主要分为集合、线性结构（元素间为一对一关系）、树形结构（一对多）以及图结构（多对多）。而数据的存储结构则包含顺序存储、链式存储、索引存储和散列存储。其中，顺序存储的顺序表，其逻辑上相邻的元素在物理位置上也相邻；链式存储的单链表，逻辑相邻的元素物理位置并不一定相邻，这种特性使得单链表在插入和删除操作上相较于顺序表更为灵活。
   • 单链表定义：在 Python 中，可通过定义ListNode类来表示单链表中的节点。代码如下：

收起

python

class ListNode:
    def __init__(self, _val=0, _next=None):
        self.val = _val
        self.next = _next

带头结点的单链表，在编写代码时更具便利性，它多了一个不存储有效数据的头结点，用于简化链表操作时对首节点的特殊处理；不带头结点的单链表虽然节省了一个节点的存储空间，但在代码实现时，对于头节点的插入、删除等操作需要额外的判断逻辑，增加了代码的复杂性。 2. 单链表操作

• 插入元素
  • 带头结点的单链表：在带头结点的单链表中，若要在第i个位置插入元素elem，可使用如下代码：

收起

python

def Insert(head, i, elem):
    assert i >= 0
    cur = head
    while i != 0:
        i -= 1
        cur = cur.next
    if not cur:
        return False
    temp = cur.next
    cur.next = elem
    elem.next = temp
    return True

该函数首先通过assert语句确保插入位置i是合法的（即i大于等于 0）。接着，使用while循环找到插入位置的前一个节点cur。若cur为空，说明插入位置超出链表长度，插入失败返回False。否则，保存cur的下一个节点temp，将elem插入到cur和temp之间，最后返回True表示插入成功。

• 不带头结点的单链表：不带头结点的单链表插入操作，在插入位置为链表头部时，需要单独处理，与其他位置的插入逻辑有所不同。若在头部插入元素elem，直接将elem的next指针指向原头节点，然后将elem作为新的头节点；若在其他位置插入，与带头结点单链表类似，先找到插入位置前一个节点，再调整指针。
• 删除元素：文档虽未详细给出删除元素的代码，但基本思路是遍历链表，找到要删除节点的前一个节点，然后调整指针绕过要删除的节点。例如，若要删除值为target的节点，遍历链表，当cur.next.val == target时，将cur.next指向cur.next.next，从而实现删除操作。在删除头节点时，需要特殊处理，将头节点指向下一个节点。
• 创建单链表
  • 尾插法：
    • 不带头结点的单链表：首先创建一个空链表（即head = None），然后每次创建新节点并将其插入到链表尾部。若链表为空，则新节点即为头节点；若链表不为空，则遍历到链表尾部，将新节点连接到尾节点的next指针。
    • 带头结点的单链表：创建一个头结点（head = ListNode()），每次创建新节点后，遍历到链表尾部（通过while cur.next循环找到尾节点cur），将新节点插入到尾节点之后。
  • 头插法：
    • 带头结点的单链表：创建头结点（head = ListNode()），每次创建新节点后，将新节点插入到头结点之后，即新节点的next指针指向头结点的next，然后头结点的next指向新节点。
    • 不带头结点的单链表：每次创建新节点后，直接将新节点插入到链表头部，即新节点的next指针指向原头节点，然后新节点成为头节点。

1. 其他链表类型
   • 双链表：双链表通过DLinkNode类解决了单链表无法逆向索引的问题。在 Python 中定义如下：

收起

python

class DLinkNode:
    def __init__(self, val=0, next=None, prior=None):
        self.val = val
        self.next = next
        self.prior = prior

每个节点除了有指向下一个节点的next指针，还有指向前一个节点的prior指针，这使得双链表在双向遍历、删除节点等操作上更加高效。

• 循环链表：
  • 循环单链表：循环单链表的特点是从任意一个节点出发，都可以找到链表中的其他任何节点。其优势在于从头找到尾和从尾找到头的时间复杂度都是\(O(1)\)，这在某些需要频繁遍历链表两端的场景下非常实用。例如，在实现循环队列时，可以利用循环单链表来优化操作。
  • 循环双链表：循环双链表结合了循环链表和双链表的特性，既可以双向遍历，又能在\(O(1)\)时间内找到表头和表尾。在一些对数据操作需要频繁双向访问的场景，如实现 LRU（最近最少使用）缓存算法时，循环双链表是一个很好的选择。

1. 链表算法示例
   • 移除链表元素：给定链表的头节点head和一个整数val，要求删除链表中所有值等于val的节点，并返回新的头节点。例如：
     • 示例 1：假设链表为[1, 2, 3, 2, 4]，val = 2，经过移除操作后，新链表为[1, 3, 4]。
     • 示例 2：若链表为[5, 5, 5]，val = 5，处理后新链表为空。
   • 旋转链表：给定链表的头节点head和整数k，需要将链表每个节点向右移动k个位置。例如：
     • 示例 1：输入链表[1, 2, 3, 4, 5]，k = 2，输出为[4, 5, 1, 2, 3]。
     • 示例 2：输入链表[0, 1, 2]，k = 4，由于k大于链表长度，实际移动次数为k % len(linked_list) = 1，输出为[2, 0, 1] 。