DoubleLinkedList(이중연결리스트)

doublylist.cpp

doublylist.h

main.cpp

이번에는 이중연결리스트 입니다.

단일 연결리스트에 비해서 이중 연결리스트는 두개의 포인터가 존재합니다.

기존의 연결리스트가 오른쪽 링크(Right Link)만 있었다면 이중 연결리스트는 이전의 노드를 가지는 왼쪽 링크(Left Link)를 가지게 됩니다.

이러한 양방향 링크는 이전 노드에 직접적 접근이 가능하다는 접근 편의성의 장점이 있지만 동시에 추가 메모리 공간을 사용한다는 단점이 있습니다.

단일연결리스트를 구현할 때는 Header 포인터만 사용했지만, 이중 연결리스트를 구현할 때는 Header 노드를 사용해야 합니다. 

이유는 오른쪽 링크과 왼쪽 링크에 각각 연결 리스트의 첫 번째 노드와 마지막 노드를 가르키는 포인터 값을 저장하며 , 이를 통해 구현의 편리함을 느낄 수 있습니다. 

일반적으로,

pNode == pNode->pLLink->pRLink = pNode->pRLink->pLLink

는 모두 같은 값을 나타냅니다. 

 

doublylist.h

1. #ifndef _DOUBLYLIST_
2. #define _DOUBLYLIST_
3.  
4. typedef struct DoublyListNodeType{
5.     int data;
6.     struct DoublyListNodeType* pLLink;
7.     struct DoublyListNodeType* pRLink;
8. }DoublyListNode;
9.  
10. typedef struct DoublyListType{
11.     int currentElementCount;  //현재 저장된 원소의 개수
12.     DoublyListNode headerNode;//헤더 노드(header Node)
13. }DoublyList;
14.  
15. DoublyList* createDoublyList();
16. void deleteDoublyList(DoublyList* pList);
17. int addDLElement(DoublyList* pList, int position, DoublyListNode element);
18. int removeDLElement(DoublyList* pList, int position);
19. void clearDoublyList(DoublyList* pList);
20. int getDoublyListLength(DoublyList* pList);
21. DoublyListNode* getDLElement(DoublyList* pList, int position);
22. void displayDoublyList(DoublyList* pList);
23. #endif
24.  
25. #ifndef _COMMON_LIST_DEF_
26. #define _COMMON_LIST_DEF_
27.  
28. #define TRUE 1
29. #define FALSE 0
30.  
31. #endif
32.  

doublylist.c

