Queue

โครงสร้างข้อมูลแบบ Queue
        โครงสร้าง  Queue เป็น list ของ Element (รายการ) ที่มีการเพิ่ม 1 ทางและลบข้อมูลออก 1 ทางมีคุณสมบัติที่เข้าก่อนออกก่อน FIFO (First in First out) 
การสร้าง Queue
        ในการสร้าง Queue สามารถจัดเก็บได้หลายลักษณะ แต่ทั่วไปจะใช้การเก็บแบบ list ทางเดียวหรือArray แบบต่อเนื่องโดยต้องใช้ pointer อีก 2 ตัว ชื่อว่า F (front pointer) เป็นตัวชี้ที่เก็บตำแหน่งส่วนหน้า และ R (rear pointer) เป็นตัวชี้ที่เก็บตำแหน่งส่วนท้าย โดยข้อมูลจะเข้าไปทาง rear หรือส่วนท้ายและจะออกจาก Queue ทาง front หรือส่วนหน้าการดำเนินงานของคิว(Queue Operations)            1. ฟังก์ชั่น Enqueue         ฟังก์ชั่น Enqueue เป็นการนำข้อมูลเพิ่มเข้าไปในคิว โดยหลังจากที่ข้อมูลได้เพิ่มเข้าไปในคิวแล้วสมาชิกใหม่ที่เพิ่มเข้าไปจะนำไป ต่อจากส่วน Rear  ซึ่งการเพิ่มข้อมูลเข้าไปในคิวก็ไม่ได้แตกต่างไปจากสแต็กตรงที่จะต้องมี พื้นที่ว่างพอที่จะใส่สมาชิกใหม่เข้าไป  ดังนั้นหากมีพื้นที่ไม่เพียงพอต่อการเพิ่มสมาชิกใหม่เข้าไปในคิวก็จะเกิด สถานะ Overflow          2.ฟังก์ชั่น Dequeue        ฟังก์ชั่น Dequeue เป็นการลบข้อมูลออกจากคิว โดยข้อมูลที่อยู่ส่วน Front จะถูกคืนค่าส่งไปยังยูสเซอร์หรือโมดูลที่เรียกใช้จากนั้นก็จะนำข้อมูลนี้ออก จากคิวในกรณีที่มีการเรียกใช้ฟังก์ชั่นนี้และหากภายในคิวไม่มีข้อมูล ก็จะทำให้เกิดสถานะ Underflow          3.ฟังก์ชั่น Queue Front        ฟังก์ชั่น Queue Front ข้อมูลที่อยู่ส่วน Front นั้น สามารถดึงขึ้นมาใช้งานได้ด้วยฟังก์ชั่น Queue Frontฟังก์ชั่นดังกล่าวจะทำการคืนค่าข้อมูลกลับไปยังผู้เรียกใช้โดยไม่มีการ เปลี่ยนแปลงใด ๆ ในคิวอย่างไรก็ตามหากในคิวว่างเปล่า และมีการเรียกใช้งานฟังก์ชั่นนี้  ก็จะทำให้เกิดสถานะของข้อผิดพลาดที่เรียกว่าUnderflow 
คิว (Queue) เป็นโครงสร้างข้อมูลที่รู้จักและนำมาใช้งานมากเช่นเดียวกับสแตก (Stack) และมีลักษณะเป็นรายการในแนวเชิงเส้น (Linear List) เช่นกัน มีข้อกำหนดให้ชุดปฏิบัติการสามารถเพิ่มค่าเข้าไปในตอนท้ายของรายการเพียงด้านเดียว เรียกว่า ส่วนหลัง (Rear) และลบค่าในตอนต้นของรายการเพียงด้านเดียว เรียกว่าส่วนหน้า (Front) ซึ่งกำหนดคิวเป็นรูปแบบดังนี้
    Q = [Q1, Q2, . . .  , QT]
                โดย Front (Q) คือ Q1 และ Rear (Q) คือ QT มีจำนานสมาชิกในคิวเท่ากับ T ดังในรูปที่ 5.1 โดยลักษณะมีตัวชี้ส่วนหน้าอยู่ด้านซ้ายและตัวชี้ด้านท้ายอยู่ด้านขวา และอาจกลับด้านกันก็ได้ให้ตัวชี้ส่วนหน้าอยู่ด้านขวาและตัวชี้ส่วนท้ายอยู่ด้านซ้าย
              
 

                       Front                                                                                                 Rear
