跳跃表

说明：基于有序单链表的跳跃表

进度：初始化、插入、跳表节点补全、删除

后续：查询、节点不足时的删除

import random


class Node(object):
    def __init__(self, item, next):
        self.item = item
        self.next = next


class Link(object):
    def __init__(self, init_list: list):
        """
        初始化
        """
        self._link = None
        self._reverse_link = None
        self.length = 0
        self._link = self._init_link(init_list)
        self._index = 0

    def _init_link(self, init_list: list):
        if len(init_list) < 1:
            return None
        _link = None
        init_list.reverse()
        for item in init_list:
            _link = Node(item, _link)
        self.length += len(init_list)
        return _link

    @property
    def list(self):
        """
        将链表转换成list
        :return:
        """
        res = []
        link = self._link
        while link:
            res.append(link.item)
            link = link.next
        return res

    def clear(self):
        """
        清空链表
        :return:
        """
        self._link = None
        self.length = 0

    def delete(self, item):
        """
        删除某个元素
        :param item:
        :return:
        """
        link = self._link
        prev = None
        while link:
            if item == link.item:
                if prev is None:
                    self._link = link.next
                else:
                    prev.next = link.next
                break
            prev = link
            link = link.next
        self.length -= 1

    def insert(self, item, index):
        """
        向链表index位置插入一个item元素
        :param item:
        :param index:
        :return:
        """
        i = 0
        if index == 0:
            self._link = Node(item, self._link)
        else:
            if index == self.length - 1:
                _index = index
            else:
                _index = index - 1
            link = self._link
            while link:
                if _index == i:
                    link.next = Node(item, link.next)
                    break
                i = i + 1
                link = link.next
        self.length += 1

    def append(self, append_list: list):
        """
        向链表添加多个元素
        :param append_list:
        :return:
        """
        link = self._link
        while link:
            if link.next is None:
                link.next = self._init_link(append_list)
                break
            link = link.next

    def get_index(self, item):
        """
        获取某个元素的下标
        :param item:
        :return:
        """
        link = self._link
        index = 0
        while link:
            if link.item == item:
                return index
            link = link.next
            index += 1

    def get_node(self, index):
        """
        根据下标获取某个节点对象
        :param index:
        :return:
        """
        link = self._link
        _index = 0
        while link:
            if _index == index:
                print(_index)
                return link
            link = link.next
            _index += 1

    def reverse(self, next=None):
        """
        链表反转
        :return:
        """
        if next is None:
            link = self._link
        else:
            link = next
        if link is None:
            return
        self._reverse_link = Node(link.item, self._reverse_link)
        if link.next is None:
            self._link = self._reverse_link
            self._reverse_link = None
            return
        self.reverse(link.next)

    def empty(self):
        """
        链表是否为空
        :return:
        """
        if self._link is None:
            return True
        else:
            return False

    def in_link(self, item):
        """
        判断元素是否在链表中
        :param item:
        :return:
        """
        link = self._link
        while link:
            if item == link.item:
                return True
            link = link.next
        return False

    def __iter__(self):
        return self

    def __next__(self):
        link = self._link
        _index = 0
        while link:
            if _index == self._index:
                self._index += 1
                return link.item
            link = link.next
            _index += 1
        self._index = 0
        raise StopIteration

    @property
    def reverse_link(self):
        return self._reverse_link

    @property
    def link(self):
        return self._link


