algorithm

บทที่ 1

การเขียนโปรแกรม

Data Type  : ชนิดของข้อมูล

1.ข้อมูลชนิดตัวอักษร  (Character) คือ ข้อมูลที่เป็นรหัสแทนตัวอักษรหรือค่าจำนวนเต็ม ได้แก่ ตัวอักษร ตัวเลขและกลุ่ม

ตัวอักขระพิเศษใช้พื้นที่ในการเก็บข้อมูล 1 ไบต์

2.ข้อมูลชนิดจำนวนเต็ม (Integer) คือ ข้อมูลที่เป็นเลขจำนวนเต็ม ได้แก่ จำนวนเต็มบวก จำนวนเต็มลบ และศูนย์ 

ข้อมูลชนิดจำนวนเต็มใช้พื้นที่ในการเก็บข้อมูล ขนาด 2 ไบต์

3.ข้อมูลชนิดจำนวนเต็มที่มีขนาด 2 เท่า (Long Integer)  คือ ข้อมูลที่เป็นเลขจำนวนเต็ม ใช้พื้นที่ในการเก็บเป็น 2 เท่าของ Integer 

คือมีขนาด 4 ไบต ์

4.ข้อมูลชนิดเลขทศนิยม (Float) คือ ข้อมูลที่เป็นเลขทศนิยม ขนาด 4 ไบต์

5.ข้อมูลชนิดเลขทศนิยมอย่างละเอียด (Double)  คือ ข้อมูลที่เป็นเลขทศนิยม ใช้พื้นที่ในการเก็บข้อมูลเป็น 2 เท่าของ

float คือมีขนาด 8 ไบต์ 

ผังงาน (Flowchart)

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

ประโยชน์ของผังงาน

-ช่วยลำดับขั้นตอนการทำงานของโปรแกรม และสามารถนำไปเขียนโปรแกรมได้โดยไม่สับสน

-ช่วยใดข้อผิดพลาด

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

-ช่วยให้ผู้อื่นสามารถศึกษาการทำงานของโปรแกรมได้อย่างง่าย และรวดเร็วมากขึ้น

วิธีการเขียนผังงานที่ดี

-ใช้สัญลักษณ์ตามที่กำหนดไว้

-ใช้ลูกศรแสดงทิศทางการไหลของข้อมูลจากบนลงล่าง หรือจากซ้ายไปขวา

-คำอธิบายในภาพควรสั้นกระทัดรัด และเข้าใจง่าย

-ทุกแผนภาพต้องมีลูกศรแสดงทิศทางเข้า - ออก

-ไม่ควรโยงเส้นเชื่อมผังงานที่อยู่ไกลมาก ๆ ควรใช้สัญลักษณ์จุดเชื่อมต่อแทน

-ผังงานควรมีการทดสอบความถูกต้องของการทำงานก่อนนำไปเขียนโปรแกรม

ผังงานโปรแกรม

-จุดเริ่มต้น / สิ้นสุดของโปรแกรม

-ลูกศรแสดงทิศทางการทำงานของโปรแกรมและการไหลของข้อมูล

-ใช้แสดงคำสั่งในการประมวลผล หรือการกำหนดค่าข้อมูลให้กับตัวแปร

-แสดงการอ่านข้อมูลจากหน่วยเก็บข้อมูลสำรองเข้าสู่หน่วยความจำหลักภายในเครื่องหรือการแสดงผลลัพธ์จากการประมวลผลออกมา

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

-แสดงผลหรือรายงานที่ถูกสร้างออกมา

-แสดงจุดเชื่อมต่อของผังงานภายใน หรือเป็นที่บรรจบของเส้นหลายเส้นที่มาจากหลายทิศทางเพื่อจะไปสู่การทำงานอย่างใดอย่างหนึ่งที่เหมือนกัน

-การขึ้นหน้าใหม่ ในกรณีที่ผังงานมีความยาวเกินกว่าที่จะแสดงพอในหนึ่งหน้า 

สัญลักษณ์ในการเขียนผังงาน

