ในวิทยาการคอมพิวเตอร์โครงสร้างข้อมูลคือวิธีการจัดระเบียบและจัดเก็บข้อมูลซึ่งมักถูกเลือกเพื่อให้เข้าถึงข้อมูลได้อย่างมีประสิทธิภาพ^{[ 1 ] [ 2 ] [ 3 ]}กล่าวโดยละเอียด โครงสร้างข้อมูลคือการนำประเภทข้อมูล ไปใช้ในเชิงกายภาพ รวมถึงข้อกำหนดของการจัดระเบียบข้อมูลและรูปแบบการจัดเก็บข้อมูล ตลอดจนฟังก์ชันหรือการดำเนินการสำหรับการทำงานกับข้อมูลนี้ โครงสร้างข้อมูลมีความเกี่ยวข้องอย่างใกล้ชิดกับประเภทข้อมูลนามธรรม (ADT) ^{[ 4 ]}โครงสร้างข้อมูลอธิบายถึงการแสดงข้อมูลในหน่วยความจำและวิธีการดำเนินการ ในขณะที่ ADT อธิบายถึงรูปแบบเชิงตรรกะหรือโครงสร้างพีชคณิตของประเภทข้อมูล—การดำเนินการใดบ้างที่ได้รับอนุญาตและผลลัพธ์ที่ได้—โดยไม่กล่าวถึงวิธีการนำการดำเนินการเหล่านั้นไปใช้^{[ 4 ]}ผู้เขียนบางคนไม่ใช้คำว่า "ประเภทข้อมูลนามธรรม" และอ้างถึงรูปแบบเชิงตรรกะและเชิงกายภาพของโครงสร้างข้อมูลโดยตรง^{[ 5 ]}

โครงสร้างข้อมูลที่มีประสิทธิภาพเป็นสิ่งจำเป็นสำหรับการจัดการชุดข้อมูลขนาดใหญ่และเป็นพื้นฐานในการออกแบบอัลกอริทึม ฐานข้อมูลเชิง สัมพันธ์ มักใช้ ดัชนี B-treeสำหรับการดึงข้อมูล^{[ 6 ]}ในขณะที่การใช้งานคอมไพเลอร์มักใช้ตารางแฮชเพื่อค้นหาตัวระบุ [ ^{7 ] ระบบ}ไฟล์และเครื่องมือค้นหาใช้โครงสร้างข้อมูลเฉพาะทางอย่างกว้างขวาง^{[ 8 ] [ 9 ]} Rob Pikeกล่าวว่าการเลือกโครงสร้างข้อมูลเกือบจะมีผลกระทบต่อประสิทธิภาพมากกว่าการเลือกอัลกอริทึมเสมอ เนื่องจากอัลกอริทึมมักจะชัดเจนในตัวเอง^{[ 10 ]}โครงสร้างข้อมูลใช้เพื่อจัดระเบียบข้อมูลทั้งในหน่วยความจำหลัก ( RAM ) และหน่วยเก็บข้อมูลรอง (เช่น ดิสก์) ^{[ 11 ]}

การนำโครงสร้างข้อมูลไปใช้เกี่ยวข้องกับการเขียนชุดซับรูทีนเช่น การแทรก การลบ การท่องไป หรือการค้นหา ซึ่งจะสร้างและจัดการอินสแตนซ์ของโครงสร้างนั้น โครงสร้างข้อมูลสามารถนำไปใช้ได้โดยใช้ภาษาและเทคนิคการเขียนโปรแกรมที่หลากหลาย โครงสร้างข้อมูลจะสอดคล้องกับการนำไปใช้ที่เป็นรูปธรรมเพียงอย่างเดียวโดยตรง ซึ่งแตกต่างจาก ADT ที่อธิบายพฤติกรรมและการดำเนินการโดยไม่ขึ้นอยู่กับการนำไปใช้ใดๆ อาจมีโครงสร้างข้อมูลที่เป็นรูปธรรมหลายแบบสำหรับ ADT เดียวกัน ตัวอย่างเช่น รายการเชื่อมโยงหรืออาร์เรย์ที่ปรับขนาดได้สำหรับ ADT รายการ^{[ 12 ]}ด้วยเหตุนี้ ประสิทธิภาพของโครงสร้างข้อมูลจึงเชื่อมโยงอย่างใกล้ชิดกับการนำไปใช้ที่เป็นรูปธรรม และต้องได้รับการประเมินผ่านเกณฑ์มาตรฐานและการจำลองเชิงทฤษฎี^{[ 13 ]}

