Queues Structure

บทที่ 4

คิว

Queues Structure

                โครงสร้างการทำงานแบบคิวคือการมีการจัดลำดับการเข้าและออกข้อมูลอย่างเป็นลำดับ ข้อมูลใดเข้ามาก่อนก็จะดำเนินการก่อน  หากข้อมูลใดเข้ามาทีหลังก็จะดำเนินการทีหลัง เรียกลักษณะของการดำเนินการแบบนี้ว่า  First In First Out (FIFO) หรือเข้าก่อนออกก่อน

ลักษณะของคิว

•                    โครงสร้างข้อมูลแบบคิวเป็นโครงสร้างเชิงเส้นและไม่เชิงเส้น

•                     มีทางเข้าและออก 2  ทาง

•                    มีการทำงานแบบลำดับ

•                    สามารถนำข้อมูลเข้าและนำข้อมูลออกสลับกันได้

•                    มีลำดับการทำงานแบบเข้าก่อนออกก่อน (FIFO)

ประเภทของคิว มี 3 ประเภท

•                    คิวธรรมดา (Queue)

•                    คิววงกลม (Circular Queue)

•                    คิวที่เรียงลำดับตามความสำคัญ (Priority Queue)

การดำเนินการของคิว

     เมื่อนำเข้าข้อมูลจะต้องจัดเรียงในลักษณะการต่อท้ายกัน

•                    ข้อมูลที่อยู่ส่วนท้ายของการเก็บข้อมูล เรียกว่า  Rear

•                    ข้อมูลที่อยู่ส่วนหัวของการเก็บข้อมูล ซึ่งจะเรียกว่า  Front

•                    การนำข้อมูลเข้าไปในคิว  เรียกว่า Insert (Enqueue)

•                    การนำข้อมูลออกจากคิว เรียกว่า Remove (Dequeue)

•                    คิวธรรมดา (Queue)

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

 

การนำข้อมูลเข้า Enqueue

ž             ก่อนนำสมาชิกเข้าคิว ต้องตรวจสอบว่าคิวเต็มหรือไม่ โดยที่ ถ้า rear = maxQ แสดงว่าคิวเต็ม (เมื่อ maxQ คือขนาดของคิว)

•                    การนำข้อมูลใหม่เข้ามาแถวคอย จะเพิ่มเข้ามาด้านหลัง

•                    และจะนำเข้ามาเรื่อย ๆ จนเต็ม หรือเรียกว่า แถวคอยเต็ม (Queue Overflow)

•                    ดังนั้นการนำสมาชิกเข้าคิว จึง เป็นการเพิ่มค่าพอยน์เตอร์ rear

•                    หากมีสมาชิกในคิวเพียงค่าเดียวพอยน์เตอร์ rear และ front จะเท่ากัน

•                    Queue : Array Implementation

•                    INSERT-Q Algorithm

•                     

                front = rear = 0

                if( rear == maxQ)

                                write “Overflow”

                else

                                if(front==0)

                                                front  ← 1

                                                rear ← 1

                                                Q[rear] ← Item

                                Else

                                                rear  ←  rear + 1

                                                 Q[rear] ← Item

การนำข้อมูลออก  Dequeue

ž             ก่อนนำสมาชิกออกจากคิว ต้องตรวจสอบดูก่อนว่าคิวว่างเปล่าหรือไม่ โดยเงื่อนไขการตรวจสอบคือ front = rear = 0

•                    ข้อมูลที่จะนำออกก่อนจะเป็นข้อมูลที่อยู่ ด้านหน้า

•                    สามารถนำข้อมูลออกเรื่อย ๆ จนไม่มีข้อมูล หรือเรียกว่า แถวคอยว่าง  (Queue Underflow)

•                    ดังนั้นการนำสมาชิกออกจากคิวจึง เป็นการเพิ่มค่าพอยน์เตอร์ front

คิววงกลม (Circular Queue)

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

คิววงกลม (Circular Queue)

•                    ลักษณะของคิวแบบวงกลม

•                    เหมือนคิวธรรมดาคือมีตัวชี้ 2 ตัวคือ front และ rear สำหรับแสดงตำแหน่งหัวคิวและท้ายคิวตามลำดับ

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

Circular Queue

•                    ลักษณะของคิวแบบวงกลม (ต่อ)

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

•                    ดังนั้นคิววงกลมจะสามารถเพิ่มข้อมูลเข้าไปในคิวได้ จนกว่าคิวจะเต็มจริง ๆ

คิวลำดับความสำคัญ หรือ แถวคอยเชิงบุริมภาพ
(Priority Queue)

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

คิวลำดับความสำคัญ หรือ แถวคอยเชิงบุริมภาพ
(Priority Queue)

•                    ใน คิวธรรมดา ข้อมูลที่เข้ามาก่อนจะมีสิทธิ์ออกก่อน (First In First  Out:FIFO) อย่างไรก็ตาม มีบางครั้งที่เราต้องยกให้สมาชิกบางประเภทได้ทำงานก่อนทั้งที่มาทีหลัง เช่น การให้คิวงานที่เล็กกว่าได้ทำก่อน หรือ การให้สิทธิพิเศษแก่การทำงานบางประเภท

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

คิวลำดับความสำคัญ หรือ แถวคอยเชิงบุริมภาพ
(Priority Queue)

	คิวลำดับความสำคัญ หรือ แถวคอยเชิงบุริมภาพ (Priority Queue)

Priority Queue

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

• typedef struct {   int    priority;

                                 char data;

                             }  Queue;

     Queue    priority_queue[15];

การประยุกต์ใช้ Queue

ตัวอย่างการประยุกต์คิวมาใช้งานบนคอมพิวเตอร์

-  การเข้าคิวของโปรเซสหรืองานต่าง ๆ เพื่อรอการประมวลผลจากซีพียูตามลำดับ

-  การแบ่งเวลา (Time Sharing) ด้วยการจำกัดตารางเวลาการประมวลผลของแต่ละโปรเซส ส่งผลให้สามารถหมุนเวียนการประมวลผลในแต่ละโปรเซสสลับไปมาได้ ทำให้ดูเหมือนกับการประมวลผลงานหลาย ๆ อย่างได้ในเวลาเดียวกัน (Multitasking)

- การเข้าคิวเพื่อรอผลลัพธ์จากเครื่องพิมพ์

Linked-List

บทที่ 3

linked-list

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

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

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

List

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

ตัวอย่าง

1)    Array

   

   Count                                                        1        2        3        4

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

•       ตัวชี้ (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) ของโหนดขวามือสุดก็จะเก็บตำแหน่งที่อยู่ของโหนดที่อยู่ทางซ้ายมือสุด