รูปที่ 5.1 ตัวอย่างลักษณะของคิวที่มีตัวชี้ส่วนหน้าอยู่ด้านซ้ายและตัวชี้ส่วนท้ายอยู่ด้านขวา
                สมาชิก Q1 จะเข้ามาก่อนสมาชิก QJ สำหรับ I < J   และ QI ซึ่งอยู่ในคิวนานที่สุดและถูกลบออกจากคิวก่อนสมาชิกที่เข้ามาหลัง
                ลักษณะของคิวถูกนำมาใช้แก้ไขปัญหาต่างๆในแอปพลิเคชั่นต่างๆ เช่น จำลอง (Simulation) การทำงานของระบบจริงในกิจกรรมแบบเข้าก่อนออกก่อน เช่น การเข้าแถวเพื่อนซื้อของหรือชำระเงินเพื่อตรวจสอบการให้บริการเพียงพอหรือไม่ การนำคิวไปใช้ในการสำรวจพิจารณา (Observation) ตามปริมาณรถติดเพื่อควบคุมไฟจราจรตามทางแยก การนำหลักการของคิว (Queuing Theory) มาใช้ เช่น การส่งข้อมูลข่าวสารในเครือข่าย การส่งแฟ้มข้อมูลไปยังพริ้นเตอร์เพื่อพิมพ์งานตามลำดับคิว หรือรูปแบบการสลับตู้รถไฟบนราง ดังในรูปที่ 5.2

การพูดในที่ชุมนุมชน

เทคนิคการพูดในที่ชุมนุมชน
การพูดในที่ชุมนุม คือ การสนทนาที่ได้ขยายขอบเขตให้กว้างขึ้น
 เป็นการสื่อสารอย่างมีจุดมุ้งหมาย

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

วิธีการพูดในที่ชุมชน

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

การระงับการประหม่าตื่นเต้น
1. การเตรียมตัวที่ดี : การคิด การอ่าน การพูด ฝึกซ้อมเตรียมตัวมาเป็นอย่างดี
(ควรมีการเตรียมข้อมูลอย่างน้อย 2 สัปดาห์)
2. บอกตัวเองว่า การตื่นเต้นไม่ได้เกิดกับเราเพียงคนเดียว
3. บอกตัวเองว่า นี้คือส่วนหนึ่งของการเล่นเกมส์ เพราะต้องเผชิญกับสภาวะ
การถูกทดสอบว่า
เราเล่นสำเร็จหรือไม่
4. มองภาพคนฟังทุกคนให้เป็นมิตรอย่างสม่ำเสมอ ส่วนมากคนพูดที่เกิด
อาการประหม่า เพราะกลัวคนฟัง
5. มีสมาธิ ไม่วอกแว่กเอาใจใส่กับเนื้อหาสาระที่พูด
6. การผ่อนคลาย ความเครียด ในขณะรอพูด จงบอกตัวเองว่า 
"ทำใจให้สบาย เราทำได้"
ให้พูดออกไปด้วยความมั่นใจ เพราะเราพูดในสิ่งที่คนอื่นไม่รู้ 
แต่เราทำมากับมือ
7. เรามักถามตัวเองเสมอว่า "นี้เราจะทำสำเร็จหรือไม่"
" เราจะทำได้ " ขอให้ท่านลงมือทำ และทำให้ดีที่สุด เท่าความสามารถที่มี
8. ขอให้ก้าวออกมาเริ่มต้นครั้งแรก และจะพัฒนาได้ในครั้งต่อๆ ไป
(ประสบการณ์ คือบทเรียน)

