รายการโยงแบบเดี่ยวในภาษาลิสป์

Vee Satayamas
Mar 19, 2016 · 1 min read

วันก่อนผมคิดว่า John McCarthy ทำไมไม่ใช้แถวลำดับเป็นหลัก พอเขียนโปรแกรมในภาษาลิสป์มาได้สักพักผมก็ได้คำตอบแล้วแต่ก็ไม่แน่ว่าจะถูกผิดแค่ไหน

ผมนึกเอาว่าเขาน่าจะออกแบบลิสป์มาสำหรับการใช้ฟังก์ชันเวียนบังเกิดโดยที่ไม่ต้องไปเปลี่ยนแปลงข้อมูลในโครงสร้างที่มีอยู่แล้ว และไม่ต้องสำเนาข้อมูลใหม่ทั้งหมด

แถวลำดับสมาชิกตัวถัดไปก็คือข้อมูลที่อยู่ติดกัน

การจะแทรกข้อมูลเข้าไปก็ต้องแทรกไปถ้าไม่ไปแก้ไขแถวลำดับเดิม ไม่ก็ต้องสร้างแถวลำดับขึ้นมาใหม่เลย

ไม่เหมือนรายการโยงแบบเดี่ยวที่ว่าไม่ต้องยุ่งกับรายการเก่าเลย เพียงแต่สร้างสมาชิกใหม่ที่ชี้ไปที่รายการเก่าก็พอ

รายการโยงแบบโยงสองทางก็ทำแบบนี้ไม่ได้ เพราะรายการเก่าจะต้องชี้มาที่สมาชิกใหม่ด้วยทำให้ต้องไปแก้รายการเก่าอีก

ในภาษาลิสป์เพิ่มสมาชิกใหม่ในรายการแบบในรูปภาพใช้คำสั่ง (cons “donkey” existing-list) ผลที่ได้จากคำสั่งนี้เอาคืนค่าของฟังก์ชันได้เลย ฟังก์ชันแบบเวียนบังเกิดหลายครั้งถูกอะไรใช้แทนการวนซ้ำ ดังนั้นฟังก์ชันก็จะถูกเรียกบ่อย ๆ การสำเนาข้อมูลทั้งชุดบ่อย ๆ จึงไม่มีประสิทธิภาพ

โดยสรุปแล้ว รายการโยงแบบเดี่ยวช่วยให้เขียนโปรแกรมแบบไม่ต้องแก้ไขโครงสร้างเดิมและไม่ต้องสำเนามาใหม่ทั้งหมด ดังนั้นรายการโยงแบบเดี่ยวเหมาะที่จะใช้กับฟังก์ชันเวียนบังเกิดที่มันจะถูกเรียกบ่อย ๆ มาก

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store