二十五岁时我们都一样愚蠢、多愁善感,喜欢故弄玄虚,可如果不那样的话,五十岁时也就不会如此明智。
标题:Python - 高级链表
在前面的章节中我们已经看到了链接列表,但它只能在前面进行介绍。在本章中,我们看到另一种链接列表,其中可以前进和后退。这样一个链表被称为双链表。以下是双向链表的特点。
- 双链表包含称为第一个和最后一个的链接元素。
- 每个链接都有一个数据字段和两个称为next和prev的链接字段。
- 每个链接都使用其下一个链接与其下一个链接链接。
- 每个链接都使用其上一个链接与之前的链接链接。
- 最后一个链接将链接作为空来标记列表的结尾。
创建双向链表
我们使用Node类创建一个双链表。现在我们使用与单链表中相同的方法,但是除了存在于节点中的数据之外,头指针和下一个指针将用于正确分配以在每个节点中创建两个链接。
class Node: def __init__(self, data): self.data = data self.next = None self.prev = None class doubly_linked_list: def __init__(self): self.head = None # Adding data elements def push(self, NewVal): NewNode = Node(NewVal) NewNode.next = self.head if self.head is not None: self.head.prev = NewNode self.head = NewNode # Print the Doubly Linked list def listprint(self, node): while (node is not None): print(node.data), last = node node = node.next dllist = doubly_linked_list() dllist.push(12) dllist.push(8) dllist.push(62) dllist.listprint(dllist.head)当上面的代码被执行时,它会产生以下结果 -
62 8 12插入双链表中
在这里我们将看到如何使用以下程序将节点插入到双向链接列表中。该程序使用一个名为插入的menthod,它将新节点插入到双向链表头部的第三个位置。
# Create the Node class class Node: def __init__(self, data): self.data = data self.next = None self.prev = None # Create the doubly linked list class doubly_linked_list: def __init__(self): self.head = None # Define the push method to add elements def push(self, NewVal): NewNode = Node(NewVal) NewNode.next = self.head if self.head is not None: self.head.prev = NewNode self.head = NewNode # Define the insert method to insert the element def insert(self, prev_node, NewVal): if prev_node is None: return NewNode = Node(NewVal) NewNode.next = prev_node.next prev_node.next = NewNode NewNode.prev = prev_node if NewNode.next is not None: NewNode.next.prev = NewNode # Define the method to print the linked list def listprint(self, node): while (node is not None): print(node.data), last = node node = node.next dllist = doubly_linked_list() dllist.push(12) dllist.push(8) dllist.push(62) dllist.insert(dllist.head.next, 13) dllist.listprint(dllist.head)当上面的代码被执行时,它会产生以下结果 -
62 8 13 12附加到双向链表
追加到双向链表将在最后添加元素。
# Create the node class class Node: def __init__(self, data): self.data = data self.next = None self.prev = None # Create the doubly linked list class class doubly_linked_list: def __init__(self): self.head = None # Define the push method to add elements at the begining def push(self, NewVal): NewNode = Node(NewVal) NewNode.next = self.head if self.head is not None: self.head.prev = NewNode self.head = NewNode # Define the append method to add elements at the end def append(self, NewVal): NewNode = Node(NewVal) NewNode.next = None if self.head is None: NewNode.prev = None self.head = NewNode return last = self.head while (last.next is not None): last = last.next last.next = NewNode NewNode.prev = last return # Define the method to print def listprint(self, node): while (node is not None): print(node.data), last = node node = node.next dllist = doubly_linked_list() dllist.push(12) dllist.append(9) dllist.push(8) dllist.push(62) dllist.append(45) dllist.listprint(dllist.head)当上面的代码被执行时,它会产生以下结果 -
62 8 12 9 45请注意元素9和45在追加操作中的位置。