วันพฤหัสบดีที่ 18 สิงหาคม พ.ศ. 2554

การพูด

  การพูด

การพูด  มีความสำคัญต่อชีวิตมนุษย์เป็นอันมาก  ไม่ว่าจะอยู่  ณ  ที่ใด    ประกอบกิจการงานใด  หรือคบหาสมาคมกับผู้ใด  ก็ต้องสื่อสารด้วยการพูดเสมอ  จึงมักพบว่า  ผู้ที่ประสบความสำเร็จในกิจธุระการงาน   การคบหาสมาคมกับผู้อื่น  ตลอดจนการทำประโยชน์แก่สังคมส่วนรวม    ล้วนแต่เป็นคนที่มีประสิทธิภาพในการพูดทั้งสิ้นส่วนหนึ่งของการพูดสามารถสอนและฝึกได้  อาจกล่าวได้ว่า  การพูดเป็น   " ศาสตร ์"  มีหลักการ และกฎเกณฑ์เพื่อให้ผู้เรียนมีทักษะ ถึงขั้นเป็นที่พอใจอีกส่วนหนึ่งเป็นความสารถพิเศษหรือศิลปะเฉพาะตัวของผู้พูดแต่ละบุคคล  บางคนมีความสามารถที่จะตรึงผู้ฟังให้นิ่งอยู่กับที่จิตใจจดจ่ออยู่กับการฟังเรื่องที่พูด  ผู้พูดบางคนสามารถพูดให้คนฟังหัวเราะได้ตลอดเวลา  ศิลปะเฉพาะตัวนี้
            เป็นสิ่งที่ลอกเลียนกันได้ยาก  แต่อาจพัฒนาขึ้นได้ในแต่ละบุคคล  ซึ่งการพูดที่มีประสิทธิภาพเกิดจากการสังเกตวิธีการที่ดีและมีโอกาสฝึกฝน
                                ประเภทของการพูด   แบ่งได้  2  ประเภท  คือ
                        1.  การพูดระหว่างบุคคล  ได้แก่
      •     การทักทายปราศัย  ลักษณะการทักทายปราศัยที่ดีดังนี้
        • หน้าตายิ้มแย้มแจ่มใส  แสดงอาการยินดีที่ได้พบผู้ที่เราทักทาย
        • กล่าวคำปฏิสันถารที่เป็นที่ยอมรับกันในสังคม  เช่น สวัสดีครับ  สวัสดีค่ะ
        • แสดงกิริยาอาการประกอบคำปฏิสันถาร
        • ข้อความที่ใช้ประกอบการทักทายควรเป็นเรื่องที่ก่อให้เกิดความสบายใจ
      •  การแนะนำตนเอง  การแนะนำเป็นสิ่งจำเป็น และมีความในการดำเนินชีวิตประจำวัน  บุคคลอาจแนะนำตนเองในหลายโอกาสด้วยกัน การแนะนำตนเองมีหลักปฏิบัติดังนี้คือ  ต้องบอกชื่อ   นามสกุล  บอกรายละเอียดกับตัวเรา และบอกวัตถุประสงค์ในการแนะนำตัว
      •  การสนทนา   หมายถึง  การพูดคุยกัน  พูดจาเพื่อนสื่อสารแลกเปลี่ยนความรู้  ความคิด  ความรู้สึก  และประสบการณ์   การรับสารที่ง่ายที่สุ  ด    คือ  การสนทนา    
        •  คุณสมบัติของการสนทนาที่ดี  คือ
          • หน้าตายิ้มแย้มแจ่มใส
          • ใช้ถ้อยคำสำนวนภาษาที่ง่าย  ๆ  สุภาพ  คำพูดและน้ำเสียงน่าฟัง เป็นกันเองกับคู่สนทนา                                                     
                           2. การพูดในกลุ่ม                                              การพูดในกลุ่มเป็นกิจกรรมที่สำคัญในสมัยปัจจุบัน  ทั้งในชีวิตประจำวันและในการศึกษาเป็นเปิดโอกาสให้สมาชิกในกลุ่มได้ซักถาม  แสดงความคิดเห็น  หรือเกี่ยวกับเหตุการณ์ที่เกิดขึ้นแล้วมาเล่าให้ฟังกัน  มีวิธีการดังต่อไปนี้
          •  เล่าถึงเนื้อหาและประเด็นประเด็นสำคัญ ๆ  ว่ามีอะไรบ้าง
          • ภาษาที่ใช้ควรเป็นภาษาที่ง่าย
          • น้ำเสียงชัดเจนน่าฟัง  เน้นเสียงในตอนที่สำคัญ   
          • ใช้กิริยาท่าทางประกอบการเล่าเรื่องตามความเหมาะสม
          • ผู้เล่าเรื่อควรจำเรื่องไดเป็นอย่างดี
          • มีการสรุปข้อคิดในตอนท้าย

    วันจันทร์ที่ 8 สิงหาคม พ.ศ. 2554

    บทที่ 5 สแต็ก

    สแต็ก(Stack)

    ความรู้พื้นฐานเกี่ยวกับสแตก
                สแตกเป็นลิเนียร์ลิสต์ที่มีคุณสมบัติที่ว่าเมื่อทำการเพิ่มข้อมูลหรือ ลบข้อมูลในสแตก กระทำทีปลายข้างเดียวกัน ปลายข้างนั้นเรียกว่า ท๊อปของสแตก (Top Of Stack)  ซึ่งคุณสมบัติเรียกว่า ไลโฟลิสต์ (LIFO List) หรือ พูชดาวน์ลิสต์ (Pushdown List) คือสมาชิกที่เข้าลิสต์ที่หลังสุดจะได้ออกจากลิสต์ก่อน การเพิ่มข้อมูลเข้าสแตกจะเรียกว่าพูชชิ่ง (pushing) การนำข้อมูลจากสแตกเรียกว่า ป๊อปปิ้ง (poping) การเพิ่มหรือลบข้อมูลในสแตกทำที่ท๊อปของสแตก ท๊อปของสแตกนี้เองเป็นตัวชี้สมาชิกตัวท้ายสุดของสแต็ก

    การเพิ่มข้อมูลในสแตก (pushing stack)
                การเพิ่มข้อมูลเข้าสแตก หมายถึงการเพิ่มข้อมูลเข้าในสแตก โดยให้ทับบนข้อมูลสุดท้ายในสแตกจะสามารถเพิ่มเข้าได้เรื่อย ๆ จนกว่าจะเต็มสแตก ความหมายของคำว่า สแตกเต็ม คือท๊อปของสแตกชี้ที่เนื้อที่สุดท้ายของสแตกแล้ว เช่น ถ้า สแตกนั้นจองเนื้อที่ไว้ N เนื้อที่โดยที่สามารถบรรจุสมาชิกในสแตกได้ N ตัว เมื่อสแตกว่างค่าท๊อปเป็นศูนย์ เมื่อสแตกเต็มค่าท๊อปเป็น N ดังนั้นเมื่อท๊อปชี้ที่ N ก็ไม่สามารถ Push ข้อมูลลงสแตกได้อีก

                นิยาม push(S,x)
                ถ้าให้ S เป็นสแตก และ X เป็นข้อมูล ขบวนการ push (S,X) หมายถึง การ push ข้อมูล X ลงสแตก โดยการ push จะเริ่มจากสแตกว่างโดยให้ค่า  TOP เป็นศูนย์ เมื่อมีการ push ข้อมูลเข้าในสแตก ค่า Top จะเปลี่ยนเพิ่มขึ้นทีละหนึ่งทุกครั้งที่ทำการ push
                โดยสามารถเขียนขั้นตอนวิธีการ push ได้ดังนี้
    Procecdre push(var S:  stack; X : itemtype);
                Begin
                            If top > = upperbound then Writeln('Stack Full')
                            Else
                            Begin
                                        Top := top +1;
                                        S[top] := X;
                            End;
                End;


                การดึงข้อมูลจากสแตก (Popping Stack)
                การดึงข้อมูลออกจากสแตก หมายถึงการนำข้อมูลที่อยู่บนสุดในสแตกหรือที่ชี้ด้วยท๊อปออกจากสแตก จะสามารถ pop สแตกได้เรื่อย ๆ จนกว่าสแตกจะว่าง
               
    นิยาม pop(S)
    ถ้าให้ S เป็นสแตก ขบวนการ pop(S) คือการนำข้อมูลบนสุดในสแตกออกจากสแตกและให้ค่าเป็นข้อมูลที่นำออกจากสแตก ดังนั้นถ้านำคำสั่ง X= pop(S) ก็คือการนำข้อมูลที่ท๊อปของสแตกมา และใส่ค่าไว้ที่ X หรือการเซตค่า X ให้เท่ากับข้อมูลที่ดึงจากสแตก
    โดยเขียนขั้นตอนวิธีการ pop ได้ดังนี้
    Function Pop (VarS: stack) : itemtype;
                Begin
                            If empty(s) Then Writeln('Stack Empty')
                            Else Begin
                                        Pop := S[top];
                                        Top := top -1;
                                   End;
                End;

    การว่างของสแตก
    นิยาม empty(s)
    ถ้า S เป็นสแตก ขบวนการ empty(S) จะส่งผลเป็นจริง (true) เมื่อสแตกว่าง และส่งผลเป็นเท็จ (false) เมื่อสแตกไม่ว่าง

    การประยุกต์ของสแตก
    สแตกเป็นโครงสร้างข้อมูลที่มีประโยชน์มาก ถูกนำไปใช้ทั้งในซอฟท์แวร์ระบบ (System Software) และในการประยุกต์โดยยูสเซอร์ เช่น ช่วยคอมไพเลอร์ (Compiler) สร้างกฏเกณฑ์ของการโปรแกรมมิ่งเกี่ยวกับการเรียกโปรแกรมย่อย กฏเกณฑ์ของการโปรแกรมมิ่งอีกอย่างคือ คำสั่งเงื่อนไขซ้อน (Nested IF) ก็เช่นกัน สแตก ช่วยบอกว่า Else นี้คู่กับ IF ใด ซึ่งมีกฏเกณฑ์ว่า Else แรกจะคู่กับ If หลังสุด และ Else ถัดไป ก็จะคู่กับ IF ที่ถัดขึ้นไป จาก IF หลังสุด
    การแปลงนิพจน์ Infix ให้เป็น Postfix
    ผู้เขียนโปรแกรมสั่งให้เครื่องคำนวณต้องเขียนนิพจน์ที่ต้องการไปในตัวโปรแกรม ซึ่งนิพจน์เหล่านี้เรียกว่า นิพจน์ Infix คือนิพจน์ที่มีโอเปอร์เรเตอร์ (Operator) อยู่ระหว่างโอเปอร์แรนด์ (Operand) ทั้งสอง เช่น A+B เครื่องหมาย + เป็นโอเปอร์เรเตอร์ระหว่างโอเปอร์แรนด์ A และ B ซึ่งเห็นว่าเป็นนิพจน์ที่มนุษย์คุ้นเคย ข้อเสียของนิพจน์ infix ทีททำให้คอมไพเลอร์ยุ่งยาก คือลำดับความสำคัญของโอเปอร์เรเตอร์ (Precedence) ที่ต่างกัน เช่นเครื่องหมายยกกำลัง (ใช้ ^ ในการเขียนโปรแกรม) มีความสำคัญมากกว่าเครื่องหมายคูณ และหาร และเครื่องหมายคูณและหารมีความสำคัญมากกว่าเครื่องหมายบวกและลบ
             Operator  คือเครื่องหมายกระทำ + - * / ^
             Operand   คือตัวแปรต่าง ๆ A,B,C,D,E  เช่น A+B*C,(A*B)-C

          ลำดับความสำคัญ Operator
    1. เครื่องหมายยกกำลัง ^
    2. เครื่องหมายคูณกับหาร  *,/
    3. เครื่องหมายบวกกับลบ +,-
    4. เครื่องหมายวงเล็บ () กระทำก่อนเช่น A+(B*C)
    5. เครื่องหมายระดับเดียวกันไม่มีวงเล็บให้ทำจากซ้ายไปขวา เช่น A+B+C


              เมื่อการประมวลนิพจน์ infix เป็นไปด้วยความยากที่การคำนวณไม่เป็นไปตามลำดับของเครื่องหมายโอเปอร์เรเตอร์ที่มีก่อนหลัง คอมไพเลอร์จึงแปลงนิพจน์ infix ให้เป็น postfix เสียก่อน
              นิพจน์ Postfix ก็คือนิพจน์ที่มีโอเปอเรเตอร์อยู่หลังโอเปอร์แรนด์ทั้งสองของมัน เช่น
                            AB+     หมายถึง             A+B
                            AB-      หมายถึง             A-B
                            AB*      หมายถึง             A*B

    อัลกอริทึมแปลงนิพจน์ Infix ให้เป็นนิพจน์ Postfix
                เนื่องจากนิพจน์ infix มีลำดับความสำคัญของเครื่องหมายโอเปอร์เรเตอร์ซึ่งหมายความว่าโอเปอร์เรเตอร์ที่มาก่อนอาจจะไม่ใช่โอเปอร์เรเตอร์ที่ถูกประมวลผลก่อน ดังนั้น สแตกซึ่งมีคุณสมบัติเป็น LIFO List จึงมีส่วนช่วยในการแปลงนิพจน์ infix ให้เป็นนิพจน์ postfix ในการนี้มีสิ่งที่เกี่ยวข้อง 3 อย่างคือหนึ่งข้อมูลเข้ามาซึ่งเป็นนิพจน์ infix สองข้อมูลออกหรือผลลัพธ์คือนิพจน์ Postfix โดยอัลกอริทึมมีดังนี้
      1. ถ้าข้อมูลเข้า (input character) เป็นโอเปอร์แรนด์ให้พิมพ์ออกเป็นผลลัพธ์ (postfix string)
      2. ถ้าข้อมูลเข้าเป็นโอเปอร์เรเตอร์ ทำดังนี้
                1.1  ถ้าสแตกยังว่างอยู่ในpush โอเปอร์เรเตอร์ลงสแตก
                1.2  ถ้าสแตกไม่ว่างให้เปรียบเทียบ โอเปอร์เรเตอร์ที่เข้ามากับโอเปอร์เรเตอร์ที่ท๊อปของสแตก
    2.2.1ถ้าโอเปอร์เรเตอร์ที่เข้ามามี precedence น้อยกว่าหรือเท่ากับโอเปอร์เรเตอร์ที่ท๊อปของสแตก ให้ pop สแตกไปเป็นผลลัพธ์และเปรียบเทียบกับโอเปอร์เรเตอร์ที่ท๊อปของสแตกต่อไป หยุดเมื่อโอเปอร์เรเตอร์ทีเป็นข้อมูลเข้ามี precedence มากกว่าโอเปอร์เรเตอร์ ที่ท๊อปของสแตก หลังจากนั้นให้ push ข้อมูลลงสแตก
    2.2.2 ถ้าโอเปอร์เรเตอร์เข้ามี precedence มากกว่า โอเปอร์เรเตอร์ที่ท๊อปของสแตก ให้ push ลงสแตก
                      3. ถ้าข้อมูลเข้าเป็นวงเล็บเปิด ให้ push ลงสแตก
          4.ถ้าข้อมูลเข้าเป็นวงเล็บปิดให้   pop    สแตกจนกว่าจะถึงวงเล็บเปิดและนำผลที่    pop    ออกไปเป็นผลลัพธ์       โดยทิ้งวงเล็บปิดและเปิดไป
                5.  ถ้าข้อมูล หมด ให้ pop สแตกไปไว้เป็นผลลัพธ์จนสแตกว่าง
    การแปลงนิพจน์ Infix เป็น Postfix

    1. นิพจน์  A+B*C-D
    Infix                Stack                             Postfix


    A                                                 A
    +                          +                     A
    B                          +                     AB
    *                             +*                 AB

    C                           +*                 ABC

    -                              -                   ABC*+

    D                            -                   ABC*+D

    ABC*+D-

    2. นิพจน์  (A+B)*C-D
    Infix                Stack                             Postfix
    (                       (                                    
    A                      (                          A
    +                      (+                          A
    B                      (+                        AB
    )                        ( )                       AB+
    *                          *                       AB+
    C                        *                       AB+C
    -                          -                       AB+C*
    D                        -                       AB+C*D
                                       AB+C*D-

    วันจันทร์ที่ 25 กรกฎาคม พ.ศ. 2554

    บทที่ 4 ลิงค์ลิสต์

    ลิงค์ลิสต์
    วัตถุประสงค์เชิงพฤติกรรม (Behavioral Objectives)
    หลังจากศึกษาจบบทเรียนนี้แล้ว นักศึกษาจะมีความสามารถดังนี้
    (After studying this chapter, you will be able to)
    1. ศึกษาข้อมูลลิงค์ลิสต์
    2. แสดงตัวอย่างการปฏิบัติการพื้นฐานของลิงค์ลิสต์
    3. แสดงตัวอย่างลิงค์ลิสต์ทาเดียว
    4. แสดงตัวอย่างลิงค์ลิสต์วงกลม
    5. ปฏิบัติการลิงค์ลิสต์สองทาง
    6. ปฏิบัติการลิงค์ลิสต์หลายทาง
    7. จัดบอร์ดเชิงปฏิบัติการ “โครงสร้างข้อมูลลิงค์ลิสต์”
    8. สนทนาเชิงปฏิบัติการ “ลิงค์ลิสต์วงกลม”
    9. อธิบายคำศัพท์ได้ 12 คำ
    โครงสร้างข้อมูลลิ้งค์ลิสต์
                    วิธีแก้ปัญหาในการย้ายข้อมูลที่พบในการจัดเก็บที่มีรูปแบบเรียงตามลำดับ(Sequential)เปลี่ยนมาใช้รูปแบบไม่เรียงตามลำดับ (Non-sequential)ซึ่งรูปแบบการเรียงตามลำดับจะมีสมาชิกเรียงต่อเนื่องติดกันในทางตรรกะ (Logical) และทางกายภาพ(Physical) เป็นแบบเดียวกัน แต่รูปแบบไม่เรียงตามลำดับสมาชิกต่อเนื่องติดกันในทางตรรกะ ส่วนทางกายภาพไม่จำเป็นต้องเหมือนกัน โดยในทางตรรกะจะแสดงด้วยแต่ละสมาชิกมีการชี้ (Point) ต้อไปยังสมาชิกตัวถัดไป สมาชิกทุกตัวในรายการจึงถูกเชื่อมต่อ (Link) เข้าด้วยกัน ดังรูปที่ 6.1 เป็นรายการเชื่อมต่อหรือเรียกว่าลิ้งค์ลิสต์ (Linked List) มีสมาชิก N ตัว แต่ละสมาชิกเรียกว่าโหนด (Node)

                    จากรูปที่ 6.1 มีตัวแปรพอยน์เตอร์ First ชี้ไปยังโหนดแรกของรายการ แต่ละโหมดมีตัวเชื่อมเป็นพอยน์เตอร์ที่ชี้ไปยังโหนดถัดไปโดยโหนดสุดท้ายมีค่าเป็น NULL แสดงให้ทราบว่าไม่ได้ชี้ไปยังโหมดถัดไป แต่ละโหนดเป็นโครงสร้างข้อมูลเรคคอร์ด ประกอบด้วยสองส่วน คือ
                    1.ส่วนเก็บข้อมูล (Info) ใช้เก็บข้อมูลข่าวสารที่มีโครงสร้างข้อมูลเบื้องต้นหรือเรียบง่าย
                    2.ส่วนการเชื่อมต่อ (Next) เป็นตัวชี้หรือพอยน์เตอร์เก็บค่าแอดเดรสใช้อ้างไปยังโหนดถัดไปในหน่วยความจำ
                    สำหรับในทางกายภาพของลิ้งค์ลิสต์ แต่ละดหนดไม่จำเป็นต้องอยู่ติดกัน อาจกระจัดกระจายไปยู่ส่วนไหนก็ได้ในหน่วยความจำโดยมีตัวเชื่อมชี้ไปยังตัวตำแหน่งของโหนดถัดไป
                    ดังที่กล่าวในตอนต้นโครงสร้างสแตกและคิวมีการใช้อาร์เรย์ในการเก็บค่า สมาชิกทุกตัวจึงถูกจำกัดให้เป็นชนิดเดียวกัน(Homogenous) ซึ่งแก้ไขโดยเปลี่ยนมาใช้ลิ้งค์ลิสต์ที่มีโครงสร้างข้อมูลต่างกันได้ นอกจากนี้ยังมีผลดีในการปฏิบัติการแทรกข้อมูลหรือลบข้อมูล เพียงแต่ย้ายการชี้ของตัวแปรพอยน์เตอร์เท่านั้น ทำให้สมาชิกอื่นไม่มีผลกระทบ แต่ในกรณีค่าใช้จ่ายแล้วลิงค์ลิสต์จะสูงกว่าที่ต้องใช้พื้นที่เผิ่มมากขึ้นสำหรับส่วนการเชื่อมต่อเพื่อชี้ไปยังโหนดถัดไป และการค้นหาโหนดที่ต้องการใช้เวลามากเนื่องจากเป็นการค้นหาเรียงตามลำดับ (Sequential Search) ได้โหนดเดียวโดยเริ่มต้นที่โหนดแรกเสมอ

    การปฏิบัติการพื้นฐานของลิงค์ลิสต์
                    สิ่งสำคัญอย่างหนึ่งในการใช้โครงสร้างข้อมูลลิงค์ลิสต์ คือ ตัวแปรพอยน์เตอร์ (Pointer Variable) ซึ่งเก็บค่าเป็นตำแหน่งแอดเดรสในหน่วยความจำ (Memory Address) ในการปฏิบัติการกับลิ้งค์ลิสต์และให้มีความถูกต้องจะใช้ตัวแปรพอยน์เตอร์ในการจัดการเรื่องต่อไปนี้
    1.ใช้ทดสอบกับค่า NULL
    2.ใช้ทดสอบว่ามีค่าเท่ากับตัวแปรพอยน์เตอร์อื่น
    3.กำหนดให้มีค่าเป็น NULL
    4.กำหนดให้ชี้ไปยังโหนด
                    ชุดปฏิบัติการของลิ้งค์ลิสต์ที่ทกวานร่วมกับตัวแปรพอยน์เตอร์ มีดังนี้
    1.Node(P)  ส่งโหนดที่ถูกชี้ด้วยต้วแปรพอยน์เตอร์ P กลับมาให้
    2.INFO(P) ส่งค่าในส่วนเก็บข้อมูลของโหนดที่ถูกชี้ด้วยตัวแปรพอยน์เตอร์ P กลับมาให้
    3.Next(P)  ส่งพอยน์เตอร์ในส่วนการเชื่อมต่อขยองโหนดที่ถูกชี้ด้วยตัวแปรพอยน์เตอร์ P กลับมาให้
     
    การแทรกโหนดไว้ในลิ้งค์ลิสต์
                    อัลกอลิทึมในการแทรกโหนดใหม่เข้าไปไว้ในลิ้งค์ลิสต์ดังในตารางที่6.1

    ตารางที่ 6.1 อัลกอริทึมการแทรกโหนดใหม่ลงในลิ้งค์ลิสสต์

            ตัวอย่างการแทรกโหนดใหม่ไว้ในลิ้งค์ลิสต์ โดยเริ่มต้นสร้างเป็นโหนด I ในหน่วยความจำกำหนดส่วนเก็บข้อมูลมีค่า L ส่วนการเชื่อมต่อมี่ค่าเป็น NULL ซึ่งมีตัวแปรพอยน์เตอร์ New  ชี้อยู่ ดังในรูปที่ 6.2 และมีลิงค์ลิสต์ที่ต้องการแทรกโหนดใหม่เข้ามาระหว่างโหนด 2 เป็นโหนดก่อนหน้า (Predecessor) และโหนด 3 เป็นโหนดถัดไป (Successor) ดังนั้นจึงกำหนดให้ตัวแปรพอยน์เตอร์ P ชี้ไปยังโหนด 2 และขั้นตอนในการแทรกประกอบด้วย

    1. Next(New) =Next (P) กำหนดให้ตัวชี้ของโหนด I เปลี่ยนไปชี้ยังโหนด 3 ซึ่งเป็นส่วนหลังของการแทรกโหนดใหม่ ในรูปที่ 6.3






    1. Next(P) =New กำหนดให้ตัวชี้ของโหนด 2 ที่มีตัวแปรพอยน์เตอร์ P ชี้อยู่เปลี่ยนไปชี้ยังโหนด I ที่มีตัวแปรพอยน์เตอร์ New ชี้อยู่ ในรูปที่ 6.4

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

               พิจารณาจากตัวอย่างลิ้งค์ลิสต์ในรูปที่ 6.5 ต่อไปนี้ เป็นอัลกอริทึมในการลบโหนดออกจากลิ้งค์ลิสต์ โดยเริ่มต้นให้ตัวแปรพอยน์เตอร์ P ชี้ไปโหนด 2 ซึ่งเป็นโหนดก่อนหน้าโหนด 3 ที่ต้องการลบ และชั้นตอนในการลบประกอบด้วย

                 (a)       Q = Next (P) เป็นการใช้ตัวแปรพอยน์เตอร์ Q เป็นตัวช่วย กำหนดให้ชี้ไปยังโหนด 3 ที่ต้องการลบในรูปที่ 6.6
                      
    (b)     Next(P) =Next (Q)  กำหนดให้ตัวชี้ของโหนด 2 ที่มีตัวแปรพอยน์เตอร์ P ชี้อยู่เปลี่ยนไปชี้ยังโหนด 4 ซึ่งเป็นโหนดถัดไปหลังโหนดที่ตัวแปรพอยน์เตอร์ Q ชี้อยู่ ในรูปที่ 6.7
     
           (c) Free (Q) หลังจากนั้นจึงปลดปล่อยโหนดที่ต้องการลบซึ่งมีตัวพอยน์เตอร์ Q ชี้อยู่ เพื่อคืนพื้นที่หน่วยความจำของโหนดที่ลบไปและนำไปใช้กับงานอื่นได้ (Reuse)ได้เป็น
    รูปที่ 6.8

                    ลำดับการทำงานดังกล่าวจะเห็นว่ามีเพียง 2 โหนดเท่านั้นที่มาเกี่ยวข้อง คือ โหนดที่ตัวแปรพอยน์เตอร์ P และ  Q ชี้อยู่ ส่วนโหนดอื่นๆ ไม่ถูกเรียกใช้งานหรือเปลี่ยนแปลง ยกเว้นในกรณีที่ตัวแปรพอยน์เตอร์ P ชี้ไปยังโหนดสุดท้ายไม่สามารถลบโหนดถัดไปได้ ซึ่งต้องมีการไขอัลกอริทึมโดยตรวจสอบก่อนจะทำการลบ
    ลิ้งค์ลิสต์ทางเดียว
       โดยทั่งไปลิ้งค์ลิสต์จะมีโหนดที่มีส่วนการเชื่อมต่อชี้ไปยังโหนดถัดไปเพียงทางเดียว (Unidirectional)         ดังที่ผ่านมา เรียกว่าลิ้งค์ลิสต์ทางเดียว (Singly Linked List ) ซึ่งนอกจากจะมีชุดปฏิบัติการแทรกและลบโหนดแล้วยังมีอัลกอรึทึมในการจัดการลิงค์แบบอื่น ๆ ดังนี้
                    1.การค้นหาแต่ละโหนด เป็นการเริ่มต้นที่โหนดแรกจากนั้นหาไปทีละโหนดตามลำดับที่เชื่อมต่อกันจนกว่าจะพบโหนดในลิงค์ลิสต์ดังในตารางที่ 6.3
    ตารางที่ 6.3 อัลกอริทึมการวิ่งไปยังแต่ละโหนดในลิ้งค์ลิสต์

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

                    3.การแทรกโหนดที่ตอนต้นลิงค์ลิสต์ เป็นการสร้างโหนดใหม่ขึ้นมาและนำไปต่อจากโหนดสุดท้ายของลิงค์ลิสต์ (Append) โดยโหนดสุดท้ายเดิมจะชี้ไปยังโหนดใหม่ที่กลายเป็นโหนดสุดท้ายแทน ถ้าให้การลบโหนดเป็นที่โหนดแรกทำให้ลักษณะการทำงานจะเป็นแบบเดียวกับโครงสร้างข้อมูลคิว ดังรูปที่ 6.10 โดยมีตัวแปรพอยน์เตอร์ Front ชี้ที่โหนดแรกและ Rear ชี้ที่โหนดสุดท้าย จำนวนค่าสมาชิกที่ใส่ลงไปก็ไม่จำกัดเหมือนกับการใช้อาร์เรย์

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

                    ปัญหาอย่างหนึ่งของการใช้ลิงค์ลิสต์วงกลมคือการวิ่งไปแต่ละโหนดจะเป็นการวนลูปที่ไม่รู้จบ แนวทางหนึ่งในการแก้ปัญหาคือ การเพิ่มโหนดหัรายการ (Head Node) เข้ามาในตอนต้นหรือตอนท้ายลิงค์ลิสต์วงกลม ดังในรูปที่ 6.12 ซึ่งมีความแตกต่างจากโหนดอื่น ๆ ที่มีข้อมูลพิเศษหรือค่าสัญลักษณ์ (Flag) บอกให้ทราบว่าเป็นโหนดหัวรายการ

                    การวิ่งไปแต่ละโหนดจะทราบได้ว่าจุดสิ้นสุดอยู่ตรงไหนโดยใช้โหนดหัวรายการ นอกจากนี้การใช้โหนดหัวรายการ กับลิงค์ลิสต์ทางเดียวช่วยการทำงานมีประสิทธิภาพมากขึ้น เช่น ทุก ๆ โหนดในลิงค์ลิสต์จะมีโหนดก่อนหน้าเสมอ ทำให้อัลกอริทึมในการแทรกหรือลบโหนดมีความสะดวงและง่ายขึ้น เมื่อลิงค์ลิสต์วงกลมว่าง (Empty Circular Linked Lidt) จะมีเพียงโหนดหัวรายการเท่านั้นและมีพอยน์เตอร์ชี้กลับมาที่ตัวเอง ดังในรูปที่ 6.13
    ตัวอย่างการใช้ลิ้งค์ลิสต์วงกลม
                    ปัญหาโจเซฟ (Josephus Problem) เป็นที่รู้จักกันมากและนำลิงค์ลิสต์วงกลมมาใช้ในการแก้ปัญหา   เริ่มต้นเมื่อมีทหารกลุ่มหนึ่งถูกข้าศึกล้อมรอบอยู่ในเมืองซึ่งไม่สามารถต่อสูและหมดหวังที่จะชนะได้ แต่มีม้าเพียงตัวเดียวที่จะขี่พาหนีออกไปได้ กลุ่มทหารจึงตัดสินใจ เลือกคนที่โชคดีขี่ม้าหนีไปโดยการให้ทุกคนนั่งเป็นวงกลม  จากนั้นสุ่มเลือกชื่อทหารคนหนึ่งเพื่อเริ่มต้นและนับทหารทีละคนในวงกลมจนเท่ากับ  N  ก็ให้ทหารคนนั้นออกจากวงกลม  และเริ่มต้นนับแบบเดิมเมื่อถึงคนที่  N  ก็ออกจากวงกลมไปเรื่อย ๆ จนจำนวนทหารลดลงเหลือเพียงคนสุดท้ายเป็นผู้ที่ได้ขี่ม้าหนีไป  เช่น  รูปที่  6.14  มีทหารอยู่  5  คนมีการนับเพื่อคัดออกเท่ากับ  4  จากรูป  (a)  จะได้คนสุดท้ายคือคนที่เริ่มต้นนับในรูป  (e)

                   
                    ถ้าเราเป็นทหารคนหนึ่งควรจะยีนเป็นลำดับเท่าไรจึงจะเป็นคนสุดท้ายโดยมีทะหารทั้งหมด M คน และจำนวนการนับเพื่อคัดออกเท่ากับ N อัลกอริทึมในการปัญหาดังกล่าวจึงนำลิงค์ลิสต์วงกลมมาช่วยดังในตารางที่ 6.4 คือ โปรแกรม Linklist.c
    ตารางที่ 6.4 ตัวอย่างโปรแกรม LinList.c

    ลิ้งค์ลิสต์สองทาง
                    ในบางครั้งการทำงานกับลิงค์ลิสต์อาจต้องการวิ่งไปยังโหนดต่าง ๆ ในลิงค์ลิสต์โดยการถอยกลับไปยังโหนดก่อนหน้าหรือลบแต่ละโหนด เพื่อห้เกิดประสิทธิภาพจึงนำลิงค์ลิสต์สองทาง (Doubly Linked List) มาใช้แทนลิงค์ลิสต์ทางเดียว ดังในรูปที่ 6.15 ซึ่งแต่ละโหนดประกอบด้วย 3 ส่วน คือ
                    1.ส่วนเก็บข้อมูล (Info) ใช้เก็บข้อมูลข่าวสารที่มีโครงสร้างข้อมูลเบื้องต้นหรือเรียบง่าย
                    2.ส่วนการเชื่อมต่อถัดไป (Next) เป็นตัวชี้หรือพอยน์เตอร์เก็บค่าแอดเดรสใช้อ้างไปยังโหนดถัดไปในหน่วยความจำ
                    3.ส่วนการเชื่อมต่อก่อนหน้า เป็นตัวชี้หรือพอยน์เตอร์เก็บค่าแอดเดรสใช้อ้างกลับไปยังโหนดก่อนหน้าในหน่วยความจำ

                    ลิงค์ลิสต์สองทางบางครั้งเรียกว่าลิงค์ลิสต์สมมาตร (Symmetrically Linked List) เนื่องจากมีตัวชี้จากสองทิศทาง (Bidirectional) ทั้งด้านซ้ายและขวา เมื่อนำมาใช้เป็นลิงค์ลิสต์สองทางวงกลม (Circular Doubly Linked List) ได้ดังในรูปที่ 6.16 โดยอาจยกเลิกโหนดหัวรายการก็ได้

                    ในการปฏิบัติการจะชี้ไปยังโหนดถัดไปโดยใช้ Next(P) และชี้กลับไปยังโหนดก่อนหน้าโดยใช้ Prior(P) ตัวชี้ทั้งสองมักจะเป็นพอยน์เตอร์ใช้ชื่อ Right และ Left หรือใช้ s-link (Successor) และ          p-link (Predecessor) ดังนั้นเมื่อมีตัวแปรพอยน์เตอร์ p ชี้ไปยังโหนดใดจะได้ว่า
                                    Next (Prior (P)) = P = Prior (Next (P))
                    การถอยกลับไปหนึ่งโหนดและไปข้างหน้าหนึ่งโหนดก็จะกลับมายังโหนดเดิม หรือไปข้างหน้าหนึ่งโหนดและถอยกลับหนึ่งโหนดก็กลับมายังโหนดเดิมเช่นกัน สำหรับลิงค์ลิสต์สองทางว่าง (Empty Doubly Linked List) มีพอยน์เตอร์ทั้งสองชี้กลับมายังโหนดหัวรายการดังในรูปที่ 6.17 ซึ่งไม่มีโหนดอื่นอยู่ในลิงค์ลิสต์ จะได้ว่า
                                    Prior (Head) = Head = Next (Head)

    การแทรกโหนดไว้ในลิงค์ลิสต์สองทาง
                    การแทรกโหนดใหม่เข้าไปไว้ในลิงค์ลิสต์สองทางจะมีอัลกอริทึมดังในตารางที่ 6.5
    ตารางที่ 6.5 อัลกอริทึมการแทรกโหนดใหม่ลงในลิงค์ลิสต์สองทาง

                    ตัวอย่างที่ใช้จะเริ่มต้นโดยใช้โหนดใหม่ I ขึ้นในหน่วยความจำ กำหนดส่วนเก็บข้อมูลมีค่า L, ส่วนการเชื่อมต่อ Left และ Right มีค่าเป็น NULL ซึ่งเป็นตัวแปรพอยน์เตอร์ New ชี้อยู่ดังในรูปที่ 6.18 และมีลิงค์ลิสต์สองทางที่มีการแทรกโหนดใหม่เข้ามาระหว่างโหนด 2 เป็นโหนดก่อนหน้าและโหนด 3 เป็นโหนดถัดไป จึงกำหนดให้ตัวแปรพอยน์เตอร์ P ชี้ไปยังโหนด 2 และขั้นตอนในการแทรกประกอบด้วยดังต่อไปนี้

    1. Next(New) = Next(P) กำหนดให้ตัวชี้ Right ของโหนด I เปลี่ยนไปชี้ยังโหนด 3 ซึ่งเป็นส่วนหลังของการแทรกโหนดใหม่ ในรูปที่ 6.19 และ Prior(New) = P กำหนดให้ตัวชี้ Left ของโหนด I เปลี่ยนไปชี้ยังโหนด 2 ซึ่งเป็นส่วนก่อนหน้าของการแทรกโหนดใหม่

    1. Next(P) = New กำหนดให้ตัวชี้ Right ของโหนด 2 ที่มีตัวแปรพอยน์เตอร์ P ชี้อยู่เปลี่ยนไปชี้ที่โหนด I ที่มีตัวแปรพอยน์เตอร์ New ชี้อยู่ ในรูปที่ 6.20 และ Prior(P) = New กำหนดให้ตัวชี้ Left ของโหนด 3 เปลี่ยนไปชี้ยังโหนด I เช่นกัน

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

    การลบโหนดออกจากลิงค์ลิสต์สองทาง
                    อัลกอริทึมที่นำมาใช้ลบโหนดออกจากลิงค์ลิสต์ดังในตารางที่ 6.6
    ตารางที่ 6.6 อัลกอริทึมการลบโหนดออกจากลิงค์ลิสต์สองทาง

                    พิจารณาจากตัวอย่างลิงค์ลิสต์สองทางในรูปที่ 6.21 เป็นอัลกอริทึมในการลบโหนดออกจากลิงค์ลิสต์สองทาง โดยเริ่มต้นให้ตัวแปรพอยน์เตอร์ P ชี้ไปโหนด 2 ซึ่งเป็นโหนดที่ต้องการลบ และขั้นตอนการลบประกอบด้วย

    1. Next(Prior(P)) = Next(P) เป็นการใช้ตัวชี้ left ของโหนดที่ต้องการลบอ้างกลับไปยังโหนดก่อนหน้าเพื่อชี้ Right ชี้ไปยังโหนดถัดไปต่อจากโหนดที่ต้องการลบ ในรูปที่ 6.22


    1. Prior(Next(P)) = Prior(P) เป็นการใช้ตัวชี้ Right ขอองโหนดที่ต้องการลบอ้างไปยังโหนดถัดไปเพื่อสร้างตัวชี้ Left ชี้กลับไปยังโหนดก่อนหน้าโหนดที่ต้องการลบในรูปที่ 6.23

    1. Free(P) หลังจากนั้นจึงปลดปล่อยโหนดที่ต้องการลบซึ่งมีตัวแปรพอยน์เตอร์ P ชี้อยู่ เพื่อคืนพื้นที่หน่วยความจำของโหนดที่ลบไปและนำไปใช้กับงานอื่นได้ (Reuse) ได้เป็นรูปที่ 6.24

                    ลำดับการทำงานจะมี 3 โหนดที่มาเกี่ยวข้อง คือ โหนดที่ต้องการลงมีตัวแปรพอยน์เตอร์ P โหนดก่อนหน้าและโหนดถัดไป ส่วนโหนดอื่น ๆ ไม่ถูกเรียกใช้งานหรือเปลี่ยนแปลง
    ลิ้งค์ลิสต์หลายทาง
                    มีอยู่หลายกรณีที่นำลิงค์ลิสต์มาใช้งานตามความเหมาะสมซึ่งแต่ละโหนดจะถูกกำหนดให้ส่วนการเชื่อมต่อมีมากกว่าสองทางเรียกว่าลิงค์ลิสต์หลายทาง (Multi-linked List) อย่างเช่นในรูปที่ 6.25 ที่แต่ละโหนดในลิงค์ลิสต์จะมีตัวชี้สามทางโดยมีพื้นฐานเป็นลิงค์ลิสต์สองทางซึ่งมีส่วนเก็บข้อมูลคือ NameLength เก็บค่าความยาวของสตริง กับส่วนเชื่อมต่อที่เป็นตัวชี้ Right และ Left และส่วนที่เชื่อมต่อที่สาม คือ ตัวชี้ NamePtr ใช้ชี้ไปยังข้อมูลจริงอีกทีซึ่งมีโครงสร้างข้อมูลสตริงเก็บไว้ในหน่วยความจำที่ขอมาแทนการเก็บไว้ภายในโหนด

                    ลิงค์ลิสต์หลายทางจะเป็นลักษณะพื้นฐานของโครงสร้างของข้อมูลอื่นที่จะกล่าวในบทต่อ ๆ ไป เช่น ทรี (Tree) กราฟ (Graph) และนำไปใช้จัดการกับแฟ้มข้อมูล (File)