¿¬°á ¸®½ºÆ®(Linked List)

¡á Ãß»óÈ­ ÀÚ·áÇü(ADT : Abstract Data Type)

- ÀÚ·áÇü(°³³ä)°ú ±âº»¿¬»ê À¯ÇüÀÇ ÁýÇÕÀ¸·Î ±âº»¿¬»êÀ» ¹®Á¦ÇØ°á ÇÁ·Î±×·¥ÀÇ ±¸Çö°ú ºÐ¸®ÇÏ¿© ¸ðµâÈ­ ÇÁ·Î±×·¡¹ÖÀ» °¡´ÉÇÏ°Ô ÇÏ¿© µð¹ö±ë, °øµ¿ ÇÁ·Î±×·¡¹Ö, ½Ã½ºÅÛ È®Àå µîÀÌ ¿ëÀÌÇÔ.
- »ç·Ê : ¸®½ºÆ®(list) ÀÏ·ÃÀÇ ¼ø¼­°¡ ÀÖ´Â ÀÚ·á(node)µéÀÇ ÁýÇÕ
            (±âº»¿¬»ê : find, insert, delete, make_empty, print_list µî)

  Ãß»óÈ­ÀÚ·áÇüÀº ¸ðµâÈ­ ¼³°èÀÇ È®ÀåÀ¸·Î º¼ ¼ö ÀÖÀ¸¸ç, ÀÏ·ÃÀÇ ¿¬»êÇüŸ¦ ¸ð¾Æ ³õÀº °ÍÀ¸·Î ±×·¯ÇÑ ¿¬»êÀÇ ±¸Çö¹æ¹ý°ú ºÐ¸®ÇØ ÁÁÀº °ÍÀÌ´Ù. Á¤¼ö³ª ½Ç¼ö¸¦ ÀÚ·áÇüÀ̶ó°í ºÎ¸£µíÀÌ ¸®½ºÆ®, ÁýÇÕ, ±×·¡ÇÁ¸¦ Ãß»óÈ­ÀÚ·áÇüÀ̶ó°í ºÎ¸¥´Ù. Á¤¼ö³ª ½Ç¼ö¸¦ °¡Áö°í µ¡¼À°ú °ö¼ÀÀ» ÇϵíÀÌ Ãß»óÈ­ÀÚ·áÇüµµ ±âº»¿¬»êÀÌ ÀÖ´Ù. ¿¹¸¦ µé¸é ÁýÇÕ(set) Ãß»óÈ­ÀÚ·áÇü¿¡¼­ ÁýÇÕÀÇ ÅëÇÕ(union), ¿ä¼ÒÀÇ Å½»ö(find) µîÀ» ±âº»¿¬»êÀ¸·Î º¼ ¼ö ÀÖ´Ù. ÀÚ·áÃß»óÈ­ÀÇ ±âº»°³³äÀº ÀÌ·¯ÇÑ ±âº»¿¬»êÀ» ¸ðµâÈ­ÇÏ¿© ÇÁ·Î±×·¥ÇÏ¸é ´Ù¸¥ °÷¿¡¼­´Â µµ´Ù½Ã ÇÁ·Î±×·¥ÇÏÁö ¾Ê°í ÇÔ¼öÈ£Ãâ¿¡ ÀÇÇÏ¿© ºÒ·¯ ¾²µµ·Ï ÇÑ´Ù´Â °ÍÀÌ´Ù. µû¶ó¼­ ÇÁ·Î±×·¥ ¼öÁ¤½Ã ÃÖ¼ÒÇÑÀÇ ³ë·Â¸¸ ÇÊ¿äÇÏ°Ô µÈ´Ù. Ãß»óÈ­ÀÚ·áÇüÀ» ±ÔÁ¤ÇÒ ¶§¿¡´Â ±âº»¿¬»êÀ» ÇÔ²² ±ÔÁ¤Çϴµ¥ ¾î¶°ÇÑ ¿¬»êµéÀ» ±âº»¿¬»êÀ¸·Î ÇÒ °ÍÀ̳Ĵ Á¤ÇØÁø ±ÔÄ¢ÀÌ ¾øÀ¸¸ç ¼³°èÀÚÀÇ Àǵµ¿¡ µû¶ó ´Þ¶óÁø´Ù. ¿ä¾àÇϸé Ãß»óÈ­ÀÚ·áÇüÀ̶õ ÀÚ·áÇü°ú ±âº»¿¬»êÀÇ À¯ÇüÀ» ÇÔ²² ±ÔÁ¤ÇÏ°í ¿¬»êÀÇ ±¸ÇöÀº ºÐ¸®ÇÔÀ¸·Î½á ¸ðµâÈ­ ÇÁ·Î±×·¥À» °¡´ÉÇÏ°Ô ÇÏ´Â °ÍÀÌ´Ù.