เรื่อง Linked List

เนื้อหา
- โครงสร้างข้อมูลแบบลิงค์ลิสต
- กระบวนงานและฟังกชั่นที่ใช้ดำเนินงานพื้นฐาน
- การสร้างลิงค์ลิสต
- ลิงค์ลิสต์แบบซับซ้อน

จุดประสงค์การเรียนรู้
1. เพื่อให้นักศึกษาทราบโครงสร้างข้อมูลแบบลิงค์ลิสต
2. เพื่อให้ทราบกระบวนการทำงานและฟังกชั่นที่ ใช้ดำเนินงานพื้นฐานของลิงค์ลิสต
3. เพื่อให้นักศึกษาทราบวิธีการสร้างลิงค์ลิสต
4. เพื่อให้นักศึกษาทราบการทางานของลิงค์ลิสต แบบซับซ้อน

ลิงค์ลิสต (Linked List) เป็นวิธีการเก็บ ข้อมูลอย่างต่อเนื่องของอิลิเม้นต์ต่าง ๆ โดยมีพอยเตอร์เป็นตัวเชื่อมต่อแต่ละอิลิเม้นท์ เรียกว่าโนด (Nodeซึ่งในแต่ละโนดจะประกอบไปด้วย 2 ส่วน คือ Dataจะเก็บข้อมูลของอิลิเม้นท์ และส่วนที่สอง คือ Link Field จะทำหน้าที่เก็บ ตำแหน่งของโนดต่อไปในลิสต

ในส่วนของdataอาจจะเป็นรายการเดียวหรือเป็นเรคคอร์ดก็ได้ในส่วนของ linkจะเป็นส่วนที่เก็บตำแหน่งของโหนดถัดไปใน โหนดสุดท้ายจะเก็บคา Null ซึ่งไม่ได้ชี้ไปยังตำแหน่งใด ๆ เป็นตัวบอกการ สิ้นสุดของลิสตในลิงค์ลิสตจะมีตัวแปรสำหรับชี้ ตำแหน่งลิสต (List pointer variable)ซึ่งเป็นที่เก็บตำแหน่งเริ่มต้นของลิสต ซึ่งก็ คือโหนดแรกของลิสตนั้นเอง ถ้าลิสต์ไม่มีข้อมูล ข้อมูลในโหนดแรกของลิสตจะเป็น Null

ในส่วนของdataอาจจะเป็นรายการเดียวหรือเป็นเรคคอร์ดก็ได้ในส่วนของ linkจะเป็นส่วนที่เก็บตำแหน่งของโหนดถัดไปใน โหนดสุดท้ายจะเก็บคา Null ซึ่งไม่ได้ชี้ไปยังตำแหน่งใด ๆ เป็นตัวบอกการ สิ้นสุดของลิสตในลิงค์ลิสตจะมีตัวแปรสำหรับชี้ ตำแหน่งลิสต (List pointer variable)ซึ่งเป็นที่เก็บตำแหน่งเริ่มต้นของลิสต ซึ่งก็ คือโหนดแรกของลิสตนั้นเอง ถ้าลิสต์ไม่มีข้อมูล ข้อมูลในโหนดแรกของลิสตจะเป็น Null

โครงสร้างข้อมูลแบบลิงค์ลิสตโครงสร้างข้อมูลแบบลิงค์ลิสตจะแบ่งเป็น 2 ส่วน คือ

1. Head Structure จะประกอบไปด้วย 3 ส่วน ได้แก่ จำนวนโหนดในลิสต (Count)พอยเตอร์ที่ชี้ไปยัง โหนดที่เข้าถึง(Pos) และพอยเตอร์ที่ชี้ไปยังโหนดข้อูมลแรกของลิสต (Head)

2. Data Node Structure จะประกอบไปด้วยข้อมูล (Data) และพอยเตอร์ที่ชี้ไปยังข้อมูลตัวถัดไป

กระบวนงานและฟังกชั่นทใช้ดำเนินงานพื้นฐาน

1. กระบวนงาน Create Listหน้าที่ สร้างลิสตว่างผลลัพธ์ ลิสตว่าง

Algorithm CreateList

Pre Nothing

Post Head node allocated or error returned

Return Head node pointer or null if memory overflow

1. if (memory available)

1 allocate (Pnew)

2 pNew->head = null pointer

3 pNew->count = 0
2. else

1 pNew = null poiter

3. return pNew

End CreateList

โครงสร้างข้อมูลแบบลิงค์ลิสต
โครงสร้างข้อมูลแบบลิงค์ลิสตจะแบ่งเป็น 2 ส่วน คือ
1. Head Structure จะประกอบไปด้วย 3 ส่วน ได้แก่
จำนวนโหนดในลิสต (Count)พอยเตอร์ที่ชี้ไปยัง โหนดที่เข้าถึง(Pos) และพอยเตอร์ที่ชี้ไปยังโหนดข้อูมลแรกของลิสต (Head)
2. Data Node Structure จะประกอบไปด้วยข้อมูล (Data) และพอยเตอร์ที่ชี้ไปยังข้อมูลตัวถัดไป

กระบวนงานและฟังกชั่นทใช้ดำเนินงานพื้นฐาน
1. กระบวนงาน Create List
หน้าที่ สร้างลิสตว่าง
ผลลัพธ์ ลิสตว่าง Algorithm CreateList
Pre Nothing
Post Head node allocated or error returned
Return Head node pointer or null if memory overflow
1. if (memory available)
1 allocate (Pnew)
2 pNew->head = null pointer
3 pNew->count = 0
2. else
1 pNew = null poiter
3. return pNew
End CreateList

2.กระบวนงาน Insert Nodeหน้าที่เพิ่มข้อมูลลงไปในลิสตบริเวณตำแหน่งที่ต้องการข้อมูลนำเข้าลิสต ข้อมูล และตำแหน่งผลลัพธ์ ลิสตที่มีการเปลี่ยนแปลง

Algorithm insertNode
val pPre ,
val dataIn )