ลักษณะการพูดที่ดี
1. ออกเสียงให้ชัดเจน
-คำที่นำมาใช้ต้องการความหมาย
ภาษาอังกฤษต้องแปล
-วรรคตอนดี ถูกต้อง
-อักษรควบกล้ำ
-วางหัวข้อก่อน-หลังให้ชัดเจน
-น้ำหนักของเสียง (อันไหนเน้นต้องเน้น)

2. ความถูกต้องแม่นยำ
-ตรวจสอบข้อมูลของผู้ฟังให้ถูกต้องก่อนพูด
-ไม่ควรใช้ำคำย่อ เช่น พ.ศ., กกต. ฯลฯ
-ข้อมูลตรงกับความจริง

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

นักพูดที่ดี
1. มีสมาธิ เอาใจใส่ต่อสิ่งที่กำลังทำอยู่
2. มีความกระฉับกระเฉง สนใจสิ่งต่างๆ รอบๆ ตัว กระตือรือล้น มีชีวิตชีวา
3. ต้องเป็นคนมีความคิด รอบคอบ ไม่ใช่เพียงเพื่อขอให้ได้พูด
4. สำนึกในความรับผิดชอบ
-รับผิดชอบต่อผู้ฟัง พูดในสิ่งที่มีประโยชน์คุ้มค่าต่อเวลา
-รับผิดชอบต่อบุคคลิ่นที่ร่วมอยู่ในรายการ
-รับผิดชอบต่อหัวข้อเรื่อง เนื้อหาที่นำมาพูดได้ความชัดเจน
5. มีลักษณะผู้นำ (ยืนตัวตรง , เปิดเผยตัวเองในที่สาธารณะชน)
6. รู้จักประมาณตน ถ่อมตน รู้จักทำใจให้เป็นกลาง รู้จักตัวเองมีเหตุผล มีสติ สุขภาพจิตดี

การใช้ทัศนูปกรณ์
1. มีขนาดใหญ่มองเห็นชัดเจนจากทุกมุมห้อง
2. การบรรยายประกอบควรยืนด้านข้างอุปกรณ์
3. ควรศึกษาทำความเข้าใจอุปกรณ์ก่อนการบรรยาย
4. ถ้าจำเป็นต้องถืออุปกรณ์ด้วยตัวเอง ควรไว้ด้านหน้า หรือด้านข้างลำตัว
เนื่องจากอุปกรณ์ที่นำเสนอ เป็นประโยชน์ต่อคนฟัง ไม่ใช่คนพูด
5. การวาดภาพบนกระดานดำ ควรมีการฝึกมาก่อน
6. เอกสารแจกผู้ฟัง ควรมากพอเท่าจำนวนผู้ฟัง ไม่ควรใช้การหมุนเวียน
กรณีเอกสารมีน้อยจะทำให้เกิดความวุ่นวายสับสน
7. หัวข้อทเรื่องเนื้อหาของการพูด ควรใช้กระดาษบันทึกขนาดเล็ก ใส่หมายเลขตามลำดับก่อนหลังตามลำดับ

ข้อห้ามที่ไม่ควรทำ
การพูด : เอ้อ อ้า แบบว่า ก็ และก็ แล้วอ้า คิดว่า ควร
วลีที่ปราศจากความหมาย : อะไรเนี๊ยะ อะไรพวกเนี๊ยะนะฮะ พูดใช้ได้ ดีพอสมควร ใช้ได้ดีพอสมควร เหล่าเนี๊ยะนะฮะ ............นะคะ .............นะครับ ฯลฯ

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

Stack

โครงสร้างข้อมูลสแตก

                โครงสร้างสแตกข้อมูลที่รู้จักและนำมาใช้งานชนิดหนึ่งก็คือ สแตก (Stack) มีลักษณะเป็นรายการในแนวเชิงเส้น (Linear List) รูปแบบหนึ่ง และมีข้อกำหนดให้ชุดปฏิบัติการ สามารถเพิ่มและลบรายการเพียงด้านเดียว ซึ่งเป็นด้านบนสุดของสแตก (Top of Stack)

