How to implement redis double linked list in python

redis Double linked list

Features:

• len: O(1), get the length of the linked list

• head: O(1), the first node at the head

• tail: O(1) the first node at the tail

• No loop: non Circular linked list

• #void *: Store any type of data. (Dynamic language comes naturally)

2. Double linked list API interface

Create/destroy/initialize:

• ##listCreate

• listEmpty

• listRelease

Add node/delete node:

• listAddNodeHead

• listAddNodeTail

• listInsertNode

• listDelNode

Implementing iterator/forward/reverse traversal:

• listGetIterator

• listReleaseIterator

• listRewind

• listRewindTail

##listNext
• list copy, search, rotate and merge operations:

  
  

listDup
listSearchKey

• ##listIndex

• listRotateTailToHead

• listRotateHeadToTail

• listJoin

• ##Source code

3. Use python to implement redis double Linked list api

Refer to redis list definition node and DLinkList

• Python dynamic language needs to manually manage memory application and release.

• Use generators to lazily implement forward and reverse traversal.

• """
  参考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()

The above is the detailed content of How to implement redis double linked list in python. For more information, please follow other related articles on the PHP Chinese website!