การสร้างสแตกด้วยลิงค์ลิสต์

การสร้างสแตกด้วยลิงค์ลิสต์ ในการสร้างสแตกด้วยลิงค์ลิสต์ หมายถึงเราเลือกการแทนที่ข้อมูลของสแตกด้วยลิงค์ลิสต์ซึ่งเป็นการจัดสรรเนื้อที่หน่วยความจำแบบไดนามิก นั้นคือ หน่วยความจำจะถูกจัดสรรเมื่อมีการขอใช้จริง ๆ ระหว่างการประมวลผลโปรแกรมผ่านตัวแปรชนิด pointer การสร้างสแตกนี้จะสร้างในยูนิตชื่อ StackUL โหนดและลิงค์ ลิงค์ลิสต์หรือลิสต์ เป็นโครงสร้างข้อมูลแบบหนึ่งซึ่งประกอบด้วยข่าวสารหรือสมาชิก หลายๆตัว โดยที่ข่าวสารหรือสมาชิกเหล่านั้นจะถูกติดกันเป็นสายยาว โดยมีส่วน พอยน์เตอร์เป็นตัวเชื่อม แต่ละข่าวสารหรือข่าวสารในลิสต์ จะเรียกว่า โหนด ( Node ) โหนด หรือ cell คือ พื้นที่ในหน่วยความจำ ซึ่งประกอบด้วยอย่างน้อย 2 ฟิลด์ คือ INFO และ LINK INFO หมายถึง ส่วนเก็บข้อมูลของข่าวสารหรือสมาชิกในลิสต์ LINK หมายถึง ส่วนเก็บตำแหน่งหรือที่อยู่ของโหนดในลิสต์ถัดจากโหนดที่ชี้อยู่ LINK หมายถึง ตัวที่ใช้เชื่อมโยงข้อมูลแต่ละโหนดให้อยู่รวมกันเป็นสายข้อมูล ตัวอย่าง INFO LINK โหนด P : NODE (P) หมายถึง โหนดที่ถูกชี้โดยพอยน์เตอร์ P INFO (P) หมายถึง ส่วนที่เก็บข่าวสารหรือสมาชิกของโหนด P LINK (P) หมายถึง ส่วนตำแหน่งหรือที่อยู่ของโหนดถัดจากโหนด P การท่องเข้าไปในลิสต์
 
 
การท่องเข้าไปในลิสต์   เป็นลักษณะการเข้าถึงสมาชิกในลิสต์แต่ละตัวตั้งแต่ตัวแรกแรกไปอาจเพื่อจุดประสงค์บางอย่าง เช่น ต้องการพิมพ์ข้อมูลในลิสต์ เพื่อนับจำนวนข้อมูลในลิสต์ เพื่อหาข้อมูลในลิสต์ เราไม่สามารถที่จะไปยังสมาชิกตัวที่ใดๆ ในลิงค์ลิสต์โดยไม่ผ่านสมาชิกตัวที่ 1 การท่องไปในลิงค์ลิสต์ต้องใช้พอยน์เตอร์เพื่อท่องไปในลิสต์ ดังอัลกอริทึม 1. trav:=head; 2. while trav <> null do 3. begin print info (trav); trav := link(trav); 6. end; คำสั่งแรกให้พอยน์เตอร์ trav ชี้ที่ต้นลิสต์ คำสั่งที่สองตรวจสอบว่าในระหว่างที่พอยน์เตอร์ trav ยังไม่มีค่าเป็น null ให้ทำตามคำสั่งในบรรทัดที่ 4 และ 5 คือให้พิมพ์ข้อมูลใน info ฟิลด์ของโหนดที่ชี้ด้วย trav นั้น หลังจากนั้นเลื่อนพอยน์เตอร์ trav ชี้โหนดถัดไป คำสั่งในบรรทัดที่ 2 ที่ถูกทำซ้ำๆจนกว่าเงื่อนไขในคำสั่งไม่เป็นจริง คือ จะหยุดทำงานในบรรทัดที่ 4 และ 5 เมื่อพอยน์เตอร์ trav = null คือ trav ชี้ตกลิสต์ไปแล้ว การเพิ่มและลบข้อมูลในลิงค์ลิสต์ โอเปอร์เรชันพื้นฐานในลิงค์ลิสต์มี 2 อย่างคือ การเพิ่มข้อมูลและการลบหรือดึงข้อมูล ไม่ ว่าจะเป็นการเพิ่มหรือลบข้อมูลทำได้ 2 จุดคือ กระทำที่ต้นลิสต์ และกระทำที่หลังโหนด ที่ชี้ด้วย p ใดๆ
 
 
การเพิ่มข้อมูลในลิงค์ลิสต์ หมายถึง การเพิ่มโหนดใหม่ที่บรรจุข้อมูลที่เพิ่มเข้าในลิงค์ลิสต์ และการลบข้อมูลในลิงค์ลิสต์ หมายถึง การลบโหนดที่บรรจุข้อมูลที่ต้องการลบออกจากลิงค์ลิสต์ ดังนั้นจึงขอแสดงขั้นตอนการเพิ่มโหนดและการลบโหนดในลิงค์ลิสต์ จากลิงค์ลิสต์ที่ชี้ด้วย Head และมี Node (New) ดังรูป (a) นี้ต้องการเพิ่มโหนด (New) ที่ต้นลิสต์มีขั้นตอนดังนี้ 1. Link (New) := head 2. Head := New เส้นไข่ปลา แสดงทางที่เกิดขึ้นพร้อมหมายเลขกำกับ เพื่อแสดงลำดับของขั้นตอน รูป (b) แสดงผลลัพธ์ของการเพิ่มโหนดที่ต้นลิสต์ ให้สังเกตว่าเราไม่สามารถสลับลำดับขั้นตอนเป็น 1. HEAD := NEW; 2. LINK (NEW) := HEAD; ลิสต์ว่าง ลิสต์ว่างเป็นลิสต์ที่มีสมาชิกเป็นโหนดว่างที่ได้จากโหนดที่ถูกนำออกจากลิสต์อื่นๆ และจาก ลิสต์ว่างนี้เอง ถ้าผู้ใช้ต้องการเพิ่มโหนดเข้าไปลิสต์หนึ่งลิสต์ใดก็สามารถนำไปใช้ได้ การเพิ่มโหนดเข้าลิสต์ว่างหรือการนำโหนดจากลิสต์ว่างนี้ไปใช้ ไม่ว่าจะกระทำที่ต้นลิสต์ หรือ ในตำแหน่งใดๆในลิสต์ ย่อมได้ผลที่เหมือนกัน ( เนื่องจากเป็นโหนดว่าง ) ดังนั้นการเพิ่มโหนดในลิสต์ว่าง และการนำโหนดจากลิสต์ที่เกิดขึ้นในหน่วยความจำ โหนดแต่ละโหนดไม่จำเป็นต้องอยู่ติดกัน การสร้างลิงค์ลิสต์ การสร้างลิงค์ลิสต์ หรือ การนำข้อมูลเก็บในโครงสร้างลิงค์ลิสต์ ก็คือ การเพิ่มลิสต์ข้อมูลเข้าลิสต์ ณ ตำแหน่งสุดท้ายตลอดจนข้อมูลหมด เช่น ลิสต์ L = ( 5,6,7) เมื่ออยู่ในโครงสร้างลิงค์ลิสต์หน้าตาจะเป็นดังนี้ ^ 7 6 5 head เพื่อความสะดวกในการสร้างลิงค์ลิสต์ต้องอาศัยพอยน์เตอร์อีกตัวหนึ่งที่คอยชี้โหนดสุดท้ายของลิสต์ตลอดเวลา เพื่อที่เมื่อมีข้อมูลที่จะเก็บในลิงค์ลิสต์ก็เพียงแต่เชื่อมต่อเข้ากับโหนดสุดท้ายของลิสต์ของลิงค์ลิสต์เท่านั้น ขั้นตอนเป็นดังนี้ โดยมี HEAD ชี้ต้นลิสต์ LAST 5 ^ HEAD เมื่อเพิ่มข้อมูล 6 เข้าไปในลิสต์ LAST 5 6 ^ HEAD เมื่อเพิ่มข้อมูล 7 เข้าไปในลิสต์ LAST 5 7 ^ 6 ^ HEAD
 
 
ในการสร้างสแตกด้วยลิงค์ลิสต์ หมายถึงเราเลือกการแทนที่ข้อมูลของสแตกด้วยลิงค์ลิสต์ซึ่งเป็นการจัดสรรเนื้อที่หน่วยความจำแบบไดนามิก นั้นคือ หน่วยความจำจะถูกจัดสรรเมื่อมีการขอใช้จริง ๆ ระหว่างการประมวลผลโปรแกรมผ่านตัวแปรชนิด pointer การสร้างสแตกนี้จะสร้างในยูนิตชื่อ StackUL โหนดและลิงค์ ลิงค์ลิสต์หรือลิสต์ เป็นโครงสร้างข้อมูลแบบหนึ่งซึ่งประกอบด้วยข่าวสารหรือสมาชิก หลายๆตัว โดยที่ข่าวสารหรือสมาชิกเหล่านั้นจะถูกติดกันเป็นสายยาว โดยมีส่วน พอยน์เตอร์เป็นตัวเชื่อม แต่ละข่าวสารหรือข่าวสารในลิสต์ จะเรียกว่า โหนด ( Node ) โหนด หรือ cell คือ พื้นที่ในหน่วยความจำ ซึ่งประกอบด้วยอย่างน้อย 2 ฟิลด์ คือ INFO และ LINK INFO หมายถึง ส่วนเก็บข้อมูลของข่าวสารหรือสมาชิกในลิสต์ LINK หมายถึง ส่วนเก็บตำแหน่งหรือที่อยู่ของโหนดในลิสต์ถัดจากโหนดที่ชี้อยู่ LINK หมายถึง ตัวที่ใช้เชื่อมโยงข้อมูลแต่ละโหนดให้อยู่รวมกันเป็นสายข้อมูล ตัวอย่าง INFO LINK โหนด P : NODE (P) หมายถึง โหนดที่ถูกชี้โดยพอยน์เตอร์ P INFO (P) หมายถึง ส่วนที่เก็บข่าวสารหรือสมาชิกของโหนด P LINK (P) หมายถึง ส่วนตำแหน่งหรือที่อยู่ของโหนดถัดจากโหนด P การท่องเข้าไปในลิสต์ การท่องเข้าไปในลิสต์เป็นลักษณะการเข้าถึงสมาชิกในลิสต์แต่ละตัวตั้งแต่ตัวแรกแรกไปอาจเพื่อจุดประสงค์บางอย่าง เช่น ต้องการพิมพ์ข้อมูลในลิสต์ เพื่อนับจำนวนข้อมูลในลิสต์ เพื่อหาข้อมูลในลิสต์ เราไม่สามารถที่จะไปยังสมาชิกตัวที่ใดๆ ในลิงค์ลิสต์โดยไม่ผ่านสมาชิกตัวที่ 1 การท่องไปในลิงค์ลิสต์ต้องใช้พอยน์เตอร์เพื่อท่องไปในลิสต์ ดังอัลกอริทึม 1. trav:=head; 2. while trav <> null do 3. begin print info (trav); trav := link(trav); 6. end; คำสั่งแรกให้พอยน์เตอร์ trav ชี้ที่ต้นลิสต์ คำสั่งที่สองตรวจสอบว่าในระหว่างที่พอยน์เตอร์ trav ยังไม่มีค่าเป็น null ให้ทำตามคำสั่งในบรรทัดที่ 4 และ 5 คือให้พิมพ์ข้อมูลใน info ฟิลด์ของโหนดที่ชี้ด้วย trav นั้น หลังจากนั้นเลื่อนพอยน์เตอร์ trav ชี้โหนดถัดไป คำสั่งในบรรทัดที่ 2 ที่ถูกทำซ้ำๆจนกว่าเงื่อนไขในคำสั่งไม่เป็นจริง คือ จะหยุดทำงานในบรรทัดที่ 4 และ 5 เมื่อพอยน์เตอร์ trav = null คือ trav ชี้ตกลิสต์ไปแล้ว การเพิ่มและลบข้อมูลในลิงค์ลิสต์ โอเปอร์เรชันพื้นฐานในลิงค์ลิสต์มี 2 อย่างคือ การเพิ่มข้อมูลและการลบหรือดึงข้อมูล ไม่ ว่าจะเป็นการเพิ่มหรือลบข้อมูลทำได้ 2 จุดคือ กระทำที่ต้นลิสต์ และกระทำที่หลังโหนด ที่ชี้ด้วย p ใดๆ การเพิ่มข้อมูลในลิงค์ลิสต์ หมายถึง การเพิ่มโหนดใหม่ที่บรรจุข้อมูลที่เพิ่มเข้าในลิงค์ลิสต์ และการลบข้อมูลในลิงค์ลิสต์ หมายถึง การลบโหนดที่บรรจุข้อมูลที่ต้องการลบออกจากลิงค์ลิสต์ ดังนั้นจึงขอแสดงขั้นตอนการเพิ่มโหนดและการลบโหนดในลิงค์ลิสต์ จากลิงค์ลิสต์ที่ชี้ด้วย Head และมี Node (New) ดังรูป (a) นี้ต้องการเพิ่มโหนด (New) ที่ต้นลิสต์มีขั้นตอนดังนี้
 