การเขียนผังงาน (Flowchart) มี 3 แบบ 

1. ผังงานแบบเรียงลำดับ  (Sequemce Flowchart) 

เป็นการเขียนผังงานแบบง่ายที่สุด ทำงานจากบนลงล่าง ตามลูกศร

2. ผังงานแบบมีทางเลือกหรือแบบมีเงื่อนไข   (Selectiom or Condition Flowchart)  

คือตรวจสอบเงื่อนไขถ้าเป็นจริง ก็ทำงานตามเงื่อนไขที่เป็นจริง ถ้าเป็นเท็จก็ทำตามเงื่อนไขที่เป็นเท็จ

กรณี 1 ทางเลือก

3.รหัสจำลองที่เรียกว่า การเขียนซูโดโค้ด (Pseudo Code) คือการเขียนคำอธิบายขั้นตอนการทำงานของโปรแกรม  โดยใช้ถ้อยคำผสมระหว่างภาษาอังกฤษและภาษาการเขียนโปรแกรมแบบโครงสร้าง  ซึ่งจะช่วยให้ผู้เขียนโปรแกรมสามารถพัฒนาขั้นตอนต่าง ๆ  ให้เป็นโปรแกรมได้ง่ายขึ้น  ส่วนใหญ่มักใช้คำเฉพาะ  (Reserve Word)  ที่มีในภาษาการเขียนโปรแกรมและมักเขียนด้วยตัวอักษรตัวใหญ่  ซูโดโค้ดที่ดี  จะต้องมีความชัดเจน  สั้น  และได้ใจความ  ข้อมูลต่าง ๆ  ที่ใช้จะถูกเขียนอยู่ในรูปของตัวแปร

รูปแบบ Algorithm  <ชื่อของอัลกอริทึม>

START

1……………………………….

2……………………………….

3…………………………………

END

linked-list

บทที่ 3

linked-list

โครงสร้างข้อมูล link list

จากการทำงานของโครงสร้างข้อมูลอาร์เรย์ (Array Structure) , โครงสร้างข้อมูลสแตก (Stack Structure) และโครงสร้างข้อมูลคิว (Queue Structure) มีลักษณะการจัดเก็บข้อมูลและการเข้าถึงข้อมูลในโครงสร้างแบบลำดับเป็นพื้นที่ต่อเนื่องกัน  การใช้งานของโครงสร้างถูกจำกัดไว้ไม่สามารถทำการปรับเปลี่ยนหรือแก้ไขขนาดของโครงสร้างได้ หรือหากต้องการปรับเปลี่ยนโครงสร้างใหม่ จะทำให้เสียเวลาในการประมวลผล ซึ่งในการใช้งานโปรแกรมพื้นที่หน่วยความจำ (Memory) เป็นสิ่งจำเป็นมาก การแก้ไขปัญหาดังกล่าว โดยใช้โครงสร้างข้อมูลแบบอื่น ๆ เป็นสิ่งจำเป็นที่ต้องพิจารณาและยากมาก

•          เป็นการจัดเก็บชุดข้อมูลเชื่อมโยงต่อเนื่องกันไปตามลำดับ โครงสร้างข้อมูลแบบลิงค์ลิสต์จะประกอบไปด้วยส่วนที่เรียกว่า สมาชิก ( Node) ส่วน เก็บข้อมูล (Data) และตำแหน่งของสมาชิกตัวถัดไป (Link)

List

•          สร้างลิสต์แบบง่ายมี 2 วิธี

1)    Array

2)    2) Link List

แนะนำ Linked List

Array

  0          1          2         3          4

Data     Next

   Node

ปัญหาของตัวแปรแบบ Array

1. ตัวแปรแบบ Array มีการจองเนื้อที่ที่อยู่ติดกันตามจำนวนที่ต้องการไว้ก่อน เช่น ถ้าต้องการจัดเก็บข้อมูลจำนวน 10,000 ค่า แต่ละค่าใช้เนื้อที่ 2 byte เนื้อที่ทั้งหมดที่ถูกจองจะเป็น 20,000 byte ซึ่งบางครั้งอาจจะไม่มีเนื้อที่ว่างที่อยู่ติดกันเพียงพอสำหรับเก็บข้อมูล 20,000 byte ทำให้โปรแกรมไม่สามารถทำงานได้

