گره (علوم رایانه)

در علوم رایانه، گره (به انگلیسی: Node) رکوردی است که از یک فیلد داده و همچنین از یک یا چند فیلد که پیوندی به دیگر گره‌ها هستند، تشکیل می‌شود. فیلدهای داده و پیوند معمولاً توسط اشاره‌گرها یا مراجع پیاده‌سازی می‌شوند. هر چند که جاسازی کردن داده‌ها به شکل مستقیم در گره هم بسیار رایج است. گره‌ها برای ساختن ساختار داده‌های پیوندی و سلسله‌مراتبی مانند لیست پیوندی، درخت و گراف استفاده می‌شوند. ساختار داده‌های بزرگ و پیچیده‌تر می‌توانند از گروهی از گره‌های بهم‌پیوسته تشکیل شوند. از لحاظ مفهومی، گره‌ها مشابه راس‌های تشکیل‌دهنده یک گراف هستند.

مثال‌هایی از پیاده سازی به شبه‌کد

گره زیر از یک فیلد برای ذخیره کردن داده‌ها و از یک فیلد پیوندی به نام next تشکیل شده‌است:

 record SinglyLinkedNode {
    next, // A reference to the next node
    data // Data or reference to data
 }

فیلد پیوندی اشاره‌گری به گره بعدی است. سه نمونه از چنین گرهی تشکیل یک لیست پیوندی را می‌دهند:

گره زیر شامل دو فیلد پیوندی است:

 record DoublyLinkedNode {
    previous, // A reference to the previous node
    next, // A reference to the next node
    data // Data or reference to data
 }

سه نمونه از گره بالا تشکیل یک لیست دوپیوندی با طول ۳ را می‌دهند:

همچنین یک پیاده‌سازی رایج دیگر گرهی با دو اشاره‌گر به فرزندهای چپ و راست و همچنین اشاره‌گری به گره والد است:

 record BinaryNode {
    parent, // A reference to the parent node                                
    left_child, // A reference to the left child node
    right_child, // A reference to the right child node
    data // Data or reference to data
 }

منابع