1. Link (New) := head
2. Head := New เส้นไข่ปลา แสดงทางที่เกิดขึ้นพร้อมหมายเลขกำกับ เพื่อแสดงลำดับของขั้นตอน รูป (b) แสดงผลลัพธ์ของการเพิ่มโหนดที่ต้นลิสต์ ให้สังเกตว่าเราไม่สามารถสลับลำดับขั้นตอนเป็น 1. HEAD := NEW; 2. LINK (NEW) := HEAD; ลิสต์ว่าง ลิสต์ว่างเป็นลิสต์ที่มีสมาชิกเป็นโหนดว่างที่ได้จากโหนดที่ถูกนำออกจากลิสต์อื่นๆ และจาก ลิสต์ว่างนี้เอง ถ้าผู้ใช้ต้องการเพิ่มโหนดเข้าไปลิสต์หนึ่งลิสต์ใดก็สามารถนำไปใช้ได้ การเพิ่มโหนดเข้าลิสต์ว่างหรือการนำโหนดจากลิสต์ว่างนี้ไปใช้ ไม่ว่าจะกระทำที่ต้นลิสต์ หรือ ในตำแหน่งใดๆในลิสต์ ย่อมได้ผลที่เหมือนกัน ( เนื่องจากเป็นโหนดว่าง ) ดังนั้นการเพิ่มโหนดในลิสต์ว่าง และการนำโหนดจากลิสต์ที่เกิดขึ้นในหน่วยความจำ โหนดแต่ละโหนดไม่จำเป็นต้องอยู่ติดกัน การสร้างลิงค์ลิสต์ การสร้างลิงค์ลิสต์ หรือ การนำข้อมูลเก็บในโครงสร้างลิงค์ลิสต์ ก็คือ การเพิ่มลิสต์ข้อมูลเข้าลิสต์ ณ ตำแหน่งสุดท้ายตลอดจนข้อมูลหมด เช่น ลิสต์ L = ( 5,6,7) เมื่ออยู่ในโครงสร้างลิงค์ลิสต์หน้าตาจะเป็นดังนี้ ^ 7 6 5 head เพื่อความสะดวกในการสร้างลิงค์ลิสต์ต้องอาศัยพอยน์เตอร์อีกตัวหนึ่งที่คอยชี้โหนดสุดท้ายของลิสต์ตลอดเวลา เพื่อที่เมื่อมีข้อมูลที่จะเก็บในลิงค์ลิสต์ก็เพียงแต่เชื่อมต่อเข้ากับโหนดสุดท้ายของลิสต์ของลิงค์ลิสต์เท่านั้น ขั้นตอนเป็นดังนี้ โดยมี HEAD ชี้ต้นลิสต์ LAST 5 ^ HEAD เมื่อเพิ่มข้อมูล 6 เข้าไปในลิสต์ LAST 5 6 ^ HEAD เมื่อเพิ่มข้อมูล 7 เข้าไปในลิสต์ LAST 5 7 ^ 6 ^ HEAD

 