1. บางกรณีจองเนื้อที่ไว้สำหรับเก็บข้อมูล 10,000 ค่า เนื่องจากไม่ทราบจำนวนข้อมูลที่ต้องการเก็บ แต่เมื่อใช้งานจริง เก็บข้อมูลเพียง 2,000 ค่า ทำให้เหลือเนื้อที่ที่ยังไม่ได้ใช้ แต่ไม่สามารถนำไปใช้งานอื่นได้
2. กรณีจองเนื้อที่ไว้สำหรับเก็บข้อมูล 10,000 ค่า แต่การใช้งานจริงมีข้อมูลที่ต้องเก็บมากกว่า 10,000 ค่า ก็ไม่สามารถเก็บข้อมูลส่วนที่เหลือได้ เนื่องจากจองไว้แค่ไหน ก็ใช้ได้แค่นั้น

คุณสมบัติของลิงค์

•          ลิงค์ลิสต์จะใช้เฮดพอยน์เตอร์ (pHead)เป็นตัวชี้ไปยังโหนดแรกของลิสต์ ในขณะที่พอยน์เตอร์หรือลิงค์ของแต่ละโหนดก็จะเชื่อมโยงลิงค์ไปยังโหนดตัวถัดไปโดยโหนดตัวสุดท้ายที่ไม่มีลิงค์ให้เชื่อมต่อจะถูกกำหนดค่าให้เป็น null ซึ่งในที่นี้ใช้สัญลักษณ์               แทน

•          โหนดของข้อข้อมูลจะประกอบไปด้วย Data และ Link โดย

–        Data คือข้อมูลหรือสารสนเทศที่สามารถนำไปใช้ประโยชน์

–        Link คือตัวชี้หรือพอยน์เตอร์ที่ใช้สำหรับเชื่อมโยงไปยังโหนดถัดไป

•          ไม่มีความสัมพันธ์ทางการภาพระหว่างโหนด

•          ข้อมูลที่จัดเก็บภายในหน่วยความจำไม่จำเป็นต้องอยู่ติดกัน

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

•          ขนาดของหน่วยความจำที่ใช้เท่ากับข้อมูลที่จัดเก็บ คือ หน่วยความจำที่ใช้งานจะพอดีกับข้อมูลเพราะไม่ได้ระบุขนาดไว้ก่อนจำทำให้ไม่มีหน่วยความจำที่จองไว้เหลือเหมือนการใช้อาร์เรย์

•          กรณีที่เฮดพอยน์เตอร์ไม่มีตัวชี้หรือไม่มีสมาชิก เฮดพอยน์เตอร์จะถูกกำหนดค่าเป็น null ซึ่งหมายถึงลิสต์ว่างนั่นเอง

ไม่มีความสัมพันธ์ทางการภาพระหว่างโหนด

โครงสร้างข้อมูลแบบลิงค์ลิสต์ประกอบด้วยโหนดต่างๆต่อกันโดยแต่ละโหนดมีส่วนที่สำคัญ 2 ส่วนคือ ส่วนที่เก็บข้อมูล (Data) และ ส่วนที่เก็บตัวชี้ (Pointer)

data                        pointer

25

x

                            data                                 pointer                 

Andaman

45.5

38.7

5

ข้อดีของลิงค์ลิสต์

•       เป็นโครงสร้างที่ง่ายต่อการเพิ่มหรือลบข้อมูล

•       ไม่จำเป็นต้องขยับอิลิเมนต์ของลิสต์ไปข้างหน้าเพื่อให้เกิดพื้นที่ว่าง ในกรณีที่มีการลบอิลิเมนต์ตรงส่วนหน้าหรือส่วนกลางของลิสต์เช่นเดียวกับอาร์เรย์

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

