19-2-³ª.ÀÌÁß ¿¬°á ¸®½ºÆ®

´Ü¼ø ¿¬°á ¸®½ºÆ®´Â ÀÚ½ÅÀÇ ´ÙÀ½ ³ëµå¿¡ ´ëÇÑ ¸µÅ©(next)¸¸À» °¡Áö±â ¶§¹®¿¡ µÚÂÊÀ¸·Î¸¸ À̵¿ÇÒ ¼ö ÀÖÀ¸¸ç ¾ÕÂÊÀ¸·Î´Â À̵¿ÇÒ ¼ö ¾ø´Ù. ¸µÅ©¸¦ Á¶ÀÛÇÒ ¶§µµ ¾ÕÂÊ ³ëµåÀÇ ¸µÅ©¸¦ ¾×¼¼½ºÇÒ ¼ö ¾ø±â ¶§¹®¿¡ Ç×»ó ÁöÁ¤ÇÑ ³ëµåÀÇ ¿À¸¥ÂÊ¿¡¸¸ »ðÀÔÇÒ ¼ö ÀÖÀ¸¸ç ƯÁ¤ ³ëµå¸¦ ¹Ù·Î »èÁ¦ÇÏÁö ¸øÇÏ°í ´ÙÀ½ ³ëµå¸¸À» »èÁ¦ÇÒ ¼ö ÀÖ´Ù. ÀÌ¿¡ ºñÇØ ÀÌÁß ¿¬°á ¸®½ºÆ®´Â ÀüÈÄÀÇ ³ëµå¿¡ ´ëÇÑ ¸µÅ©¸¦ °¢°¢ µû·Î °¡Áø´Ù.

 

struct Node

{

     int value;

     Node *prev;

     Node *next;

};

 

³ëµå¿¡ ÀúÀåµÇ´Â µ¥ÀÌÅÍ ¿Ü¿¡ ¾ÕÂÊ ³ëµåÀÇ ¹øÁö¸¦ °¡Áö´Â prev¿Í µÚÂÊ ³ëµåÀÇ ¹øÁö¸¦ °¡Áö´Â next ¸µÅ©°¡ Æ÷ÇԵǾî ÀÖ´Ù. ±×·¡¼­ ÀÌÁß ¿¬°á ¸®½ºÆ®ÀÇ ³ëµå´Â ÀÚ½ÅÀÇ µÚÂÊ ³ëµå »Ó¸¸ ¾Æ´Ï¶ó ¾ÕÂÊ ³ëµåµµ ãÀ» ¼ö ÀÖÀ¸¸ç ¸µÅ©¸¦ Á¶ÀÛÇÒ ¶§µµ ¾ÕµÚÀÇ ³ëµå¸¦ ÀÚÀ¯·Ó°Ô ¾×¼¼½ºÇÒ ¼ö ÀÖ´Ù. Áï ¼ø¹æÇâ»Ó¸¸ ¾Æ´Ï¶ó ¿ª¹æÇâ ¼øȸµµ °¡´ÉÇÑ °ÍÀÌ´Ù.

´ë½Å ¸µÅ©°¡ Çϳª ´õ µé¾î°¡±â ¶§¹®¿¡ ±â¾ï Àå¼Ò¸¦ ±×¸¸Å­ ´õ ¼ÒºñÇÏ°í ¸µÅ©¸¦ °ü¸®ÇÏ´Â Äڵ尡 Á¶±Ý ´õ º¹ÀâÇØÁø´Ù´Â °ÍÀÌ ´ÜÁ¡ÀÌ´Ù. ÇÏÁö¸¸ ¿äÁòÀÇ ÄÄÇ»ÅÍ È¯°æ¿¡¼­ ¸Þ¸ð¸®¸¦ Á¶±Ý ´õ ¾²´Â °ÍÀº Å« ºÎ´ãÀÌ ¾Æ´Ñµ¥´Ù ³ëµå °ü¸®°¡ ÀÚÀ¯·Ó±â ¶§¹®¿¡ ´Ü¼ø ¿¬°á ¸®½ºÆ®º¸´Ù´Â ÀÌÁß ¿¬°á ¸®½ºÆ®°¡ ÈξÀ ´õ È°¿ë¼ºÀÌ ³ô´Ù°í ÇÒ ¼ö ÀÖ´Ù. ´ÙÀ½ ¿¹Á¦´Â ÀÌÁß ¿¬°á ¸®½ºÆ®¸¦ Å×½ºÆ®Çϴµ¥ ¾ÕÀÇ ¿¹Á¦º¸´Ù ±â´ÉÀÌ Á» ´õ ¸¹´Ù.

 

¿¹ Á¦ : DoubleList

#include <Turboc.h>

 

// ³ëµå ±¸Á¶Ã¼

struct Node

{

     int value;

     Node *prev;

     Node *next;

};

 

Node *head;

 

// ¿¬°á ¸®½ºÆ® ÃʱâÈ­ - ¸Ó¸®¸¦ ÇÒ´çÇÑ´Ù.

void InitList()