โดยทั่วไปแล้วโครงสร้างข้อมูลจะอาศัยความสามารถของคอมพิวเตอร์ในการจัดเก็บและเข้าถึงข้อมูลผ่านที่อยู่หน่วยความจำ (ตามที่ระบุโดยตัวชี้ — สตริงบิต —หรือโดยนามธรรมมากขึ้นผ่านการอ้างอิง ) ซึ่งสามารถจัดเก็บไว้ในหน่วยความจำและจัดการโดยโปรแกรมได้ ตัวอย่างเช่นอาร์เรย์และเรคอร์ดจะจัดเก็บองค์ประกอบในตำแหน่งหน่วยความจำที่ต่อเนื่องกัน ซึ่งต้องใช้โครงสร้างที่ตายตัว แต่ช่วยให้เข้าถึงดัชนีได้อย่างรวดเร็วโดยการคำนวณที่อยู่ผ่านการดำเนินการทางคณิตศาสตร์ในทางตรงกันข้ามโครงสร้างข้อมูลที่เชื่อมโยง (เช่น รายการเชื่อมโยงและต้นไม้) จะจัดเก็บที่อยู่ขององค์ประกอบที่เกี่ยวข้องไว้ภายในโครงสร้าง ทำให้สามารถใช้หน่วยความจำได้อย่างยืดหยุ่นและปรับขนาดได้แบบไดนามิก วิธีการจัดโครงสร้างข้อมูลที่แตกต่างกันเหล่านี้มีข้อดีข้อเสียที่แตกต่างกันและเหมาะสมกับงานที่แตกต่างกัน ตัวอย่างเช่น การจัดสรรหน่วยความจำที่ต่อเนื่องกันในอาร์เรย์ช่วยให้เข้าถึงและแก้ไขข้อมูลได้อย่างรวดเร็ว ส่งผลให้ประสิทธิภาพดีขึ้นในสถานการณ์การประมวลผลข้อมูลแบบลำดับ^{[ 14 ]}

มีโครงสร้างข้อมูลหลายประเภท โดยทั่วไปสร้างขึ้นจากประเภทข้อมูลพื้นฐาน ที่เรียบง่ายกว่า ตัวอย่างที่รู้จักกันดีได้แก่: ^{[ 15 ]}

