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