{

     head=(Node *)malloc(sizeof(Node));

     head->prev=NULL;

     head->next=NULL;

}

 

// ÁöÁ¤ÇÑ ³ëµåÀÇ ¿À¸¥ÂÊ¿¡ »ðÀÔÇÑ´Ù.

Node *InsertNodeRight(Node *Target,Node *aNode)

{

     Node *New;

     Node *Right;

 

     New=(Node *)malloc(sizeof(Node));

     *New=*aNode;

 

     Right=Target->next;

     New->next=Right;

     New->prev=Target;

     Target->next=New;

     if (Right) {

          Right->prev=New;

     }

     return New;

}

 

// ÁöÁ¤ÇÑ ³ëµåÀÇ ¿ÞÂÊ¿¡ »ðÀÔÇÑ´Ù.

Node *InsertNodeLeft(Node *Target,Node *aNode)

{

     Node *Left;

 

     Left=Target->prev;

     if (Left) {

          return InsertNodeRight(Left,aNode);

     }

     return NULL;

}

 

// Á¦ÀÏ ³¡¿¡ ³ëµå¸¦ Ãß°¡ÇÑ´Ù.

void AppendNode(Node *aNode)

{

     Node *tail;

 

     for (tail=head;tail->next;tail=tail->next) {;}

     InsertNodeRight(tail,aNode);

}

 

// ´Ü¼ø ¿¬°á ¸®½ºÆ®¿Í´Â ´Þ¸® ÀÚ±â ÀÚ½ÅÀ» Áö¿ï ¼ö ÀÖ´Ù.

BOOL DeleteNode(Node *Target)

{

     Node *Left,*Right;

 

     // Çì´õ´Â Áö¿ï ¼ö ¾øÀ½

     if (Target==NULL || Target==head) {

          return FALSE;

     }

     Left=Target->prev;

     Right=Target->next;

 

     Left->next=Right;

     if (Right) {                   // Ÿ°ÙÀÌ ³¡ ³ëµåÀÏ °æ¿ì

          Right->prev=Left;

     }

     free(Target);

 

     return TRUE;

}

 

// idx¹ø° ³ëµå¸¦ ã´Â´Ù.

Node *FindNodeByIndex(int idx)

{

     Node *Now;

     int Index=0;

 

     for (Now=head->next;Now;Now=Now->next) {

          if (Index == idx) {

              return Now;

          }

          Index++;

     }

     return NULL;

}

 

// ³ëµåÀÇ ¼ø¼­°ªÀ» ±¸ÇÑ´Ù.

int GetNodeIndex(Node *Target)

{

     Node *Now;

     int Index=0;

 

     for (Now=head->next;Now;Now=Now->next) {

          if (Now == Target) {

              return Index;

          }

          Index++;

     }

     return -1;

}

 

// ³ëµåÀÇ °³¼ö¸¦ Á¶»çÇÑ´Ù.

int GetListCount()

{

     Node *Now;

     int Count=0;

 

     for (Now=head->next;Now;Now=Now->next) {

          Count++;

     }

     return Count;

}

 

// ¿¬°á ¸®½ºÆ®ÀÇ ¸ðµç ³ëµå¿Í ¸Ó¸®¸¦ ÇØÁ¦ÇÑ´Ù.

void UnInitList()

{

     while (DeleteNode(head->next)) {;}

 

     free(head);

     head=NULL;

}

 

void main()

{

     int i;

     Node *Now,Temp;

 

     InitList();

     for (i=1;i<=5;i++) {

          Temp.value=i;

          AppendNode(&Temp);

     }

 

     // ¼øȸÇϸ鼭 Ãâ·Â

     for (Now=head->next;Now;Now=Now->next) {

          printf("%d\t",Now->value);

     }

     printf("\n");

 

     // °³¼ö, µ¥ÀÌÅÍ 3À» °¡Áø ³ëµå¿Í ¾ÕµÚ ³ëµå¸¦ Á¶»çÇÑ´Ù.

     printf("³ëµå °³¼ö = %d\n",GetListCount());

     for (Now=head->next;Now;Now=Now->next) {

          if (Now->value == 3) break;

     }

     if (Now) {

          printf("Mid=%d, ¾Õ ³ëµå=%d, µÞ ³ëµå=%d\n",Now->value,

              Now->prev->value,Now->next->value);

     }

 

     printf("3¹ø ³ëµå = %d\n", FindNodeByIndex(3)->value);

 

     UnInitList();

}

 

main¿¡¼­´Â ¿¬°á ¸®½ºÆ®¸¦ ÃʱâÈ­ÇÏ°í 5°³ÀÇ ³ëµå¸¦ Ãß°¡ÇÑ ÈÄ Ãâ·Â, °Ë»ö, ÀüÈÄ ³ëµå Á¶»ç µîÀ» ÇØ º¸ÀδÙ. Áï, ÀÌÁß ¿¬°á ¸®½ºÆ®°¡ °¡Áø ¸ðµç ±â´ÉÀ» ÇÑ ¹ø¾¿ ´Ù ºÒ·¯ º¸°í Àå±â ÀÚ¶û ´ëȸ¸¦ ÇÑ ¹ø ÇØ º¸´Â °ÍÀÌ´Ù. ½ÇÇà °á°ú´Â ´ÙÀ½°ú °°´Ù.

 