เรียกว่าตัวชี้สแตก (Stack Pointer) มีรูปแบบเป็น (Top)(S)โดยสแตกมีการกำหนดเป็นรูปแบบดังนี้

  S = [s_{1 ,S}2, … ,S_T]

ด้านบนสุดของสแตกจะอยู่ที่ Top (S) =S_T และมีจำนวนสมาชิกในสแตกเท่ากับ T

ดังในรูปที่ 4.1

รูปที่ 4.1 ตัวอย่างลักษณะสแตกที่มีสมาชิกเท่ากับ T มีตัวชี้สแตก Top

สแตกมีลักษณะเดียวกับที่วางจานหรือถาดในร้านอาหาร ดังในรูปที่ 4.2 ที่มีสปริงอยู่ด้านล่างและมีจานวางซ้อนเป็นขั้น ๆ จะมีเพียงจานที่อยู่บนหยิบออกไปได้ สแตกถูกนำมาใช้แก้ไขปัญหาต่าง ๆ ดังต่อไปนี้

ปัญหาที่ 1  เนื่องจากคอมพิวเตอร์ทำงานในรูปแบบของเลขฐาน 2 แต่ในส่วนของผู้ใช้งานจะเป็นเลขฐาน 10 จึงต้องแปลงค่าจากเลขฐาน 10 ไปเป็นเลขฐาน 2 เช่น เปลี่ยนจาก 26 เป็น 11010

ปัญหาที่ 2  คอมไพเลอร์ (Compiler) จะต้องคำนวณนิพจน์ (Expression) ทางคณิตศาสตร์ที่มีเครี่องหมายวงเล็บเปิดและปิดเข้ามาเกี่ยวข้อง

ปัญหาที่ 3  โปรแกรมเกมเล่นไพ่ (Card Game) จะมีที่วางกองไพ่และการแจกไพ่ได้เฉพาะใบที่อยู่บนสุด

ปัญหาที่ 4  รูปแบบปัญหาการทำงานบางอย่าง  เช่น  การทำงานของ  Switching Box ของเครือข่าย หรือรูปแบบการสลับตู้รถไฟบนราง  ดังในรูปที่ 4.3

 

รูปที่ 4.3 ตัวอย่างการใช้สแตกแก้ปัญหาการสลับตู้รถไฟบนราง

ปัญหาต่าง ๆ  เหล่านี้สามารถแก้ไขโดยใช้โครงสร้างสแตก  ซึ่งมีลักษณะการทำงานในรูปแบบที่เรียกว่าเข้าทีหลังออกก่อน (Last-In-First-Out, LIFO) เมื่อมีค่าใหม่เข้ามาก็จะใส่ลงในสแตกซ้อนทับค่าเดิมที่เก็บอยู่ลงไปอยู่ด้านล่างไปเรื่อย ๆ ในลักษณะแบบนี้

การปฏิบัติการของสแตก

                จากลักษณะดังที่กล่าวมาของสแตก  จะต้องมีการปฏิบัติการเข้ามาช่วยการทำงานของสแตกให้มีความถูกต้อง

1.    CreateStack( ) ใช้สร้างสแตกใหม่ขึ้นมาใช้งานและกำหนดค่าเริ่มต้นต่าง ๆ

2.    Push(value,  stack)  ใช้เพิ่มค่าใหม่เก็บลงในสแตกที่ใช้งานอยู่  มีอัลกอริทึมการทำงานเป็นดังในตารางที่ 4.1

ตารางที่ 4.1  อัลกอริทึมการเพิ่มค่าใหม่เก็บลงในสแตก

        1.  ตรวจสอบสแตกว่าจะมีสมาชิกอยู่เต็มหรือไม่  โดยเปรียบเทียบค่า Top กับขนาดอาร์เรย์

        2.  ถ้าสแตกไม่เต็ม

                    2.1  เพิ่มค่าให้กับ Top โดยการบวก 1

                    2.2  ทำการนำค่าที่ได้มาเก็บลงในสแตกในตำแหน่ง Top ไม่เช่นนั้นแจ้งกลับมาว่าสแตกเต็ม

        3.  Pop(stack)  ใช้ดึงค่าออกจากสแตกที่ใช้งานอยู่และส่งค่า value กลับมาให้ มีอัลกอริทึมการ   ทำงานเป็นดังในตารางที่ 4.2

