数据结构 04 链表

链表

无序链表: 每个节点的入口都是链头.
有序链表: 每个节点的入口是根据已有节点比较, 存放在大于和小于值的中间.
双向无序链表: 每个节点都有两个引用, 分别声明 左边节点和右边节点(相邻).
双向有序链表: 每个节点都有两个引用, 分别声明 左边节点和右边节点(相邻).

# -.- coding:utf-8 -.-
from __future__ import print_function

CHAIN_TYPE = {
    "UnorderedChain": "无序链表",
    "OrderedChain": "有序链表",
    "BidirectionalUnorderedChain": "双向无序链表",
    "BidirectionalOrderedChain": "双向有序链表"
}


class Node(object):

    def __init__(self, data):
        self.__data = data
        self.__right = None

    @property
    def right(self):
        return self.__right

    @right.setter
    def right(self, item):
        self.__right = item

    @property
    def data(self):
        return self.__data

    @data.setter
    def data(self, item):
        self.__data = item

    def __str__(self):
        return "<Node {}>".format(self.data)


class BidirectionalNode(Node):

    def __init__(self, data):
        super(BidirectionalNode, self).__init__(data)
        self.__left = None

    @property
    def left(self):
        return self.__left

    @left.setter
    def left(self, item):
        self.__left = item


class Chain(object):

    def __init__(self):
        self.chain = None

    def add(self, item):
        raise NotImplementedError()

    def remove(self, item):
        raise NotImplementedError()

    def get_node(self, item):
        node = self.chain
        while node:
            if node.data == item:
                return node
            # 链尾右边是None, 因此不会死循环.
            node = node.right

    def search(self, item):
        if self.get_node(item):
            return True
        return False

    def empty(self):
        return self.chain is None

    def size(self):
        node = self.chain
        count = 0
        while node:
            count += 1
            node = node.right
        return count

    def __str__(self):
        node = self.chain
        s = []
        while node:
            s.append(node.data)
            node = node.right
        return "{}".format(s)

    def __iter__(self):
        return self

    def __next__(self):
        if self.chain is None:
            raise StopIteration
        data = self.chain.data
        self.chain = self.chain.right
        return data

    def next(self):
        self.__next__()


class UnorderedChain(Chain):

    def add(self, item):
        node = Node(item)
        node.right = self.chain
        self.chain = node

    def remove(self, item):
        pass


class OrderedChain(Chain):

    def add(self, item):
        node = Node(item)
        previous = None
        current = self.chain

        while current:
            if current.data > item:
                break
            previous = current
            # 链尾右边是None, 因此不会死循环.
            current = current.right

        if previous is None:
            node.right = self.chain
            self.chain = node
        else:
            previous.right = node
            node.right = current

        return True

    def remove(self, item):
        pass


class BidirectionalUnorderedChain(Chain):

    def add(self, item):
        node = Node(item)
        node.right = self.chain
        if self.chain:
            self.chain.left = node
        self.chain = node

    def remove(self, item):
        pass


class BidirectionalOrderedChain(Chain):
    def add(self, item):
        node = Node(item)
        previous = None
        current = self.chain

        while True:
            if current is None:
                break
            if current.data > item:
                break
            previous = current
            current = current.right

        if previous is None:
            node.right = self.chain
            self.chain = node
            return True

        previous.right = node
        node.left = previous
        if current:
            current.left = node
            node.right = current
        return True

    def remove(self, item):
        pass


def main(cls):
    chain = cls()
    cls_name = chain.__class__.__name__
    print("链表: <{} {}>".format(cls_name, CHAIN_TYPE.get(cls_name)))
    # 增加测试数据
    chain.add(31)
    chain.add(27)
    chain.add(28)
    chain.add(29)
    chain.add(30)
    # 查看链表元素数量
    print("查看链表元素数量: ", chain.size())
    # 查看链表
    print("查看链表: ", chain)

    # 查看Node对象
    if "Bidirectional" in cls_name:
        print("查看Node 29对象 Left：", chain.get_node(29).left)
    print("查看Node 29对象 Current：", chain.get_node(29))
    print("查看Node 29对象 Right：", chain.get_node(29).right)

    # 遍历链表
    for i in chain:
        print("遍历链表: ", i)


if __name__ == '__main__':
    main(UnorderedChain)
    main(OrderedChain)
    main(BidirectionalUnorderedChain)
    main(BidirectionalOrderedChain)

    # 输出结果
    # 链表: <UnorderedChain 无序链表>
    # 查看链表元素数量:  5
    # 查看链表:  [30, 29, 28, 27, 31]
    # 查看Node 29对象 Current： <Node 29>
    # 查看Node 29对象 Right： <Node 28>
    # 遍历链表:  30
    # 遍历链表:  29
    # 遍历链表:  28
    # 遍历链表:  27
    # 遍历链表:  31
    
    
    
    # 链表: <OrderedChain 有序链表>
    # 查看链表元素数量:  5
    # 查看链表:  [27, 28, 29, 30, 31]
    # 查看Node 29对象 Current： <Node 29>
    # 查看Node 29对象 Right： <Node 30>
    # 遍历链表:  27
    # 遍历链表:  28
    # 遍历链表:  29
    # 遍历链表:  30
    # 遍历链表:  31
    
    
    
    # 链表: <BidirectionalUnorderedChain 双向无序链表>
    # 查看链表元素数量:  5
    # 查看链表:  [30, 29, 28, 27, 31]
    # 查看Node 29对象 Left： <Node 30>
    # 查看Node 29对象 Current： <Node 29>
    # 查看Node 29对象 Right： <Node 28>
    # 遍历链表:  30
    # 遍历链表:  29
    # 遍历链表:  28
    # 遍历链表:  27
    # 遍历链表:  31
    
    
    
    # 链表: <BidirectionalOrderedChain 双向有序链表>
    # 查看链表元素数量:  5
    # 查看链表:  [27, 28, 29, 30, 31]
    # 查看Node 29对象 Left： <Node 28>
    # 查看Node 29对象 Current： <Node 29>
    # 查看Node 29对象 Right： <Node 30>
    # 遍历链表:  27
    # 遍历链表:  28
    # 遍历链表:  29
    # 遍历链表:  30
    # 遍历链表:  31