链表和双链表的Python实现

# 结点
class Node:
    def __init__(self, data, next_node):
        self.data = data
        self.next_node = next_node

# 创建链表
class LinkedList:
    def __init__(self, first_node):
        self.first_node = first_node

    def link_read(self, read_index):
        # 从第一个结点开始
        current_node = self.first_node
        current_index = 0
        while current_index < read_index:
            # 当前索引小于要找的索引,就需要继续顺着链往下找,直至找到我们要找的索引值
            current_node = current_node.next_node
            current_index += 1
            # 如果读到最后一个结点之后,就说明所找的索引不在链表中,因此返回None
            if not current_node:
                return None
        return current_node.data

    def link_search(self, search_value):
        # 从第一个结点开始
        current_node = self.first_node
        current_index = 0
        while current_node.data != search_value:
            # 如果当前结点的值不是要找的值,就需要继续顺着链往下找,直至找到我们要找的值
            current_node = current_node.next_node
            current_index += 1
            # 如果读到最后一个结点之后,就说明所找的值不在链表中,因此返回None
            if not current_node:
                return None
        return current_index

    def link_insert(self, new_data, insert_at_index):
        # 创建插入的新结点
        new_node = Node(new_data, None)
        # 如果在开头插入, 则将新结点指向原first_node
        # 并重新设置first_node
        if insert_at_index == 0:
            new_node.next_node = node_01
            self.first_node = new_node
            return "insert at start successfully"
        # 找到新结点插入位置前的那一个结点
        current_node = self.first_node
        current_index = 0
        prevent_index = insert_at_index - 1
        while current_index < prevent_index:
            temporary_node = current_node
            # 当前索引小于要找的索引前一个,就需要继续顺着链往下找,直至找到我们要找的索引值
            current_node = current_node.next_node
            current_index += 1
            # 如果要添加的结点超过链表最大索引就插入链表最末尾
            if not current_node:
                current_node = temporary_node
                break
        # 当前结点下一个结点是新结点,新结点的下一个结点是当前结点的下一结点
        new_node.next_node = current_node.next_node
        current_node.next_node = new_node
        return "insert successfully"

    def link_delete(self, delete_at_index):
        # 如果删除的结点是第一个,则只需将first_node重置为第二个结点便可
        if delete_at_index == 0:
            self.first_node = node_02
            return node_01.data
        # 如果删除的结点不是第一个,需要找到要删结点的前一个结点
        current_node = self.first_node
        current_index = 0
        prevent_index = delete_at_index - 1
        while current_index < prevent_index:
            temporary_node = current_node
            current_node = current_node.next_node
            current_index += 1
            # 如果要删除的结点超过链表最大索引就删除链表最末尾的结点
            if not current_node.next_node:
                temporary_node.next_node = None
                return temporary_node.data
        # 要删除的结点和要删除结点的后一个结点
        delete_node = current_node.next_node
        after_delete_node = delete_node.next_node
        # 将要删除结点的前一个结点的next_node指向要删除结点的后一个结点
        current_node.next_node = after_delete_node
        delete_node.next_node = None
        return delete_node.data

if __name__ == ‘__main__‘:
    node_09 = Node("plus", None)
    node_08 = Node("flay", node_09)
    node_07 = Node("dump", node_08)
    node_06 = Node("blog", node_07)
    node_05 = Node("load", node_06)
    node_04 = Node("lope", node_05)
    node_03 = Node("amid", node_04)
    node_02 = Node("upon", node_03)
    node_01 = Node("once", node_02)
    # 将第一个结点node_01作为指针创建链表
    link_list = LinkedList(node_01)

    print(link_list.link_read(5))
    print(link_list.link_search("dump"))
    print(link_list.link_insert("jeep", 12))
    print(link_list.link_delete(13))

# 结点
class Node:
    def __init__(self, data):
        self.data = data
        self.previous_node = None
        self.next_node = None

# 创建双链表
class DoublyLinkedList:
    def __init__(self, first_node, last_node):
        self.first_node = first_node
        self.last_node = last_node

    # 在链表末尾插入数据
    def insert_at_end(self, insert_value):
        # 创建新结点
        new_node = Node(insert_value)
        # 如果链表还没有任何结点
        if not self.first_node:
            self.first_node = new_node
            self.last_node = new_node
        else:
            # 否则,将新结点的prevent_node指向链表的原last_node
            new_node.previous_node = self.last_node
            # 将链表的原last_node的next_node指向新结点
            self.last_node.next_node = new_node
            # 将链表的原last_node重新设置为新结点
            self.last_node = new_node
        return new_node.data

    # 在链表开头删除数据
    def remove_from_front(self):
        remove_node = self.first_node
        self.first_node = remove_node.next_node
        return remove_node.data

# 基于双链表的队列
class LinkQueue:
    def __init__(self, first_node, last_node):
        self.link_queue = DoublyLinkedList(first_node, last_node)
    # 入队
    def entry_queue(self, entry_value):
        self.link_queue.insert_at_end(entry_value)
        return str(entry_value) + "入队成功"
    # 出队
    def leave_queue(self):
        remove_node = self.link_queue.remove_from_front()
        return str(remove_node) + "出队成功"
    # 查看队列末尾数据
    def link_tail(self):
        tail_value = self.link_queue.last_node.data
        return tail_value

if __name__ == ‘__main__‘:
    node_09 = Node("plus")
    node_08 = Node("flay")
    node_07 = Node("dump")
    node_06 = Node("blog")
    node_05 = Node("load")
    node_04 = Node("lope")
    node_03 = Node("amid")
    node_02 = Node("upon")
    node_01 = Node("once")
    node_01.next_node = node_02
    node_02.previous_node = node_01
    node_02.next_node = node_03
    node_03.previous_node = node_02
    node_03.next_node = node_04
    node_04.previous_node = node_03
    node_04.next_node = node_05
    node_05.previous_node = node_04
    node_05.next_node = node_06
    node_06.previous_node = node_05
    node_06.next_node = node_07
    node_07.previous_node = node_06
    node_07.next_node = node_08
    node_08.previous_node = node_07
    node_08.next_node = node_09
    node_09.previous_node = node_08

    # 将第一个结点node_01作为开始指针,将最后一个结点node_09作为结尾指针创建链表
    doubly_link_list = DoublyLinkedList(node_01, node_09)

    print(doubly_link_list.insert_at_end("blue"))
    print(doubly_link_list.remove_from_front())

    my_queue = LinkQueue(node_01, node_09)

    print(my_queue.entry_queue("lazy"))
    print(my_queue.leave_queue())
    print(my_queue.link_tail())