1. #include <stdio.h>
2. #include <stdlib.h>
3. #include <string.h>
4. #include "doublylist.h"
5.  
6. DoublyList* createDoublyList()
7. {
8.     DoublyList* pReturn = NULL;
9.  
10.     pReturn = (DoublyList*) malloc(sizeof(DoublyList));
11.    
12.     if(pReturn != NULL)
13.     {
14.         memset(pReturn, 0, sizeof(DoublyList));
15.  
16.         pReturn->headerNode.pLLink = NULL;
17.         pReturn->headerNode.pRLink = NULL;
18.     }
19.     else
20.     {
21.         printf("memory error, createDoublyList()\n");
22.         return NULL;
23.     }
24.     return pReturn;
25. }
26. int addDLElement(DoublyList* pList, int position, DoublyListNode element)
27. {
28.     int i = 0;
29.     int ret = FALSE;
30.     DoublyListNode* pPreNode = NULL;
31.     DoublyListNode* pNewNode = NULL;
32.    
33.     if(pList != NULL)
34.     {
35.         if(position >= 0 && position <= pList->currentElementCount)
36.         {
37.             pNewNode = (DoublyListNode*) malloc(sizeof(DoublyListNode));
38.             if(pNewNode == NULL)
39.             {
40.                 printf("error, memory, addDLElement()\n");
41.                 return ret;
42.             }
43.             *pNewNode = element;
44.             pNewNode->pLLink = NULL;
45.             pNewNode->pRLink = NULL;
46.  
47.             pPreNode = &(pList->headerNode);
48.  
49.             for(i=0; i<position; i++)
50.             {
51.                 pPreNode = pPreNode->pRLink;
52.             }
53.             pNewNode->pLLink = pPreNode;
54.             pNewNode->pRLink = pPreNode->pRLink;
55.             pPreNode->pRLink = pNewNode;
56.             pPreNode->pRLink->pLLink = pNewNode;
57.  
58.             pList->currentElementCount++;
59.             ret = TRUE;
60.         }
61.         else
62.         {
63.             printf("position error, addDLElement()\n");
64.         }
65.     }
66.     else
67.     {
68.         printf("pList is NULL\n");
69.     }
70.     return NULL;
71. }
72. int removeDLElement(DoublyList* pList, int position)
73. {
74.     int i = 0;
75.     int ret = FALSE;
76.     int arraycount = 0;
77.     DoublyListNode* pDelNode = NULL;
78.     DoublyListNode* pPreNode = NULL;
79.    
80.     if(pList != NULL)
81.     {
82.         arraycount = getDoublyListLength(pList);
83.  
84.         if(position >= 0 && position < arraycount)
85.         {
86.  
87.             pPreNode = &(pList->headerNode);
88.  
89.             for(i = 0; i<position; i++)
90.             {
91.                 pPreNode = pPreNode->pRLink;
92.             }
93.             pDelNode = pPreNode->pRLink;
94.  
95.             pPreNode->pRLink = pDelNode->pRLink;
96.             pDelNode->pRLink->pLLink = pPreNode;
97.             free(pDelNode);
98.             pList->currentElementCount--;
99.             ret = TRUE;
100.         }
101.         else
102.         {
103.             printf("position error, removeDLElement()\n");
104.         }
105.     }
106.     return ret;
107. }
108. void deleteDoublyList(DoublyList* pList)
109. {
110.     if(pList!=NULL)
111.     {
112.         clearDoublyList(pList);
113.         free(pList);
114.     }
115. }
116. void clearDoublyList(DoublyList* pList)
117. {
118.     if(pList!=NULL)
119.     {
120.         while(pList->currentElementCount>0)
121.         {
122.             removeDLElement(pList, 0);
123.         }
124.     }
125. }
126. int getDoublyListLength(DoublyList* pList)
127. {
128.     int ret;
129.  
130.     if(pList!=NULL)
131.     {
132.         ret = pList->currentElementCount;
133.     }
134.     return ret;
135. }
136. DoublyListNode* getDLElement(DoublyList* pList, int position)
137. {
138.     DoublyListNode* pReturn = NULL;
139.     DoublyListNode* pNode = NULL;
140.     int i = 0;
141.     if(pList!=NULL)
142.     {
143.         if(position >=0 && position < pList->currentElementCount)
144.         {
145.             pNode = pList->headerNode.pRLink;
146.             for(i=0; i<position; i++)
147.             {
148.                 pNode = pNode->pRLink;
149.             }
150.             pReturn = pNode;
151.         }
152.         else
153.         {
154.             printf("position error, getDLElement()\n");
155.         }
156.     }
157.     return pReturn;
158. }
159. void displayDoublyList(DoublyList* pList)
160. {
161.     int i = 0;
162.    
163.     if(pList != NULL)
164.     {
165.         printf("현재 노드 갯수 : %d\n", pList->currentElementCount);
166.  
167.         for(i = 0; i<pList->currentElementCount; i++)
168.         {
169.             printf("[%d] - %d\n", i, getDLElement(pList, i)->data);
170.         }
171.     }
172.     else
173.     {
174.         printf("not existed element\n");
175.     }
176. }
177.  

main.cpp

1. #include <stdio.h>
2. #include <stdlib.h>
3. #include <string.h>
4. #include "doublylist.h"
5.  
6. int main()
7. {
8.     int i, arraycount;
9.     i = arraycount = 0;
10.     DoublyList* pList = NULL;
11.     DoublyListNode* pValue = NULL;
12.     DoublyListNode node;
13.  
14.     pList = createDoublyList();
15.    
16.     if(pList != NULL)
17.     {
18.         node.data = 1;
19.         addDLElement(pList, 0, node);
20.  
21.         node.data = 3;
22.         addDLElement(pList, 1, node);
23.  
24.         node.data = 5;
25.         addDLElement(pList, 2, node);
26.  
27.         arraycount = getDoublyListLength(pList);
28.  
29.         for(i=0; i<arraycount; i++)
30.         {
31.             pValue = getDLElement(pList, i);
32.             printf("position[ %d ] - %d\n", i, pValue->data);
33.         }
34.        
35.         removeDLElement(pList, 0);
36.         displayDoublyList(pList);
37.     }
38.     return 0;
39. }
40.  

소스코드는 보시면 이해 가실꺼예요~ 

이로써 단일연결리스트, 원형 연결리스트, 더블 연결리스트 까지 다 했네요.

다음엔 다항식 할께요~