¸µÅ©µå¸®½ºÆ® ÀڷᱸÁ¶
ÃÑ ÆäÀÌÁö ¼ö : 3224

Àüü ÇÔ¼ö/¿ë¾î»çÀü
Facebook Joinc ±×·ì   Joinc QA »çÀÌÆ®



joinc´Â Firefox¿Í chrome¿¡¼­ Å×½ºÆ® Çß½À´Ï´Ù. IE¿¡¼­´Â Å×À̺íÀÌ ±úÁö°Å³ª À̹ÌÁö°¡ º¸ÀÌÁö ¾ÊÀ» ¼ö ÀÖ½À´Ï´Ù. ƯÈ÷ ±¸±Û DocsÀ̹ÌÁöÀÇ °æ¿ì ¿¢¹Úó¸®µÉ ¼ö ÀÖ½À´Ï´Ù.

¸µÅ©µå ¸®½ºÆ®

¸µÅ©µå ¸®½ºÆ®

À± »ó¹è

dreamyun@yahoo.co.kr

고친 과정
고침 0.82003³â 3¿ù 1ÀÏ 23½Ã
ÃÖÃÊ ¹®¼­ÀÛ¼º

1. Linked List

1.1. °³¿ä

Linked List(ÀÌÇÏ ¸µÅ©µå¸®½ºÆ®)´Â ½ºÅÃ, Å¥¿Í ÇÔ²² °¡Àå ±âº»ÀûÀÎ ÀڷᱸÁ¶°¡ µÈ´Ù. ÀڷᱸÁ¶ÀÇ À̸§°ú °°ÀÌ ¸µÅ©µå ¸®½ºÅ©´Â ÀÚ·áµéÀ» ¿¬°áµÈ ¸®½ºÆ®È­ ½ÃÄѼ­ °ü¸®ÇÑ´Ù.

¸µÅ©µå ¸®½ºÆ®´Â °¢ µ¥ÀÌÅ͸¦ ¼­·Î ¿¬°áÇØ¼­ °ü¸®Çϸç, À̶§ °¢°¢ÀÇ µ¥ÀÌÅ͸¦ ³ëµå(node)¶ó°í ºÒ¸®¿ì´Â Unit¿¡ ³Ö¾î¼­ °ü¸®ÇÑ´Ù. ½ºÅÃÀ̳ª Å¥¿Í °°Àº °æ¿ì °¢ À§Ä¡¿¡ µ¥ÀÌÅÍÀÚü°¡ ÀúÀåµÇ´Â °Í°ú´Â ¾à°£´Ù¸£´Ù. ÀÌó·³ µ¥ÀÌÅ͸¦ ³ëµå¿¡ ³Ö¾î¼­ °ü¸®ÇÏ´Â ÀÌÀ¯´Â µ¥ÀÌÅÍÀÇ ¸®½ºÆ®¸¦ À¯ÁöÇϱâ À§Çؼ­ µ¥ÀÌÅͿܿ¡µµ ´ÙÀ½ µ¥ÀÌÅÍÀÇ À§Ä¡¸¦ ³ªÅ¸³¾¼ö ÀÖ´Â ¾î¶² ºÎ°¡ÀûÀÎ Á¤º¸°¡ ÇÊ¿äÇϱ⠶§¹®ÀÌ´Ù.

그림 1. ¸µÅ©µå ¸®½ºÆ®ÀÇ ±¸Á¶

µ¥ÀÌÅÍÀÇ À§Ä¡¸¦ ³ªÅ¸³»±â À§Çؼ­ »ç¿ëÇÒ¼ö Àִ°ÍÀº pointer°¡ µÉ°ÍÀÌ´Ù. Áï ³ëµå´Â µ¥ÀÌÅÍ¿Í ÇÔ²² ´ÙÀ½ µ¥ÀÌÅÍÀÇ À§Ä¡Á¤º¸¸¦ °¡Áö°í ÀÖ´Â "Æ÷ÀÎÅÍ"¸¦ Æ÷ÇÔÇÏ°Ô µÈ´Ù.