ตารางที่ 4.2  อัลกอริทึมดึงค่าออกจากสแตก

1.    ตรวจสอบว่าสแตกว่างหรือไม่ โดยเปรียบเทียบค่า Top กับขนาดอาร์เรย์

2.    ถ้าสแตกไม่ว่าง

2.1  ทำการดึงค่าในตำแหน่ง  Top ออกมาให้

2.2  ลดค่าของ Top โดยการลบ 1 ไม่เช่นนั้นแจ้งกลับมาว่าสแตกว่าง

        3.  isEmpty(stack)  ใช้ตรวจสอบว่าสแตกที่ใช้งานอยู่ว่างหรือไม่  ถ้าไม่มีค่าเก็บไว้เลยจะส่งค่าจริงกลับให้

                   

                เมื่อนำสแตกมาใช้งานตามลำดับดังในรูป (a) ถึง (g) มีการทำงานโดยใช้ชุดปฏิบัติการ Push และ Pop ดังนี้

(a)    เริ่มต้นสร้างสแตก  S ขึ้นมาทำงานจะได้เป็นสแตกว่าง  ไม่มีสมาชิกโดยตัวชึ้สแตก Top ยังไม่มีค่า

(b)   นำค่า  B เก็บต่อโดยใช้ Push(B) สแตก S = [A,B] ตัวชี้สแตก Top = B

          

(c)นำค่า C เก็บต่อโดยใช้ Push(C) สแตก S = [A,B,C]ตัวชี้สแตก Top =C

           

(d)    ต้องการดึงค่าออกมาโดยใช้ Pop( ) สแตก S = [A,B] ตัวชี้สแตกTop = B

                 

(e)ต้องการดึงค่าออกมาใช้ Push() สแตก S=[A,B] ตัวชี้สแตก Top =c

      

(f) นำค่า D, E เก็บต่อโดยใช้ Push(D) และ Push(E) ตามลำดับ สแตก S = [A,B,D,E] ตัวชี้สแตก Top = E

       

(g) ดึงค่าออกมา 3 ค่าโดยใช้ Pop( )  3  ครั้งและเก็บค่า F โดยใช้ Push(F) สแตก S = [A,F] ตัวชี้สแตก Top = F

                  

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

ตัวอย่างการใช้สแตก

                จากปัญหาในตอนต้นกล่าวถึงปัญหาการเปลี่ยนเลขฐาน  10  เป็นเลขฐาน  2   เนื่องจากการคำนวณเป็นการหารเลขฐาน  10  เศษที่เหลือจะได้เป็นเลขฐาน  2  เมื่อนำมาแสดงผลจะเป็นตัวเลขจากซ้ายไปขวา  แต่เลขฐาน  2  เป็นตัวเลขจากขวาไปซ้ายจึงเกิดการสลับด้านกัน  จึงนำสแตกมาช่วยแก้ปัญหานี้  ดังในตารางที่ 4.3 คือ โปรแกรม Stack.c

ตารางที่ 4.3 ตัวอย่างโปรแกรม Stack.c

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

การใช้สแตกแก้ปัญหาการแปลงนิพจน์คณิตศาสตร์

                คอมไพเลอร์จะแปลงคำสั่งจากภาษาระดับสูง  (High-level  Language)  ไปเป็นภาษาเครื่อง (Machine Language) ส่วนหนึ่งที่ต้องแปลงคือนิพจน์คณิตศาสตร์ เช่น X = A * B + C ซึ่งมีลักษณะที่เรียกว่า  Infix  Notation  มีเครื่องหมายคำนวณอยู่ระหว่างโอเปอแร้น (Operand) โดยแปลงไปเป็นนิพจน์แบบ Postfix  Notation มีเครื่องหมายคำนวณนำหน้าโอเปอแร้น แต่เนื่องจากนิพจน์แบบ Infix มีการนำเครื่องหมายวงเล็บเข้ามาใช้ทำให้ทิศทางการคำนวณเปลี่ยนไป   ดังในตารางที่ 4.4 เป็นตัวอย่างของการคำนวณแบบเดียวกัน

