먼저, 연결 리스트를 구현하기 앞서 ADT(Abstract Data Type) 을 먼저 정의하자.
ADT는 쉽게 설명해서 구현 하고자 하는 코드의 기능 (함수) 을 나열한 것이라고 생각하면 된다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 | // 초기화할 리스트의 주소 값을 인자로 전달한다. // 리스트 생성 후 제일 먼저 호출되어야 하는 함수이다. void ListInit(List *plist); // 리스트에 데이터를 저장한다. 매개변수 data에 전달된 값을 저장한다. void LInsert(List* plist, LData data); // 첫 번째 데이터의 다음 데이터가 pdata가 가리키는 메모리에 저장된다. // 데이터의 참조를 위한 초기화가 진행된다. // 참조 성공 시 TRUE(1), 실패 시 FALSE(0) 을 반환 int LFirst(List* plist, LData pdata); // 참조된 데이터의 다음 데이터가 pdata가 가리키는 메모리에 저장된다. // 순차적인 참조를 위해서 반복 호출이 가능하다. // 참조를 새로 시작하려면 먼저 LFirst 함수를 호출해야 한다. // 참조 성공 시 TRUE(1), 실패 시 FALSE(0) 반환 int LNext(List* plist, LData* pdata); // LFirst 또는 LNext 함수의 마지막 반환 데이터를 삭제한다. // 삭제된 데이터는 반환된다. // 마지막 반환 데이터를 삭제하므로 연이은 반복 호출을 허용하지 않는다. LData LRemove(List* plist); // 리스트에 저장되어 있는 데이터의 수를 반환한다. int LCount(List* plist); cs | |
이 ADT를 토대로 연결 리스트를 구현 해보자.
참고로 이번에 구현 하게 될 연결 리스트는 단일 연결 리스트이다.
먼저 DLinkedList.h 이다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 | #ifndef __D_LINKED_LIST_H__ #define __D_LINKED_LIST_H__ #define TRUE 1 #define FALSE 0 typedef int LData; typedef struct _node { LData data; struct _node *next; } Node; typedef struct _linkedList { Node *head; Node *cur; Node *before; int numOfData; int (*comp)(LData d1, LData d2); } LinkedList; typedef LinkedList List; void ListInit(List *plist); void LInsert(List *plist, LData data); int LFirst(List *plist, LData *pdata); int LNext(List *plist, LData *pdata); LData LRemove(List *plist); int LCount(List *plist); #endif | cs |
그리고 DLinkedList.c 이다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 | #include <stdio.h> #include <stdlib.h> #include “DLinkedList.h” void ListInit(List* plist) { plist–>head = (Node*)malloc(sizeof(Node)); plist–>head–>next = NULL; plist–>comp = NULL; plist–>numOfData = 0; } void FInsert(List* plist, LData data) { Node* newNode = (Node*)malloc(sizeof(Node)); newNode–>data = data; newNode–>next = plist–>head–>next; plist–>head–>next = newNode; (plist–>numOfData)++; } void LInsert(List* plist, LData data) { if (plist–>comp == NULL) FInsert(plist, data); } int LFirst(List* plist, LData* pdata) { if (plist–>head–>next == NULL) return FALSE; plist–>before = plist–>head; plist–>cur = plist–>head–>next; *pdata = plist–>cur–>data; return TRUE; } int LNext(List* plist, LData* pdata) { if (plist–>cur–>next == NULL) return FALSE; plist–>before = plist–>cur; plist–>cur = plist–>cur–>next; *pdata = plist–>cur–>data; return TRUE; } LData LRemove(List* plist) { Node* rpos = plist–>cur; LData rdata = rpos–>data; plist–>before–>next = plist–>cur–>next; plist–>cur = plist–>before; free(rpos); (plist–>numOfData)––; return rdata; } int LCount(List* plist) { return plist–>numOfData; } | cs |
제대로 잘 작동하기 위해 main 함수를 작성 해보자.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 | #include <stdio.h> #include “DLinkedList.h” int main(void) { // 리스트의 생성 및 초기화 /////// List list; int data; ListInit(&list); // 5개의 데이터 저장 LInsert(&list, 11); LInsert(&list, 11); LInsert(&list, 22); LInsert(&list, 22); LInsert(&list, 33); // 저장된 데이터의 전체 출력 /////// printf(“현재 데이터의 수: %d \n”, LCount(&list)); if (LFirst(&list, &data)) { printf(“%d “, data); while (LNext(&list, &data)) printf(“%d “, data); } printf(“\n\n”); // 숫자 22을 검색하여 모두 삭제 /////// if (LFirst(&list, &data)) { if (data == 22) LRemove(&list); while (LNext(&list, &data)) { if (data == 22) LRemove(&list); } } // 삭제 후 남아있는 데이터 전체 출력 /////// printf(“현재 데이터의 수: %d \n”, LCount(&list)); if (LFirst(&list, &data)) { printf(“%d “, data); while (LNext(&list, &data)) printf(“%d “, data); } printf(“\n\n”); return 0; } | cs |