¸µÅ©µå¸®½ºÆ®ÀÇ °æ¿ì µ¥ÀÌÅ͸¦ ³ëµå´ÜÀ§·Î °ü¸®ÇÏ°í µ¥ÀÌÅÍ¿Í ´õºÒ¾î Æ÷ÀÎÅͱîÁö °¡Áö°í ÀÖ¾î¾ß ÇÔÀ¸·Î ÇÊ¿¬ÀûÀ¸·Î ÀڷᱸÁ¶ÀÇ »çÀÌÁî°¡ Á»´õ(¾à°£) Ä¿Áú¼ö ¹Û¿¡ ¾ø´Ù. Æ÷ÀÎÅÍÇüÀÇ Å©±â°¡ 4 byte·Î (µ¥ÀÌÅͼö X 4)¸¸Å­ÀÇ ºÎ°¡ÀûÀÎ °ø°£ÀÌ ´õÇÊ¿äÇϱ⠶§¹®ÀÌ´Ù(ÀÌÁß ¸µÅ©µå¸®½ºÆ®¶ó¸é (µ¥ÀÌÅͼö X 4 X 2)¸¸Å­). ¹¹ ¿äÁò¿¡¾ß ¸Þ¸ð¸®°¡°Ýµµ ½Î°í ÇÏ´Ï±î º°¹®Á¦°¡ ¾ø°ÚÁö¸¸, ¾î¶µç µ¥ÀÌÅÍ ³¶ºñ°¡ ½ÉÇÒ¼ö ÀÖ´Ù´Â °¡Á¤ÇÏ¿¡ »ç¿ëÇϱ⠹ٶõ´Ù. ¿¹¸¦µé¾î intÇü ¼ýÀÚ¸¦ ÀúÀåÇÏ´Â ¸µÅ©µå¸®½ºÆ®¶ó¸é ´ÜÁö 4byte¸¦ ÀúÀåÇϱâ À§Çؼ­ 4byteÀÇ ºÎ°¡ÀûÀÎ Á¤º¸°¡ ´õ µé¾î°¡¾ß ÇÒ°ÍÀ̱⠶§¹®ÀÌ´Ù. 2¹è ÀÌ»óÀÇ ¸Þ¸ð¸® ³¶ºñ¶ó°í ÇÒ¼ö ÀÖ´Ù.

¸µÅ©µå¸®½ºÆ®°¡ ½ºÅà ȤÀº Å¥¿Í ºñ±³Çؼ­ °¡Áö´Â Ư¡Àº ´ÙÀ½°ú °°´Ù. ½ºÅÃ,Å¥´Â ¹è¿­·Î ĪÇϵµ·Ï ÇϰڴÙ.

  1. ¹è¿­ÀÇ °æ¿ì ¿¬¼ÓÀûÀÎ °ø°£¿¡ À§Ä¡ÇÔÀ¸·Î ƯÁ¤À§Ä¡¿¡ ÀÖ´Â µ¥ÀÌÅÍ¿¡ Á¢±ÙÇϰíÀÚ ÇÒ¶§ O(1)ÀÇ ½Ã°£ÀÌ ¼Ò¸ðµÈ´Ù. ±×·¯³ª ¸µÅ©µå¸®½ºÆ®ÀÇ °æ¿ì O(N)ÀÇ ½Ã°£ÀÌ ¼Ò¸ðµÈ´Ù. óÀ½³ëµå ºÎÅÍ ¼øÈ¯À» ÇØ¾ßÇϱ⠶§¹®ÀÌ´Ù.

  2. ¹è¿­ÀÇ °æ¿ì óÀ½°ú ¸¶Áö¸·¿¡ µ¥ÀÌÅ͸¦ »ðÀÔÇÏ´Â°Ç ¸Å¿ì ½±°í È¿À²ÀûÀÌÁö¸¸ Áß°£¿¡ ÀÖ´Â µ¥ÀÌÅ͸¦ »èÁ¦Çϰųª, »ðÀÔÇÏ´Â°Ç »ó´ëÀûÀ¸·Î ¾î·Æ°í ºñÈ¿À²ÀûÀÌ´Ù. ¸µÅ©µå ¸®½ºÆ®´Â ÀÌ·¯ÇÑ °æ¿ì ¸Å¿ì È¿À²ÀûÀÌ´Ù.

  3. ¹è¿­ÀÇ °æ¿ì ÀÏ´Ü ¸¸µé¾îÁø »çÀÌÁ Á¶Á¤ÇÒ¼ö ¾øÀ¸³ª(¹°·Ð reallocÇϸéµÇ±ä ÇÏÁö¸¸) ¸µÅ©µå¸®½ºÆ®´Â ÀÚÀ¯·Ó°Ô »çÀÌÁ Á¶Á¤ÇÒ¼ö ÀÖ´Ù.


1.2. ¸µÅ©µå ¸®½ºÆ®ÀÇ Á¾·ù

