Python에서 Redis 이중 연결 목록을 구현하는 방법

redis 이중 연결 목록

기능:

• len: O(1), 연결 목록의 길이를 가져옵니다.

• head: O(1), 머리의 첫 번째 노드

• tail: O(1) tail 첫 번째 노드

• acycl: 비순환 연결 목록

• void *: 모든 유형의 데이터를 저장합니다. (동적 언어는 자연스럽게 제공됨)

2. 이중 연결 목록 API 인터페이스

Create/destroy/initialize:

• listCreate

• listEmpty

• listRelease

노드 추가/노드 삭제:

• listAddNodeHead

• listAddNodeTail

• listInsertNode

• listDelNode

반복자/정방향/역방향 탐색 구현:

• listGetIterator

• listReleaseIterator

• listRewind

• listRewindTail

• listNext
  목록 복사, 찾기, 회전 병합 작업:

• listDup

• listSearchKey

• listIndex

• listRotateTailTo Head

• listRotateHeadToTail

• listJoin

소스 코드

3. Python을 사용하여 Redis 이중 연결 목록의 API를 구현합니다.

• Redis 목록 정의 노드 및 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(&#39;find node:&#39;, 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 이중 연결 목록을 구현하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!