Python - รายการที่เชื่อมโยงขั้นสูง
เราได้เห็นรายการที่เชื่อมโยงแล้วในบทก่อนหน้าซึ่งเป็นไปได้ที่จะเดินทางไปข้างหน้าเท่านั้น ในบทนี้เราจะเห็นรายการที่เชื่อมโยงอีกประเภทหนึ่งซึ่งสามารถเดินทางได้ทั้งไปข้างหน้าและข้างหลัง รายการที่เชื่อมโยงดังกล่าวเรียกว่ารายการที่เชื่อมโยงเป็นทวีคูณ ต่อไปนี้เป็นคุณสมบัติของรายการที่เชื่อมโยงแบบทวีคูณ
- รายการที่เชื่อมโยงแบบทวีคูณประกอบด้วยองค์ประกอบลิงก์ที่เรียกว่ารายการแรกและรายการสุดท้าย
- แต่ละลิงก์มีฟิลด์ข้อมูลและฟิลด์ลิงก์สองฟิลด์ที่เรียกว่าถัดไปและก่อนหน้า
- แต่ละลิงค์เชื่อมโยงกับลิงค์ถัดไปโดยใช้ลิงค์ถัดไป
- แต่ละลิงค์เชื่อมโยงกับลิงค์ก่อนหน้าโดยใช้ลิงค์ก่อนหน้า
- ลิงก์สุดท้ายมีลิงก์เป็นโมฆะเพื่อทำเครื่องหมายจุดสิ้นสุดของรายการ
การสร้างรายการที่เชื่อมโยงแบบทวีคูณ
เราสร้างรายการที่เชื่อมโยงแบบทวีคูณโดยใช้คลาสโหนด ตอนนี้เราใช้แนวทางเดียวกับที่ใช้ใน Singly Linked List แต่ตัวชี้และตัวชี้ถัดไปจะใช้สำหรับการกำหนดที่เหมาะสมเพื่อสร้างลิงก์สองลิงก์ในแต่ละโหนดนอกเหนือจากข้อมูลที่มีอยู่ในโหนด
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
การแทรกลงในรายการที่เชื่อมโยงเป็นทวีคูณ
ที่นี่เราจะดูวิธีการแทรกโหนดไปยัง Doubly Link List โดยใช้โปรแกรมต่อไปนี้ โปรแกรมใช้คำแนะนำที่มีชื่อแทรกซึ่งแทรกโหนดใหม่ที่ตำแหน่งที่สามจากส่วนหัวของรายการที่เชื่อมโยงแบบทวีคูณ
# 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 สำหรับการดำเนินการผนวก