¸µÅ©µå¸®½ºÆ®¿¡´Â 3°¡ÁöÀÇ Á¾·ù°¡ ÀÖ´Ù. ½Ì±Û¸µÅ©µå¸®½ºÆ®, ÀÌÁ߸µÅ©µå ¸®½ºÆ®, ȯÇü¸µÅ©µå ¸®½ºÆ®Àε¥ °¢°¢ÀÇ ¸µÅ©µå¸®½ºÆ®ÀÇ ±¸Çö Ư¡¿¡ ´ëÇØ¼­ ¾Ë¾Æº¸µµ·Ï ÇϰڴÙ.


1.2.1. ½Ì±Û¸µÅ©µå¸®½ºÆ®

singly Linked List¶ó°íµµ ºÒ¸®¿ì´Â ½Ì±Û¸µÅ©µå¸®½ºÆ®´Â °¡Àå°£´ÜÇÑ ±¸Á¶¸¦ °¡Áö´Â ¸µÅ©µå ¸®½ºÆ®ÀÌ´Ù.

그림 2. ½Ì±Û ¸µÅ©µå ¸®½ºÆ®ÀÇ ±¸Á¶

°¢ ³ëµå´Â ÀúÀåÇϰíÀÚÇÒ µ¥ÀÌÅÍ¿Í ´ÙÀ½ ³ëµå¸¦ °¡¸®Å°´Â Æ÷ÀÎÅ͸¦ Æ÷ÇÔÇÑ´Ù. ½Ì±Û¸µÅ©µå¸®½ºÆ®¿¡¼­ °¢ ³ëµå´Â ´ÙÀ½³ëµåÀÇ À§Ä¡¸¦ °¡¸®Å°±â ¶§¹®¿¡, ¿ì¸®´Â ¹Ýµå½Ã ½ÃÀÛ³ëµåÀÇ À§Ä¡¸¦ ¾Ë°í ÀÖ¾î¾ß¸¸ ÇÒ°ÍÀÌ´Ù. ¶ÇÇÑ ÀÌÀü³ëµåÀÇ À§Ä¡´Â ¾Ë¼ö¾øµµ·Ï µÇ¾î ÀÖ´Ù.


1.2.2. ÀÌÁ߸µÅ©µå¸®½ºÆ®

Double Linked List¶ó°í ºÒ¸®¿î´Ù. ´ÙÀ½³ëµå¸¦ °¡¸®Å°´Â ÇϳªÀÇ Æ÷ÀÎÅ͸¸ °¡Áö°í ÀÖ´Â ½Ì±Û¸µÅ©µå¸®½ºÆ®¿Í´Â ´Þ¸® ÀÌÀü³ëµå¸¦ °¡¸®Å°´Â Æ÷ÀÎÅ͵µ °¡Áö°í ÀÖ´Ù. Àü¹æÇâ, ÈĹæÇâ¾î´À ÂÊÀ¸·ÎµçÁö ¼øÈ¯ÀÌ °¡´ÉÇÑ ¸µÅ©µå¸®½ºÆ®ÀÌ´Ù.

그림 3. ÀÌÁß ¸µÅ©µå ¸®½ºÆ®ÀÇ ±¸Á¶


1.2.3. ȯÇü¸µÅ©µå¸®½ºÆ®

그림 4. ȯÇü ¸µÅ©µå ¸®½ºÆ®ÀÇ ±¸Á¶

´Ù¸¥ ¸µÅ©µå¸®½ºÆ®¿Í ´Ù¸¥Á¡À̶ó¸é ¸¶Áö¸· ³ëµå°¡ NULLÀÌ ¾Æ´Ñ óÀ½³ëµå¸¦ °¡¸®Å°´Â°Í Á¤µµÀÌ°í ´Ù¸¥ Â÷ÀÌÁ¡Àº ¾ø´Ù.

À§ÀÇ ±×¸²Àº ½Ì±Û¸µÅ©µå¸®½ºÆ®ÀÇ È¯Çü±¸Á¶¸¦ ³ªÅ¸³½ ±×¸²ÀÌ´Ù. ÀÌÁ߸µÅ©µå¸®½ºÆ®¿¡µµ µ¿ÀÏÇÏ°Ô Àû¿ëµÉ¼ö ÀÖ´Ù.


2. ¸µÅ©µå¸®½ºÆ®ÀÇ ±¸Çö

±×·³ ½ÇÁ¦·Î ¸µÅ©µå¸®½ºÆ®¸¦ ±¸ÇöÇØº¸µµ·Ï ÇϰڴÙ.


2.1. »ðÀÔ,»èÁ¦