Pre pList is a pointer to a valid list head structurep
Pre is a pointer todata’s logical predecessordataIn contains data to be inserted
Post data have been insert in sequence
Return true if successful, false if memory overflow
Allocate (pNew)
If (memory overflow)
1 return false
pNew->data = dataIn
3. If (pPre null)
1 pNew->link = pList->head
2 pList->head = pNew
5. else
1 pNew->link = pPre->link
2 pPre->link = pNew
6. pList->count = pList->count +1
7. Return true
End insertNode

3. กระบวนงาน Delete Node หน้าที่ลบสมาชิกในลิสตบริเวณตำแหน่งที่ต้องการข้อมูลนำเข้าข้อมูลและตำแหน่งผลลัพธ์ ลิสตที่มีการเปลี่ยนแปลง

Algorithm deleteNode
val pPre ,
val pLoc ,
ref dataOut )

Pre pList is a pointer to a valid list head structure
pPre is a pointer to predecessor node
pLoc is a pointer to node to be deleteddataOut is address to pass deleted data to

calling module
Post data have been delete and return to caller

1. dataOut = pLoc->data
2. if (pPre null)
1 pList->head = pLoc->link
3. Else1 pPre->link = pLoc->link
4. pList->count = pList->count - 1
5. Release (pLoc)
6. ReturnEnd deleteNode
4. กระบวนงาน Search listหน้าที่ค้นหาข้อมูลในลิสตที่ต้องการข้อมูลนำเข้าลิสตผลลัพธ์ ค่าจริงถ้าพบข้อมูล ค่าเท็จถ้าไม่พบข้อมูล

Algorithm searchList (
val pList val pPre ,
ref pLoc ,
val target )

Pre pList is a pointer to a valid list head structure
pPre is a pointer to receive predecessor
pLoc is a pointer to receive current node
target is the key being sought
Post pLoc points to first node with equal or greater key or null if target >
key of last node

pPre points to largest node smaller than key or null if target<>

Return true if found, false if not found
pPre = null
pLoc = pList->head
loop (pLoc not null AND target > pLoc->data.key)

1 pPre = pLoc
2 pLoc = pLoc->link
If (pLoc null)
1 found = false
else
1 if (target equal pLoc->data.key)
1 found = true
2 else
1 found = false
Return found
Return searchList

5.กระบวนงาน Traverse หน้าที่ ท่องไปในลิสตเพื่อเข้าถึงและประมวลผลข้อมูลนำเข้าลิสตผลลัพธ์ ขึ้นกับการประมวลผล เช่น เปลี่ยนแปลงค่าใน node , รวมฟิลด์ในลิสต , คำนวณค่าเฉลยของฟิลด์ เป็นต้น

Algorithm traverse
ref dataPtr)
Pre pList is a pointer to a valid list head structurefromWhere is 0 to start at the first elementdataPtr is address of a pointer to dataPost address placed in dataPtr and return true or if end of list, returnfalseReturn true if next element located, false if end of list