【搞定算法面试】- 松散链表

前言

链表和数组作为最基本的计算机数据结构，相信许多准备面试的小伙伴都经操练已久。这里我们谈谈一种高效的链表实现-Unrolled Linked List，即松散链表。

什么是松散链表

松散链表是链表的一种变形或者改良，它的每个节点由一数组来存储元素，节点数组的容量是固定的。

1. 插入操作： 根据下标找到位置后插入元素。如果当前插入节点数组已满则创建一个新节点，并且将当前节点一半的元素移至新节点的数组中，最后插入元素。
2. 删除操作： 根据下标删除元素。删除元素后的节点可能需要其临近节点作合并操作。

举个例子：

松散链表的优点

• 松散链表同时具有数组随机访问的优点和链表高效的插入删除特性。
• 由于每个节点会承载多个元素，所以松散链表的节点空间开销更少。

代码实现

给定一松散链表，链表的每个节点包含一个数组。要求实现insert(idx, obj), remove(idx)和get(idx)方法。

class Node:    def __init__(self, capacity=16):        self.elements = [None] * capacity        self.size = 0  # 节点的元素个数        self.cap = capacity  # 节点的容量        self.next = None

class UnrolledLinkedList:    def __init__(self):        self.total_size = 0  # 链表的总元素个数        self.head, self.tail = Node(-1), Node(-1)  # 哨兵节点        node = Node()        self.head.next = node        node.next = self.tail

def insert(self, idx, obj):        if idx < 0 or idx > self.total_size:            return                # 找到插入节点和位置        cur = self.head.next        while idx >= cur.size:            if idx == cur.size:                break            idx -= cur.size            cur = cur.next                    if cur.size == cur.cap:            # 插入节点已满，创建新节点            node = Node()            next = cur.next            cur.next = node            node.next = next                        # 将插入节点一般元素移至新节点            move_idx = cur.size // 2            for i in range(move_idx, cur.size):                node.elements[i - move_idx] = cur.elements[i]                cur.elements[i] = None                cur.size -= 1                node.size += 1                        # 更新插入位置            if idx >= move_idx:                idx -= move_idx                cur = node                # 插入元素        for i in range(cur.size - 1, idx - 1, -1):            cur.elements[i + 1] = cur.elements[i]        cur.elements[idx] = obj                cur.size += 1        self.total_size += 1

def remove(self, idx):        if idx < 0 or idx >= self.total_size:            return                # 找到删除元素的节点和位置        cur = self.head.next        while idx >= cur.size - 1:            if idx == cur.size - 1:                break            idx -= cur.size            cur = cur.next        # 删除元素        for i in range(idx, cur.size - 1, 1):            cur.elements[i] = cur.elements[i + 1]        cur.elements[cur.size - 1] = None        cur.size -= 1        if cur.next.cap != -1 and cur.cap >= cur.size + cur.next.size:            # 合并删除元素节点的下一节点至当前节点            next = cur.next            for i in range(0, next.size):                cur.elements[cur.size + i] = next.elements[i]            cur.size += next.size            cur.next = next.next        self.total_size -= 1

def get(self, idx):        if idx < 0 or idx >= self.total_size:            return None        cur = self.head.next        while idx >= cur.size:            idx -= cur.size            cur = cur.next        return cur.elements[idx]

最后

..首发，感谢阅读！

欢迎关注个人微信公众号【摸鱼师的技术博客】！

.