´Ù¸¥ ÀڷᱸÁ¶µé°ú ¸¶Âù°¡Áö·Î ¸µÅ©µå¸®½ºÆ® ¿ª½Ã µ¥ÀÌÅÍÀÇ »ðÀÔ, »èÁ¦°¡ °¡Àå ±âº»ÀÌ µÇ´Â ±â´ÉµéÀÌ´Ù. ¿ì¼± ¸µÅ©µå¸®½ºÆ®»ó¿¡¼­ ¾î¶»°Ô µ¥ÀÌÅÍÀÇ »ðÀÔ »èÁ¦°¡ ÀÌ·ç¾î Áú¼ö ÀÖ´ÂÁö¿¡ ´ëÇØ¼­ ¾Ë¾Æº¸ÀÚ.


2.1.1. ³ëµå »ðÀÔ

¿ì¼± ³ëµå»ðÀÔ¿¡ ´ëÇØ¼­ ¾Ë¾Æº¸ÀÚ. ¾Æ·¡´Â ¸µÅ©µå ¸®½ºÆ®¿¡¼­ ³ëµå°¡ »ðÀԵǴ ÀüÇüÀûÀÎ °úÁ¤À» º¸¿©ÁØ´Ù.

그림 5. ¸µÅ©µå ¸®½ºÆ®¿¡¼­ÀÇ ³ëµå»ðÀÔ

À§ÀÇ ±×¸²Àº ³ëµå2 ¿Í ³ëµå5 Áß°£¿¡ »õ·Î¿î ³ëµå4°¡ »ðÀԵɶ§ ¾î¶² ¹æ½ÄÀ¸·Î »ðÀÔÀÌ µÇ´ÂÁö¸¦ º¸¿©ÁØ´Ù. ³ëµå2°¡ ±âÁ¸¿¡ °¡¸£Å°´ø ·Îµå´Â ³ëµå5¿´´Âµ¥, ¿©±â¿¡ »õ·Î¿î ³ëµå4°¡ »ðÀԵǾúÀ½À¸·Î ³ëµå4¸¦ °¡¸£Å°µµ·Ï Æ÷ÀÎÅ͸¦ ¼öÁ¤ÇÑ´Ù. »ðÀÔµÈ ³ëµå4 ¿ª½Ã ´ÙÀ½ ³ëµå·Î ³ëµå5¸¦ °¡¸£Å°µµ·Ï Æ÷ÀÎÅ͸¦ ¼öÁ¤ÇÑ´Ù. ÀÌ·Î½á ³ëµå»ðÀÔÀÌ ³¡³µ´Ù. ¸Å¿ì °£´ÜÇÏ´Ù.

¸¸¾à Ãß°¡µÇ´Â ³ëµå4°¡ °¡Àå ¸¶Áö¸·ÀÏ °æ¿ì¿¡´Â °¡¸£Å³ ´ÙÀ½³ëµå°¡ ¾øÀ½À¸·Î NULLÀ» °¡¸£Å°°Ô µÈ´Ù.

¸µÅ©µå¸®½ºÆ®°¡ ½ºÅÃÀ̳ª Å¥¿¡ ºñÇØ¼­ °¡Áö´Â ÀåÁ¡À̶ó¸é, ÀÓÀÇÀÇ ÁöÁ¡¿¡ ´ëÇÑ ³ëµåÀÇ Ãß°¡¹× »èÁ¦°¡ °¡´ÉÇÏ´Ù´Â Á¡ÀÌ´Ù. ±×·¡¼­ ´Ü¼øÈ÷ óÀ½°ú ¸¶Áö¸·¿¡ µ¥ÀÌÅ͸¦ »èÁ¦ÇÏ´Â ½ºÅÃÀ̳ª Å¥¿¡ ºñÇØ¼­ Á»´õ ´Ù¾çÇÑ »ðÀÔ±â´ÉÀ» Æ÷ÇÔ½Ãų¼ö ÀÖ´Ù. ¾Æ¸¶µµ ´ÙÀ½°ú °°Àº »ðÀÔ±â´ÉÀ» Æ÷ÇÔ½Ãų¼ö ÀÖÀ»°ÍÀÌ´Ù.

표 1. Áö¿øÇÏ´Â »ðÀÔÀÇ Á¾·ù

push_back°¡Àå µÚ¿¡ ³ëµå Ãß°¡
push_front°¡Àå ¾Õ¿¡ ³ëµå Ãß°¡
insertÀÓÀÇÀÇ À§Ä¡¿¡ ³ëµå Ãß°¡


2.1.2. ³ëµå »èÁ¦

