python怎么實現redis雙鏈表

這篇文章主要介紹“python怎么實現redis雙鏈表 ”，在日常操作中，相信很多人在python怎么實現redis雙鏈表 問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”python怎么實現redis雙鏈表 ”的疑惑有所幫助！接下來，請跟著小編一起來學習吧！

redis 雙鏈表

特點:

• len: O(1)，獲取鏈表長度

• head: O(1), 頭部第一個節點

• tail: O(1) 尾部第一個節點

• 無環: 非循環鏈表

• void *: 存儲任意類型數據。 (動態語言天然自帶)

2.雙鏈表API接口

創建/銷毀/初始化:

• listCreate

• listEmpty

• listRelease

添加節點/刪除節點:

• listAddNodeHead

• listAddNodeTail

• listInsertNode

• listDelNode

實現迭代器/正向/反向遍歷:

• listGetIterator

• listReleaseIterator

• listRewind

• listRewindTail

• listNext
  list復制，查找，旋轉合并操作:

• listDup

• listSearchKey

• listIndex

• listRotateTailToHead

• listRotateHeadToTail

• listJoin

源碼

3.使用python實現redis雙鏈表的api

• 參考redis list定義節點和DLinkList

• python動態語言需要手動管理內存申請釋放.

• 使用生成器, 偷懶式實現正向反向遍歷.

"""
參考redis adlist.c. 實現雙鏈表相關的api
    
        head           tail
None    <-     <-      <-
        1       2       3       
        ->      ->     ->       None    

len:3
"""
import copy
from typing import Any

class  Node(object):
    def __init__(self, data) -> None:
        self.next = None
        self.pre = None
        self.data = data
    
    def __str__(self) -> str:
        return f"{self.data}"