1       2       3       4       5

³ëµå °³¼ö = 5

Mid=3, ¾Õ ³ëµå=2, µÞ ³ëµå=4

3¹ø ³ëµå = 4

 

µ¥ÀÌÅÍ 3À» °¡Áö´Â ³ëµå¸¦ °Ë»öÇÏ°í ÀÌ ³ëµåÀÇ ÁÂ¿ì ³ëµå¸¦ °¢°¢ Á¶»çÇؼ­ Ãâ·ÂÇߴµ¥ ÀÌÁß ¿¬°á ¸®½ºÆ®´Â ¾çÂÊ ¸µÅ©¸¦ ´Ù °¡Áö°í ÀÖÀ¸¹Ç·Î ÀÌ·± °ÍÀÌ °¡´ÉÇÏ´Ù. ¿¹Á¦ÀÇ °¢ ºÎºÐÀ» ºÐ¼®ÇØ º¸ÀÚ. ´Ü¼ø ¿¬°á ¸®½ºÆ®º¸´Ù ¸µÅ© Á¶ÀÛÀÌ Á¶±Ý º¹ÀâÇϱâ´Â ÇÏÁö¸¸ ¸µÅ©¸¦ ÅëÇØ ³ëµå¸¦ ³í¸®ÀûÀ¸·Î ¿¬°áÇÑ´Ù´Â ±âº» °³³äÀº ºñ½ÁÇÏ´Ù.

³ëµåÀÇ »ðÀÔ

´Ü¼ø ¿¬°á ¸®½ºÆ®´Â ÁÖ¾îÁø Ÿ°Ù ³ëµåÀÇ ¿À¸¥ÂÊ¿¡¸¸ »õ ³ëµå¸¦ »ðÀÔÇÒ ¼ö ÀÖÁö¸¸ ÀÌÁß ¿¬°á ¸®½ºÆ®´Â ¾çÂÊ ¸ðµÎ »ðÀÔÇÒ ¼ö ÀÖ´Ù. ±×·¡¼­ »ðÀÔ ÇÔ¼öµµ Left, Right µÎ °³°¡ Á¦°øµÇ´Âµ¥ ¿À¸¥ÂÊ¿¡ »ðÀÔÇÏ´Â Right¸¦ ¸ÕÀú ºÐ¼®ÇØ º¸ÀÚ. ³ëµå 3°ú ³ëµå 4 °¡¿îµ¥¿¡ ³ëµå 5¸¦ »õ·Î »ðÀÔÇÏ´Â ÀϹÝÀûÀÎ °æ¿ì¸¦ º¸ÀÚ. »ðÀÔ ÀüÀÇ ¸ð¾çÀº ´ÙÀ½°ú °°´Ù.

³ëµå 3ÀÇ next ¸µÅ©°¡ ³ëµå 4¸¦ °¡¸®Å°°í ÀÖ°í ³ëµå 4ÀÇ prev ¸µÅ©°¡ ³ëµå 3À» °¡¸®Å°°í ÀÖ¾î µÎ ³ëµå°¡ ¼­·Î ¾ÕµÚ¿¡ ÀÖÀ½À» ±â¾ïÇÏ°í ÀÖ´Ù. ¹°·Ð ÀÌ µÎ ³ëµåÀÇ ¾çÂÊ¿¡´Â ¶Ç ´Ù¸¥ ³ëµåµéÀÌ ÀÖ°í ¸µÅ©·Î ¿¬°áµÇ¾î ÀÖÀ» °ÍÀÌ´Ù. ÀÌ »óÅ¿¡¼­ ³ëµå3 ´ÙÀ½¿¡ 5ÀÇ °ªÀ» °¡Áö´Â ³ëµå¸¦ »ðÀÔÇÑ´Ù¸é ÀÌ ÇÔ¼ö´Â »õ ³ëµå¸¦ ¸Þ¸ð¸®»ó¿¡ ÇÒ´çÇÏ°í µ¥ÀÌÅ͸¦ 5·Î ÃʱâÈ­ÇÑ´Ù.

»õ·Î¿î ³ëµå°¡ »ý¼ºµÇ±â´Â ÇßÁö¸¸ ¸µÅ©¸¦ Á¶Á¤ÇÏÁö ¾Ê¾ÒÀ¸¹Ç·Î ÀÌ ³ëµå´Â Ȧ·Î Á¸ÀçÇÒ »Ó ¾ÆÁ÷ ¿¬°á ¸®½ºÆ®ÀÇ ÀÏ¿øÀ¸·Î Æ÷ÇÔµÇÁö´Â ¾Ê¾Ò´Ù. ³ëµå3Àº ÇÔ¼öÀÇ Àμö·Î Àü´ÞµÇ¾úÀ¸¹Ç·Î TargetÀÌ µÇ°í TargetÀÇ ¿À¸¥ÂÊ¿¡ ÀÖ´Â ³ëµå 4°¡ Right°¡ µÇ°í »õ·Î »ý¼ºµÈ ³ëµå´Â New¶ó´Â À̸§À» °¡Áø´Ù. ±âÁ¸ ³ëµåÀÇ ¸µÅ©¸¦ º¯°æÇϱâ Àü¿¡ ¸ÕÀú »õ·Î ¸¸µç ³ëµåÀÇ ¸µÅ©¸¦ ¼öÁ¤ÇÏ¿© ¿¬°á ¸®½ºÆ®¿¡ Æ÷ÇÔ½ÃŲ´Ù.