³ëµå »èÁ¦¿ª½Ã ±×¸²À¸·Î ¼³¸íÇÏ¸é ½±°Ô ÀÌÇØ°¡´ÉÇÏ´Ù.

그림 6. ¸µÅ©µå ¸®½ºÆ®¿¡¼­ÀÇ ³ëµå»èÁ¦

À§ÀÇ ¸µÅ©µå ¸®½ºÆ®¿¡¼­ ³ëµå4¸¦ »èÁ¦ÇÑ´Ù°í ÇÏÀÚ. ³ëµå4°¡ ¾ø¾îÁö¸é ³ëµå4¸¦ °¡¸£Å°´ø ³ëµå3ÀÌ ³ëµå5¸¦ °¡¸£Å°µµ·Ï Æ÷ÀÎÅ͸¦ º¯°æÇÏ¸é µÈ´Ù. ±×°É·Î ³¡ÀÌ´Ù.(¹°·Ð ³ëµå4´Â free½ÃÄÑÁà¾ß ÇÑ´Ù.) ¸¸¾à óÀ½³ëµå¸¦ »èÁ¦ÇÑ´Ù¸é ´ÜÁö óÀ½³ëµå¸¸ free½ÃŰ¸é µÉ°ÍÀÌ´Ù. ±×·¯³ª À̶§ óÀ½³ëµå°¡ ¾îµðÀÎÁö ¾Ë¼ö ¾øÀ½À¸·Î óÀ½³ëµåÀÇ À§Ä¡¸¦ °¡¸£Å°´Â ´Ù¸¥ Æ÷ÀÎÅÍ º¯¼ö¸¦ ÀÌ¿ëÇØ¼­ À§Ä¡¸¦ ÀúÀåÇØ¾ß ÇÒ°ÍÀÌ´Ù.

¿ª½Ã ´Ù¾çÇÑ »èÁ¦±â´ÉÀ» Á¦°øÇÒ°ÍÀÌ´Ù.

표 2. Áö¿øÇÏ´Â »èÁ¦ÀÇ Á¾·ù

pop_back°¡Àå µÚÀÇ ³ëµå »èÁ¦
pop_front°¡Àå ¾ÕÀÇ ³ëµå »èÁ¦
eraseÀÓÀÇÀÇ À§Ä¡¿¡ ÀÖ´Â ³ëµå »èÁ¦


2.2. µ¥ÀÌÅÍ º¸¿©ÁÖ±â

µ¥ÀÌÅ͸¦ »ðÀÔÇϰųª »èÁ¦Çß´Ù¸é, ½ÇÁ¦ ³ëµåÁ¤º¸¸¦ º¸°í ½ÍÀ»¶§°¡ ÀÖÀ»°ÍÀÌ´Ù. ÀÌ·²°æ¿ì óÀ½³ëµåºÎÅÍ ¼øÈ¯À» ½ÃÄÑ¾ß ÇÒ°ÍÀÌ´Ù. ¼øÈ¯ÀÇ ¹æ¹ýÀº °£´ÜÇÏ´Ù. ´ÙÀ½³ëµå¸¦ °¡¸£Å°´Â Æ÷ÀÎÅͰ¡ NULLÀÌ µÉ¶§±îÁö °è¼Ó ³ëµå¸¦ Áõ°¡½ÃÄÑ ³ª°¡¸é µÉ°ÍÀÌ´Ù. À̿ܿ¡µµ ÆíÀǸ¦ À§Çؼ­ óÀ½°ú ¸¶Áö¸· µ¥ÀÌÅÍ Á¤µµ¸¦ ¾ò¾î¿Ã¼ö ÀÖ´Â º°µµÀÇ ¸Þ¼­µå¸¦ Á¦°øÇϴ°͵µ ±¦ÂúÀº ¹æ¹ýÀÌ µÉ°ÍÀÌ´Ù.


2.3. ¸µÅ©µå ¸®½ºÆ® µ¥ÀÌÅÍÃß»ó ±¸Çö

