가자미의 개발이야기
C언어로 링크드리스트(연결리스트) 만들기 본문
개념
1. 포인터를 이용해서 물리적으로 떨어진 노드들을 논리적으로 연결.
2. 최대 원소 개수 지정 불필요.
3. 중간에 원소 추가 시 이동 연산 불필요.
4. 물리적으로 연결된 것이 아니기 때문에 탐색 연산 비용이 높음
헤더파일
|
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
|
#ifndef _LINKEDLIST_
#define _LINKEDLIST_
typedef struct ListNodeType
{
int data;
struct ListNodeType* pLink;
}ListNode;
typedef struct LinkedListType {
int currentElementCount;
ListNode headerNode; //데이터가 없는 헤더노드. 연결역할을 한다.
}LinkedList;
LinkedList* createLinkedList();
int addLLElement(LinkedList* pList, int position, ListNode element);
int removeLLElement(LinkedList* pLIst, int position);
ListNode* getLLElement(LinkedList* pList, int position);
void clearLinkedList(LinkedList* pList);
int getLinkedListLength(LinkedList* pList);
void deleteLinkedList(LinkedList* pList);
#endif
#ifndef _COMMON_LIST_DEF_
#define _COMMON_LIST_DEF_
#define TRUE 1
#define FALSE 0
#endif
|
cs |
함수정의코드
|
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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
|
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "linkedlist.h"
LinkedList* createLinkedList() {
LinkedList* pReturn = NULL;
pReturn = (LinkedList*)malloc(sizeof(LinkedList)); //메모리 할당
if (pReturn != NULL) {
memset(pReturn, 0, sizeof(LinkedList)); //구조체 초기화
}
else {
printf("오류, 메모리할당 createLinkedList()\n");
return NULL;
}
return pReturn;
}
int addLLElement(LinkedList* pList, int position, ListNode element) {
int ret = FALSE;
int i = 0;
ListNode* pPreNode = NULL;
ListNode* pNewNode = NULL;
if (pList != NULL) {
if (position >= 0 && position <= pList->currentElementCount) {
pNewNode = (ListNode*)malloc(sizeof(ListNode)); //추가될 노드에 메모리 할당
if (pNewNode != NULL) {
*pNewNode = element; //새로운 노드에 내용 입력(유지보수 향상을 위해 노드 자체를 입힘)
pNewNode->pLink = NULL; //연결 사슬 초기화
pPreNode = &(pList->headerNode); //들어가야할 위치를 찾기 위한 노드
for (i = 0; i < position; i++) {
pPreNode = pPreNode->pLink; //다음 노드로 계속 넘어감
}
pNewNode->pLink = pPreNode->pLink; //노드 연결
pPreNode->pLink = pNewNode;
pList->currentElementCount++;
ret = TRUE;
}
else {
printf("오류, 메모리할당 addLLElement()\n");
}
}
else {
printf("오류, 위치 인덱스 [%d], addLLElement()\n", position);
}
}
return ret;
}
int removeLLElement(LinkedList* pList, int position) {
int ret = FALSE;
int i = 0;
int arrayCount = 0;
ListNode* pNode = NULL;
ListNode* pDelNode = NULL;
if (pList != NULL) {
arrayCount = getLinkedListLength(pList);
if (position >= 0 && position < arrayCount) {
pNode = &(pList->headerNode);
for (i = 0; i < position; i++) { //노드 위치 찾기
pNode = pNode->pLink;
}
pDelNode = pNode->pLink; //노드 링크 맞추기
pNode->pLink = pDelNode->pLink;
free(pDelNode); //제거할 노드 메모리 해제
pList->currentElementCount--;
ret = TRUE;
}
else {
printf("오류, 위치 인덱스-[%d], removeLLElement()\n", position);
}
}
return ret;
}
ListNode* getLLElement(LinkedList* pList, int position) {
ListNode* pReturn = NULL;
ListNode* pNode = NULL;
if (pList != NULL) {
if (position >= 0 && position < pList->currentElementCount) {
pNode = &(pList->headerNode);
int i = 0;
for (i = 0; i <= position; i++) {
pNode = pNode->pLink;
}
pReturn = pNode;
}
}
return pReturn;
}
void deleteLinkedList(LinkedList* pList) {
if(pList!=NULL){
clearLinkedList(pList);
free(pList);
}
}
void clearLinkedList(LinkedList* pList) {
if (pList != NULL) {
if (pList->currentElementCount > 0) {
for (int i = pList->currentElementCount; i >0; i--) {
removeLLElement(pList, pList->currentElementCount - 1);
}
}
}
}
int getLinkedListLength(LinkedList* pList) {
int ret = 0;
if (pList != NULL) {
ret = pList->currentElementCount;
}
return ret;
}
int isEmpty(LinkedList* pList) {
int ret = FALSE;
if (pList != NULL) {
if (pList->currentElementCount == 0) {
ret = TRUE;
}
}
return ret;
}
|
cs |
활용 예시 코드
|
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
|
#include <stdint.h>
#include <stdlib.h>
#include "linkedlist.h"
void displayLinkedList(LinkedList* pList) {
int i = 0;
if (pList != NULL) {
printf("현재 원소 개수: %d\n", pList->currentElementCount);
for (i = 0; i < pList->currentElementCount; i++) {
printf("[%d],%d\n", i, getLLElement(pList, i)->data);
}
}
else {
printf("원소가 없어요!\n");
}
}
int main(int argc, char* argv[]) {
int i = 0;
int arrayCount = 0;
LinkedList* pList = NULL;
ListNode* pNode = NULL;
ListNode node;
pList = createLinkedList();
if (pList != NULL) {
node.data = 1;
addLLElement(pList, 0, node);
node.data = 2;
addLLElement(pList, 1, node);
node.data = 3;
addLLElement(pList, 2, node);
displayLinkedList(pList);
removeLLElement(pList, 0);
displayLinkedList(pList);
clearLinkedList(pList);
displayLinkedList(pList);
deleteLinkedList(pList);
}
return 0;
}
|
cs |
실행 결과
'Computer Science > 자료구조' 카테고리의 다른 글
| [자료구조] C언어로 배열 스택 구현하기 (0) | 2021.02.10 |
|---|---|
| [자료구조] 연결리스트로 다항식 구현하기 (0) | 2021.02.10 |
| C언어로 원형 연결 리스트 만들기 (0) | 2021.02.09 |
| C언어로 구현한 리스트 자료구조(ArrayList) (0) | 2021.02.03 |
| 알고리즘 분석 기준 (0) | 2021.01.29 |
'Computer Science/자료구조' Related Articles
more