NewÀÇ ´ÙÀ½ ³ëµå´Â Right°¡ µÇ°í ÀÌÀü ³ëµå´Â TargetÀÌ µÈ´Ù. ±×¸®°í ±âÁ¸ ³ëµåÀÇ ¸µÅ©¸¦ º¯°æÇÏ¿© »õ·Î »ý¼ºµÈ ³ëµå¸¦ ¾ÕµÚ ³ëµå·Î ¹èÄ¡Çϴµ¥ New´Â TargetÀÇ ´ÙÀ½ ³ëµåÀ̸鼭 RightÀÇ ÀÌÀü ³ëµå°¡ µÇ¾î µÎ ³ëµå »çÀÌ¿¡ ³¢¾îµç´Ù. ³ëµå Çϳª¸¦ »ðÀÔÇϱâ À§ÇØ ¾ÕµÚ ¹× ÀÚ½ÅÀÇ ¸µÅ©±îÁö 4°³ÀÇ ¸µÅ© Á¶ÀÛÀÌ ÇÊ¿äÇÏ´Ù. ¸µÅ© Á¶ÀÛÀÌ ¸ðµÎ ¿Ï·áµÈ ÈÄÀÇ ¸ð¾çÀº ´ÙÀ½°ú °°´Ù. ³ëµå 5°¡ ³ëµå3°ú ³ëµå4 »çÀÌ¿¡ ¾ÆÁÖ ¿¹»Ú°Ô »ðÀԵǾú´Ù.

ÀÌ»óÀº µÎ ³ëµå »çÀÌ¿¡ »õ·Î¿î ³ëµå°¡ ³¢¾îµå´Â ÀϹÝÀûÀÎ °æ¿ìÀÌ°í Á¦ÀÏ ¾Õ°ú µÚ¿¡ »ðÀԵǴ °æ¿ì¸¦ À§ÇØ Æ¯º°ÇÑ ¿¹¿Ü 󸮰¡ ÇÊ¿äÇÏ´Ù. Á¦ÀÏ ¾Õ¿¡ »ðÀ﵃ °æ¿ì´Â TargetÀ¸·Î head°¡ ÁÖ¾îÁ³À» ¶§Àε¥ ¸Ó¸® ³ëµå°¡ Á¸ÀçÇϹǷΠÀϹÝÀûÀÎ °æ¿ì¿Í µ¿ÀÏÇÏ°Ô Ã³¸®ÇÏ¸é µÈ´Ù. Á¦ÀÏ µÚ¿¡ »ðÀ﵃ °æ¿ì´Â TargetÀÌ ¸¶Áö¸· ³ëµåÀÏ ¶§Àε¥ ÀÌ ¶§´Â ¿À¸¥ÂÊ ³ëµåÀÎ Right°¡ NULLÀ̹ǷΠRight->prev¸¦ Á¶ÀÛÇÏ´Â Äڵ常 Á¦¿ÜÇÏ¸é µÈ´Ù. NULL->prev Äڵ带 ½ÇÇàÇϸé ÇÁ·Î±×·¥Àº ´çÀå ´Ù¿îµÇ¾î ¹ö¸°´Ù. »õ·Î »ðÀԵǴ ³ëµåÀÇ next°¡ Target->nextÀÇ °ªÀÎ NULLÀ» °¡Á®°¡¹Ç·Î ÀÌ ³ëµå°¡ »õ·Î¿î ³¡ ³ëµå°¡ µÉ °ÍÀÌ´Ù.

¿ÞÂÊ »ðÀÔ ¹× Ãß°¡