¿¹Á¦ÀÇ ±¸ÇöÀº C++ÀÇ ÅÛÇø´À» ÀÌ¿ëÇØ¼­ ±¸ÇöÇÏ°Ô µÉ°ÍÀÌ´Ù. ¸µÅ©µå¸®½ºÀÇ ±¸Çö°°Àº°æ¿ì C¸¦ ÀÌ¿ëÇÑ ±¸ÇöÀ» ¼±È£ÇÒ¼ö Àִµ¥, Ưº°È÷ C++°ú ´Ù¸¦°Ô ¾ø°í, ¾Æ¹«·¡µµ µ¥ÀÌÅÍ Ãß»óÀ» À§Çؼ­´Â C++À» ÀÌ¿ëÇÏ´Â°Ô È¿°úÀûÀÓÀ¸·Î C++À» ¼±ÅÃÇß´Ù. C¸¦ ÀÌ¿ëÇÑ ¸µÅ©µå¸®½ºÆ®ÀÇ ±¸ÇöÀº µ¿Àû ¸Þ¸ð¸®ÇҴ縦 Âü°íÇϱ⠹ٶõ´Ù.

±×¸®°í ½Ì±Û¸µÅ©µå¸®½ºÆ®¸¦ ÀÌ¿ëÇÑ ±¸ÇöÀ» ÇϰڴÙ. ³ª¸ÓÁö´Â »ç½Ç»ó ½Ì±Û¸µÅ©µå¸®½ºÆ®¸¦ ¾à°£ º¯ÇüÇÑ °ÍÀ̰í, ½Ì±Û¸µÅ©µå¸®½ºÆ®°¡ Á»´õ ±¸ÇöÇÏ±â ÆíÇϱ⠶§¹®ÀÌ´Ù. ½Ì±Û¸µÅ©µå¸®½ºÆ®ÀÇ ±¸ÇöÀ» ÀÌÇØÇÑ´Ù¸é ´Ù¸¥ ¸µÅ©µå¸®½ºÆ®ÀÇ ±¸Çöµµ °£´ÜÇÒ°ÍÀÌ´Ù.

¿¹Á¦´Â ¾ö°ÝÇÑ ±ÔÄ¢À» µû¸£Áö ¾ÊÀ¸¸ç, ¸µÅ©µå¸®½ºÆ®ÀÇ °³³äÀÌÇØ¿¡ ÃÐÁ¡À» ¸ÂÃâ°ÍÀÌ´Ù. ¿¹¸¦µé¾î ƯÁ¤À§Ä¡ÀÇ ³ëµåµ¥ÀÌÅ͸¦ °¡Á®¿À´Â °æ¿ì ¾Æ·¡ÀÇ ÄÚµå´Â ¸Å¿ì ºñÈ¿À²ÀûÀÌ´Ù. ³ëµåÀÇ À§Ä¥¸¦ Áõ°¡½Ãų¶§¸¶´Ù ³ëµåÀÇ Ã³À½ºÎÅÍ ¼øÈ¯Çϱ⠶§¹®ÀÌ´Ù. À̰ÍÀÇ ¼öÁ¤¹æ¹ýÀº ¿©·¯°¡Áö°¡ ÀÖ´Ù. °¡ÀåÃÖ±ÙÀÇ ³ëµå¸¦ ±â¾ïÇÏ°Ô Çϴ¹æ¹ý°ú ÀÌÅÍ·¹ÀÌÅÍ(iterator)°³³äÀ» Àû¿ëÇÏ´Â ¹æ¹ýÀÌ ±×°ÍÀÌ´Ù.

¶ÇÇÑ ½Ì±Û¸µÅ©µå¸®½ºÆ®ÀÓÀ¸·Î ¼ø¹æÇâÀ¸·Î ³ëµå¸¦ ã¾Æ°¡´Â°Ç °¡´ÉÇÏÁö¸¸ ¿ª¹æÇâ(µÚ¿¡¼­ ¾ÕÀ¸·Î) ³ëµå¸¦ ã¾Æ°¡´Â°Ç ºÒ°¡´ÉÇÏ´Ù. ±×·³À¸·Î °¡ÀåµÚ¿¡ ÀÖ´Â ³ëµå¸¦ »èÁ¦ÇϰíÀÚ ÇÒ¶§ ¾î¿¼ö ¾øÀÌ ³ëµåÀÇ Ã³À½ºÎÅÍ ¸¶Áö¸·±îÁö ÈÈ¾î ³ª°¡¾ß ÇÑ´Ù. ¿ª½Ã ºñÈ¿À²ÀûÀÌ´Ù. ÀÌ·± ºñÈ¿À²ÀÇ ¹®Á¦´Â ´õºí¸µÅ©µå¸®½ºÆ®¸¦ ÀÌ¿ëÇÏ¸é °¡´ÉÇÒ°ÍÀÌ´Ù.

¿¹Á¦ : linked.cc

#include <iostream>
#include <string>
#include <iterator>

using namespace std;

