Embedded Files
Home / ອານກໍລິກທຶມ / Linked List
ບົດທີ 3 Link list
ບົດທີ 3 Link list
- ລີ້ງລິດ (Link list)
ແມ່ນໂຄງສ້າງຂໍ້ມູນທີ່ປະກອບດ້ວຍການລວບລວມຂອງ nodes, ແຕ່ລະປະກອບດ້ວຍອົງປະກອບຂໍ້ມູນແລະການອ້າງອີງ (ຫຼື pointer) ໄປຫາ node ຕໍ່ໄປໃນລໍາດັບ. nodes ແມ່ນເຊື່ອມຕໍ່ໂດຍການອ້າງອິງເຫຼົ່ານີ້, ປະກອບເປັນໂຄງສ້າງຄ້າຍຄືຕ່ອງໂສ້. node ທໍາອິດໃນລໍາດັບແມ່ນເອີ້ນວ່າຫົວຂອງບັນຊີລາຍຊື່ເຊື່ອມຕໍ່, ແລະ node ສຸດທ້າຍເອີ້ນວ່າຫາງ. ຖ້າການອ້າງອີງຂອງ node ເປັນ null, ມັນຫມາຍຄວາມວ່າມັນເປັນ node ສຸດທ້າຍໃນບັນຊີລາຍຊື່ທີ່ເຊື່ອມຕໍ່.
ບັນຊີລາຍຊື່ທີ່ເຊື່ອມໂຍງແມ່ນໂຄງສ້າງຂໍ້ມູນແບບເຄື່ອນໄຫວ, ຊຶ່ງຫມາຍຄວາມວ່າພວກເຂົາສາມາດເຕີບໂຕຫຼືຫຼຸດລົງໃນຂະຫນາດໃນລະຫວ່າງການປະຕິບັດໂຄງການ. ລາຍຊື່ທີ່ເຊື່ອມໂຍງສາມາດຖືກນໍາໃຊ້ເພື່ອປະຕິບັດໂຄງສ້າງຂໍ້ມູນຕ່າງໆ, ເຊັ່ນ: stacks, queues, ແລະ ຕາຕະລາງ hash.
ມີສອງປະເພດຕົ້ນຕໍຂອງບັນຊີລາຍຊື່ທີ່ເຊື່ອມໂຍງ:
ບັນຊີລາຍຊື່ທີ່ເຊື່ອມຕໍ່ແບບດ່ຽວ: ໃນບັນຊີລາຍຊື່ທີ່ເຊື່ອມຕໍ່ດຽວ, ແຕ່ລະ node ມີການອ້າງອີງເຖິງ node ຕໍ່ໄປໃນລໍາດັບ, ແຕ່ບໍ່ແມ່ນກັບ node ທີ່ຜ່ານມາ. ໂຫນດສຸດທ້າຍໃນລໍາດັບມີການອ້າງອີງເຖິງ null. ບັນຊີລາຍຊື່ທີ່ເຊື່ອມຕໍ່ແບບດ່ຽວແມ່ນງ່າຍດາຍແລະມີປະສິດທິພາບ, ແຕ່ພວກມັນບໍ່ສາມາດຖືກຂ້າມຜ່ານຕາມລໍາດັບ.
ບັນຊີລາຍຊື່ທີ່ເຊື່ອມຕໍ່ສອງເທົ່າ: ໃນບັນຊີລາຍຊື່ທີ່ເຊື່ອມຕໍ່ສອງເທົ່າ, ແຕ່ລະ node ມີການອ້າງອີງເຖິງທັງສອງ nodes ຕໍ່ໄປແລະທີ່ຜ່ານມາໃນລໍາດັບ. node ທໍາອິດໃນລໍາດັບມີການອ້າງອີງເຖິງ null ສໍາລັບ node ທີ່ຜ່ານມາ, ແລະ node ສຸດທ້າຍມີການອ້າງອີງເຖິງ null ສໍາລັບ node ຕໍ່ໄປ. ບັນຊີລາຍຊື່ທີ່ເຊື່ອມຕໍ່ສອງເທົ່າແມ່ນສະລັບສັບຊ້ອນຫຼາຍກ່ວາບັນຊີລາຍຊື່ທີ່ເຊື່ອມຕໍ່ແບບດ່ຽວ, ແຕ່ພວກມັນສາມາດຜ່ານໄດ້ທັງທິດທາງຂ້າງຫນ້າແລະດ້ານຫລັງ.
ລາຍການເຊື່ອມຕໍ່ສາມາດນໍາໃຊ້ສໍາລັບຈຸດປະສົງຫຼາຍ, ເຊັ່ນ:
ການເກັບຮັກສາແລະການເຂົ້າເຖິງການເກັບກໍາຂໍ້ມູນ.
ການປະຕິບັດສູດການຄິດໄລ່ທີ່ຕ້ອງການການຈັດສັນຫນ່ວຍຄວາມຈໍາແບບເຄື່ອນໄຫວ, ເຊັ່ນ: ການຈັດລຽງແລະການຊອກຫາ.
ການປະຕິບັດໂຄງສ້າງຂໍ້ມູນເຊັ່ນ stacks, ຄິວ, ແລະຕາຕະລາງ hash.
ຄວາມເຂົ້າໃຈກ່ຽວກັບຄຸນສົມບັດແລະການດໍາເນີນການພື້ນຖານຂອງລາຍຊື່ທີ່ເຊື່ອມໂຍງແມ່ນຈໍາເປັນສໍາລັບການດໍາເນີນໂຄງການທີ່ມີປະສິດທິພາບແລະການເລືອກໂຄງສ້າງຂໍ້ມູນທີ່ເຫມາະສົມກັບຄໍາຮ້ອງສະຫມັກທີ່ກໍານົດ.
2. ປະເພດຂອງ List Link
2. ປະເພດຂອງ List Link
ມີສອງປະເພດຕົ້ນຕໍຂອງບັນຊີລາຍຊື່ທີ່ເຊື່ອມໂຍງ: ບັນຊີລາຍຊື່ທີ່ເຊື່ອມຕໍ່ແບບດ່ຽວແລະບັນຊີລາຍຊື່ທີ່ເຊື່ອມຕໍ່ສອງເທົ່າ.
ບັນຊີລາຍຊື່ທີ່ເຊື່ອມຕໍ່ແບບດ່ຽວ: ໃນບັນຊີລາຍຊື່ທີ່ເຊື່ອມຕໍ່ດຽວ, ແຕ່ລະ node ມີການອ້າງອີງເຖິງ node ຕໍ່ໄປໃນລໍາດັບ, ແຕ່ບໍ່ແມ່ນກັບ node ທີ່ຜ່ານມາ. ໂຫນດສຸດທ້າຍໃນລໍາດັບມີການອ້າງອີງເຖິງ null. ບັນຊີລາຍຊື່ທີ່ເຊື່ອມຕໍ່ແບບດ່ຽວແມ່ນງ່າຍດາຍແລະມີປະສິດທິພາບ, ແຕ່ພວກມັນບໍ່ສາມາດຖືກຂ້າມຜ່ານຕາມລໍາດັບ. ບັນຊີລາຍຊື່ທີ່ເຊື່ອມຕໍ່ແບບດ່ຽວແມ່ນໃຊ້ໃນຫຼາຍຄໍາຮ້ອງສະຫມັກ, ເຊັ່ນ: ການເກັບຮັກສາແລະການເຂົ້າເຖິງຂໍ້ມູນ, ການປະຕິບັດ algorithms, ແລະການສ້າງໂຄງສ້າງຂໍ້ມູນ.
ບັນຊີລາຍຊື່ທີ່ເຊື່ອມຕໍ່ສອງເທົ່າ: ໃນບັນຊີລາຍຊື່ທີ່ເຊື່ອມຕໍ່ສອງເທົ່າ, ແຕ່ລະ node ມີການອ້າງອີງເຖິງທັງສອງ nodes ຕໍ່ໄປແລະທີ່ຜ່ານມາໃນລໍາດັບ. node ທໍາອິດໃນລໍາດັບມີການອ້າງອີງເຖິງ null ສໍາລັບ node ທີ່ຜ່ານມາ, ແລະ node ສຸດທ້າຍມີການອ້າງອີງເຖິງ null ສໍາລັບ node ຕໍ່ໄປ. ບັນຊີລາຍຊື່ທີ່ເຊື່ອມຕໍ່ສອງເທົ່າແມ່ນສະລັບສັບຊ້ອນຫຼາຍກ່ວາບັນຊີລາຍຊື່ທີ່ເຊື່ອມຕໍ່ແບບດ່ຽວ, ແຕ່ພວກມັນສາມາດຜ່ານໄດ້ທັງທິດທາງຂ້າງຫນ້າແລະດ້ານຫລັງ. ບັນຊີລາຍຊື່ທີ່ເຊື່ອມຕໍ່ສອງເທົ່າແມ່ນເປັນປະໂຫຍດໃນເວລາທີ່ທ່ານຕ້ອງການຜ່ານບັນຊີລາຍຊື່ທັງສອງທິດທາງຫຼືເວລາທີ່ທ່ານຕ້ອງການລຶບໂຫນດຢ່າງມີປະສິດທິພາບ.
ນອກເຫນືອຈາກບັນຊີລາຍຊື່ທີ່ເຊື່ອມຕໍ່ແບບດ່ຽວ ແລະ ສອງເທົ່າ, ຍັງມີບາງການປ່ຽນແປງອື່ນໆຂອງລາຍຊື່ທີ່ເຊື່ອມໂຍງທີ່ຖືກນໍາໃຊ້ຫນ້ອຍກວ່າ:
ບັນຊີລາຍຊື່ທີ່ເຊື່ອມໂຍງເປັນວົງກົມ: ໃນບັນຊີລາຍຊື່ທີ່ເຊື່ອມຕໍ່ເປັນວົງ, ໂຫນດສຸດທ້າຍໃນລໍາດັບມີການອ້າງອີງເຖິງໂຫນດທໍາອິດ, ປະກອບເປັນລະບົບຕ່ອງໂສ້ວົງ. ບັນຊີລາຍຊື່ທີ່ເຊື່ອມຕໍ່ເປັນວົງແມ່ນເປັນປະໂຫຍດໃນຄໍາຮ້ອງສະຫມັກທີ່ທ່ານຈໍາເປັນຕ້ອງຜ່ານບັນຊີລາຍຊື່ທີ່ບໍ່ມີກໍານົດຫຼືຢູ່ໃນ loop.
ບັນຊີລາຍຊື່ທີ່ເຊື່ອມຕໍ່ Sentinel: ໃນບັນຊີລາຍຊື່ທີ່ເຊື່ອມຕໍ່ sentinel, node ພິເສດທີ່ເອີ້ນວ່າ sentinel ແມ່ນຖືກນໍາໃຊ້ເພື່ອຫມາຍຈຸດເລີ່ມຕົ້ນຫຼືສິ້ນສຸດຂອງບັນຊີລາຍຊື່. ບັນຊີລາຍຊື່ທີ່ເຊື່ອມໂຍງ Sentinel ແມ່ນເປັນປະໂຫຍດໃນຄໍາຮ້ອງສະຫມັກທີ່ທ່ານຈໍາເປັນຕ້ອງເຮັດໃຫ້ເງື່ອນໄຂຊາຍແດນງ່າຍດາຍຫຼືຈັດການລາຍການຫວ່າງເປົ່າ.
ຄວາມເຂົ້າໃຈປະເພດຕ່າງໆຂອງລາຍຊື່ທີ່ເຊື່ອມໂຍງແລະຄຸນສົມບັດຂອງພວກມັນແມ່ນສໍາຄັນສໍາລັບການເລືອກປະເພດລາຍຊື່ທີ່ເຊື່ອມໂຍງທີ່ເຫມາະສົມສໍາລັບຄໍາຮ້ອງສະຫມັກທີ່ກໍານົດ.
3. ຄວາມສາມາດພື້ນຖານຂອງ List link
3. ຄວາມສາມາດພື້ນຖານຂອງ List link
ລາຍການທີ່ເຊື່ອມຕໍ່ສະຫນັບສະຫນູນການດໍາເນີນງານພື້ນຖານຈໍານວນຫນຶ່ງທີ່ຖືກນໍາໃຊ້ທົ່ວໄປໃນການດໍາເນີນໂຄງການ, ລວມທັງ:
Insertion: ການເພີ່ມ node ໃໝ່ໃສ່ລາຍຊື່ທີ່ເຊື່ອມຕໍ່ຢູ່ໃນຕຳແໜ່ງສະເພາະ ຫຼືຢູ່ທ້າຍລາຍການ. ການແຊກໃສ່ສາມາດເຮັດໄດ້ຢູ່ທີ່ຫົວ, ຫາງ, ຫຼືຕໍາແຫນ່ງໃດໆໃນບັນຊີລາຍຊື່ທີ່ເຊື່ອມຕໍ່. ເມື່ອໃສ່ node, ການອ້າງອິງຂອງ nodes ທີ່ຢູ່ໃກ້ຄຽງຕ້ອງໄດ້ຮັບການປັບປຸງເພື່ອຮັກສາຄວາມສົມບູນຂອງບັນຊີລາຍຊື່ທີ່ເຊື່ອມຕໍ່.
ການລຶບ: ການຖອນ node ທີ່ມີຢູ່ແລ້ວອອກຈາກບັນຊີລາຍຊື່ທີ່ເຊື່ອມຕໍ່ຢູ່ໃນຕໍາແຫນ່ງສະເພາະຫຼືອີງໃສ່ມູນຄ່າຂອງມັນ. ການລຶບສາມາດເຮັດໄດ້ຢູ່ທີ່ຫົວ, ຫາງ, ຫຼືຕໍາແຫນ່ງໃດໆໃນບັນຊີລາຍຊື່ທີ່ເຊື່ອມຕໍ່. ເມື່ອລຶບ node, ການອ້າງອິງຂອງ nodes ທີ່ຢູ່ໃກ້ຄຽງຕ້ອງໄດ້ຮັບການປັບປຸງເພື່ອຮັກສາຄວາມສົມບູນຂອງບັນຊີລາຍຊື່ທີ່ເຊື່ອມຕໍ່.
ການເຂົ້າເຖິງ: ດຶງຂໍ້ມູນອົງປະກອບຂອງ node ໃນລາຍຊື່ທີ່ເຊື່ອມໂຍງໂດຍໃຊ້ການອ້າງອີງຂອງມັນ. ການເຂົ້າເຖິງອົງປະກອບຂໍ້ມູນຂອງ node ໃຊ້ເວລາຄົງທີ່.
ຄົ້ນຫາ: ຊອກຫາ node ໃນບັນຊີລາຍຊື່ທີ່ເຊື່ອມໂຍງທີ່ປະກອບດ້ວຍຄ່າສະເພາະ. ການຄົ້ນຫາເສັ້ນແມ່ນວິທີການທົ່ວໄປທີ່ໃຊ້ເພື່ອຊອກຫາ node ໃນບັນຊີລາຍຊື່ທີ່ເຊື່ອມຕໍ່. ໃນການຊອກຫາເສັ້ນຊື່, ແຕ່ລະ node ໃນບັນຊີລາຍຊື່ທີ່ເຊື່ອມຕໍ່ຈະຖືກປຽບທຽບກັບມູນຄ່າເປົ້າຫມາຍຈົນກ່ວາການຈັບຄູ່ຈະພົບເຫັນຫຼືສິ້ນສຸດຂອງບັນຊີລາຍຊື່.
Traversal: ການໄປຢ້ຽມຢາມແຕ່ລະ node ໃນບັນຊີລາຍຊື່ທີ່ເຊື່ອມໂຍງໃນຄໍາສັ່ງສະເພາະ. ຂ້າມຜ່ານສາມາດເຮັດໄດ້ໂດຍໃຊ້ loop ທີ່ເຮັດຊ້ຳໆໃນແຕ່ລະ node ໃນລາຍຊື່ທີ່ເຊື່ອມຕໍ່. ຄໍາສັ່ງຂອງ traversal ສາມາດໄປຂ້າງຫນ້າຫຼືກັບຄືນໄປບ່ອນ, ແລະສາມາດເຮັດໄດ້ໃນຮູບແບບເສັ້ນຫຼືບໍ່ມີເສັ້ນ.
ຄວາມສັບສົນທີ່ໃຊ້ເວລາຂອງການດໍາເນີນງານເຫຼົ່ານີ້ແມ່ນຂຶ້ນກັບການປະຕິບັດສະເພາະຂອງບັນຊີລາຍຊື່ທີ່ເຊື່ອມໂຍງແລະພາສາການຂຽນໂປຼແກຼມທີ່ຖືກນໍາໃຊ້. ຕົວຢ່າງ, ການເຂົ້າເຖິງອົງປະກອບຂໍ້ມູນຂອງ node ໃຊ້ເວລາຄົງທີ່, ໃນຂະນະທີ່ການຊອກຫາ node ໃນບັນຊີລາຍຊື່ທີ່ບໍ່ໄດ້ຈັດຮຽງແມ່ນໃຊ້ເວລາເສັ້ນຊື່.
ມັນເປັນສິ່ງສໍາຄັນທີ່ຈະສັງເກດວ່າລາຍການທີ່ເຊື່ອມຕໍ່ໃຊ້ຫນ່ວຍຄວາມຈໍາຫຼາຍກວ່າ arrays ເພາະວ່າແຕ່ລະ node ຕ້ອງໄດ້ເກັບຮັກສາຄໍາອ້າງອີງໃສ່ node ຕໍ່ໄປ (ແລະອາດຈະເປັນກ່ອນຫນ້ານີ້). ນອກຈາກນັ້ນ, ລາຍຊື່ທີ່ເຊື່ອມໂຍງແມ່ນບໍ່ເຫມາະສົມສໍາລັບການເຂົ້າເຖິງອົງປະກອບແບບສຸ່ມເພາະວ່າພວກເຂົາຕ້ອງຖືກຂ້າມຜ່ານຕາມລໍາດັບເພື່ອໄປຫາຈຸດສະເພາະ. ຢ່າງໃດກໍຕາມ, ບັນຊີລາຍຊື່ທີ່ເຊື່ອມຕໍ່ແມ່ນເປັນປະໂຫຍດໃນເວລາທີ່ການຈັດສັນຫນ່ວຍຄວາມຈໍາແບບເຄື່ອນໄຫວແມ່ນຈໍາເປັນຫຼືໃນເວລາທີ່ການແຊກແລະການລຶບເລື້ອຍໆແມ່ນຈໍາເປັນ.
Page updated
Google Sites
Report abuse