ตัวอย่าง:

UNIT StackUL; INTERFACE CONST Maxsize = 100 { User supplied }; TYPE KeyType = 1..100 {ID}; DataType = RECORD Name : string[20]; Math, Stat, Comp : integer; END; StdElement = RECORD Key : Keytype ; Data : Datatype ; END; pointer = ^Node; Node = RECORD El : StdElement; Next : pointer; END; VAR Top : pointer; {Top is stack} PROCEDURE Create; PROCEDURE Push (E : StdElement); PROCEDURE Pop (VAR E : StdElement); FUNCTION Empty : boolean; FUNCTION Full : boolean; PROCEDURE Clear; IMPLEMENTATION PROCEDURE Create; BEGIN Top := nil; END; PROCEDURE Push(E : StdElement); VAR P : pointer ; BEGIN new(P); P^.El := E; P^.Next := Top; Top := P; END; PROCEDURE Pop(VAR E : StdElement); VAR P : pointer; BEGIN P := Top; E := P^.EL; Top := Top^.Next; dispose(P); END; FUNCTION Empty : boolean ; BEGIN IF Top = NIL THEN Empty := true ELSE Empty := false; END; FUNCTION Full : boolean ; BEGIN Full := false END; PROCEDURE Clear; VAR P : pointer; BEGIN WHILE Top <> NIL DO BEGIN P := Top; Top := Top^.Next; dispose(P); END; END; END. การกำหนดค่าพอยน์เตอร์ ให้ P และ R เป็นพอยน์เตอร์ชี้ไปยังโหนดดังแสดงในรูป (a ) และ Q เป็นพอยน์เตอร์ตัวหนึ่ง และต้องการให้ Q ชี้ไปที่โหนดเดียวกับที่ P ชี้อยู่ ใช้คำสั่ง Q := P (อ่านว่า Q ชี้ที่ P ชี้ ) ซึ่งแสดงไว้ดังรูป (b) และถ้าต้องการให้โหนด R เชื่อมให้อยู่ถัดจากโหนด P ให้เปลี่ยนเป็น LINK ฟิลด์ของโหนด P ให้เป็นค่าที่อยู่ในพอยน์เตอร์ R นั่นเอง ดังนั้นการเชื่อมโหนดทั้งสองให้ใช้คำสั่ง LINK (P) := R (อ่านว่า link ฟิลด์ของ P ชี้ที่ R ชี้ )