template <typename T>
class List
{
    private:
        // ³ëµå°¹¼ö
        int         node_num;
        // NODEµ¥ÀÌÅ͸¦ ÀúÀåÇÒ ±¸Á¶Ã¼ 
        struct Node
        {
            T    Data;
            Node *NextNode;
        };
        Node *mNode;  // ³ëµå ÇÒ´çÀ» À§Çؼ­ »ç¿ëÇÑ´Ù. 
        Node *SNode;  // ½ÃÀÛ³ëµå¸¦ Æ÷ÀÎÆ®ÇÑ´Ù.
        Node *NNode;  // ´ÙÀ½³ëµå¸¦ Æ÷ÀÎÆ®ÇÑ´Ù.  
        Node *ENode;  // ¸¶Áö¸·³ëµå¸¦ Æ÷ÀÎÆ®ÇÑ´Ù.

    public:
        // »ý¼ºÀÚ
        List()
        {
            node_num = 0;
        };

        // »ðÀÔ°ü·Ã ¸Þ¼­µå ------------------------

        // °¡ÀåµÚ¿¡ ³ëµå¸¦ Ãß°¡ÇÑ´Ù. 
        // ¸¶Áö¸· ³ëµå Á¤º¸¸¦ °¡Áö°í ÀÖÀ½À¸·Î 
        // »õ·Î¿î ³ëµå¸¦ ÇÒ´çÇÏ°í ±âÁ¸ÀÇ ¸¶Áö¸·³ëµå°¡ 
        // NULL´ë½Å »õ·ÎÇÒ´çµÈ ³ëµå¸¦ °¡¸®Å°°Ô ÇÏ¸é µÈ´Ù. 
        void push_back(T data)
        {
            mNode = new Node;
            mNode->Data     = data;
            mNode->NextNode = NULL;

            if (node_num == 0)
            {
                SNode = mNode;
                ENode = mNode;
            }
            else
            {
                ENode->NextNode = mNode;
                ENode = mNode;
            }
            node_num++;
        };

        // °¡Àå¾Õ¿¡ ³ëµå¸¦ Ãß°¡ÇÑ´Ù. 
        // ¸¸¾à óÀ½À¸·Î ³ëµå°¡ Ãß°¡µÇ´Â°Å¶ó¸é 
        // ÀÌ ³ëµå´Â ´ÙÀ½³ëµå·Î NULLÀ» °¡¸®Å°°Ô µÈ´Ù. 
        // ±×·¸Áö ¾ÊÀ»°æ¿ì ±âÁ¸¿¡ °¡Àå óÀ½¿¡ ÀÖ´ø ³ëµå¸¦ 
        // °¡¸®Å°°Ô µÈ´Ù. 
        void push_front(T data)
        {
            mNode = new Node;
            mNode->Data     = data;
            mNode->NextNode = NULL;
            if (node_num == 0)
            {
                SNode =  mNode;
            }
            else
            {
                mNode->NextNode = SNode;
                SNode =  mNode;
            }
            node_num++;
        };

        // ÀÓÀÇÀÇ À§Ä¡¿¡ ³ëµå¸¦ »ðÀÔÇÑ´Ù.  
        int insert(T data, int position)
        {
            Node *PNode;
            int i = 0;
            if (position > node_num)
            {
                return -1;
            }

            // óÀ½°ú ¸¶Áö¸· À§Ä¡¿¡ 
            // »ðÀÔÇÒ¶§´Â ÀÌ¹Ì ¸¸µé¾îÁø ¸Þ¼­µå¸¦
            // Ȱ¿ëÇÑ´Ù.
            if (position == 0)
            {
                push_front(data);
                return 1;
            }
            if (position == node_num)
            {
                push_back(data);
                return 1;
            }

            mNode = new Node;
            mNode->Data     = data;
            mNode->NextNode = NULL;

            NNode = SNode;
            while(NNode)
            {
                if (i == position)
                {
                    mNode->NextNode = NNode;
                    PNode->NextNode = mNode;
                    node_num++;
                    break;
                }
                PNode = NNode;
                NNode = NNode->NextNode;
                i++;
            }
            return 1;
        }


        // »èÁ¦ °ü·Ã ¸Þ¼­µå -------------------------
        // °¡Àå¾Õ¿¡ ÀÖ´Â ³ëµå¸¦ »èÁ¦
        void pop_front()
        {
            NNode = SNode->NextNode;
            delete SNode;
            SNode = NNode;
            node_num--;
        }

