โครงสร้างข้อมูลแบบลิงค์ลิสต์ (Linked list)
โครงสร้างข้อมูลแบบนี้จะให้ความสะดวกแก่การจัดการข้อมูลมากอย่างไรก็ดีในบางครั้งก็ให้ความยุ่งยากแก่ผู้ใช้เนื่องจากจะซับซ้อนกว่าแบบใช้อาร์เรย์ข้อจำกัดของการใช้อาร์เรย์คืออาร์เรย์มีขนาดคงที่ ถ้าเราจะใช้อาร์เรย์ขนาด 100 ช่องเมื่อใช้หมด 100 ช่องก็ใช้อาร์เรย์นั้นไม่ได้ถ้าไม่อนุญาตให้เคลียร์พื้นที่อาร์เาย์เพื่อใช้ซ้ำถึงแม้อนุญาตให้เคลียร์พื้นที่อาร์เรย์เพื่อใช้ซ้ำก็ไม่เป็นการสะดวกเนื่องจากอาจต้องตรวจทุกช่องในอาร์เรย์เพื่อหาว่าช่องไหนสามารถใช้ซ้ำได้นอกจากนี้การใช้พื้นที่ซ้ำยังต้องเลื่อนข่าวสารทั้งหมดไปอยู่ในส่วนอาร์เรย์อีกประการคือในภาวะการทำงานแบบ real - time ที่ต้องมีการนำข้อมูลเข้า (insertion) หรือดึงข้อมูลออก (deletion) อาร์เรย์จะไม่สะดวกแก่การใช้มากในภาวะการทำงานแบบนี้โครงสร้างแบบลิงค์ลิสต์จะสะดวกกว่า การแทนแบบใช้พอยเตอร์นี้เราต้องใช้พื้นที่เพิ่มเติมเป็นส่วนของพอยน์เตอร์ (pointer) หรือลิงค์ (link) เพื่อแสดงให้เห็นขัดว่าโหนดที่ต่อจากโหนดนั้นคือโหนดใดลักษณะของแต่ละโหนดจึงประกอบด้วยช่อง 2 ช่อง
สมมติว่าเราจะแทนชุดข่าวสารที่ประกอบด้วย A,B,C ลักษณะการแทนจะเป็นไปตามรูปซึ่งเป็นภาพแสดงแนวคิดการเก็บแบบหนึ่งส่วนการเก็บข่าวสาร A,B,C แท้จริงแล้วจะเป็นในรูปไหนก็ได้แต่ก็ต้องสอดคล้องกับแนวความคิดนี้ รูปที่ 3 แสดงถึงความเป็นไปได้อีกแบบหนึ่งเมื่อข่าวสาร A,B,C อยู่ในพื้นที่ความจำ
รูปการแทนโครงสร้างแบบลิงค์ลิสต์
ข่าวสาร A อยู่ที่ตำแหน่ง 5000 ดูได้จากค่าที่ตำแหน่ง 6000 ผู้ใช้จะต้องรู้ว่า head node ของค่าชุดนี้อยู่ที่แอดเดรส 6000 ส่วนค่า A,B,C ผู้ใช้ไม่ทราบว่าอยู่ที่ใดยกเว้นแต่จะตามพอยน์เตอร์เข้าไป จากตำแหน่ง 6000 เรารู้ว่าค่าที่อยู่ที่ตำแหน่ง 5000 คือค่าแรก (ค่า A ) จากส่วนพอยน์เตอร์ของ A (ที่ตำแหน่ง 5001) เรารู้ว่าค่าถัดไป (ค่าB) อยู่ที่ตำแหน่ง 5600 เราตามพอยน์เตอร์ไปยังตำแหน่ง 5600 พบ B ค่าพอยน์เตอร์ของ B ที่ตำแหน่ง 5601 เป็นแอดเดรสของค่าถัดไป (ค่า C) ซึ่งอยู่ที่ตำแหน่ง 5508 จากค่า C เมื่อพิจารณาค่าพอยน์เตอร์ของ C พบว่าค่า - 1 ซึ่งหมายถึงว่าสิ้นสุดของค่าชุดนี้แล้ว อนึ่งผู้ใช้ไม่สามาร5นำค่า A หรือ B หรือ C มาใช้โดยตรงอย่าในอาร์เรย์ ผู้ใช้ต้องเดิน เข้าไปหาค่าเหล่านี้ลักษณะการหาค่าแบบนี้คล้าย ๆ กับการหาค่าในเทปซึ่งเรียกว่า การหาค่าแบบลำดับ (sequential access) ซึ่งในทางปฏิบัติสำหรับระบบโปรแกรมภาษาชั้นสูงเราอาจใช้อาร์เรย์เป็นตัวเก็บค่า A,B,C และใช้อีกหนึ่งอาร์เรย์เป็นตัวเก็บพอยน์เตอร์ดังรูปซึ่งผู้ใช้ต้องทราบว่าค่าแรกของข่าวสารชุดนี้อยู่ที่ตำแหน่งที่ 2 ในอาร์เรย์ INFO (3)
รูปการแทนลิงค์ลิสต์ด้วยอาร์เรย์ 2 ชุด
ลิงค์ลิสต์เดี่ยว (Singly Linked List)
ลิงค์ลิสต์เดี่ยวหมายถึงลิงค์ลิสต์ที่แต่ละข่าวสารมีการแสดงออกถึงลำดับก่อนหลังอย่างชัดเจนโดยใช้พอยน์เตอร์นั่นคือในแต่ละข่าวสารจะมีส่วนที่บอกว่าข่าวสารตัวต่อไปอยู่ที่ใดแต่ละข่าวสารจะเรียกว่าโหนด (node) แต่ละโหนดจะมี 2 ช่อง ดูรูปที่ 1 เป็นตัวอย่างเราจะใช้สัญลักษณ์ต่อไปนี้ในการเรียกชื่อแต่ละโหนด
NODE(P) หมายถึงโหนดที่ระบุ(ถูกชี้) โดยพอยน์เตอร์P
INFO(P) หมายถึงส่วนข่าวสารของโหนดที่ถูกชี้โดย P
LINK(P) หมายถึงส่วนแอดเดรสของโหนดที่ถูกชี้P
ในระบบการแทนโดยลิงค์ลิสต์เราจะสมมติว่าหน่วยความจำจะประกอบด้วยชิ้นส่วนความจำเป็นชิ้น ๆ ดังรูปที่ 2 (เรียกว่าโหนด)แทนที่จะเป้นแบบพื้นที่ความจำติดต่อกันไปดังอาร์เรย์ชิ้นส่วนความจำทั้งหมดนี้จะคล้องกันเป็นลิงค์ลิสต์เดี่ยวขนาดมหึมาซึ่งที่รวมความจำนี้เรียกว่า storage pool หรือหน่วยเก็บข้อมูลส่วนรวมเมื่อผู้ใช้ต้องการพื้นที่เก็บข่าวสารก็เรียกเอาโหนดจาก storage pool ถ้าผู้ใช้ไม่ต้องการใช้โหนดใดก็คืนโหนดนั้นไปยัง storage poolเพื่อผู้อื่นจะได้ใช้โหนดแรกของ storage pool จะถูกชี้โดยพอยน์เตอร์ที่ชื่อ AVAIL
แนวความคิดเรื่อง storage pool นั้น ตีความได้ในงานจริง ๆ เช่น storage pool อาจประกอบด้วยเก้าอี้นั่งทั้งหมดในเครื่องบินโดยสารลำหนึ่งหรือเป็นจำนวนที่นั่งที่ยังไม่ได้จองของสายการบินหนึ่งในเวลาใด ๆ
1.1การจัดสรรหน่วยเก็บข้อมูล(Storage Allocate) การจัดสรรหน่วยเก็บข้อมูลเป็นการนำโหนดออกจากหรือคืนโหนดสู่ storage pool ซึ่งจะสมมติว่ากระทำโดยฟังก์ชัน 2 ชุด คือ ALLOCATE P และ FREE P ซึ่งจะนิยามดังนี้
ALLOCATE P :นำโหนดหนึ่งออกจาก ALLOCATE P แล้วให้พอยน์เตอร์P ชี้ไปยังโหนดนั้น
FREE P : คืนโหนดที่ถูกชี้โดย P ไปยัง storage pool
การทำงานของ ALLOCATE P ดูได้จากรูปที่ 6 ซึ่งสมมติว่า storage pool ประกอบด้วยโหนด5 โหนด หลังการประมวลผล storage pool จะประกอบด้วย 4 โหนดและโหนดP เป็นโหนดที่นำมาใช้ได้ ฟังก์ชัน ALLOCATE P สามารถเขียนเป็นชุดคำสั่งได้ดังนี้
1.IF AVAIL = - 1 THEN แจ้งผู้ใช้ว่าไม่มีโหนดเหลือใน storage pool;
2.P = AVAIL ; / * ให้ P ชี้ไปยังโหนดแรก * /
3.AVAIL = LINK (AVAIL) ; / * ดูรูปที่ 4.7 * /
รูปการทำงานของ storage pool และคำสั่ง ALLOCATE P
LINK(AVAIL) หมายถึงส่วนพอยน์เตอร์ของโหนดแรกซึ่งบอกค่าตำแหน่งของโหนดถัดไปใน storage pool ดังนั้นค่า AVAIL ใหม่ คือแอดเดรสของโหนดที่สอง (อนึ่งเราจะได้ผลเหมือนกันถ้าเขียนว่า AVAIL = LINK (P) แทนคำสั่งที่ 3 ) ก็เพียงแต่โยงลูกศรไปยังโหนดถัดไปการทำความเข้าใจระบบการใช้งานของลิงค์ลิสต์ไม่มีทางใดดีกว่าวาดรูปการทำงานของแต่ละคำสั่ง ต่อไปนี้จะแสดงวิธีการทำความเข้าใจแบบนี้ตลอดหนังสือเล่มนี้ดังนั้นของให้ผู้อ่านฝึกหัดตามไปด้วย
ต่อจากคำสั่ง ALLOCATE P เป็นการทำความเข้าใจกับคำสั่ง FREE P ชุดคำสั่งแทน FREE P จะเป็นดังนี้
1.IF AVAIL = - 1 THEN DO ; AVAIL = P;
2. LINK(AVAIL) = - 1
3. END ;
4. ELSE DO ; LINK(P) = AVAIL ;
5. AVAIL = P; 6. END;
1.2 การนำข้อมูลเข้าสู่และออกจากลิงค์ลิสต์(Insertion and Deletion)
ก่อนอื่นขอให้พิจารณาดูการนำข่าวสาร 5 เข้าสู่อาร์เรย์A (ซึ่งมี 10 ช่อง) ที่ตำแหน่ง 3 ดังรูปที่ 10 เพื่อให้ค่าต่าง ๆ เรียงอยู่ในลำดับที่ถูกต้องจะเห็นได้ว่าในลักษณะนี้จะต้องมีการเลื่อนข่าวสารในอาร์เรย์อย่างมากเพื่อเปิดทางให้กับตัวที่เข้ามาใหม่กระบวนการเช่นนี้จะเสียเวลามากถ้าแต่ละข่าวสารเป็นเรคอร์ด (record) ขนาดใหญ่ในระบบที่มีการใช้ลิงค์ลิสต์ การนำข่าวสารเข้าหรือออกจะสะดวกมากเนื่องจากสามารถทำสำเร็จได้โดยคำสั่งไม่กี่คำสั่งเพื่อเปลี่ยนค่าพอยน์เตอร์อย่างมาก 2 ค่า เท่านั้น
1) การนำข้อมูลเข้า (Insertion) สมมติว่าเรามีลิงค์ลิสต์ H อยู่แล้ว (โหนดที่ถูกชี้โดย H คือ head node ของลิงค์ลิสต์นี้ ) และเราต้องการนำข่าวสารที่ถูกชี้โดยพอยน์เตอร์P (หรือโหนดP) ไปอยู่ต่อจากโหนดH1
INSERT : PROCEDURE (X,H1) /* ต้องการนำข่าวสาร X เข้าไปต่อท้ายโหนดที่ถูกชี้โดย H1 ในลิงค์ลิสต์ที่มี head node H */
/* ให้ Q เป็นพอยน์เตอร์ที่จะใช้ชั่วคราว */
/* เราจะนำ X มาใช้โดยตรงไม่ได้ ต้องสร้างโหนดเพื่อเก็บ X เสียก่อน */
ALLOCATE Q ;
INFO(Q) = X ;
/* ก่อนจะนำ X เข้า ต้องตรวจสอบกรณีพิเศษสองกรณีคือ (1) ตรวจสอบว่าลิงค์ลิสต์ H นี้ว่างเปล่าหรือไม่ (2) ตรวจสอบว่า H1 เป็นโหนดสุดท้ายหรือไม่ */
IF H = NULL / * สมมติว่าค่า NULL ทำงานเช่นเดียวกับ - 1 */ THEN /* แสดงว่าลิงค์ลิสต์ H ว่างเปล่า */ แจ้งให้ผู้ใช้ทราบและจบ ;
IF LINK(H1) = NULL
THEN /* แสดงว่าโหนดH1 เป็นโหนดสุดท้าย */
LINK (Q) = NULL;
ELSE /* แสดงว่าโหนดH1 ไม่ใช่โหนดสุดท้าย
*/ LINK (Q) = LINK(H1);
ELSE /* แสดงว่าโหนดH1 ไม่ใช่โหนดสุดท้าย
*/ LINK (Q) = LINK(H1);
LINK (H1) = Q;
/*ในที่สุดเราจะได้ลิงค์ลิสต์ใดแล้วแต่กรณี*/
หรือ
END
INSERT;
2)การนำข้อมูลออก (Deletion) ในการนี้เราต้องการนำข้อมูลในโหนดที่ต่อถัดจากโหนดH1 มาไว้ในตัวแปร X และให้คืนโหนดนั้นไปยัง storage pool
DELETE : PROCEDURE(X,H1)
/* ฟังก์ชันนี้จะนำข่าวสารในโหนดที่ถัดจาก H1 ไปเก็บไว้ใน X แล้วคืนโหนดนั้นไปยัง storage pool*/ /* มีกรณีพิเศษที่ต้องพิจารณาสามกรณีคือ
1)ลิงค์ลิสต์ H ว่างเปล่า
2)ลิงค์ลิสต์ H ประกอบด้วยโหนดเดียว
3)โหนดH1 เป็นโหนดสุดท้าย */
IF H = NULL
THEN /*แสดงว่าลิงค์ลิสต์นั้นมีโหนดเดียว */ แจ้งให้ผู้ใช้ทราบ ,จบ ;
IF LINK(H) = NULL THEN /* แสดงว่าลิงค์ลิสต์นั้นมีโหนดเดียว */แจ้งให้ผู้ใช้ทราบ , จบ;
IF LINK (H) =NULL และ LINK(H1) = NULL THEN /* แสดงว่าโหนดH1 เป็นโหนดสุดท้าย */ แจ้งให้ผู้ใช้ทราบ , จบ ;
/* เข้าสู่จุดนี้แสดงว่ามีโหนดต่อถัดจากโหนดH1 */
/* ให้ Q เป็นพอยน์เตอร์ชั่วคราว */
ขอให้สังเกตว่าเราไม่สามารถนำโหนดH1 ออกโดยตรงได้ทั้งนี้เนื่องจากว่าเราไม่ทราบว่าโหนดก่อนโหนดH1 อยู่ที่ใด ถ้าจะในโหนดH1 ออกเราต้องหาว่าโหนดก่อนโหนดH1 อยู่ที่ใด ซึ่งจะทำได้โดยเดินเข้าไปในลิงค์ลิสต์ตั้งต้นจาก H ตามพอยน์เตอร์ไปเรื่อย ๆ จนกว่าจะพบโหนดH1 การเดินเข้าไปในลิงค์ลิสต์จะมีความสำคัญซึ่งเราจะอธิบายถึงวิธีการดังกล่าวในหัวข้อต่อไป
3)การท่องไปในลิงค์ลิสต์สมมติว่ามีลิงค์ลิสต์ H อยู่แล้ว ถ้าจะหาว่าข่าวสาร X อยู่ในลิสต์นี้หรือไม่เราจะสามารถรู้ได้โดยการค้นหาแบบลำดับ (sequential search) ตามลำดับ ตั้งต้นจาก H การท่องไปในลิงค์ลิสต์ใหม่ไม่ได้ ดังนั้นเราจะใช้พอยน์เตอร์อีกตัวมาเป็นผู้ช่วย (auxiliary pointer) เพื่อดึงตัว H1 ไปยังโหนดถัดไ»
เมื่อเราเข้าใจถึงวิธีการท่องไปในลิงค์ลิสต์แล้ว อัลกอริทึม เพื่อหาค่า X จะเขียนได้ดังนี้
SEARCHX : PROCEDURE (X) ;
/* อัลกอริทึมนี้จะหาว่า X อยู่ในลิงค์ลิสต์ H หรือไม่ */
/* ให้ H1 = เป็นพอยน์เตอร์ชั่วคราว */
IF H = NULL THEN แจ้งให้ผู้ใช้ทราบว่าลิงค์ลิสต์ H ว่างเปล่า , จบ ;
H1 = H ; /* H1 ชี้ไปยังโหนดที่อยู่หัวของลิงค์ลิสต์ */
DO WHILE (INFO(H1)นX)
IF LINK(H1) = NULL THEN GOTO OUT ;
H1 = LINK(H1);
END;
OUT:IF INFO(H1) = X THEN แจ้งให้ผู้ใช้ทราบ , จบ;
มิฉะนั้นแจ้งให้ผู้ใช้ทราบว่า X ไม่อยู่ในลิงค์ลิสต์ H ;
END SEARCHX;
1.3 ลิงค์ลิสต์แบบวงกลม (Circular linked list) เมื่อเราให้พอยน์เตอร์ของโหนดสุดท้ายในลิงค์ลิสต์(ที่มีโหนดแรกคือโหนด H) ชี้ไปยังโหนดแรก เราจะได้โครงสร้างลิงค์ลิสต์แบบวงกลมดังรูปที่18 โครงสร้างแบบนี้สะดวกกว่าแบบลิงค์ลิสต์เดี่ยวธรรมดาในแง่ที่ว่าถัดจากโหนดสุดท้ายก็เป็นโหนดแรกเลยดังนั้นการไล่พอยเตอร์จึงมีความสะดวกในบางครั้งเพราะพอยน์เตอร์จะไม่มีโอกาสตกหายไประหว่างการท่องไปในลิงค์ลิสต์
ลิงค์ลิสต์คู่ (Doubly Linked List)
ลิงค์ลิสต์คู่ (Doubly Linked List) ลิงค์ลิสต์แบบนี้เป็นลิงค์ลิสต์ที่แต่ละโหนดมีสองพอยน์เตอร์คือ LLINK และ RLINK ซึ่งจะชี้ไปยังโหนดข้างซ้ายและข้างขวาของโหนดนั้นตามลำดับ ตัวอย่างเช่นถ้าต้องการจะเก็บค่า A,B,C,D ในลิงค์ลิสต์ชนิดนี้จะได้โครงสร้างซึ่งปลายทั้งสองข้างของลิงค์ลิสต์ชนิดนี้จะมีพอยน์เตอร์ F และ R แสดงถึงโหนดแรกในทิศนั้น ถ้าใช้อาร์เรย์สร้างลิงค์ลิสต์ตามรูปที่ 19 จะต้องใช้อาร์เรย์ 3 ชุดคือ อาร์เรย์สำหรับช่องข่าวสาร (INFO) , อาร์เรย์สำหรับพอยน์เตอร์ทางซ้าย (LLINK) และอาร์เรย์สำหรับพอยน์เตอร์ทางขวา (RLINK
เมื่อเปรียบเทียบลิงค์ลิสต์คู่กับลิงค์ลิสต์เดี่ยวจะเห็นได้ชัดว่าลิงค์ลิสต์คู่ต้องใช้เนื้อที่มากกว่า เนื่องจากต้องใช้ 2 พอยน์เตอรืสำหรับแต่ละโหนดแน่นอนที่เสียไปนั้นก็เพื่อที่จะได้สิ่งบางอย่างเพิ่มเติม นั่นคือความสะดวกในการนำข่าวสารเข้าหรือออกจากลิงค์ลิสต์ ในกรณีลิงค์ลิสต์คู่เราสามารถนำโหนดใหม่เข้าทาง ด้านหน้า หรือ ด้านหลังโหนดH1 ในลิงค์ลิสต์นั้นได้นอกจากนี้เรายังสามารถคืนโหนดH1 ไปสู่ storage pool โดยตรงได้อีกด้วยอย่าลืมว่าเราไม่สามารถคืนโหนดH1 ไปสู่ storage pool ในกรณีลิงค์ลิสต์เดี่ยว
2.1 การนำข่าวสารเข้าสู่ลิงค์สิสต์คู๋สมมติว่าแต่ละโหนดใน storage pool ดังนั้นคำสั่ง ALLOCATE P จะก่อกำเนิดโหนด
เราจะสมมติว่ามีลิงค์ลิสต์คู่อย่าแล้ว และจะนำโหนดP ซึ่งเก็บข่าวสาร X เข้าสู่ลิงค์ลิสต์นี้ ที่ตำแหน่งถัดจากโหนดH1 ซึ่งจะเห้นได้ว่ากระบวนการนี้สำเร็จได้โดยการเปลี่ยนค่าพอยน์เตอร์4 ค่าอย่างไรกีดีลำดับการเปลี่ยนค่าพอยน์เตอร์มีความสำคัญมาก ถ้าเราทำตามลำดับ (1),(2),(3),(4) จะไม่สำเร็จ ส่วนรูปที่ 23
ลิงค์ลิสต์ (Linked List)
ลิสต์ (Lists) หรือรายการ ถือเป็นการจัดเก็บข้อมูลชนิดหนึ่งซึ่งข้อมูลเชื่อมต่อกันแบบเชิงเส้น แต่ละข้อมูลมักเรียกว่า อีลิเมนต์ (Element) หรือสมาชิก (Member) โดยแบ่งโดยพื้นฐานได้ 2 แบบคือแบบทั่วไป (General) และแบบจำกัด (Restricted) ซึ่งแนวคิดของลิงค์ลิสต์จะกำหนดให้แต่ละสมาชิกจะประกอบด้วย ข้อมูล (Data) และลิงก์ (Link) โดยข้อมูลอาจประกอบด้วยหลายฟิลด์ก็ได้
การดำเนินงานพื้นฐานของลิสต์ (Basic Operations of List)
1. การแทรก (Insertion)
2. การลบ (Deletion)
3. การปรับปรุง (Updation)
4. การท่องเข้าไปในลิสต์ (Traversal)
โครงสร้างข้อมูลแบบนี้จะให้ความสะดวกแก่การจัดการข้อมูลมากอย่างไรก็ดีในบางครั้งก็ให้ความยุ่งยากแก่ผู้ใช้เนื่องจากจะซับซ้อนกว่าแบบใช้อาร์เรย์ข้อจำกัดของการใช้อาร์เรย์คืออาร์เรย์มีขนาดคงที่ ถ้าเราจะใช้อาร์เรย์ขนาด 100 ช่องเมื่อใช้หมด 100 ช่องก็ใช้อาร์เรย์นั้นไม่ได้ถ้าไม่อนุญาตให้เคลียร์พื้นที่อาร์เาย์เพื่อใช้ซ้ำถึงแม้อนุญาตให้เคลียร์พื้นที่อาร์เรย์เพื่อใช้ซ้ำก็ไม่เป็นการสะดวกเนื่องจากอาจต้องตรวจทุกช่องในอาร์เรย์เพื่อหาว่าช่องไหนสามารถใช้ซ้ำได้นอกจากนี้การใช้พื้นที่ซ้ำยังต้องเลื่อนข่าวสารทั้งหมดไปอยู่ในส่วนอาร์เรย์อีกประการคือในภาวะการทำงานแบบ real - time ที่ต้องมีการนำข้อมูลเข้า (insertion) หรือดึงข้อมูลออก (deletion) อาร์เรย์จะไม่สะดวกแก่การใช้มากในภาวะการทำงานแบบนี้โครงสร้างแบบลิงค์ลิสต์จะสะดวกกว่า การแทนแบบใช้พอยเตอร์นี้เราต้องใช้พื้นที่เพิ่มเติมเป็นส่วนของพอยน์เตอร์ (pointer) หรือลิงค์ (link) เพื่อแสดงให้เห็นขัดว่าโหนดที่ต่อจากโหนดนั้นคือโหนดใดลักษณะของแต่ละโหนดจึงประกอบด้วยช่อง 2 ช่อง
สมมติว่าเราจะแทนชุดข่าวสารที่ประกอบด้วย A,B,C ลักษณะการแทนจะเป็นไปตามรูปซึ่งเป็นภาพแสดงแนวคิดการเก็บแบบหนึ่งส่วนการเก็บข่าวสาร A,B,C แท้จริงแล้วจะเป็นในรูปไหนก็ได้แต่ก็ต้องสอดคล้องกับแนวความคิดนี้ รูปที่ 3 แสดงถึงความเป็นไปได้อีกแบบหนึ่งเมื่อข่าวสาร A,B,C อยู่ในพื้นที่ความจำ
รูปการแทนโครงสร้างแบบลิงค์ลิสต์
ข่าวสาร A อยู่ที่ตำแหน่ง 5000 ดูได้จากค่าที่ตำแหน่ง 6000 ผู้ใช้จะต้องรู้ว่า head node ของค่าชุดนี้อยู่ที่แอดเดรส 6000 ส่วนค่า A,B,C ผู้ใช้ไม่ทราบว่าอยู่ที่ใดยกเว้นแต่จะตามพอยน์เตอร์เข้าไป จากตำแหน่ง 6000 เรารู้ว่าค่าที่อยู่ที่ตำแหน่ง 5000 คือค่าแรก (ค่า A ) จากส่วนพอยน์เตอร์ของ A (ที่ตำแหน่ง 5001) เรารู้ว่าค่าถัดไป (ค่าB) อยู่ที่ตำแหน่ง 5600 เราตามพอยน์เตอร์ไปยังตำแหน่ง 5600 พบ B ค่าพอยน์เตอร์ของ B ที่ตำแหน่ง 5601 เป็นแอดเดรสของค่าถัดไป (ค่า C) ซึ่งอยู่ที่ตำแหน่ง 5508 จากค่า C เมื่อพิจารณาค่าพอยน์เตอร์ของ C พบว่าค่า - 1 ซึ่งหมายถึงว่าสิ้นสุดของค่าชุดนี้แล้ว อนึ่งผู้ใช้ไม่สามาร5นำค่า A หรือ B หรือ C มาใช้โดยตรงอย่าในอาร์เรย์ ผู้ใช้ต้องเดิน เข้าไปหาค่าเหล่านี้ลักษณะการหาค่าแบบนี้คล้าย ๆ กับการหาค่าในเทปซึ่งเรียกว่า การหาค่าแบบลำดับ (sequential access) ซึ่งในทางปฏิบัติสำหรับระบบโปรแกรมภาษาชั้นสูงเราอาจใช้อาร์เรย์เป็นตัวเก็บค่า A,B,C และใช้อีกหนึ่งอาร์เรย์เป็นตัวเก็บพอยน์เตอร์ดังรูปซึ่งผู้ใช้ต้องทราบว่าค่าแรกของข่าวสารชุดนี้อยู่ที่ตำแหน่งที่ 2 ในอาร์เรย์ INFO (3)
รูปการแทนลิงค์ลิสต์ด้วยอาร์เรย์ 2 ชุด
ลิงค์ลิสต์เดี่ยว (Singly Linked List)
ลิงค์ลิสต์เดี่ยวหมายถึงลิงค์ลิสต์ที่แต่ละข่าวสารมีการแสดงออกถึงลำดับก่อนหลังอย่างชัดเจนโดยใช้พอยน์เตอร์นั่นคือในแต่ละข่าวสารจะมีส่วนที่บอกว่าข่าวสารตัวต่อไปอยู่ที่ใดแต่ละข่าวสารจะเรียกว่าโหนด (node) แต่ละโหนดจะมี 2 ช่อง ดูรูปที่ 1 เป็นตัวอย่างเราจะใช้สัญลักษณ์ต่อไปนี้ในการเรียกชื่อแต่ละโหนด
NODE(P) หมายถึงโหนดที่ระบุ(ถูกชี้) โดยพอยน์เตอร์P
INFO(P) หมายถึงส่วนข่าวสารของโหนดที่ถูกชี้โดย P
LINK(P) หมายถึงส่วนแอดเดรสของโหนดที่ถูกชี้P
ในระบบการแทนโดยลิงค์ลิสต์เราจะสมมติว่าหน่วยความจำจะประกอบด้วยชิ้นส่วนความจำเป็นชิ้น ๆ ดังรูปที่ 2 (เรียกว่าโหนด)แทนที่จะเป้นแบบพื้นที่ความจำติดต่อกันไปดังอาร์เรย์ชิ้นส่วนความจำทั้งหมดนี้จะคล้องกันเป็นลิงค์ลิสต์เดี่ยวขนาดมหึมาซึ่งที่รวมความจำนี้เรียกว่า storage pool หรือหน่วยเก็บข้อมูลส่วนรวมเมื่อผู้ใช้ต้องการพื้นที่เก็บข่าวสารก็เรียกเอาโหนดจาก storage pool ถ้าผู้ใช้ไม่ต้องการใช้โหนดใดก็คืนโหนดนั้นไปยัง storage poolเพื่อผู้อื่นจะได้ใช้โหนดแรกของ storage pool จะถูกชี้โดยพอยน์เตอร์ที่ชื่อ AVAIL
แนวความคิดเรื่อง storage pool นั้น ตีความได้ในงานจริง ๆ เช่น storage pool อาจประกอบด้วยเก้าอี้นั่งทั้งหมดในเครื่องบินโดยสารลำหนึ่งหรือเป็นจำนวนที่นั่งที่ยังไม่ได้จองของสายการบินหนึ่งในเวลาใด ๆ
1.1การจัดสรรหน่วยเก็บข้อมูล(Storage Allocate) การจัดสรรหน่วยเก็บข้อมูลเป็นการนำโหนดออกจากหรือคืนโหนดสู่ storage pool ซึ่งจะสมมติว่ากระทำโดยฟังก์ชัน 2 ชุด คือ ALLOCATE P และ FREE P ซึ่งจะนิยามดังนี้
ALLOCATE P :นำโหนดหนึ่งออกจาก ALLOCATE P แล้วให้พอยน์เตอร์P ชี้ไปยังโหนดนั้น
FREE P : คืนโหนดที่ถูกชี้โดย P ไปยัง storage pool
การทำงานของ ALLOCATE P ดูได้จากรูปที่ 6 ซึ่งสมมติว่า storage pool ประกอบด้วยโหนด5 โหนด หลังการประมวลผล storage pool จะประกอบด้วย 4 โหนดและโหนดP เป็นโหนดที่นำมาใช้ได้ ฟังก์ชัน ALLOCATE P สามารถเขียนเป็นชุดคำสั่งได้ดังนี้
1.IF AVAIL = - 1 THEN แจ้งผู้ใช้ว่าไม่มีโหนดเหลือใน storage pool;
2.P = AVAIL ; / * ให้ P ชี้ไปยังโหนดแรก * /
3.AVAIL = LINK (AVAIL) ; / * ดูรูปที่ 4.7 * /
รูปการทำงานของ storage pool และคำสั่ง ALLOCATE P
LINK(AVAIL) หมายถึงส่วนพอยน์เตอร์ของโหนดแรกซึ่งบอกค่าตำแหน่งของโหนดถัดไปใน storage pool ดังนั้นค่า AVAIL ใหม่ คือแอดเดรสของโหนดที่สอง (อนึ่งเราจะได้ผลเหมือนกันถ้าเขียนว่า AVAIL = LINK (P) แทนคำสั่งที่ 3 ) ก็เพียงแต่โยงลูกศรไปยังโหนดถัดไปการทำความเข้าใจระบบการใช้งานของลิงค์ลิสต์ไม่มีทางใดดีกว่าวาดรูปการทำงานของแต่ละคำสั่ง ต่อไปนี้จะแสดงวิธีการทำความเข้าใจแบบนี้ตลอดหนังสือเล่มนี้ดังนั้นของให้ผู้อ่านฝึกหัดตามไปด้วย
ต่อจากคำสั่ง ALLOCATE P เป็นการทำความเข้าใจกับคำสั่ง FREE P ชุดคำสั่งแทน FREE P จะเป็นดังนี้
1.IF AVAIL = - 1 THEN DO ; AVAIL = P;
2. LINK(AVAIL) = - 1
3. END ;
4. ELSE DO ; LINK(P) = AVAIL ;
5. AVAIL = P; 6. END;
1.2 การนำข้อมูลเข้าสู่และออกจากลิงค์ลิสต์(Insertion and Deletion)
ก่อนอื่นขอให้พิจารณาดูการนำข่าวสาร 5 เข้าสู่อาร์เรย์A (ซึ่งมี 10 ช่อง) ที่ตำแหน่ง 3 ดังรูปที่ 10 เพื่อให้ค่าต่าง ๆ เรียงอยู่ในลำดับที่ถูกต้องจะเห็นได้ว่าในลักษณะนี้จะต้องมีการเลื่อนข่าวสารในอาร์เรย์อย่างมากเพื่อเปิดทางให้กับตัวที่เข้ามาใหม่กระบวนการเช่นนี้จะเสียเวลามากถ้าแต่ละข่าวสารเป็นเรคอร์ด (record) ขนาดใหญ่ในระบบที่มีการใช้ลิงค์ลิสต์ การนำข่าวสารเข้าหรือออกจะสะดวกมากเนื่องจากสามารถทำสำเร็จได้โดยคำสั่งไม่กี่คำสั่งเพื่อเปลี่ยนค่าพอยน์เตอร์อย่างมาก 2 ค่า เท่านั้น
1) การนำข้อมูลเข้า (Insertion) สมมติว่าเรามีลิงค์ลิสต์ H อยู่แล้ว (โหนดที่ถูกชี้โดย H คือ head node ของลิงค์ลิสต์นี้ ) และเราต้องการนำข่าวสารที่ถูกชี้โดยพอยน์เตอร์P (หรือโหนดP) ไปอยู่ต่อจากโหนดH1
INSERT : PROCEDURE (X,H1) /* ต้องการนำข่าวสาร X เข้าไปต่อท้ายโหนดที่ถูกชี้โดย H1 ในลิงค์ลิสต์ที่มี head node H */
/* ให้ Q เป็นพอยน์เตอร์ที่จะใช้ชั่วคราว */
/* เราจะนำ X มาใช้โดยตรงไม่ได้ ต้องสร้างโหนดเพื่อเก็บ X เสียก่อน */
ALLOCATE Q ;
INFO(Q) = X ;
/* ก่อนจะนำ X เข้า ต้องตรวจสอบกรณีพิเศษสองกรณีคือ (1) ตรวจสอบว่าลิงค์ลิสต์ H นี้ว่างเปล่าหรือไม่ (2) ตรวจสอบว่า H1 เป็นโหนดสุดท้ายหรือไม่ */
IF H = NULL / * สมมติว่าค่า NULL ทำงานเช่นเดียวกับ - 1 */ THEN /* แสดงว่าลิงค์ลิสต์ H ว่างเปล่า */ แจ้งให้ผู้ใช้ทราบและจบ ;
IF LINK(H1) = NULL
THEN /* แสดงว่าโหนดH1 เป็นโหนดสุดท้าย */
LINK (Q) = NULL;
ELSE /* แสดงว่าโหนดH1 ไม่ใช่โหนดสุดท้าย
*/ LINK (Q) = LINK(H1);
ELSE /* แสดงว่าโหนดH1 ไม่ใช่โหนดสุดท้าย
*/ LINK (Q) = LINK(H1);
LINK (H1) = Q;
/*ในที่สุดเราจะได้ลิงค์ลิสต์ใดแล้วแต่กรณี*/
หรือ
END
INSERT;
2)การนำข้อมูลออก (Deletion) ในการนี้เราต้องการนำข้อมูลในโหนดที่ต่อถัดจากโหนดH1 มาไว้ในตัวแปร X และให้คืนโหนดนั้นไปยัง storage pool
DELETE : PROCEDURE(X,H1)
/* ฟังก์ชันนี้จะนำข่าวสารในโหนดที่ถัดจาก H1 ไปเก็บไว้ใน X แล้วคืนโหนดนั้นไปยัง storage pool*/ /* มีกรณีพิเศษที่ต้องพิจารณาสามกรณีคือ
1)ลิงค์ลิสต์ H ว่างเปล่า
2)ลิงค์ลิสต์ H ประกอบด้วยโหนดเดียว
3)โหนดH1 เป็นโหนดสุดท้าย */
IF H = NULL
THEN /*แสดงว่าลิงค์ลิสต์นั้นมีโหนดเดียว */ แจ้งให้ผู้ใช้ทราบ ,จบ ;
IF LINK(H) = NULL THEN /* แสดงว่าลิงค์ลิสต์นั้นมีโหนดเดียว */แจ้งให้ผู้ใช้ทราบ , จบ;
IF LINK (H) =NULL และ LINK(H1) = NULL THEN /* แสดงว่าโหนดH1 เป็นโหนดสุดท้าย */ แจ้งให้ผู้ใช้ทราบ , จบ ;
/* เข้าสู่จุดนี้แสดงว่ามีโหนดต่อถัดจากโหนดH1 */
/* ให้ Q เป็นพอยน์เตอร์ชั่วคราว */
ขอให้สังเกตว่าเราไม่สามารถนำโหนดH1 ออกโดยตรงได้ทั้งนี้เนื่องจากว่าเราไม่ทราบว่าโหนดก่อนโหนดH1 อยู่ที่ใด ถ้าจะในโหนดH1 ออกเราต้องหาว่าโหนดก่อนโหนดH1 อยู่ที่ใด ซึ่งจะทำได้โดยเดินเข้าไปในลิงค์ลิสต์ตั้งต้นจาก H ตามพอยน์เตอร์ไปเรื่อย ๆ จนกว่าจะพบโหนดH1 การเดินเข้าไปในลิงค์ลิสต์จะมีความสำคัญซึ่งเราจะอธิบายถึงวิธีการดังกล่าวในหัวข้อต่อไป
3)การท่องไปในลิงค์ลิสต์สมมติว่ามีลิงค์ลิสต์ H อยู่แล้ว ถ้าจะหาว่าข่าวสาร X อยู่ในลิสต์นี้หรือไม่เราจะสามารถรู้ได้โดยการค้นหาแบบลำดับ (sequential search) ตามลำดับ ตั้งต้นจาก H การท่องไปในลิงค์ลิสต์ใหม่ไม่ได้ ดังนั้นเราจะใช้พอยน์เตอร์อีกตัวมาเป็นผู้ช่วย (auxiliary pointer) เพื่อดึงตัว H1 ไปยังโหนดถัดไ»
เมื่อเราเข้าใจถึงวิธีการท่องไปในลิงค์ลิสต์แล้ว อัลกอริทึม เพื่อหาค่า X จะเขียนได้ดังนี้
SEARCHX : PROCEDURE (X) ;
/* อัลกอริทึมนี้จะหาว่า X อยู่ในลิงค์ลิสต์ H หรือไม่ */
/* ให้ H1 = เป็นพอยน์เตอร์ชั่วคราว */
IF H = NULL THEN แจ้งให้ผู้ใช้ทราบว่าลิงค์ลิสต์ H ว่างเปล่า , จบ ;
H1 = H ; /* H1 ชี้ไปยังโหนดที่อยู่หัวของลิงค์ลิสต์ */
DO WHILE (INFO(H1)นX)
IF LINK(H1) = NULL THEN GOTO OUT ;
H1 = LINK(H1);
END;
OUT:IF INFO(H1) = X THEN แจ้งให้ผู้ใช้ทราบ , จบ;
มิฉะนั้นแจ้งให้ผู้ใช้ทราบว่า X ไม่อยู่ในลิงค์ลิสต์ H ;
END SEARCHX;
1.3 ลิงค์ลิสต์แบบวงกลม (Circular linked list) เมื่อเราให้พอยน์เตอร์ของโหนดสุดท้ายในลิงค์ลิสต์(ที่มีโหนดแรกคือโหนด H) ชี้ไปยังโหนดแรก เราจะได้โครงสร้างลิงค์ลิสต์แบบวงกลมดังรูปที่18 โครงสร้างแบบนี้สะดวกกว่าแบบลิงค์ลิสต์เดี่ยวธรรมดาในแง่ที่ว่าถัดจากโหนดสุดท้ายก็เป็นโหนดแรกเลยดังนั้นการไล่พอยเตอร์จึงมีความสะดวกในบางครั้งเพราะพอยน์เตอร์จะไม่มีโอกาสตกหายไประหว่างการท่องไปในลิงค์ลิสต์
ลิงค์ลิสต์คู่ (Doubly Linked List)
ลิงค์ลิสต์คู่ (Doubly Linked List) ลิงค์ลิสต์แบบนี้เป็นลิงค์ลิสต์ที่แต่ละโหนดมีสองพอยน์เตอร์คือ LLINK และ RLINK ซึ่งจะชี้ไปยังโหนดข้างซ้ายและข้างขวาของโหนดนั้นตามลำดับ ตัวอย่างเช่นถ้าต้องการจะเก็บค่า A,B,C,D ในลิงค์ลิสต์ชนิดนี้จะได้โครงสร้างซึ่งปลายทั้งสองข้างของลิงค์ลิสต์ชนิดนี้จะมีพอยน์เตอร์ F และ R แสดงถึงโหนดแรกในทิศนั้น ถ้าใช้อาร์เรย์สร้างลิงค์ลิสต์ตามรูปที่ 19 จะต้องใช้อาร์เรย์ 3 ชุดคือ อาร์เรย์สำหรับช่องข่าวสาร (INFO) , อาร์เรย์สำหรับพอยน์เตอร์ทางซ้าย (LLINK) และอาร์เรย์สำหรับพอยน์เตอร์ทางขวา (RLINK
เมื่อเปรียบเทียบลิงค์ลิสต์คู่กับลิงค์ลิสต์เดี่ยวจะเห็นได้ชัดว่าลิงค์ลิสต์คู่ต้องใช้เนื้อที่มากกว่า เนื่องจากต้องใช้ 2 พอยน์เตอรืสำหรับแต่ละโหนดแน่นอนที่เสียไปนั้นก็เพื่อที่จะได้สิ่งบางอย่างเพิ่มเติม นั่นคือความสะดวกในการนำข่าวสารเข้าหรือออกจากลิงค์ลิสต์ ในกรณีลิงค์ลิสต์คู่เราสามารถนำโหนดใหม่เข้าทาง ด้านหน้า หรือ ด้านหลังโหนดH1 ในลิงค์ลิสต์นั้นได้นอกจากนี้เรายังสามารถคืนโหนดH1 ไปสู่ storage pool โดยตรงได้อีกด้วยอย่าลืมว่าเราไม่สามารถคืนโหนดH1 ไปสู่ storage pool ในกรณีลิงค์ลิสต์เดี่ยว
2.1 การนำข่าวสารเข้าสู่ลิงค์สิสต์คู๋สมมติว่าแต่ละโหนดใน storage pool ดังนั้นคำสั่ง ALLOCATE P จะก่อกำเนิดโหนด
เราจะสมมติว่ามีลิงค์ลิสต์คู่อย่าแล้ว และจะนำโหนดP ซึ่งเก็บข่าวสาร X เข้าสู่ลิงค์ลิสต์นี้ ที่ตำแหน่งถัดจากโหนดH1 ซึ่งจะเห้นได้ว่ากระบวนการนี้สำเร็จได้โดยการเปลี่ยนค่าพอยน์เตอร์4 ค่าอย่างไรกีดีลำดับการเปลี่ยนค่าพอยน์เตอร์มีความสำคัญมาก ถ้าเราทำตามลำดับ (1),(2),(3),(4) จะไม่สำเร็จ ส่วนรูปที่ 23
ลิงค์ลิสต์ (Linked List)
ลิสต์ (Lists) หรือรายการ ถือเป็นการจัดเก็บข้อมูลชนิดหนึ่งซึ่งข้อมูลเชื่อมต่อกันแบบเชิงเส้น แต่ละข้อมูลมักเรียกว่า อีลิเมนต์ (Element) หรือสมาชิก (Member) โดยแบ่งโดยพื้นฐานได้ 2 แบบคือแบบทั่วไป (General) และแบบจำกัด (Restricted) ซึ่งแนวคิดของลิงค์ลิสต์จะกำหนดให้แต่ละสมาชิกจะประกอบด้วย ข้อมูล (Data) และลิงก์ (Link) โดยข้อมูลอาจประกอบด้วยหลายฟิลด์ก็ได้
การดำเนินงานพื้นฐานของลิสต์ (Basic Operations of List)
1. การแทรก (Insertion)
2. การลบ (Deletion)
3. การปรับปรุง (Updation)
4. การท่องเข้าไปในลิสต์ (Traversal)
ไม่มีความคิดเห็น:
แสดงความคิดเห็น