ÁöÁ¤ÇÑ ³ëµåÀÇ ¿ÞÂÊ¿¡ »ðÀÔÇÏ´Â InsertNodeLeft ÇÔ¼ö´Â ±²ÀåÈ÷ ½±´Ù. ¸µÅ©¸¦ Á¶ÀÛÇÏ´Â Äڵ尡 ¸ðµÎ ¿À¸¥ÂÊ »ðÀÔ ÇÔ¼ö¿¡ ÀÖÀ¸¹Ç·Î ÀÌ ÇÔ¼ö¸¦ ´ë½Å ºÎ¸£±â¸¸ ÇÏ¸é µÈ´Ù. ¾î¶² ³ëµåÀÇ ¿ÞÂÊÀ̶õ ÀÌÀü ³ëµåÀÇ ¿À¸¥ÂÊ°ú °°À¸¹Ç·Î Target->prev¸¦ ´ë»óÀ¸·Î InsertNodeRight¸¦ È£ÃâÇÏ¸é ³ª¸ÓÁö´Â È£ÃâµÈ ÇÔ¼ö°¡ ¾Ë¾Æ¼­ ÇÒ °ÍÀÌ´Ù. Right°¡ º» ÇÔ¼öÀ̸ç Left´Â Àμö Á߰踸 ÇÏ´Â ÀÎÅÍÆäÀ̽º ¿ªÇÒ¸¸ ÇÑ´Ù. ´Ü, ÀÌÀü ³ëµå°¡ Á¸ÀçÇÏÁö ¾Ê´Â °æ¿ì¿¡ ´ëÇؼ­´Â ¿¹¿Ü 󸮸¦ ÇØ¾ß Çϴµ¥ TargetÀÌ headÀÎ °æ¿ì°¡ ÀÌ¿¡ ÇØ´çÇÑ´Ù. ¸Ó¸® ³ëµåÀÇ ¿ÞÂÊ¿¡ ¾î¶² ³ëµå¸¦ »ðÀÔÇÒ ¼ö´Â ¾øÀ¸¹Ç·Î ¿¡·¯·Î ó¸®ÇÑ´Ù.

»ðÀÔ°ú ´Þ¸® Ãß°¡´Â ¸®½ºÆ®ÀÇ Á¦ÀÏ ³¡¿¡ »õ·Î¿î ³ëµå¸¦ ´õÇÏ´Â °ÍÀÌ´Ù. ¹æ¹ýÀº »ðÀÔ°ú µ¿ÀÏÇÏÁö¸¸ »ðÀÔ À§Ä¡°¡ ²¿¸®·Î Á¤ÇØÁ® ÀÖ´Ù´Â °Í¸¸ ´Ù¸£´Ù. ¸®½ºÆ®ÀÇ Áß°£¿¡ ³ëµå¸¦ »ðÀÔÇÏ´Â °æ¿ìº¸´Ù Á¦ÀÏ ³¡¿¡ Ãß°¡ÇÏ´Â °æ¿ì°¡ ÈξÀ ´õ ¸¹´Ù. AppendNode ÇÔ¼ö´Â ´Ü¼øÈ÷ ²¿¸®¸¦ ã°í ¿À¸¥ÂÊ »ðÀÔ ÇÔ¼ö¸¦ È£ÃâÇÏ¿© ²¿¸® ´ÙÀ½¿¡ »õ ³ëµå¸¦ »ðÀÔÇÑ´Ù. ²¿¸®¸¦ ãÀ» ¶§´Â ¸Ó¸®ºÎÅÍ ¼øȸÇϸ鼭 ¸µÅ©°¡ NULLÀÎ ³ëµå¸¦ ã´Âµ¥ for¹® Çϳª·Î °£´ÜÈ÷ ±¸ÇöÇÒ ¼ö ÀÖ´Ù. ¹°·Ð ¸®½ºÆ®°¡ ±æ¾îÁö¸é ²¿¸®¸¦ ã´Â ½Ã°£µµ ±×¸¸Å­ ´À·ÁÁø´Ù.

³ëµåÀÇ »èÁ¦

³ëµå »èÁ¦ ÇÔ¼ö´Â ´Ü¼ø ¿¬°á ¸®½ºÆ®¿Í ¸¶Âù°¡Áö·Î DeleteNodeÀÌ´Ù. ´Ü¼ø ¿¬°á ¸®½ºÆ®ÀÇ °æ¿ì´Â ÀÌÀü ³ëµåÀÇ ¸µÅ©¸¦ Á¶ÀÛÇÒ ¼ö ¾øÀ¸¹Ç·Î TargetÀÇ ¿À¸¥ÂÊ ³ëµå¸¦ »èÁ¦ÇßÁö¸¸ ÀÌÁß ¿¬°á ¸®½ºÆ®´Â ¾çÂÊ ³ëµå¿¡ ¸ðµÎ Á¢±ÙÇÒ ¼ö ÀÖÀ¸¹Ç·Î TargetÀÚü¸¦ »èÁ¦ÇÒ ¼ö ÀÖ´Ù. ±×·¯¹Ç·Î »èÁ¦ÇÏ°íÀÚ ÇÏ´Â ³ëµå¸¦ ¹Ù·Î Àü´ÞÇÏ¸é µÈ´Ù. µÎ ³ëµåÀÇ Áß°£¿¡ ÀÖ´Â ³ëµå¸¦ »èÁ¦ÇÏ´Â ÀϹÝÀûÀÎ °æ¿ì¸¦ ¸ÕÀú º¸ÀÚ. ´ÙÀ½°ú °°ÀÌ 1, 2, 3 ³ëµå°¡ ¿¬°áµÇ¾î ÀÖ´Â »óÅ¿¡¼­ ³ëµå 2¸¦ »èÁ¦ÇÏ·Á°í ÇÑ´Ù.