•       เป็นโครงสร้างที่ง่ายต่อการเพิ่มหรือลบข้อมูล

•       ไม่จำเป็นต้องขยับอิลิเมนต์ของลิสต์ไปข้างหน้าเพื่อให้เกิดพื้นที่ว่าง ในกรณีที่มีการลบอิลิเมนต์ตรงส่วนหน้าหรือส่วนกลางของลิสต์เช่นเดียวกับอาร์เรย์

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

•       ตัวชี้ (Pointer) บางครั้งเรียก ลิงค์ (Link) หรือ ตัวอ้างอิง (Reference) คือ การกำหนดตัวแปร (Variable) เพื่อเก็บตำแหน่งของตัวแปรอื่นๆ หรือโครงสร้างข้อมูลอื่น ๆ ที่ใช้อยู่ในโปรแกรม

พื้นฐานที่กำกับ linked-list

•          การท่องเข้าไปในลิงค์ลิสต์

•          การเพิ่มข้อมูลลงในลิงค์ลิสต์

•          การลบข้อมูลออกจากลิงค์ลิสต์

•          การทำให้ลิสต์ว่างเปล่า

        ลักษณะของการเก็บข้อมูลและเชื่อมโยงโหนดอื่น ๆ ของลิงค์ลิสต์ เริ่มจากจุดเริ่มต้นของโครงสร้าง (Start Pointer) ซึ่งเป็นตัวแปรที่ทำหน้าที่เก็บตำแหน่งของข้อมูลที่อยู่โหนดแรกในโครงสร้างชี้ไปยังโครงสร้างข้อมูลชุดถัดไป และในโครงสร้างชุดดังกล่าวนี้ก็มี Pointer ชี้ไปยังโครงสร้างข้อมูลอื่น ๆ ต่อไปในลักษณะเดียว ส่วน Pointer ในโหนดสุดท้ายจะเก็บค่า NULL (ค่าว่าง) บางครั้งแทนตำแหน่งสุดท้ายในโครงสร้างด้วยสัญลักษณ์ทางไฟฟ้า เรียกว่า ground symbol  เป็นการแสดงตำแหน่งสุดท้ายในโครงสร้าง หรือ

Storage Pool

                Storage Pool หรือ Free List  หมายถึง  เนื้อที่ว่างในหน่วยความจำ มีลักษณะเป็นโหนดเก็บอยู่ในโครงสร้างข้อมูลลิงค์ลิสต์  หรืออาจเรียกได้ว่าเป็น Free  Stack  ลักษณะการดำเนินการเหมือนกับโครงสร้างข้อมูลสแต็ก                              เมื่อมีการเพิ่มสมาชิกใหม่ในโครงสร้างข้อมูลลิงค์ลิสต์จะนำโหนดว่าง 1 โหนดออกมาจาก Free List (เป็นโหนดแรกใน Free List) จากนั้นใส่ข้อมูลลงไปในส่วนของ Data Field หลังจากนั้น นำโหนดดังกล่าวเชื่อมโยงเข้าไปไว้ในโครงสร้างข้อมูลที่ต้องการ และหากมีการลบสมาชิกตัวใดตัวหนึ่งออกจากโครงสร้างจะต้องนำโหนดที่ถูกลบนี้ใส่คืนใน Free List ไว้เป็นโหนดแรกใน  Free  List  เสมอ

การเข้าถึงข้อมูลภายในโครงสร้างลิงค์ลิสต์

                การเข้าถึงข้อมูลภายในโครงสร้างลิงค์ลิสต์ จะต้องอาศัยพอยน์เตอร์

เป็นตัวเข้าไปในโครงสร้าง สมมติให้พอยน์เตอร์ดังกล่าว คือ PTR  และทำหน้า

ที่ชี้ตำแหน่งแอดเดรสของโหนดในโครงสร้าง เมื่อต้องการไปยังโหนดถัดไปก็ให้

ทำการเลื่อนตำแหน่งของพอยน์เตอร์  โดยตำแหน่งของโหนดถัดไปได้จากส่วน