class SkipLink(object):
    # 建立跳跃节点的随机范围
    RANDOM_START = 1
    RANDOM_END = 2

    # 随机节点，测试用
    random_test = 0

    def __init__(self, link: Link):
        self.links = [link]  # 存放所有链表头节点的列表，以level越小位置约后，原链表的level为0
        self._init_skip_link(link)
        # self.random_test = 0

    def _init_skip_link(self, link):
        """
        基于有序单链表生成跳跃表
        :param link:
        :return:
        """
        _link = link._link
        index = 0
        temp_link = Link([])
        while _link:
            if self._random_for_create_skip_node() is True:
                temp_link._link = Node(_link, temp_link._link)
                temp_link.length += 1
            _link = _link.next
            index += 1
        temp_link.reverse()  # 由于初始化时倒序的，所以要反转列表 todo 尝试编写正序生成链表的方法
        self.links.insert(0, temp_link)
        if temp_link.length > self.RANDOM_END:
            self._init_skip_link(temp_link)

    def insert(self, item):
        """
        向跳跃表插入元素
        :param item:
        :return:
        """
        self._insert_to_skip(item, 0, None, None)

    def _insert_to_skip(self, item, index, current, prev):
        """
        向跳跃表插入元素
        :param item: 要插入的元素
        :param index: 当前跳表保存在self.links中的下标
        :param current: 跳表或原表的当前节点
        :param prev:  跳表或原表的上一个节点
        :return:
        """
        length = len(self.links)
        if current is None:
            _link = self.links[index]._link
        else:
            _link = current.item
        if prev is None:
            _prev = None
        else:
            _prev = prev.item
        while _link:
            prev_item = self._get_item(_prev)
            current_item = self._get_item(_link)
            if item == current_item:
                raise Exception('元素重复')
            if _prev is None and item < current_item:
                if index == length - 1:
                    self.links[index]._link = Node(item, self.links[index]._link)
                    self.links[index].length += 1
                    self._create_skip_node(index, self.links[index]._link)
                    break
                else:
                    self._insert_to_skip(item, index + 1, _link, _prev)
                    break
            if _prev is None:
                _prev = _link
                _link = _link.next
                continue
            if _link.next is None and item > current_item:
                if index == length - 1:
                    _link.next = Node(item, None)
                    self.links[index].length += 1
                    self._create_skip_node(index, _link.next)
                    break
                else:
                    self._insert_to_skip(item, index + 1, _link, _prev)
                    break
            if item > current_item:
                _prev = _link
                _link = _link.next
                continue
            if prev_item < item < current_item:
                if index == length - 1:
                    _prev.next = Node(item, _link)
                    self.links[index].length += 1
                    self._create_skip_node(index, _prev.next)
                    break
                else:
                    self._insert_to_skip(item, index + 1, _prev, _prev)
                    break

            _prev = _link
            _link = _link.next

    def _get_item(self, link):
        """
        通过调表的指针获取原链表的具体数值
        :param link:
        :return:
        """
        if link is None:
            return None
        if isinstance(link, int) is True:
            return link
        if isinstance(link.item, Node) is False:
            return link.item
        else:
            return self._get_item(link.item)

    @staticmethod
    def _get_item_type(link):
        return isinstance(link.item, (Node,))

    def _random_for_create_skip_node_test(self):
        if random.randint(self.RANDOM_START, self.RANDOM_END) % self.RANDOM_END == 0:
            return True
        return False

    def _random_for_create_skip_node(self):
        """
        判断是否要生成跳表节点（测试用，固定间隔，伪随机，真规律）
        :return:
        """
        _random_test = self.random_test
        self.random_test += 1
        if _random_test % 2 == 0:
            return True
        else:
            return False

    def _create_skip_node(self, index, item_pointer):
        """
        创建跳表节点
        :param index:
        :param item_pointer:本函数最具迷惑性的参数，item并不是具体的值，而是上一层跳表/原表在该位置上的指针
        :return:
        """
        if self._random_for_create_skip_node() is False:
            return False
        _link = self.links[index - 1]._link
        _prev = None
        while _link:
            _item = self._get_item(_link)
            _item_pointer = self._get_item(item_pointer)
            if _item > _item_pointer and _prev is None:
                _link = Node(item_pointer, _link)
                self.links[index - 1].length += 1
                if index > 0:
                    self._create_skip_node(index - 1, _link)
                break
            if _item < _item_pointer and _link.next is None:
                _link.next = Node(item_pointer, None)
                self.links[index - 1].length += 1
                if index > 0:
                    self._create_skip_node(index - 1, _link.next)
                break
            if _item > _item_pointer:
                # 注意，这里不是item，应该是指向上层的一个指针
                _prev.next = Node(item_pointer, _link)
                self.links[index - 1].length += 1
                if index > 0:
                    self._create_skip_node(index - 1, _prev.next)
                break
            _prev = _link
            _link = _link.next
        return False

    def delete(self, item):
        """
        删除方法
        :param item:
        :return:
        """
        self._delete_node(item, 0, None)
        # 删除掉只剩下一个元素的跳表行
        if self.links[0].length < 2:
            self.delete(self._get_item(self.links[0]._link))

    def _delete_node(self, item, index, current):
        if current is None:
            _link = self.links[index]._link
        else:
            _link = current.item
        _prev = None
        while _link:
            current_item = self._get_item(_link)
            if item < current_item:
                self._delete_node(item, index+1, _prev)
                return
            if item == current_item and _prev is None:
                # 删除只有一个元素的跳表行
                if self.links[index].length == 1:
                    self.links = self.links[1:]
                    return
                self.links[index]._link = _link.next
                self.links[index].length -= 1
                if self._get_item_type(_link):
                    self._delete_node(item, index+1, _prev)
                return
            if item == current_item and _link.next is None:
                _prev.next = None
                self.links[index].length -= 1
                if self._get_item_type(_link):
                    self._delete_node(item, index+1, _prev)
                return
            if item == current_item:
                _prev.next = _link.next
                self.links[index].length -= 1
                if self._get_item_type(_link):
                    self._delete_node(item, index+1, _prev)
                return
            _prev = _link
            _link = _link.next

        # 这一行的元素删除完毕，开始下一行元素的删除
        if index < 3:
            self._delete_node(item, index+1, _prev)
            return

    def __str__(self):
        link_list = self.links[len(self.links) - 1].list
        s = ''
        for item in link_list:
            for link in self.links:
                _link = link._link
                while _link:
                    if self._get_item(_link) == item:
                        s += str(item) + '\t'
                    _link = _link.next
            s = s + '\n'
        return s


if __name__ == '__main__':
    link = Link([13, 27, 34, 38, 41, 44, 50, 55, 59, 62, 67, 80, 90])
    # link = Link(list(range(100, 1000, 3)))
    skip_link = SkipLink(link)
    print(str(skip_link))
    skip_link.delete(67)
    print('#####################')
    print(str(skip_link))

    """
    在_insert_to_skip_2方法中，多次在不同的地方进行了递归调用
    由于没有递归结束的条件（结束的条件只有while循环结束），所以递归回来之后接着上面的地方继续执行
    """

图示与边界条件：

[13, 22, 27, 34, 38, 41, 44, 50, 55, 59, 62, 67, 73, 80]
[13 27 38 44 55 62 73]
[13 38 55 73]
[13 55]

3.小于当前元素的值 并且上一个元素不存在：
如果处于原表位置：
进行插入操作
break
否则：
将当前元素作为上一个元素的起点，递归跳表

1.上一个元素不存在
交换_link和_prev
continue循环

2.下一个元素不存在 并且大于当前元素的值
如果处于原表位置：
进行插入操作
break
否则：
将当前元素作为下一层表的起点，递归跳表

4.大于当前元素的值
交换_link和_prev
continue循环

5.大于上一个元素的值小于当前元素的值
如果处于原表位置：
进行插入操作
break
否则：
将上一个元素作为下一层表的起点，递归跳表

交换_link和_prev
continue循环