이 포스팅은 윤성우 님의 열혈 자료구조를 기반으로 합니다.
연결 리스트의 개념적인 이해
먼저 연결 리스트를 배우기에 앞서서 배열 기반 리스트를 살펴보면 배열은 길이의 변경이 불가능하다는 것을 알 수 있다.
typedef struct _node {
int data; // 데이터를 담을 공간
struct _node * next; // 연결의 도구
} Node;
cs
이 Node 구조체를 이용하여 필요할 때마다 하나씩 동적 할당하여 데이터를 저장하고 이들을 배열처럼 연결할 수 있는
노드 하나의 표현
노드들의 연결 표현
먼저 ADT를 살펴보자. 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);
// 초기화할 리스트의 주소 값을 인자로 전달한다.
// 리스트 생성 후 제일 먼저 호출되어야 하는 함수이다.
void LInsert(List * plist, LData data);
// 리스트에 데이터를 저장한다. 매개변수 data에 전달된 값을 저장한다.
int LFirst(List * plist, LData * pdata);
// 첫 번째 데이터가 pdata가 가리키는 메모리에 저장된다.
// 데이터의 참조를 위한 초기화가 진행된다.
// 참조 성공 시 TRUE(1), 실패 시 FALSE(0) 반환
int LNext(List * plist, LData * pdata);
// 참조된 데이터의 다음 데이터가 pdata가 가리키는 메모리에 저장된다.
// 순차적인 참조를 위해서 반복 호출이 가능하다.
// 참조를 새로 시작하려면 먼저 LFirst함수를 호출해야 한다.
// 참조 성공 시 TRUE(1), 실패 시 FALSE(0) 반환
LData LRemove(List * plist);
// LFirst 또는 LNext 함수의 마지막 반환 데이터를 삭제한다.
// 삭제된 데이터는 반환된다.
// 마지막 반환 데이터를 삭제하므로 연이은 반복 호출을 허용하지 않는다.
int LCount(List * plist);
// 리스트에 저장되어 있는 데이터의 수를 반환한다.
void SetSortRule(List * plist, int (* comp)(LData d1, LData d2));
// 리스트에 정렬의 기준이 되는 함수를 등록한다.
cs
배열 리스트와 비교해보면 SetSortRule함수가 추가된 것을 볼 수 있으며 이는 Head에 추가할지 Tail에 추가할지 정하는 것이다. 장단점은 각각 다음과 같다.
Head 추가 방식과 Tail 추가 방식의 장단점 비교
또한 SetSortRule 함수의 매개변수를 보면 함수 포인터가 매개변수로 존재하는 것을 알 수 있는데 반환형이 int, LData형 2개를 전달받는 함수의 주소 값을 전달하는 것이다. 예를 들면 다음의 함수의 주소 값이 매개변수로 전달될 수 있다.
int WhoIsPrecede(LData d1, LData d2) {
if (d1 < d2)
return 0 ; // d1이 정렬 순서가 앞서는 경우
else
return 1 ; // d2가 정렬 순서가 앞서는 경우
}
cs
먼저 다음의 형태의 기본적인 노드의 연결 상태를 보고 단점을 파악해보자.
이제 연결 리스트를 구현해보자. 다음의 구조체를 기반으로 정의한다.
typedef struct _linkedList {
Node * head; // 더미 노드를 가리키는 멤버
Node * cur; // 참조 및 삭제를 돕는 멤버
Node * before; // 삭제를 돕는 멤버
int numOfData; // 저장된 데이터의 수를 기록하기 위한 멤버
int (* comp)(LDatat d1, LData d2); // 정렬의 기준을 등록하기 위한 멤버
} LinkedList;
cs
헤더 파일은 다음과 같다.
<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
36
37
38
#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);
void SetSortRule(List * plist, int (* comp)(LData d1, LData d2));
#endif
cs
이를 기준으로 초기화와 삽입을 살펴보자. 초기화는 다음과 같다.
void ListInit(List * plist) {
plist- > head = (Node* )malloc (sizeof (Node)); // 더미 노드의 생성
plist- > head- > next = NULL ;
plist- > comp = NULL ;
plist- > numOfData = 0 ;
}
cs
노드를 새로 추가하기 위한 함수는 다음과 같다.
void LInsert(List * plist, LData data) {
if (plist- > comp = = NULL ) // 정렬 기준이 없다면
FInsert(plist, data); // 머리에 노드를 추가
else // 정렬 기준이 있다면
SInsert(plist, data); // 정렬 기준에 의하여 노드를 추가
}
cs
여기에서 볼 수 있는 것은 comp 즉 노드를 정렬하기 위한 기준이 마련되어있느냐에 따라 FInsert, SInsert로 나뉜다는 것이다. 그러나 이들은 내부적으로 정의된 함수이기에 사용자가 직접 호출할 수 없는 함수이다.
먼저 FInsert는 다음과 같다.
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)+ + ; // 저장된 노드의 수를 하나 증가시킴
)
cs
그림으로 보면 다음과 같다.
데이터 조회 역시 배열 리스트의 그것과 비슷하지만 before과 Dummy node가 존재한다는 것에서 차이가 있다.
int LFisrt(List * plist, LData * pdata) {
if (plist- > head- > next = = NULL ) // 더미 노드가 NULL을 가리킨다면
return FALSE;
plist- > before = plist- > head; // before는 더미 노드를 가리키게 함
plist- > cur = plist- > head- > next; // cur은 첫번째 노드를 가리키게 함
* pdata = plist- > cur- > data; // 첫 번째 노드의 데이터를 전달
return TRUE; // 데이터 반환 성공!
}
cs
역시 그림으로 나타내면 다음과 같다.
LNext 역시 보면 다음과 같다.
int LNext(List * plist, LData * pdata) {
if (plist- > cur- > next = = NULL ) // cur이 NULL을 가리킨다면
return FALSE;
plist- > before = plist- > cur; // cur이 가리키던 것을 before가 가리킴
plist- > cur = plist- > cur- > next; // cur은 그 다음 노드를 가리킴
* pdata = plist- > cur- > data; // cur이 가리키는 노드의 데이터 전달
return TRUE; // 데이터 반환 성공!
}
cs
역시 그림으로 나타내면 다음과 같다.
노드의 삭제 역시 배열 기반 리스트의 삭제와 비슷하다.
LData LRemove(List * plist) {
Node * rpos = plist- > cur; // 소멸 대상의 주소 값을 rpos에 저장
LData rdata = rpos- > data; // 소멸 대상의 데이터를 rdata에 저장
plist- > before- > next = plist- > cur- > next; // 소멸 대상을 리스트에서 제거
plist- > cur = plist- > before; // cur이 가리키는 위치를 재조정!
free (rpos); // 리스트에서 제거된 노드 소멸
(plist- > numOfData)- - ; // 저장된 데이터의 수 하나 감소
return rdata; // 제거된 노드의 데이터 반환
}
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
#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);
void SetSortRule(List * plist, int (* comp)(LData d1, LData d2));
#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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#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 SInsert(List * plist, LData data)
{
Node * newNode = (Node* )malloc (sizeof (Node));
Node * pred = plist- > head;
newNode- > data = data;
while (pred- > next ! = NULL & &
plist- > comp(data, pred- > next- > data) ! = 0 )
{
pred = pred- > next;
}
newNode- > next = pred- > next;
pred- > next = newNode;
(plist- > numOfData)+ + ;
}
void LInsert(List * plist, LData data)
{
if (plist- > comp = = NULL )
FInsert(plist, data);
else
SInsert(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;
}
void SetSortRule(List * plist, int (* comp)(LData d1, LData d2))
{
plist- > comp = comp;
}
cs
<DLinkedListMain.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
#include < stdio.h>
#include "DLinkedList.h"
int main(void )
{
// List의 생성 및 초기화 /////////////////////////////
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
원형 연결 리스트 (Circular Linked List)
단순 연결 리스트에서 마지막 노드가 첫 번째 노드를 가리켜서 원의 형태로 연결이 된 리스트를 원형 연결 리스트 라고 한다. 이를 그림으로 나타내면 다음과 같다.
위의 그림에서 head나 tail에 새로운 노드 1을 추가한다고 가정하면 1 -> 2 -> 4 -> 6 -> 8 -> 1 .... 의 형태 혹은
void LInsert(List* plist, Data data) { // tail에 추가
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
if (plist->tail == NULL) { // 비어있는 경우
plist->tail = newNode;
newNode->next = newNode;
}
else {
newNode->next = plist->tail->next; // 새 노드와 기존에 저장된 노드 연결
plist->tail->next = newNode; // 기존 노드의 tail이 새 노드를 가리키게 연결
plist->tail = newNode; // tail이 새로 추가된 노드를 가르키게 함
}
(plist->numOfData)++;
}
void LInsertFront(List* plist, Data data) { // Head에 추가
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
if(plist->tail == NULL) { // 비어있는 경우
plist->tail = newNode;
newNode->next = newNode;
}
else {
newNode->next = plist->tail->next; // 새 노드와 기존에 저장된 노드 연결
plist->tail->next = newNode; // 기존 노드의 tail이 새 노드를 가르키게 연결
}
(plist->numOfData)++;
}
이번에는 조회를 살펴보자. 조회의 경우도 Fisrt, Next즉 두가지의 경우에 대한 함수가 존재한다.
int LFirst(List* plist, Data* pdata) {
if (plist->tail == NULL) { // 비어있는 경우
return FALSE;
}
plist->before = plist->tail; // before가 tail을 가리키게 한다.
plist->cur = plist->tail->next; // cur이 tail의 다음을 가리키게 한다
*pdata = plist->cur->data;
return TRUE;
}
LNext의 경우도 단순히 before가 cur을 가리키게 하고 cur에 cur이 가리키는 다음 노드를 가리키게 하면 된다.
int LNext(List* plist, Data* pdata) {
if (plist->tail == NULL) { // 비어있는 경우
return FALSE;
}
plist->before = plist->cur; // before가 cur을 가리키게 한다
plist->cur = plist->cur->next; // cur이 cur의 다음을 가리키게 한다.
*pdata = plist->cur->data;
return TRUE;
}
이 두가지 함수 모두 리스트에 원소가 없을 경우에 대해서 처리가 필요한데 단순하게 ADT를 참조하여 노드가 존재하지 않으면 False를 반환하면 된다.
이번에는 노드의 삭제에 대해서 알아보자.
Data LRemove(List* plist) {
Node* rpos = plist->cur;
Data rdata = rpos->data;
if (rpos == plist->tail) { // 삭제하려는 노드가 tail인 경우
if (plist->tail == plist->tail->next) { // 노드가 하나인 경우
plist->tail == NULL;
}
else {
plist->tail = plist->before;
}
}
plist->before->next = plist->cur->next;
plist->cur = plist->before;
free(rpos);
(plist->numOfData)--;
return rdata;
}
위에서 볼 수 있듯 삭제하려는 노드가 tail이 아닌 경우는 다음의 그림처럼 삭제를 진행하면 된다.
그러나 삭제하려는 노드가 tail인 경우는 단순하게 tail을 하나 앞으로 이동시키면 된다.
단순히 plist->tail = plist->before;을 통해서 말이다.
전체의 코드는 각각 다음과 같다.
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
#pragma once
#ifndef __C_LINKED_LIST_H__
#define __C_LINKED_LIST_H__
#define TRUE 1
#define FALSE 0
typedef int Data;
typedef struct _node
{
Data data;
struct _node* next;
} Node;
typedef struct _CLL
{
Node* tail;
Node* cur;
Node* before;
int numOfData;
} CList;
typedef CList List;
void ListInit(List* plist);
void LInsert(List* plist, Data data);
void LInsertFront(List* plist, Data data);
int LFirst(List* plist, Data* pdata);
int LNext(List* plist, Data* pdata);
Data LRemove(List* plist);
int LCount(List* plist);
#endif
cs
<CLinkedList.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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include < stdio.h>
#include "CLinkedList.h"
void ListInit(List* plist) { // 초기화
plist- > tail = NULL ;
plist- > cur = NULL ;
plist- > before = NULL ;
plist- > numOfData = 0 ;
}
void LInsert(List* plist, Data data) { // tail에 추가
Node* newNode = (Node* )malloc (sizeof (Node));
newNode- > data = data;
if (plist- > tail = = NULL ) { // 비어있는 경우
plist- > tail = newNode;
newNode- > next = newNode;
}
else {
newNode- > next = plist- > tail- > next; // 새 노드와 기존에 저장된 노드 연결
plist- > tail- > next = newNode; // 기존 노드의 tail이 새 노드를 가리키게 연결
plist- > tail = newNode; // tail이 새로 추가된 노드를 가르키게 함
}
(plist- > numOfData)+ + ;
}
void LInsertFront(List* plist, Data data) { // Head에 추가
Node* newNode = (Node* )malloc (sizeof (Node));
newNode- > data = data;
if (plist- > tail = = NULL ) { // 비어있는 경우
plist- > tail = newNode;
newNode- > next = newNode;
}
else {
newNode- > next = plist- > tail- > next; // 새 노드와 기존에 저장된 노드 연결
plist- > tail- > next = newNode; // 기존 노드의 tail이 새 노드를 가르키게 연결
}
(plist- > numOfData)+ + ;
}
int LFirst(List* plist, Data* pdata) {
if (plist- > tail = = NULL ) { // 비어있는 경우
return FALSE;
}
plist- > before = plist- > tail; // before가 tail을 가리키게 한다.
plist- > cur = plist- > tail- > next; // cur이 tail의 다음을 가리키게 한다
* pdata = plist- > cur- > data;
return TRUE;
}
int LNext(List* plist, Data* pdata) {
if (plist- > tail = = NULL ) { // 비어있는 경우
return FALSE;
}
plist- > before = plist- > cur; // before가 cur을 가리키게 한다
plist- > cur = plist- > cur- > next; // cur이 cur의 다음을 가리키게 한다.
* pdata = plist- > cur- > data;
return TRUE;
}
Data LRemove(List* plist) {
Node* rpos = plist- > cur;
Data rdata = rpos- > data;
if (rpos = = plist- > tail) { // 삭제하려는 노드가 tail인 경우
if (plist- > tail = = plist- > tail- > next) { // 노드가 하나인 경우
plist- > tail = = NULL ;
}
else {
plist- > tail = plist- > before;
}
}
plist- > before- > next = plist- > cur- > next;
plist- > cur = plist- > before;
free (rpos);
(plist- > numOfData)- - ;
return rdata;
}
int LCount(List* plist) {
return (plist- > numOfData);
}
cs
<CLinkedListMain.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
#include < stdio.h>
#include "CLinkedList.h"
int main(void )
{
// 원형 연결 리스트의 생성 및 초기화 ///////
List list;
int data, i, nodeNum;
ListInit(& list);
// 리스트에 5개의 데이터를 저장 ///////
LInsert(& list, 3 );
LInsert(& list, 4 );
LInsert(& list, 5 );
LInsertFront(& list, 2 );
LInsertFront(& list, 1 );
// 리스트에 저장된 데이터를 연속 3회 출력 ///////
if (LFirst(& list, & data))
{
printf ("%d " , data);
for (i = 0 ; i < LCount(& list) * 3 - 1 ; i+ + )
{
if (LNext(& list, & data))
printf ("%d " , data);
}
}
printf ("\n" );
// 2의 배수를 찾아서 모두 삭제 ///////
nodeNum = LCount(& list);
if (nodeNum ! = 0 )
{
LFirst(& list, & data);
if (data % 2 = = 0 )
LRemove(& list);
for (i = 0 ; i < nodeNum - 1 ; i+ + )
{
LNext(& list, & data);
if (data % 2 = = 0 )
LRemove(& list);
}
}
// 전체 데이터 1회 출력 ///////
if (LFirst(& list, & data))
{
printf ("%d " , data);
for (i = 0 ; i < LCount(& list) - 1 ; i+ + )
{
if (LNext(& list, & data))
printf ("%d " , data);
}
}
return 0 ;
}
cs
양방향 연결 리스트
양방향 연결 리스트의 경우 앞서서 구현했던 단순 연결 리스트에서 좌측 혹은 우측을 연결하는 포인터 변수의 존재가 큰 차이점 이다. 그렇다면 헤더파일과 그림을 보고 양방향 연결 리스트를 구현해보자. 헤더파일은 다음과 같다.
#ifndef __DB_LINKED_LIST_H__
#define __DB_LINKED_LIST_H__
#define TRUE 1
#define FALSE 0
typedef int Data;
typedef struct _node
{
Data data;
struct _node * next;
struct _node * prev;
} Node;
typedef struct _dbLinkedList
{
Node * head;
Node * cur;
int numOfData;
} DBLinkedList;
typedef DBLinkedList List;
void ListInit(List * plist);
void LInsert(List * plist, Data data);
int LFirst(List * plist, Data * pdata);
int LNext(List * plist, Data * pdata);
int LPrevious(List * plist, Data * pdata);
int LCount(List * plist);
#endif
리스트의 초기화는 각각의 포인터 변수를 NULL로 초기화 하면 된다. 다음과 같다.
void ListInit(List* plist) {
plist->head = NULL;
plist->cur = NULL;
plist->numOfData = 0;
}
삽입의 경우 2가지의 경우가 존재하는데 각각 리스트가 비어있을때, 비어있지 않을 때 이다.
void LInsert(List* plist, Data data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->next = plist->head;
newNode->prev = NULL;
plist->head = newNode;
(plist->numOfData)++;
}
데이터의 조회의 경우 양방향 연결 리스트의 특성으로 좌측, 우측을 모두 조회할 수 있다.
int LFirst(List* plist, Data* pdata) {
if (plist->head == NULL)
return FALSE;
plist->cur = plist->head;
*pdata = plist->head->data;
return TRUE;
}
int LNext(List* plist, Data* pdata) {
if (plist->head == NULL)
return FALSE;
plist->cur = plist->cur->next;
*pdata = plist->cur->data;
return TRUE;
}
int LPrevious(List* plist, Data* pdata) {
if (plist->head == NULL)
return FALSE;
plist->cur = plist->cur->prev;
*pdata = plist->cur->data;
return TRUE;
}
전체의 코드는 각각 다음과 같다.
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
#ifndef __DB_LINKED_LIST_H__
#define __DB_LINKED_LIST_H__
#define TRUE 1
#define FALSE 0
typedef int Data;
typedef struct _node
{
Data data;
struct _node * next;
struct _node * prev;
} Node;
typedef struct _dbLinkedList
{
Node * head;
Node * cur;
int numOfData;
} DBLinkedList;
typedef DBLinkedList List;
void ListInit(List * plist);
void LInsert(List * plist, Data data);
int LFirst(List * plist, Data * pdata);
int LNext(List * plist, Data * pdata);
int LPrevious(List * plist, Data * pdata);
int LCount(List * plist);
#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
#include < stdio.h>
#include "DBLinkedList.h"
void ListInit(List* plist) {
plist- > head = NULL ;
plist- > cur = NULL ;
plist- > numOfData = 0 ;
}
void LInsert(List* plist, Data data) {
Node* newNode = (Node* )malloc (sizeof (Node));
newNode- > data = data;
newNode- > next = plist- > head;
newNode- > prev = NULL ;
plist- > head = newNode;
(plist- > numOfData)+ + ;
}
int LFirst(List* plist, Data* pdata) {
if (plist- > head = = NULL )
return FALSE;
plist- > cur = plist- > head;
* pdata = plist- > head- > data;
return TRUE;
}
int LNext(List* plist, Data* pdata) {
if (plist- > head = = NULL )
return FALSE;
plist- > cur = plist- > cur- > next;
* pdata = plist- > cur- > data;
return TRUE;
}
int LPrevious(List* plist, Data* pdata) {
if (plist- > head = = NULL )
return FALSE;
plist- > cur = plist- > cur- > prev;
* pdata = plist- > cur- > data;
return TRUE;
}
int LCount(List* plist) {
return plist- > numOfData;
}
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
#include < stdio.h>
#include "DBLinkedList.h"
int main(void )
{
// 양방향 연결 리스트의 생성 및 초기화 ///////
List list;
int data;
ListInit(& list);
// 8개의 데이터 저장 ///////
LInsert(& list, 1 ); LInsert(& list, 2 );
LInsert(& list, 3 ); LInsert(& list, 4 );
LInsert(& list, 5 ); LInsert(& list, 6 );
LInsert(& list, 7 ); LInsert(& list, 8 );
// 저장된 데이터의 조회 ///////
if (LFirst(& list, & data))
{
printf ("%d " , data);
while (LNext(& list, & data))
printf ("%d " , data);
while (LPrevious(& list, & data))
printf ("%d " , data);
printf ("\n\n" );
}
return 0 ;
}
cs