• อาร์เรย์ คือกลุ่มขององค์ประกอบที่เรียงลำดับอย่างเฉพาะเจาะจง โดยทั่วไปแล้วจะ เป็นชนิดข้อมูลเดียวกันทั้งหมด (ขึ้นอยู่กับภาษาโปรแกรม องค์ประกอบแต่ละตัวอาจถูกบังคับให้เป็นชนิดข้อมูลเดียวกันทั้งหมด หรืออาจเป็นชนิดข้อมูลใดก็ได้) การเข้าถึงองค์ประกอบทำได้โดยใช้ดัชนีจำนวนเต็มเพื่อระบุว่าต้องการเรียกใช้องค์ประกอบใด โดยทั่วไปแล้ว การใช้งานจะจัดสรรหน่วยความจำที่ต่อเนื่องกันสำหรับองค์ประกอบของอาร์เรย์ (แต่ไม่จำเป็นเสมอไป) อาร์เรย์อาจมีขนาดคงที่หรือปรับขนาดได้
• รายการเชื่อมโยง (หรือเรียกสั้น ๆ ว่ารายการ ) คือชุดข้อมูลเชิงเส้นขององค์ประกอบข้อมูลใด ๆ ก็ได้ ซึ่งเรียกว่าโหนด โดยแต่ละโหนดจะมีค่าของตัวเอง และชี้ไปยังโหนดถัดไปในรายการเชื่อมโยง ข้อได้เปรียบหลักของรายการเชื่อมโยงเมื่อเทียบกับอาร์เรย์คือ สามารถแทรกและลบค่าได้อย่างมีประสิทธิภาพเสมอโดยไม่ต้องย้ายส่วนที่เหลือของรายการ อย่างไรก็ตาม การดำเนินการอื่น ๆ เช่นการเข้าถึงองค์ประกอบใดองค์ประกอบหนึ่งแบบสุ่มจะช้ากว่าในรายการเมื่อเทียบกับอาร์เรย์
• เรคอร์ด (เรียกอีกอย่างว่าทูเพิลหรือสตรัค ) เป็น โครงสร้าง ข้อมูลแบบรวมเรคอร์ดคือค่าที่ประกอบด้วยค่าอื่นๆ โดยทั่วไปจะมีจำนวนและลำดับที่แน่นอน และโดยทั่วไปจะจัดทำดัชนีด้วยชื่อ องค์ประกอบของเรคอร์ดมักเรียกว่าฟิลด์หรือสมาชิกในบริบทของการเขียนโปรแกรมเชิงวัตถุเรคอร์ดจะเรียกว่าโครงสร้างข้อมูลแบบธรรมดาเพื่อแยกความแตกต่างจากวัตถุ^{[ 16 ]}
• ตารางแฮชหรือที่รู้จักกันในชื่อแผนที่แฮช เป็นโครงสร้างข้อมูลที่ช่วยให้ดึงค่าได้อย่างรวดเร็วโดยใช้คีย์ โดยใช้ฟังก์ชันแฮชเพื่อแมปคีย์ไปยังดัชนีในอาร์เรย์ ทำให้สามารถเข้าถึงข้อมูลได้ในเวลาคงที่โดยเฉลี่ย ตารางแฮชมักใช้ในพจนานุกรม แคช และการจัดทำดัชนีฐานข้อมูล อย่างไรก็ตาม อาจเกิดการชนกันของแฮช ซึ่งอาจส่งผลกระทบต่อประสิทธิภาพ จึงมีการใช้เทคนิคต่างๆ เช่น การเชื่อมโยงและการกำหนดแอดเดรสแบบเปิด เพื่อจัดการกับการชนกันของแฮช
• กราฟคือกลุ่มของจุดเชื่อมต่อด้วยเส้นเชื่อม ซึ่งแสดงถึงความสัมพันธ์ระหว่างสิ่งต่างๆ กราฟสามารถใช้ในการจำลองเครือข่ายสังคม เครือข่ายคอมพิวเตอร์ และเครือข่ายการขนส่ง เป็นต้น กราฟประกอบด้วยจุดยอด (โหนด) และเส้นเชื่อม (การเชื่อมต่อระหว่างโหนด) กราฟอาจเป็นกราฟแบบมีทิศทางหรือไม่มีทิศทาง และอาจมีวงจรหรือไม่มีวงจรก็ได้ อัลกอริทึมการสำรวจกราฟ ได้แก่ การค้นหาแบบกว้าง (breadth-first search) และการค้นหาแบบลึก (depth-first search)
• สแต็กและคิวเป็นชนิดข้อมูลนามธรรมที่สามารถนำไปใช้ได้โดยใช้อาร์เรย์หรือลิสต์เชื่อมโยง สแต็กมีสองการดำเนินการหลัก ได้แก่ พุช (เพิ่มองค์ประกอบลงไปที่ด้านบนสุดของสแต็ก) และป๊อป (ลบองค์ประกอบที่อยู่บนสุดออกจากสแต็ก) ซึ่งเป็นไปตามหลักการเข้าหลังออกก่อน (LIFO) คิวมีสองการดำเนินการหลัก ได้แก่ เอนคิว (เพิ่มองค์ประกอบลงไปที่ด้านหลังของคิว) และดีคิว (ลบองค์ประกอบออกจากด้านหน้าของคิว) ซึ่งเป็นไปตามหลักการเข้าก่อนออกก่อน (FIFO)
• โครงสร้างข้อมูลแบบ ต้นไม้แสดงถึงการจัดระเบียบแบบลำดับชั้นขององค์ประกอบ ต้นไม้ประกอบด้วยโหนดที่เชื่อมต่อกันด้วยขอบ โดยมีโหนดหนึ่งเป็นราก และโหนดอื่นๆ ทั้งหมดเป็นต้นไม้ย่อย โครงสร้างข้อมูลแบบต้นไม้ถูกนำไปใช้กันอย่างแพร่หลายในอัลกอริธึมและสถานการณ์การจัดเก็บข้อมูลต่างๆต้นไม้ไบนารี (โดยเฉพาะฮีป ) ต้นไม้ AVLและต้นไม้ Bเป็นตัวอย่างของต้นไม้ที่นิยมใช้กัน ต้นไม้เหล่านี้ช่วยให้การค้นหา การจัดเรียง และการแสดงข้อมูลแบบลำดับชั้นมีประสิทธิภาพและเหมาะสมที่สุด
• โครงสร้างข้อมูลแบบ ไทร(Trie)หรือต้นไม้คำนำหน้า (Prefix Tree) เป็นต้นไม้ชนิดพิเศษที่ใช้ในการดึงข้อมูลสตริงอย่างมีประสิทธิภาพ ในโครงสร้างไทร แต่ละโหนดจะแทนอักขระหนึ่งตัวในสตริง และเส้นเชื่อมระหว่างโหนดจะแทนอักขระที่เชื่อมต่อกัน โครงสร้างนี้มีประโยชน์อย่างยิ่งสำหรับงานต่างๆ เช่น การเติมข้อความอัตโนมัติ การตรวจสอบการสะกดคำ และการสร้างพจนานุกรม ไทรช่วยให้ค้นหาและดำเนินการต่างๆ ได้อย่างรวดเร็วโดยอิงจากคำนำหน้าของสตริง