ของ  LINK  ในโหนดปัจจุบัน

                การเข้าถึงในโครงสร้างเรียกว่า การทำ Traversing มีขั้นตอนดังต่อไปนี้

               

                กำหนดให้ DATA เป็นโครงสร้างข้อมูลลิงค์ลิสต์   และพอยน์เตอร์  PTR 

                ทำหน้าที่ชี้โหนดที่กำลังดำเนินการ  Process  อยู่ในขณะนั้น  (Current Node)

                1. กำหนดค่าเริ่มต้นให้กับพอยน์เตอร์  PTR.

                2. การวนรอบดำเนินการ   Process  ข้อมูล

                3. Apply Process to DATA [PTR]

                4. เปลี่ยนค่าพอยน์เตอร์  PTR ให้ชี้โหนดถัดไป

                5. เสร็จสิ้นขั้นตอน

การเพิ่มข้อมูลในโครงสร้าง

                เมื่อกำหนดโครงสร้างข้อมูลเรียบร้อยแล้ว ก็สามารถทำการเพิ่มข้อมูลในโครงสร้างได้   โดยการขอโหนดว่างจาก   free  list  และนำมาเชื่อมโยงกับรายการข้อมูลที่มีอยู่เดิมในโครงสร้างตรงตำแหน่งที่ต้องการ

                การเพิ่มข้อมูลในโครงสร้างข้อมูลลิงค์ลิสต์ อาจเกิดในลักษณะที่ต่างกัน ซึ่งสรุปได้เป็น 3 ลักษณะ  คือ

1. การเพิ่มข้อมูลที่จุดเริ่มต้นของโครงสร้าง

                2. การเพิ่มข้อมูลต่อจากโหนดที่กำหนด

                3. การเพิ่มข้อมูลที่จุดสุดท้ายของโครงสร้าง

•          การเพิ่มข้อมูลลงในลิงค์ลิสต์

–        เพิ่มที่ส่วนต้นของลิสต์

–        เพิ่มที่ส่วนท้ายของลิสต์

–        แทรกเข้าไปในลิสต์

•          การเพิ่มข้อมูลที่จุดเริ่มต้นของโครงสร้าง

เป็นการเพิ่มโหนดของข้อมูลไปยังตำแหน่งแรกของโครงสร้างลิงค์ลิสต์ โดยการเปลี่ยนค่าเริ่มต้นให้ชี้ไปยังตำแหน่งของโหนดใหม่ (NEW Node) ที่สร้างขึ้น และให้ Pointer ของโหนดใหม่ชี้ไปยังตำแหน่งเริ่มต้นเดิมแทน

•          ขั้นตอนการเพิ่มข้อมูลที่ตำแหน่งเริ่มต้นของโครงสร้าง

                1. ตรวจสอบ OVERFLOW  ถ้าโหนดใหม่มีค่าเป็น NULL แสดงว่า OVERFLOW

                2. กำหนด PTR ให้ชี้ไปที่โหนดของ FREE  LIST

                3.ใส่ข้อมูลใหม่ลงไปในโหนดใหม่

                4.ให้โหนดใหม่ชี้ไปยังโหนดเริ่มต้นเดิมและเปลี่ยนตำแหน่งเริ่มต้นให้ชี้ไปยังโหนดใหม่

•          การเพิ่มข้อมูลลงในลิงค์ลิสต์

–        แทรกเข้าไปในลิสต์

การเพิ่มข้อมูลต่อจากโหนดที่กำหนด

                เป็นการแทรกโหนดข้อมูลใหม่เข้าไประหว่างโหนดข้อมูล 2 โหนด โดยการเปลี่ยน Pionter ที่ชี้โหนดเก่าให้ชี้ไปยังตำแหน่งของโหนดใหม่ และ ให้ Poinnter ของโหนดใหม่ขี้ไปยังตำแหน่งเดิมแทน

