双向链表_实现append pop insert iternodes

作者: 青蛙兄 分类: 习题 发布时间: 2019-07-20 23:36
class SingleNode:  

    """ 

    代表一个节点 

    """  

  

    def __init__(self, val, next=None, prev=None):  

        self.val = val  

        self.next = next  

        self.prev = prev  

  

    def __repr__(self):  

        return str(self.val)  

  

    def __str__(self):  

        return str(self.val)  

  

  

class LinkdList:  

    """ 

    容器类,某种方式存储一个个节点 

    """  

  

    def __init__(self):  

        self.head = None  

        self.tail = None  

  

    def append(self, val):  

        node = SingleNode(val)  

        if self.head is None:  

            self.head = node  

        else:  

            self.tail.next = node  

            node.prev = self.tail  

        self.tail = node  

  

    def iternodes(self, reverse=False):  

        current = self.tail if reverse else self.head  

        while current:  

            yield current  

            current = current.prev if reverse else current.next  

  

    def pop(self):  

        """ 

        弹出tail尾部 

        :return: 

        """  

        if self.tail is None:  

            raise Exception("Empty")  

        tail = self.tail  

        prev = tail.prev  

        if prev is None:  

            self.head = None  

            self.tail = None  

        else:  

            self.tail = prev  

            prev.next = None  

        return tail.val  

  

    def getitem(self, index):  

        if index < 0:  

            return None  

        current = None  

        for i, node in enumerate(self.iternodes()):  

            if i == index:  

                current = node  

                break  

            if current is not None:  

                return current  

  

    def insert(self, index, val):  

        if index < 0:  

            raise Exception("Error")  

        current = None  

        for i, node in enumerate(self.iternodes()):  

            if i == index:  

                current = node  

                break  

        if current is None:  

            self.append(val)  

            return  

  

        prev = current.prev  

  

        node = SingleNode(val)  

        if prev is None:  # 头部插入  

            self.head = node  

            node.next = current  

            current.prev = node  

        else:  

            node.prev = prev  

            node.next = current  

            current.prev = node  

            prev.next = node  

  

  

lst = LinkdList()  

node = SingleNode(1)  

lst.append(node)  

node = SingleNode(2)  

lst.append(node)  

node = SingleNode(3)  

lst.append(node)  

node = SingleNode(4)  

lst.append(node)  

lst.insert(0,5)  

# lst.pop()  

# lst.pop()  

# lst.pop()  

  

for node in lst.iternodes():  

    print(node)  


发表评论

电子邮件地址不会被公开。