class DLinkList(object):
    def __init__(self) -> None:
        self.head = None
        self.tail = None
        self.len = 0
    
    def empty(self) -> None:
        self.head = None
        self.tail = None
        self.len = 0
    
    def add_node_head(self, data=None) -> Node:
        """[頭插法]

        Args:
            data ([type], optional): [description]. Defaults to None.
        """
        new_node = Node(data=data)
        if self.len == 0:
            # 鏈表為空. 處理頭/尾指針
            self.tail = new_node
            self.head = new_node
        else:
            # 插入新節點
            new_node.next = self.head
            self.head.pre = new_node
            self.head = new_node
        self.len += 1
        return new_node
    
    def add_node_tail(self, data: Any=None) -> Node:
        """[尾插法]

        Args:
            data ([type], optional): [description]. Defaults to None.
        """
        new_node = Node(data=data)
        if self.len == 0:
            # 鏈表為空. 處理頭/尾指針
            self.tail = new_node
            self.head = new_node
        else:
            # 插入新節點
            new_node.pre = self.tail
            new_node.next = self.tail.next
            self.tail.next = new_node
            # 更新尾指針
            self.tail = new_node
        self.len += 1
        return new_node
    
    def insert_node(self, old_node: Node=None, data: Any=None, after: bool=False) -> None:
        """[插入新節點, 在舊節點的前/后]

        Args:
            old_node (Node, optional): [舊節點]. Defaults to None.
            data (Any, optional): [新數據]. Defaults to None.
            after (Bool, optional): [是否在之后插入]. Defaults to False.
        """
        assert self.len, f"self.len({self.len}) must > 0"
        new_node = Node(data=data)
        if after:
            new_node.pre = old_node
            new_node.next = old_node.next
            old_node.next.pre = new_node
            old_node.next = new_node
            if self.tail == old_node:
                self.tail = new_node
        else:
            new_node.pre = old_node.pre
            new_node.next = old_node
            old_node.pre.next = new_node
            old_node.pre = new_node
            if self.head == old_node:
                self.head = new_node
        self.len += 1
    
    def del_node(self, node: Node) -> None:
        """[刪除節點]

        Args:
            node (Node): [description]
        """
        assert self.len, "DLinklist is None"
        if not node:
            return
        if node == self.head:
            self.head = node.next
        else:
            # 1.處理next
            node.pre.next = node.next
        
        if node == self.tail:
            self.tail = node.pre
        else:
            # 2.處理pre
            node.next.pre = node.pre
        
        node.pre = None
        node.next = None
        del node 
        self.len -= 1

    def next(self, reversed:bool=False):
        """[獲取生成器]

        Args:
            reversed (bool, optional): [description]. Defaults to False.

        Returns:
            [type]: [description]
        """
        if reversed:
            return self._reverse_next()
        return self._next()

    def _reverse_next(self):
        """[反向迭代, 使用生成器記錄狀態]

        Yields:
            [type]: [description]
        """
        cur = self.tail
        idx = self.len - 1
        while cur:
            yield (idx, cur)
            idx -= 1
            cur = cur.pre

    def _next(self):
        """[正向迭代, 使用生成器記錄狀態]]

        Yields:
            [type]: [description]
        """
        cur = self.head
        idx = 0
        while cur:
            yield (idx, cur)
            idx += 1
            cur = cur.next
    
    def dup(self):
        return copy.deepcopy(self)
    
    def find(self, key: Any=None) -> tuple:
        if not key:
            return
        
        g = self.next()
        for idx, node in g:
            if node.data == key:
                return idx, node
        return -1, None
    
    def rotate_tail_to_head(self) -> None:
        """[正向旋轉節點]
        移動尾節點，插入到頭部
        """
        assert self.len >= 2, "dlist len must >=2"
        head = self.head
        tail = self.tail
        # remove tail
        self.tail = tail.pre
        self.tail.next = None
        # move to head 
        tail.next = head
        tail.pre = head.pre
        self.head = tail

    def rotate_head_to_tail(self) -> None:
        """[反向旋轉節點]
        移動頭點，插入到尾部
        """
        assert self.len >= 2, "dlist len must >=2"
        head = self.head
        tail = self.tail
        # remove head
        self.head = head.next
        self.head.pre = None
        # move to tail
        tail.next = head
        head.pre = tail
        self.tail = head
        self.tail.next = None

    def join(self, dlist: Any=None):
        """[合并雙鏈表]

        Args:
            dlist (Any, optional): [description]. Defaults to None.
        """
        pass

    def __str__(self) -> str:
        ans = ""
        for idx, node in self.next(reversed=False):  
            ans += f"idx:({idx}) data:({node.data})n"
        return ans


def test_add_node(dlist:DLinkList=None):
    n = 5
    for i in range(n):
        dlist.add_node_tail(data=i)
        # dlist.add_node_head(data=i)
    print(dlist)

def test_del_node(dlist:DLinkList=None):
    i = dlist.len
    while i: 
        node = None
        dlist.del_node(node)
        i -= 1
    print(dlist)
    
def test_insert_node(dlist:DLinkList=None):
    # dlist.insert_node(old_node=old_node, data=100, after=True)
    # print(dlist, id(dlist))
    # nlist = dlist.dup()
    # print(nlist, id(nlist))
    idx, fnode = dlist.find(1)
    print('find node:', idx, fnode)
    dlist.insert_node(fnode, 100, after=True)
    print("insert after")
    print(dlist)
    dlist.insert_node(fnode, 200, after=False)
    print("insert before")
    print(dlist)

def test_rotate(dlist:DLinkList=None):
    print("move head to tail")
    dlist.rotate_head_to_tail()
    print(dlist)

    print("move tail to head")
    dlist.rotate_tail_to_head()
    print(dlist)

def test_join(dlist:DLinkList=None, olist:DLinkList=None):
    print("join list")
    nlist = dlist.join(olist)
    print(nlist)


def main():
    dlist = DLinkList()
    test_add_node(dlist)
    # test_del_node(dlist)
    # test_insert_node(dlist)
    test_rotate(dlist)

if __name__ == "__main__":
    main()

到此，關于“python怎么實現redis雙鏈表 ”的學習就結束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習，快去試試吧！若想繼續學習更多相關知識，請繼續關注億速云網站，小編會繼續努力為大家帶來更多實用的文章！