面试笔试记录--双向链表（Python）

左手的ㄟ右手 2022-05-10 11:34 91阅读 0赞

双向链表也叫[双链表][Link 1]，是链表的一种，它的每个数据结点中都有两个[指针][Link 2]，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向[循环链表][Link 3]。

'''节点类'''
    class Node(object):
        def __init__(self,data = None):
            self.data = data
            self.pre = None
            self.next = None
    
        '''初始化双向链表'''
    
    class DLinkList(object):
        def __init__(self):
            """
            设置头尾，操作比较容易
            头－－（next）－－》尾
            尾－－（pre）－－》头
            :return:
            """
            head = Node()
            tail = Node()
            self.head = head
            self.tail = tail
            self.head.next = self.tail
            self.tail.pre = self.head
    
        def __len__(self):
            length = 0
            node = self.head
            while node.next != self.tail:
                length += 1
                node = node.next
            return length
    
        def print_(self):
            node = self.head
            while node.next != self.tail:
                print(node.next.data)
                node = node.next
    
        def append(self,data):
            """
            :param data:
            :return:
            """
            node = Node(data)
            x = self.tail.pre
            x.next = node
            node.pre = x
            node.next = self.tail
            self.tail.pre = node
            return node
    
        def get(self,index):
            """
            获取第index个值，若index>0正向获取else 反向获取
            :param index:
            :return:
            """
            node = self.head.next
            num = None
            for i in range(index+1):
                num = node.data
                node = node.next
            return num
    
        def set(self,index,data):
            node =self.head
            for i in range(index+1):
                node = node.next
            node.data = data
            return node
    
        def insert(self,index,data):
            """
                因为加了头尾节点所以获取节点node就一定存在node.next 和 node.pre
                :param index:
                :param data:
                :return:
                """
            length = len(self)
            if (index+1)>length:
                return False
            index = index if index >=0 else index + 1+length
    
            next_node = self.get(index)
            if next_node:
                node = Node(data)
                pre_node = next_node.pre
                pre_node.next = node
                node.pre = pre_node
                node.next = next_node
                next_node.pre = node
                return node
    
        def delete(self,index):
            node = self.head
            for i in range(index):
                node = node.next
            node2 = node.next.next
            node.next = node2
            node2.pre = node
    
        '''反转链表'''
    
        def __reversed__(self):
            """
            1.node.next --> node.pre
              node.pre --> node.next
            2.head.next --> None
              tail.pre --> None
            3.head-->tail
             tail-->head
            :return:
            """
            pre_head = self.head
            tail = self.tail
    
            def reverse(pre_node, node):
                if node:
                    next_node = node.next
                    node.next = pre_node
                    pre_node.pre = node
                    if pre_node is self.head:
                        pre_node.next = None
                    if node is self.tail:
                        node.pre = None
                    return reverse(node, next_node)
                else:
                    self.head = tail
                    self.tail = pre_head
    
            return reverse(self.head, self.head.next)
    
        def clear(self):
            self.head.next = self.tail
            self.tail.pre = self.head
    
    
    n = DLinkList()
    n.append(5)
    n.append(6)
    n.append(7)
    n.append(8)
    n.__reversed__()
    n.delete(0)
    n.print_()

[Link 1]: https://baike.baidu.com/item/%E5%8F%8C%E9%93%BE%E8%A1%A8/5827945
[Link 2]: https://baike.baidu.com/item/%E6%8C%87%E9%92%88/2878304
[Link 3]: https://baike.baidu.com/item/%E5%BE%AA%E7%8E%AF%E9%93%BE%E8%A1%A8/3228465