•          ขันตอนการเพิ่มข้อมูลที่ตำแหน่งโหนดที่กำหนดของโครงสร้าง

                1. ตรวจสอบ OVERFLOW  ถ้าโหนดใหม่มีค่าเป็น NULL แสดงว่า OVERFLOW

                2. กำหนด PTR ให้ชี้ไปที่โหนดของ FREE  LIST

                3. ใส่ข้อมูลใหม่ลงไปในโหนดใหม่

                4. กำหนดค่าให้โหนดแรก ถ้า PTR = NULL ให้กำหนดโหนดใหม่เป็นจุดเริ่มต้น ถ้า PTR <> NULL  ให้นำโหนดใหม่มาต่อ

(PTR ชี้ไปที่โหนดใหม่)

•          การเพิ่มข้อมูลลงในลิงค์ลิสต์

–        เพิ่มที่ส่วนท้ายของลิสต์

การเพิ่มข้อมูลต่อจากโหนดที่กำหนด

                เป็นการแทรกโหนดข้อมูลใหม่เข้าไประหว่างโหนดข้อมูล 2 โหนด โดยการเปลี่ยน Pionter ที่ชี้โหนดเก่าให้ชี้ไปยังตำแหน่งของโหนดใหม่ และ ให้ Poinnter ของโหนดใหม่ขี้ไปยังตำแหน่งเดิมแทน

•          ขั้นตอนการเพิ่มข้อมูลที่ตำแหน่งโหนดที่กำหนดของโครงสร้าง

                1. ตรวจสอบ OVERFLOW  ถ้าโหนดใหม่มีค่าเป็น NULL แสดงว่า OVERFLOW

                2. กำหนด PTR ให้ชี้ไปที่โหนดของ FREE  LIST

                3. ใส่ข้อมูลใหม่ลงไปในโหนดใหม่

                4. กำหนดค่าให้โหนดแรก ถ้า PTR = NULL ให้กำหนดโหนดใหม่เป็นจุดเริ่มต้น ถ้า PTR <> NULL  ให้นำโหนดใหม่มาต่อ

(PTR ชี้ไปที่โหนดใหม่)

การท่องเข้าไปในลิงค์ลิสต์

การเพิ่มข้อมูลลงในลิงค์ลิสต์

การลบข้อมูลออกจากลิงค์ลิสต์

การทำให้ลิสต์ว่างเปล่า

การลบข้อมูลจากโครงสร้าง

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

                การลบข้อมูลออกจากโครงสร้างลิงค์ลิสต์ เกิดขึ้นได้หลายลักษณะสรุปได้ดังนี้

                1. การลบโหนดแรก

                2. การลบโหนดที่อยู่หลังโหนดที่กำหนด

                3. การลบโหนดสุดท้าย

•          ขั้นตอนการลบโหนดมีดังนี้

                1. เก็บค่าตำแหน่งและค่าของ Pointer ของโหนดที่ต้องการล

                2. กำหนดค่าของ Pointer ของโหนดที่ต้องการลบ ไปยังโหนดก่อนหน้านั้น

                3. กำหนดตำแหน่งของโหนดที่ต้องการลบคืนกลับไปยัง Storage Pool

•          ประเภทของโครงสร้างข้อมูลลิงค์ลิสต์

                โครงสร้างข้อมูลลิงค์ลิสต์  แบ่งเป็น  2  กลุ่มใหญ่ ๆ  ได้แก่

                1. โครงสร้างข้อมูลลิงค์ลิสต์เดี่ยว  (Singly Linked List : SLL)

                2. โครงสร้างข้อมูลลิงค์ลิสต์คู่  (Doubly Linked List : DLL)