ภาษาแอสเซมบลีส่วนใหญ่ และ ภาษาระดับต่ำบาง ภาษา เช่นBCPL (Basic Combined Programming Language) ขาดการสนับสนุนโครงสร้างข้อมูลในตัว ในทางกลับกันภาษาโปรแกรมระดับสูง หลายภาษา และภาษาแอสเซมบลีระดับสูงบางภาษา เช่นMASMมีไวยากรณ์พิเศษหรือการสนับสนุนในตัวอื่นๆ สำหรับโครงสร้างข้อมูลบางอย่าง เช่น เรคอร์ดและอาร์เรย์ ตัวอย่างเช่น ภาษาC (ซึ่งเป็นทายาทโดยตรงของ BCPL) และ ภาษา Pascalรองรับโครงสร้าง และเรคอร์ดตามลำดับ นอกเหนือจากเวกเตอร์ ( อาร์เรย์หนึ่งมิติ) และอาร์เรย์หลายมิติ^{[ 17 ] [ 18 ]}

ภาษาโปรแกรมส่วนใหญ่มีกลไก ไลบรารีบางอย่างที่ช่วยให้สามารถนำการใช้งานโครงสร้างข้อมูลไปใช้ซ้ำได้ในโปรแกรมต่างๆ ภาษาโปรแกรมสมัยใหม่มักมาพร้อมกับไลบรารีมาตรฐานที่ใช้งานโครงสร้างข้อมูลที่ใช้กันทั่วไป ตัวอย่างเช่นไลบรารีเทมเพลตมาตรฐานของ C++ , เฟรมเวิร์กคอลเลกชันของ Javaและเฟรมเวิร์ก .NETของ Microsoft

ภาษาโปรแกรมสมัยใหม่โดยทั่วไปยังสนับสนุนการเขียนโปรแกรมแบบโมดูลาร์ซึ่งเป็นการแยกส่วนระหว่างอินเทอร์เฟซของโมดูลไลบรารีและการใช้งานภายใน บางภาษามีชนิดข้อมูลแบบทึบแสงที่ช่วยให้ผู้ใช้สามารถซ่อนรายละเอียดการใช้งานภายในได้ภาษาโปรแกรมเชิงวัตถุเช่นC++ , JavaและSmalltalkมักใช้คลาสเพื่อจุดประสงค์นี้

โครงสร้างข้อมูลที่เป็นที่รู้จักจำนวนมากมี เวอร์ชัน แบบขนานซึ่งอนุญาตให้เธรดการคำนวณหลายเธรดเข้าถึงอินสแตนซ์เฉพาะของโครงสร้างข้อมูลพร้อมกันได้^{[ 19 ]}

• ปีเตอร์ บราส, โครงสร้างข้อมูลขั้นสูง , สำนักพิมพ์มหาวิทยาลัยเคมบริดจ์ , 2008, ISBN 978-0521880374
• Donald Knuth , ศิลปะแห่งการเขียนโปรแกรมคอมพิวเตอร์ , เล่ม 1. Addison-Wesley , ฉบับพิมพ์ครั้งที่ 3, 1997, ISBN 978-0201896831
• Dinesh Mehta และSartaj Sahni , คู่มือโครงสร้างข้อมูลและการประยุกต์ใช้ , Chapman and Hall / CRC Press , 2004, ISBN 1584884355
• นิคเลาส์ เวิร์ธ , อัลกอริทึมและโครงสร้างข้อมูล , เพรนทิส ฮอลล์ , 1985, ISBN 978-0130220059

• โครงสร้างข้อมูลแบบเปิด โดย แพท โมริน
• GH GonnetและR. Baeza-Yates , คู่มืออัลกอริทึมและโครงสร้างข้อมูล - ในภาษาปาสคาลและซี , ฉบับพิมพ์ครั้งที่สอง, Addison-Wesley, 1991, ISBN 0-201-41607-7
• Ellis Horowitzและ Sartaj Sahni, พื้นฐานของโครงสร้างข้อมูลในภาษาปาสคาล , สำนักพิมพ์ Computer Science Press , 1984, ISBN 0-914894-94-3

• คำอธิบายจากพจนานุกรมอัลกอริทึมและโครงสร้างข้อมูล
• หลักสูตรโครงสร้างข้อมูล
• การวิเคราะห์โครงสร้างข้อมูลจากมุมมองของ .NET
• ชาฟเฟอร์, ซี. โครงสร้างข้อมูลและการวิเคราะห์อัลกอริทึม