ตารางที่ 4.4  ลักษณะนิพจน์แบบ Infix, Posifix, และ Prefix Notation

การแปลงนิพจน์แบบ Infix เป็นแบบ  Postfix

          เมื่อพิจารณาการแปลงนิพจน์แบบ Infix เป็นแบบ Postfix เป็นขั้นตอนการแปลงโดยเริ่มต้นจากสแกนนิพจน์ Infix ทีละตัว  หากพบวงเล็บก็จะทำส่วนที่อยู่ในวงเล็บให้เสร็จก่อนเป็นนิพจน์ย่อย (Subexpression) ซึ่งจะได้เป็นอัลกอริทึมดังในตารางที่ 4.5

ตารางที่ 4.5  อัลกอริทึมการแปลงนิพจน์แบบ Infix เป็นแบบ Postfix

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

a.       รับค่า  (Token) ตัวถัดไปในนิพจน์  Infix (ประกอบด้วย ค่าคงที่ ตัวแปร เครื่องหมายคำนวณ วงเล็บเปิดและปิด

b.       ค่าที่รับเข้ามา ถ้าเป็น

b.1  โอเปอแร้น (ค่าคงที่,ตัวแปร)                               นำไปแสดงทางจอภาพ

b.2  วงเล็บเปิด                                                               ให้นำใส่ลงในสแตก (Push)

b.3  วงเล็บปิด                                                                 ดึงค่าออกจากสแตก (Pop) และนำไปแสดงทางจอภาพ  ทำจนกว่าจะพบวงเล็บเปิด

b.4  เครื่องหมายคำนวณ                                               ถ้าสแตกว่าง  หรือค่าที่รับมามี Precedence สูงกว่าค่าบนสแตกให้นำใส่ลงในสแตก (Push) ถ้าหากค่าที่รับมามี Precedence น้อยกว่าค่าบนสแตกให้ดึงค่าออกจากสแตก (Pop)

            3.  เมื่อทำจนค่าในนิพจน์ Infix หมด ให้ดึงค่าออกจากสแตก (Pop) แสดงทางจอภาพตามลำดับ จนกว่าสแตกว่าง

             จากอัลกอริทึมดังกล่าวเมื่อนำมาใช้กับตัวอย่างนิพจน์ 7*8-(2+3) จะได้เป็นลำดับขั้นตอนดังในรูปที่ 4.4 หรือเขียนเป็นแบบตารางได้ดังในตารางที่ 4.6

ตารางที่ 4.6 การแปลงนิพจน์ 7*8-(2+3) เป็นนิพจน์ Postfix

การหาค่าคำตอบจากการคำนวณนิพจน์ Postfix

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

ตารางที่ 4.7  อัลกอริทึมการหาค่าคำตอบจากนิพจน์ Postfix

                จากอัลกอริทึมดังกล่าวเมื่อนำมาใช้กับตัวอย่างนิพจน์ 24*95+- จะเป็นไปตามลำดับขั้นตอนดังในรูปที่ 4.5 หรือเขียนเป็นแบบตารางได้ดังในตารางตารางที่ 4.8

    ตาราง 4.8 การหาค่าคำตอบจากนิพจน์

ลิ้งค์ลิสต์

โครงสร้างข้อมูลลิ้งค์ลิสต์ 
                วิธีแก้ปัญหาในการย้ายข้อมูลที่พบในการจัดเก็บที่มีรูปแบบเรียงตามลำดับ(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 ใช้ชี้ไปยังข้อมูลจริงอีกทีซึ่งมีโครงสร้างข้อมูลสตริงเก็บไว้ในหน่วยความจำที่ขอมาแทนการเก็บไว้ภายในโหนด