•          โครงสร้างข้อมูลลิงค์ลิสต์คู่  (Doubly Linked List)

                โครงสร้างข้อมูลลิงค์ลิสต์คู่  (Doubly Linked List) เป็นโครงสร้างที่แต่ละโหนดข้อมูลสามารถชี้ตำแหน่งโหนดข้อมูลถัดไปได้ 2 ทิศทาง (มีพอยน์เตอร์ชี้ตำแหน่งอยู่สองทิศทาง) โดยมีพอยน์เตอร์อยู่ 2 ตัว คือ  พอยน์เตอร์ LLINK  ทำหน้าที่ชี้ไปยังโหนดด้านซ้ายของโหนดข้อมูลนั้น ๆ และ พอยน์เตอร์ RLINK ทำหน้าที่ชี้ไปยังโหนดด้านขวาของโหนดข้อมูลนั้น ๆ

                การใช้งานของโหนดข้อมูลแบบลิงค์ลิสต์คู่ คือ พอยน์เตอร์ LLINK  จะชี้ไปยังโหนดด้านซ้ายของโหนดข้อมูลนั้น ๆ โดยพอย์เตอร์ที่โหนดข้อมูลสุดท้ายทางด้านซ้าย (LLINK ตัวสุดท้าย) จะมีค่าเป็น NULL และ พอยน์เตอร์ RLINK ทำหน้าที่ชี้ไปยังโหนดด้านขวาของโหนดข้อมูลนั้น ๆ โดยพอย์เตอร์ที่โหนดข้อมูลสุดท้ายทางด้านขวา (RLINK ตัวสุดท้าย) จะมีค่าเป็น NULL เช่นกัน

·         ชนิดของโครงสร้างข้อมูลลิงค์ลิสต์แบบ  Doubly Linked List

                แบ่งออกเป็น 2 แบบ คือ

                1. โครงสร้างข้อมูลลิงค์ลิสต์แบบ  Ordinary  Doubly  Linked List(ODLL)

                2. โครงสร้างข้อมูลลิงค์ลิสต์แบบ  Circularly  Doubly Linked List            

       (CDLL)

                โครงสร้างข้อมูลลิงค์ลิสต์แบบ Ordinary DLL คือ ลักษณะของโครงสร้างลิงค์ลิสต์ที่ส่วนของพอยน์เตอร์ที่ link ทางซ้าย (LLINK) ของโหนดซ้ายมือสุดและพอยน์เตอร์ที่ link ทางด้านขวาสุดของโครงสร้าง (RLINK)  มีค่าเป็น NULL ทั้งคู่  เพื่อแสดงว่าเป็นโหนดสุดท้ายของโครงสร้างที่ปลายทั้งสองด้าน

ขั้นตอนการเพิ่มโหนดข้อมูลมีดังนี้

                1. ตรวจสอบว่า โหนด n เป็นโหนดว่างหรือไม่  (ถ้าโหนด n มีค่าเป็น NULL แสดงว่าเป็นโหนดว่าง)

                2. ถ้าโหนด n ไม่เป็นโหนดว่าง ให้กำหนดพอยน์เตอร์ของ n

                n -> r  =  p -> r

                n -> l = q -> l

3. กำหนดพอยน์เตอร์  p -> r ให้เป็นตำแหน่งของโหนด n

4. กำหนดพอยน์เตอร์  q -> l ให้เป็นตำแหน่งของโหนด n

                5. ใส่ข้อมูลลงไปในโหนด n

ขั้นตอนการลบโหนดมีดังนี้

                1. ตรวจสอบว่ามีข้อมูลหรือไม่  (ถ้าโหนด r และ l มีค่าเป็น start แสดงว่าไม่มีข้อมูล)

                2. ถ้ามีข้อมูล ให้กำหนดพอยน์เตอร์ของ p และ q

                p -> r  =  d -> r

                q -> l = d -> l

                3. คืนโหนดที่ลบให้กับระบบ

                โครงสร้างข้อมูลลิงค์ลิสต์แบบ Circularly DLL คือ  ลักษณะของ Doubly linked list ที่มี Link ทางซ้าย  (LLINK) ของโหนดซ้ายมือสุดเก็บตำแหน่งที่อยู่ของโหนดที่อยู่ทางขวามือสุดและ Link ทางด้านขวา (RLINK) ของโหนดขวามือสุดก็จะเก็บตำแหน่งที่อยู่ของโหนดที่อยู่ทางซ้ายมือสุด