ลิงค์ลิสต์แบบสองทิศทาง

ลิงค์ลิสต์แบบสองทิศทาง (Doubly Linked List)

ได้เป็นโครงสร้างของข้อมูลไว้ในnodeเป็นลำดับ โดยแต่ละnodeจะประกอบไปด้วยข้อมูลและpointer 2ตัว ชี้ไปยังnode ถัดไปและอีกหนึ่งตัวชี้ไปยังnodeถัดไปและอีกหนึ่งตัวชี้ไปยังnodeก่อนหน้า ยกเว้นnodeแรกที่Pointer สำหรับชี้ไปnode ก่อนหน้าจะชี้ไปที่nullและnode สุดท้ายที่pointer สำหรับชี้ไปnodeถัดไปจะชี้ไปที่null ถ้านํา node มาเรียงต่อๆกัน เป็นลำดับจะได้doubly linked list ของข้อมูล n ตัวโดยจะกำหนดให้มี pointer อย่างน้อย1ตัวที่ชี้ไปยังnodeตัวแรกของdoubly linkedlist เสมอ

ส่วนประกอบ

1. ส่วนเก็บข้อมูล (data) ใช้เก็บข้อมูลข่าวสารที่มีโครงสร้างข้อมูลเบื้องต้นหรือเรียบง่าย
2. ส่วนการเชื่อมต่อถัดไป (Next) เป็นตัวชี้หรือพอยน์เตอร์เก็บค่าแอดเดรสใช้อ้างไปยังโหนดถัดไปในหน่วยความจำ
3. ส่วนการเชื่อมต่อก่อนหน้า เป็นตัวชี้หรือพอยน์เตอร์เก็บค่าแอดเดรสใช้อ้างกลับไปยังโหนดก่อนหน้าในหน่วยความจำ(Prev)

doubly linked lists

class Node:

   # Constructor to create a new node
   def __init__(self, data):
       self.data = data
       self.next = None
       self.prev = None      
    # Class to create a Doubly Linked List

class DoublyLinkedList:

   # Constructor for empty Doubly Linked List
   def __init__(self):
       self.head = None

การเพิ่มnode

2.1 การเพิ่มnode ข้างหน้า

def push(self, new_data):
       new_node = Node(new_data)
       new_node.next = self.head
       if self.head is not None:
           self.head.prev = new_node
       self.head = new_node

2.1 การเพิ่มnode ข้างหลัง

def append(self, new_data):
       new_node = Node(new_data)
       new_node.next = None
       if self.head is None:
           new_node.prev = None
           self.head = new_node
           return
       last = self.head
       while(last.next is not None):
           last = last.next
       last.next = new_node
       new_node.prev = last
       return

การลบnode

def delete(self, valueToDelete):
       currentNode = self.head
       previousNode = None
       while currentNode is not None:
           if currentNode.data == valueToDelete:
               if previousNode is None: 
                   newHead = currentNode.next
                   currentNode.next = None
                   return newHead # Deleted the head
               previousNode.next= currentNode.next
               return self.head
           previousNode = currentNode
           currentNode = currentNode.next
       return self.head# Value to delete was not found.

การค้นหาnode

def search(self,data):
       node = self.head
       while (node and node.data != data):
           node = node.next
           return None
       return node.data 

การแสดงผล

def printList(self):
       output = '['
       currentNode = self.head
       while currentNode is not None:
           output += str(currentNode.data)
           currentNode = currentNode.next
           if currentNode is not None:
               output += ', '
       output += ']'
       return output

See also

• [[1]]
• [[2]]