Äڵ带 °£´ÜÇÏ°Ô Çϱâ À§ÇØ Å¸°ÙÀÇ ÁÂ¿ì ³ëµå¸¦ Left, Right¿¡ ±¸ÇØ ³õ´Âµ¥ Left´Â Target->prev, Right´Â Target->next·Î ½±°Ô ±¸ÇÒ ¼ö ÀÖ´Ù. ¹Ì¸® ÁÂ¿ì ³ëµå¸¦ ±¸ÇØ ³õÁö ¾ÊÀ¸¸é Target->prev->next µûÀ§ÀÇ º¹ÀâÇÑ ¼ö½ÄÀÌ ÇÊ¿äÇØÁö°í Äڵ带 Àб⠾î·Á¿öÁø´Ù. Target ÀÚü´Â Àá½Ã ÈÄ ÇØÁ¦µÉ °ÍÀ̹ǷΠ¸µÅ©¸¦ Á¶ÀÛÇÒ ÇÊ¿ä°¡ ¾øÀ¸¸ç Left, Right°¡ ¼­·Î ÀÌ¿ôÇÒ ¼ö ÀÖµµ·Ï¸¸ ÇÏ¸é µÈ´Ù.

LeftÀÇ ´ÙÀ½ ³ëµå¸¦ Right·Î ÁöÁ¤ÇÏ°í RightÀÇ ÀÌÀü ³ëµå¸¦ Left·Î ÁöÁ¤Çϸé ÀÌ µÎ ³ëµå°¡ Á÷Á¢ ¿¬°áµÇ¾î Áß°£ÀÇ ³ëµå 2´Â ¿¬°á¿¡¼­ Á¦¿ÜµÈ´Ù. free(Target)À¸·Î TargetÀÇ ¸Þ¸ð¸®¸¦ ÇØÁ¦Çϸé ÀÌ ³ëµå´Â ¹°¸®ÀûÀ¸·Î »ç¶óÁø´Ù.

ÀÌ ÇÔ¼ö´Â ¿©·¯ °¡Áö ¿¹¿Ü¸¦ ó¸®Çϴµ¥ TargetÀÌ NULLÀ̾ ³¡ ³ëµåÀÏ ¶§´Â »èÁ¦ÇÒ ´ë»óÀÌ ¾øÀ¸¹Ç·Î »èÁ¦¸¦ °ÅºÎÇÑ´Ù. ¶ÇÇÑ TargetÀÌ headÀÏ ¶§µµ ¸Ó¸®¸¦ Áö¿ï ¼ö ¾øÀ¸¹Ç·Î À̶§µµ »èÁ¦ÇÒ ¼ö ¾ø´Ù. Target ÀÚü°¡ ¸¶Áö¸· ³ëµåÀÎ °æ¿ì´Â »èÁ¦´Â °¡´ÉÇÏÁö¸¸ ¿À¸¥ÂÊ ³ëµåÀÎ Right°¡ Á¸ÀçÇÏÁö ¾ÊÀ¸¹Ç·Î RightÀÇ prev¸¦ Á¶ÀÛÇÒ ÇÊ¿ä°¡ ¾ø°í Á¶ÀÛÇؼ­µµ ¾ÈµÈ´Ù.

°Ë»ö

FindNodeByIndex ÇÔ¼ö´Â ¼ø¼­°ªÀ¸·ÎºÎÅÍ ¿øÇÏ´Â ³ëµå¸¦ ã´Â´Ù. ¿¬°á ¸®½ºÆ®ÀÇ ³ëµå´Â ¹è¿­°ú ´Þ¸® ÷ÀÚ°¡ ¾øÁö¸¸ ¿¬°á ¼ø¼­¿¡ µû¶ó ¹øÈ£¸¦ ºÙÀÏ ¼ö ÀÖ´Ù. ¼ø¼­´Â 0ºÎÅÍ ½ÃÀÛÇϸç ù ¹ø° ³ëµå°¡ 0¹ø, µÎ ¹ø° ³ëµå°¡ 1¹øÀÎ ¼ÀÀÌ´Ù. ¸Ó¸®ºÎÅÍ ¼øȸÇϸ鼭 °¢ ³ëµåÀÇ ¹øÈ£¸¦ ¼¼´Ù°¡ ÁöÁ¤ÇÑ ¹øÈ£¿¡ À̸£·¶À» ¶§ÀÇ ³ëµå Æ÷ÀÎÅ͸¦ ¸®ÅÏÇÑ´Ù. ¸¸¾à ¼ø¼­°ªÀÌ ÃÑ ³ëµå °³¼öº¸´Ù ´õ Å©´Ù¸é °Ë»öÀº ½ÇÆÐÇÏ°í NULLÀÌ ¸®ÅϵȴÙ.

