แนวคิดพื้นฐานเกี่ยวกับลิสต์แบบเชิงเส้น (Linear List Concepts)

การเรียงลำดับของข้อมูลภายในลิสต์ที่มีลักษณะเป็นลำดับต่อเนื่อง สามารถอธิบายได้ โดยสมาชิก หรืออิลิเมนต์แต่ละตัวจะเชื่อมโยง
อิลิเมนต์ตัวถัดไปลักษณะเป็นรายการต่อเนื่องกันไปตัวอย่างเช่น อิลิเมนต์ ลำดับที่สองจะอยู่ถัดจากอิลิเมนต์ลำดับที่หนึ่ง หรืออิลิเมนต์ลำดับที่สามจะอยู่ถัด

จากอิลิเมนต์ตัวที่สอง ซึ่งจะลำดับเช่นนี้ไปเรื่อยๆ จนกระทั่งถึงอิลิเมนต์ลำดับที่ n+1ซึ่งจะอยู่ถัดจากอิลิเมนต์ลำดับที่ n และด้วยคุณสมบัติดังที่กล่าวมานั้นเราจึงเรียกว่าลิสต์นั่นเอง

นอกจากนี้แล้ว ลิสต์แบบเชิงเส้นยังสามารถแบ่งออกเป็น 2 ประเภทด้วยกันคือ

- ลิสต์แบบทั่วไป (General List)

ลักษณะของลิสต์แบบทั่วไป เราสามารถแทรกหรือลบรายการลิสต์ ณ ตำแหน่งใดๆก็ได้ โดยปราศจากข้อจำกัดในด้านของการดำเนินงานภายในลิสต์ นอกจากนี้แล้ว ลิสต์แบบทั่วไปยังสามารถ แบ่งออกเป็น

1. ลิสต์แบบสุ่ม (Random List) ซึ่งข้อมูลภายในลิสต์จะไม่เรียงลำดับ

2. ลิสต์แบบเรียงลำดับ (Order List) ที่ข้อมูลภายในลิสต์จะถูกจัดเรียงอย่างเหมาะสมด้วยคีย์

3. ลิสต์แบบมีข้อจำกัด (Restricted List)ข้อมูลที่อยู่ภายในลิสต์แบบมีข้อจำกัด ไม่ว่าจะเป็นการเพิ่มหรือการลบข้อมูลออกจากลิสต์จะต้องกระทำที่จุดปลายด้านใดด้านหนึ่งของลิสต์เท่านั้น เช่น ลิสต์แบบ FIFO ก็คือคิว ในขณะที่ลิสต์แบบ LIFO ก็คือสแต็ก

3.1 แนวคิดของลิสต์ลิสต์ (Linked List Concepts)

แนวคิดพื้นฐานเกี่ยวกับลิสต์แบบเชิงเส้น (Linear List Concepts)

โครงสร้างข้อมูลแบบอาร์เรย์และโครงสร้างข้อมูลแบบลิงก์ลิสต์ก็ยังสามารถนำไปพัฒนาโครงสร้างข้อมูลแบบสแต็กและคิว

ในการใช้อาร์เรย์เพื่อจัดเก็บข้อมูลแบลิสต์นั้นข้อมูลภายในหน่วยความจำจะถูกจัดเก็บเป็นลำดับต่อเนื่องกันไปซึ่งทำให้ง่ายต่อการอ้างอิงข้อมูล เพียงแค่ตำแหน่ง Bass Address ก็สามารถจัดการกับข้อมูลภายในได้แล้วแต่สำหรับลิงก์ลิสต์นั้นจะมีข้อแตกต่างตรงที่ข้อมูลภายในหน่วยความจำ จะไม่ได้อยู่ในลำดับต่อเนื่องเหมือนกับอาร์เรย์ แต่จะถูกเชื่อมโยงด้วยลิงก์หรือพอยน์เตอร์ ดังนั้นอิลิเมนต์แต่ละตัวภายในลิงก์ลิสต์จะมีการบรรจุแอดเดรสเพื่อชี้ไปยังตำแหน่งโหนดตัวถัดไป ซึ่งแต่ละโหนดก็จะบรรจุส่วนสำคัญอยู่ 2 ส่วนด้วยกันคือ

ข้อมูล (Data)

ในส่วนของข้อมูลจะมีการจัดเก็บสารสนเทศที่สามารถนำไปใช้ในการประมวลผลตามที่ต้องการต่อไป

ลิงค์ (Link)

ในส่วนของลิสต์นั้น จะใช้สำหรับเชื่อมโยงไปยังข้อมูลโดยเริ่มต้นจากเฮดพอยน์เตอร์ที่ชี้ไปยังตำแหน่งโหนดแรกของลิสต์ จากนั้นลิงก์ในแต่ละโหนดก็จะเชื่อมโยงไปยังโหนดตัวถัดไปเรื่อยๆส่วนชื่อของลิสต์จะเป็นชื่อเดียวกันกับชื่อตัวแปรพอยน์เตอร์โดยลิงก์ลิสต์อย่างง่ายที่จะกล่าวถึงต่อไปนี้คือ ซิงเกิลลิงก์ลิสต์ (Single-Linked List) ซึ่งจะมีเพียงลิงก์เดียวที่ใช้เชื่อมโยงไปยังโหนดตัวถัดไป

ตัวอย่าง การแทนลิงก์ลิสต์ในหน่วยความจำ

ที่มา : https://www.youtube.com/watch?v=XJU4KZ-CT5w