Python实现列表和链表

Python实现列表和链表

list[index]                      O(1)
list.append                      O(1)
list.insert                      O(n)
list.pop(index) 默认删last        O(1)
list.remove(element)             O(n)        

class Array(object):
    def __init__(self, size=32):
        self._size = size
        self._items = [None] * self._size

    def __getitem__(self, index):
        return self._items[index]

    def __setitem__(self, index, value):
        self._items[index] = value

    def __len__(self):
        return self._size

    def clear(self, value=None):
        for i in range(len(self._items)):
            self._items[i] = value

    def __iter__(self):
        for item in self._items:
            yield item

单链表

缺点：1. remove时是O(n) 2.只能单向遍历

linked_list.append(value)           O(1)
linked_list.appendleft(value)       O(1)
linked_list.find(value)             O(n)
linked_list.remove(value)           O(n)

class Node(object):
    def __init__(self, value=None, next=None):
        self.value, self.next = value, next


class LinkedList(object):
    def __init__(self, msxsize=None):
        # msxsize=None代表无限大
        self.maxsize = msxsize
        # self.root 是根节点，根节点的next一般指向头节点head节点
        self.root = Node()
        self.length = 0
        # self.tailnode表示最后一个节点
        self.tailnode = None

    def __len__(self):
        return self.length

    def append(self, value):
        # 判断当前最大值是否超过了允许的最大值
        if self.maxsize is not None and len(self) > self.maxsize:
            raise Exception("Full")
        node = Node(value)
        tailnode = self.tailnode
        if tailnode is None:
            # 表明现在只有一个root节点, 然后指向当前的node节点即可
            self.root.next = node
        else:
            # 否则把最后一个节点的next指向当前的node节点
            self.tailnode.next = node
        # 更新最后一个节点为node，因为我们把node放到了最后，而self.tailnode代表最后一个节点，所以要更新
        self.tailnode = node
        # 链表长度加一
        self.length += 1

    def appendleft(self, value):
        # 定义头节点
        headnode = self.root.next
        node = Node(value)
        # 根节点指向新的head节点: node节点
        self.root.next = node
        # node节点指向之前的head节点
        node.next = headnode
        self.length += 1

    def iter_node(self):
        # 第一个节点
        curnode = self.root.next
        # 当前节点不是最后一个节点时
        while curnode is not self.tailnode:
            yield curnode
            # 当前节点更新为下一个节点
            curnode = curnode.next
        # 寻找到最后节点时，也需要把最后一个节点yield出来
        yield curnode

    def __iter__(self):
        for node in self.iter_node():
            yield node.value

    def remove(self, value):
        """
        删除包含值的一个节点，将其前一个节点的next指向下一个节点即可  O(n)
        :param value:
        :return:
        """
        # 根节点
        prevnode = self.root
        for curnode in self.iter_node():
            if curnode.value == value:
                prevnode.next = curnode.next
                if curnode is self.tailnode:
                    # 注意更新 tailnode
                    self.tailnode = prevnode
                del curnode
                self.length -= 1
                # 返回1代表成功
                return 1
            else:
                # 更新 prevnode
                prevnode = curnode
        # 返回-1表示删除失败
        return -1

    def find(self, value):
        # O(n)
        index = 0
        for node in self.iter_node():
            if node.value == value:
                return index
            index += 1
        # 返回-1表示没找到
        return -1

    def popleft(self):
        # O(1)
        if self.root.next is None:
            raise Exception("pop from empty LinkedList")
        headnode = self.root.next
        # 根节点指向头节点的下一个节点
        self.root.next = headnode.next
        value = headnode.value
        self.length -= 1
        del headnode
        return value

    def clear(self):
        for node in self.iter_node():
            del node
        self.root.next = None
        self.length = 0

双端链表

class Node(object):
    def __init__(self, value=None, prev=None, next=None):
        self.value, self.prev, self.next = value, prev, next


class CirculaDoubleLinkedList(object):
    def __init__(self, msxsize=None):
        # msxsize=None代表无限大
        self.maxsize = msxsize
        node = Node()
        node.next, node.prev = node, node
        self.root = node
        self.length = 0

    def __len__(self):
        return self.length

    def headnode(self):
        return self.root.next

    def tailnode(self):
        # 根节点的prev指向尾节点
        return self.root.prev

    def append(self, value):
        # 判断当前最大值是否超过了允许的最大值
        if self.maxsize is not None and len(self) > self.maxsize:
            raise Exception("Full")
        node = Node(value=value)
        tailnode = self.tailnode()
        # 最后一个节点指向新的最后节点
        tailnode.next = node
        # 新的最后节点指向前节点
        node.prev = tailnode
        # node的下一个节点指向root
        node.next = self.root
        # 根节点的上一个节点指向新的最后节点，形成闭环
        self.root.prev = node
        self.length += 1

    def appendleft(self, value):
        # 判断当前最大值是否超过了允许的最大值
        if self.maxsize is not None and len(self) > self.maxsize:
            raise Exception("Full")
        node = Node(value=value)
        # 如果根节点的下一个节点是自己，则证明是空的
        if self.root.next is self.root:
            # 新节点的下一个指向根节点
            node.next = self.root
            # 新节点的上一个指向根节点
            node.prev = self.root
            # 根节点的下一个指向新节点
            self.root.next = node
            # 根节点的上一个指向新节点
            self.root.prev = node
        else:
            # 新节点的上一个节点指向根节点
            node.prev = self.root
            # 获取头节点
            headnode = self.headnode()
            # 新节点的下一个指向头节点
            node.next = headnode
            # 头节点的上一个指向新节点
            headnode.prev = node
            # 根节点的下一个指向新节点
            self.root.next = node
            self.length+=1

    def remove(self, node):
        # O(1)  node is not value
        if node is self.root:
            return
        else:
            # 被删除节点的上一个节点的next指向被删除节点的下一个节点
            node.prev.next = node.next
            # 被删除节点的下一个节点的prev指向被删除节点的上一个节点
            node.next.prev = node.prev
        self.length -= 1
        return node

    def iter_node(self):
        if self.root.next is self.root:
            return
        curnode = self.root.next
        while curnode is not self.root:
            yield curnode
            curnode = curnode.next
        yield curnode

    def __iter__(self):
        for node in self.iter_node():
            yield node.value

    def iter_node_reverse(self):
        if self.root.next is self.root:
            return
        curnode = self.root.prev
        while curnode is not self.root:
            yield curnode
            curnode = curnode.prev
        yield curnode