FindNodeIndex´Â ¹Ý´ë·Î ƯÁ¤ ³ëµåÀÇ ¼ø¼­°ªÀ» ±¸Çϴµ¥ ¼øȸÁß¿¡ Æ÷ÀÎÅÍ°¡ ÀÏÄ¡ÇÏ´Â ³ëµåÀÇ ¼ø¼­°ªÀ» ¸®ÅÏÇÑ´Ù. ¼ø¼­°ªÀ¸·Î ³ëµå¸¦ ã´Â °Íº¸´Ù ´õ ½Ç¿ëÀûÀÎ °Ë»ö ÇÔ¼ö´Â ³»¿ëÀ¸·Î ³ëµå¸¦ ã´Â °ÍÀÌ´Ù. ÀÌ ¿¹Á¦ÀÇ °æ¿ì ³»¿ë °Ë»ö ÇÔ¼ö¸¦ ÀÛ¼ºÇÑ´Ù¸é ¾Æ¸¶ ´ÙÀ½°ú °°Àº ÇüÅ·ΠÀÛ¼ºÇÒ ¼ö ÀÖÀ» °ÍÀÌ´Ù.

 

Node *FindNode(Node *Start,Node *aNode)

{

     Node *Now;

 

     for (Now=Start->next;Now;Now=Now->next) {

          if (Now->value == aNode->value) {

              return Now;

          }

     }

     return Now;

}

 

³»¿ë °Ë»öÀ» ÇÏ·Á¸é ¸®½ºÆ® Àüü¸¦ ¼øȸÇϸ鼭 ¿øÇÏ´Â °ªÀ» °¡Áø ³ëµå¸¦ ã¾Æ¾ß ÇÑ´Ù. Àμö·Î Àü´ÞµÈ Start ³ëµå ÀÌÈĺÎÅÍ ¼øȸ¸¦ Ç쵂 StartÀÚü´Â °Ë»ö ´ë»ó¿¡¼­ Á¦¿ÜÇߴµ¥ ÀÌ´Â ¿¬¼ÓÀûÀÎ °Ë»öÀ» À§Çؼ­ÀÌ´Ù. Á¶°Ç¿¡ ¸Â´Â ³ëµå°¡ ¿©·µ ÀÖÀ» °æ¿ì °Ë»öµÈ ³ëµåºÎÅÍ ´Ù½Ã °Ë»öÀ» ½ÃÀÛÇÏ¸é ¸®½ºÆ®ÀÇ ³¡±îÁö ¿øÇÏ´Â ³ëµå¸¦ ãÀ» ¼ö ÀÖ´Ù. ÀÌ¿¡ ºñÇØ strchr Ç¥ÁØ ÇÔ¼ö´Â ÁöÁ¤ÇÑ ¹øÁöºÎÅÍ °Ë»öÀ» ½ÃÀÛÇϹǷΠ°Ë»öµÈ ¹®ÀÚ¸¦ Á¦¿Ü½ÃÅ°±â À§ÇØ ¹Ýµå½Ã p++ÇÏ¿© ´ÙÀ½ À§Ä¡·Î À̵¿ÇØ¾ß ¿¬¼âÀûÀÎ °Ë»öÀ» ÇÒ ¼ö ÀÖ´Ù. ¸®½ºÆ® Àüü¸¦ ¼øȸÇߴµ¥ Á¶°Ç¿¡ ¸Â´Â ³ëµå°¡ ¹ß°ßµÇÁö ¾Ê¾Ò´Ù¸é À̶§´Â NULL¸¦ ¸®ÅÏÇÑ´Ù.

³»¿ë °Ë»ö ÇÔ¼ö¸¦ ¸¸µå´Â ¹æ¹ýÀÌ Æ¯º°È÷ ¾î·ÆÁö´Â ¾ÊÁö¸¸ ¿¹Á¦¿¡´Â ÀÌ ÇÔ¼ö°¡ ÀÛ¼ºµÇ¾î ÀÖÁö ¾Ê´Ù. ¿Ö³ÄÇÏ¸é °Ë»öÀº º»ÁúÀûÀ¸·Î Node¿¡ Á¾¼ÓÀûÀ̱⠶§¹®¿¡ ¹Ì¸® ÇÔ¼ö·Î ¸¸µé¾î ³õÀ» °¡Ä¡°¡ ¾øÀ¸¸ç ¸¸µé¾î ºÁ¾ß ±×´ë·Î Àç»ç¿ëÇÒ ¼öµµ ¾ø±â ¶§¹®ÀÌ´Ù. À§ÀÇ FindNode ÇÔ¼ö´Â ³ëµå°¡ Á¤¼öÇüÀÇ value¸¦ °¡Áø´Ù´Â °¡Á¤À» ÇÏ°í ¸¸µç °ÍÀÏ »ÓÀÌ¸ç ¸¸¾à ¹®ÀÚ¿­À̳ª Æ÷ÀÎÅ͸¦ °¡Áø´Ù¸é °Ë»ö ¹æ¹ýµµ ´Þ¶óÁú °ÍÀÌ´Ù. ¶ÇÇÑ ¹®ÀÚ¿­ÀÇ °æ¿ì ¿ÏÀü ÀÏÄ¡¸¦ °Ë»öÇÒ °ÍÀÎÁö ºÎºÐ¸¸ ÀÏÄ¡ÇÏ´Â ³ëµåµµ °Ë»ö ´ë»óÀÎÁö, ´ë¼Ò¹®ÀÚ ±¸ºÐÀº ¾î¶»°Ô ÇÒ °ÍÀÎÁö µî¿¡ µû¶ó ³ëµå ºñ±³ ¹æ¹ýµµ ´Þ¶óÁø´Ù.

