במדעי המחשב, מבנה נתונים הוא דרך לאיחסון נתונים במחשב. האחסון הוא בזכרון המחשב או בטבלאות בבסיסי נתונים. מבני נתונים מספקים הפשטה מסוימת של המציאות.

מקובל מגוון רחב של מבני נתונים, שכל אחד מהם מאפשר אלגוריתם יעיל לבעיה מסוימת של אחסון נתונים ואחזורם. פעמים רבות, בחירת מבנה הנתונים הנאות הוא שלב חשוב בעיצוב התוכנית. בשפות תכנות לתכנות מונחה עצמים מיוחסת חשיבות מיוחדת לתמיכה במבני נתונים.

מבני הנתונים הנפוצים הם:

• רשימה (list) - אוסף סדרתי של איברים.
  • מערך (array) - אוסף של תאים שניתן לגשת לכל אחד מהם באמצעות מספרו הסידורי.
  • רשימה מקושרת (linked list) - רשימה שבה כל איבר מצביע על האיבר הבא אחריו.
• טבלת גיבוב (Hash Table) - מערך בעל טווח אינדקסים קטן יחסית לטווח האינדקסים המקורי של הערכים שרוצים לאחסן.
• מחסנית (stack): מבנה נתונים שמזכיר מחסנית של רובה: האיבר שנכנס ראשון למחסנית יוצא ממנה אחרון (נכנס אחרון יוצא ראשון - LIFO).
• תור (queue) - מבנה נתונים שמזכיר תור של בני אדם: האיבר שנכנס ראשון לתור יוצא ממנו ראשון (נכנס ראשון יוצא ראשון - FIFO).
• דו-תור (deque) - משלב את התכונות של תור ושל מחסנית.
• גרף (graph)
  • עץ חיפוש (tree) - עץ מכוון וממוין.
    • עץ AVL - עץ חיפוש בינארי שמתקן את עצמו תוך כדי בנייה באמצעות "גלגולים" כך שגובהו יישאר נמוך יחסית למספר האיברים בו.
    • עץ אדום שחור - עץ חיפוש בינארי הבנוי לפי הגבלות מצמצות גובה הבנויות סביב הגדרת חלק מקודקודיו כאדומים וחלק כשחורים.
    • עץ B+ - עץ חיפוש שבו לכל צומת מספר גדול של בנים, כך שגובהו קטן יחסית למספר האיברים שהוא מכיל.
  • ערימה (heap) - עץ שבו כל צומת גדול (או קטן) משני בניו.

העיסוק במבני נתונים הוא חלק מהתפתחותם של מדעי המחשב בחצי השני של המאה העשרים, אך שימוש ברעיונות אלה מופיע כבר בפירוש רש"י (בראשית, כה כו) העוסק בהולדת יעקב ועשו, ובו מסביר רש"י שהרחם הוא מחסנית. בלשונו של רש"י: "צא ולמד משפופרת שפיה קצרה, תן בה שתי אבנים זו תחת זו - הנכנסת ראשונה תצא אחרונה, והנכנסת אחרונה תצא ראשונה".

קישורים חיצוניים

• קורס באלגוריתמים ומבני נתונים ב־ArsDigita (הרצאות מוקלטות וחומרים)

מבני נתונים | מדעי המחשב

Data structure | Estructura de datos | Struktura podataka | Datastruktur | Datenstruktur | Estructura de datos | Tietorakenne | Structure de données | Adatszerkezet | Struktur data | Gagnagrind | データ構造 | 자료구조 | Datastructuur | Datastruktur | Struktura danych | Estrutura de dados | Структуры данных | Údajová štruktúra | Podatkovna struktura | Datastruktur | โครงสร้างข้อมูล | Структури даних | 数据结构