        // °¡ÀåµÚ¿¡ ÀÖ´Â ³ëµå¸¦ »èÁ¦
        // ½Ì±Û ¸µÅ©µå ¸®½ºÆ®¶ó¼­ °¡ÀåµÚ¿¡ ÀÖ´Â ³ëµå¸¦ 
        // Áö¿ï°æ¿ì ¾î¿¼ö ¾øÀÌ Ã³À½ºÎÅÍ ³ëµå¸¦ °Ë»öÇÏ´Â ¼ö 
        // ¹Û¿¡ ¾ø´Ù. 
        // ´õºí¸µÅ©µå ¸®½ºÆ®¶ó¸é Á»´õ ½±°Ô »èÁ¦ °¡´ÉÇÒ°ÍÀÌ´Ù.  
        void pop_back()
        {
            int i = 0;
            Node *PNode;
            NNode = SNode;

            while(1)
            {
                if(i == node_num - 1)
                {
                    PNode->NextNode = NULL;
                    delete(NNode);
                    break;
                }
                PNode = NNode;
                NNode = NNode->NextNode;
                i++;
            }
            node_num--; 
        }


        // °ª °¡Á®¿À±â ¸Þ¼­µå -----------------------

        // °¡Àå¾ÕÀÇ ³ëµå¿¡¼­ µ¥ÀÌÅ͸¦ °¡Á®¿Â´Ù.
        T front()
        {
            return SNode->Data; 
        }

        // °¡ÀåµÚÀÇ ³ëµå¿¡¼­ µ¥ÀÌÅ͸¦ °¡Á®¿Â´Ù.
        T back()
        {
            return ENode->Data;
        }

        // ³ëµå¸¦ ¼øÈ¯Çϸ鼭 ¸ðµç µ¥ÀÌÅ͸¦ Ãâ·ÂÇÑ´Ù.
        void show()
        {
            NNode = SNode;

            while(NNode)
            {
                cout << NNode->Data << endl;
                NNode = NNode->NextNode;
            }
        }

        // ÀÓÀÇÀÇ À§Ä¡¿¡ ÀÖ´Â ³ëµåÀÇ µ¥ÀÌÅ͸¦ 
        // °¡Á®¿Â´Ù.  
        // ÀÌ ¸Þ¼­µå´Â ºñÈ¿À²ÀûÀÌ°í ±ò²ûÇÏÁö ¸øÇÏ´Ù. 
        // ¹Ù²ãº¸ÀÚ. 
        T get(int num)
        {
            int i = 0;
            if (num > node_num)
            {
                return NULL;
            }
            NNode = SNode;
            while(i < num)
            {
                NNode = NNode->NextNode;
                i++;
            }
            return NNode->Data;
        }

        // ºÎ°¡ ¸Þ¼­µå ----------------------------- 
        int size()
        {
            return node_num;
        }
};

int main()
{
    List<string> list;

    // Å×½ºÆ®
    list.push_back("A");
    list.push_back("B");
    list.push_back("C");
    list.push_front("D");
    list.insert("100", 1);
    list.push_front("101");

    cout << "Size " << list.size() << endl;
    cout << "First Data is " << list.front() << endl;
    cout << "Last Data is " << list.back() << endl;
    list.show();

    list.pop_front();
    list.show();

    list.pop_back();
    list.show();

    cout <<"GET DATA" << list.size() << endl;
    for (int i =0; i < list.size(); i++)
    {
        cout << list.get(i) << endl;
    }
}
			


3. °á·Ð

ÀÌ»ó ¸µÅ©µå¸®½ºÆ®¿Í ¸µÅ©µå¸®½ºÆ® µ¥ÀÌÅÍ Ãß»ó¿¡ ´ëÇØ¼­ ¾Ë¾Æº¸¾Ò´Ù. ÀÌ·Î½á ±âº»ÀڷᱸÁ¶ÀÎ ½ºÅÃ,Å¥,¸µÅ©µå¸®½ºÆ®¿¡ ´ëÇÑ ±âº»ÀûÀÎ ³»¿ëÀ» ¸ðµÎ ´Ù·ç¾ú´Ù. ´ÙÀ½¹øºÎÅÍ´Â À̰͵éÀÇ ÀÀ¿ë°ú ÇÔ²² ±âº»ÀûÀÎ ÀڷᱸÁ¶¿¡ °ü·ÃµÈ ¾Ë°í¸®ÁòµéÀ» ¾Ë¾Æº¸°Ô µÉ°ÍÀÌ´Ù.

category_Database
category__3
EmailÀ» ±âÀÔÇϸé, ´ñ±ÛÀÌ ¸ÞÀÏ·Î Àü´ÞµË´Ï´Ù.