¸¸¾à Á¤ Àç»ç¿ë °¡´ÉÇÑ °Ë»ö ÇÔ¼ö¸¦ ÀÛ¼ºÇÏ°íÀÚ ÇÑ´Ù¸é °Ë»ö ÇÔ¼ö°¡ ÇÔ¼ö Æ÷ÀÎÅ͸¦ ¹Þ¾ÆµéÀÌ°í ¼øȸÁß¿¡ ºñ±³ ÇÔ¼ö¸¦ ºÒ·¯¼­ ÇÁ·Î±×·¥ÀÌ Á÷Á¢ ³ëµå¸¦ ºñ±³ÇÏ´Â ¹æ¹ýÀ» ¾µ ¼ö´Â ÀÖ´Ù. ±×·¯³ª ÀÌ·¸°Ô ÇÒ ¹Ù¿¡¾ß ±×³É ÇÁ·Î±×·¥ÀÌ Á÷Á¢ ¼øȸÇϸ鼭 °Ë»öÀ» ÇÏ´Â ÆíÀÌ ÈξÀ ´õ °£ÆíÇÏ´Ù. ºñ±³ ÇÔ¼ö¸¦ ¸¸µé°í ÇÔ¼ö Æ÷ÀÎÅ͸¦ Àü´ÞÇÏ´Â °Íº¸´Ù´Â Â÷¶ó¸® ¼øȸÇÏ´Â °Ô ÈξÀ ´õ ½±´Ù. ±×·¡¼­ °Ë»öÀÌ ÇÊ¿äÇÒ °æ¿ì ÇÁ·Î±×·¥ÀÇ ÇÊ¿ä¿¡ ¸Â°Ô FindNode ÇÔ¼ö´Â ¸Å¹ø ¼öÁ¤Çؼ­ »ç¿ëÇϰųª ¾Æ´Ï¸é È£Ãâ¿ø¿¡¼­ À§ ÇÔ¼ö°¡ ÇÏ´Â ¹æ¹ý´ë·Î Á÷Á¢ ¼øȸÇϸ鼭 ãµÇ if¹®ÀÇ Á¶°Ç¸¸ ³ëµå¿¡ ¸Â°Ô ¼öÁ¤ÇÏ¸é µÈ´Ù.

main¿¡¼­´Â ¿¬°á ¸®½ºÆ®¸¦ ¼øȸÇϸ鼭 3ÀÇ °ªÀ» °¡Áø ³ëµå¸¦ °Ë»öÇÏ¿´À¸¸ç ÀÌ ³ëµåÀÇ ¾Õ, µÚ ³ëµå°ªµµ °°ÀÌ Ãâ·ÂÇØ º¸¾Ò´Ù. ÀÌÁß ¿¬°á ¸®½ºÆ®À̹ǷΠprev, next¸¦ ÀÐÀ¸¸é °ð¹Ù·Î ÀüÈÄÀÇ ³ëµå¸¦ Á¶»çÇÒ ¼ö ÀÖ´Ù. FindNodeByIndex ÇÔ¼ö·Î 3¹ø° ³ëµå¸¦ ã¾Æ ±× °ªÀ» Ãâ·ÂÇØ º¸±âµµ ÇÑ´Ù.

°³¼ö Á¶»ç

¿¬°á ¸®½ºÆ®¿¡ Æ÷ÇÔµÈ ³ëµåÀÇ ÃÑ °³¼ö¸¦ ¾Ë°í ½Í´Ù¸é À̶§µµ ¼øȸÇØ¾ß ÇÑ´Ù. ¸Ó¸®¿¡¼­ºÎÅÍ ¼øȸÇϸ鼭 °³¼ö¸¦ Çì¾Æ¸®´Ù°¡ ³¡ ³ëµå¿¡ À̸£·¶À» ¶§ Çì¾Æ¸®°í ÀÖ´ø °³¼ö¸¦ ¸®ÅÏÇÏ¸é µÈ´Ù. Á¤¼ö°ª Çϳª¸¦ ¾ò±â À§ÇØ ¿¬°á ¸®½ºÆ® Àüü¸¦ ¼øȸÇØ¾ß ÇÑ´Ù´Â °ÍÀÌ Á¶±Ý ºÒ¸¸½º·´±â´Â ÇÏÁö¸¸ ¾î¿ ¼ö°¡ ¾ø´Ù. °³¼ö¸¦ Á¶»çÇÒ ÀÏÀÌ ÀÚÁÖ ÀÖ´Ù¸é º°µµÀÇ Àü¿ªº¯¼ö¸¦ ¼±¾ðÇÏ°í »ðÀÔ, »èÁ¦½Ã¸¶´Ù ÀÌ º¯¼ö¸¦ °ü¸®ÇØ ÁÖ´Â ¹æ¹ýÀ» »ý°¢ÇØ º¼ ¼ö ÀÖ´Ù.