연결 기반의 리스트 간단히 연결 리스트라고 불리는 리스트의 구현을 이해하기 위해서는 malloc와 free함수를 기반으로 하는 메모리의 동적할당에 대한 완전한 이해가 되어야 한다.
#include <stdio.h>
int main()
{
int arr[10];
int readCount =0;
int readData;
int i;
while(1)
{
printf("자연수 입력 : ");
scanf("%d", &readData);
if(readData<1)
break;
arr[readCount++] = readData;
}
for(i= 0; i<readCount; i++)
printf("%d", arr[i]);
return 0;
}
=============================실행결과===================
자연수 입력 : 1
자연수 입력 : 2
자연수 입력 : 3
자연수 입력 : 4
자연수 입력 : 5
자연수 입력 : 0
1 2 3 4 5
이는 0이하의 값이 입력될 때까지 입력이 계속되는 간단한 예제이다.
하지만 이 예제에서 다음과 같은 배열의 단점을 분명히 보여준다.
"배열은 메모리의 특성이 정적이어서(길이의 변경이 불가능해서) 메모리의 길이를 변경하는 것이 불가능하다."
위 예제를 실행한 후 0이하의 값을 입력받지 않고 계속해서 자연수만 입력을 하면 할당된 배열의 길이를 넘어서는 문제가 발생한다. 이렇듯 특성이 정적인 배열은 필요로 하는 메모리의 크기에 유연하게 대처하지 못한다. 그래서 등장한것이 '동적인 메모리의 구성'이다.
아래 예제는 연결리스트를 구현한 것이다.
#include <stdio.h>
#include <stdlib.h>
typedef struct _node
{
int data;
struct _node *next;
}Node;
int main()
{
Node *head =NULL;
Node *tail =NULL;
Node *cur =NULL;
Node* newNode = NULL;
int readData;
//데이터를 입력받는 과정
while(1)
{
printf("자연수 입력: ");
scanf("%d", &readData);
if(readData<1)
break;
//노드의 추가 과정
newNode = (Node*) malloc(sizeof(Node)); //노드생성의 동적할당
newNode ->data = readData; //생성된 노드에 데이터를 넣음
newNode ->next = NULL; //노드가 가리키는 값은 NULL
if(head ==NULL) //만약 첫 노드라면
head = newNode;
else //두번째 이후 노드라면
tail->next = newNode;
tail = newNode;
}
printf("\n");
//입력 받은 데이터의 출력과정
printf("입력 받은 데이터의 전체 출력\n);
if(head ==NULL)
{
printf("저장된 자연수가 존재하지 않습니다.\n");
}
else
{
cur =head;
printf("%d ", cur->data); //첫번째 데이터 출력
while(cur ->next !=NULL) //두번째 이후 데이터 출력
{
cur = cur->next; //cur이 다음노드를 가리키게함
printf("%d ", cur->data); //cur이 가리키는 노드의 데이터를 출력
}
}
printf("\n\n");
//메모리의 해제과정
if(head ==NULL)
{
return 0; //해제할 노드가 존재하지 않음
}
else
{
Node *delNode = head; //헤드 노드를 임시 저장
Node *delNextNode = head->next; //헤드의 다음 노드를 임시 저장
printf("%d을(를) 삭제합니다. \n", head->data);
free(delNode); //첫번째 노드 삭제
while(delNextNode !=NULL) //두 번째 이후 노드 삭제
{
delNode = delNextNode; //한칸씩 옮김
delNextNode = delNextNode->next;
printf("%d을(를) 삭제합니다. \n", delNode->data);
free(delNode);
}
}
return 0;
}
=================================실행결과===============================
자연수 입력 :2
자연수 입력 :4
자연수 입력 :6
자연수 입력 :8
자연수 입력 :0
입력 받은 데이터의 전체출력!
2 4 6 8
2을(를) 삭제합니다.
4을(를) 삭제합니다.
6을(를) 삭제합니다.
8을(를) 삭제합니다.
이제 위의 예제를 설명하겠다.
typedef sturct _node
{
int data; //데이터를 담을 공간
struct _node *next; //연결의 도구
}Node;
위 구조체의 멤버 next는 Node형 구조체 변수의 주소 값을 저장할 수 있는 포인터 변수이다.
next는 연결할 목적으로 선언된 멤버이다.
이 멤버로 인해 모든 Node 형 구조체 변수는 다른 Node형 구조체 변수를 가리킬수 있다.
프로그램 실행 중에 필요할 때마다 메모리 공간을 마련하는 유일한 방법은 'malloc 또는 그와 유사한 성격의 함수를 호출하는 메모리의 동적할당'이다.
"필요할 때마다 바구니의 역할을 하는 구조체 변수를 하나씩 동적할당해서 이들을 연결한다."
그리고 앞서 정의한 구조체 Node의 변수를 가리켜 '노드'라 하는데, 이는 데이터를 담는 바구니 보다는 연결이 가능한 개체라는 사실에 중점을 두어 지은 이름이다.
이렇게 구조체의 정의 하나만 가지고도 연결 리스트의 기본원리를 모두 말할 수 있다.
연결리스트에서 데이터의 삽입
Node *head =NULL; //리스트의 머리를 가리키는 포인터 변수
Node *tail = NULL; //리스트의 꼬리를 가리키는 포인터 변수
Node *cur =NULL; //저장된 데이터의 조회에 사용되는 포인터 변수
이들은 연결리스트에 주요한 역할을 하는 포인터 변수들이다.
위 상태에서 구조체 Node의 포인터 변수 head와 tail이 모두 NULL을 가리키는 상태가 된다.
while(1)
{
....
newNode = (Node *) malloc (sizeof(Node)); //노드의 생성
newNode ->data = readData; //노드의 데이터 저장
newNode -> next = NULL; //노드의 next를 NULL로 초기화
if(head ==NULL) //첫번째 노드라면
head =newNode; //첫번째 노드를 head가 가리키게 한다.
else 두번째 이후 노드라면
tail ->next = newNode;
tail = newNode; //노드의 끝을 tail이 가리키게 함
}
과정1.
위의 반복문에서 세문장에 의해 노드가생성되고 또 초기화 된다.
newNode = (Node *) malloc (sizeof(Node)); //노드의 생성
newNode ->data = readData; //노드의 데이터 저장
newNode -> next = NULL; //노드의 next를 NULL로 초기화
증 이상태에서는
노드가 새로 생성되고
노드의 next는 NULL값을 가리킨다 .
그리고 haed와 tail도 각각 널 값을 가리킨다.
과정2.
if(head ==NULL) //첫번째 노드라면
head =newNode; //첫번째 노드를 head가 가리키게 한다.
else 두번째 이후 노드라면
tail ->next = newNode;
head가 새로 생성된 노드를 가리킨다.
과정3.
그리고 이어서 while문의 마지막에 위치한 문장을 실행하게 된다.
tail = newNode; //노드의 끝을 tail이 가리키게 함.
tail이 새로운 노드를 가리킨다.
이로써 현재 한개의 노드만 추가되어있고, head와 tail이 새로 생긴 노드를 가리키고 있고 , 새로생긴 노드의 next는 NULL값을 가리키고 있다.
위에서 주목할 점은 head와 tail이 첫 번째 노드를 가리키고 있다는 점이다.
head는 리스트의 머리를 나타내고, tail은 리스트의 꼬리를 나타낸다.
노드가 몇개 추가 되건 이는 변함이 없어야 한다.
두 번째 이후의 노드를 추가하는 과정을 보자.
while(1)
{
....
newNode = (Node *) malloc (sizeof(Node)); //노드의 생성
newNode ->data = readData; //노드의 데이터 저장
newNode -> next = NULL; //노드의 next를 NULL로 초기화
if(head ==NULL) //첫번째 노드라면
head =newNode; //첫번째 노드를 head가 가리키게 한다.
else 두번째 이후 노드라면
tail ->next = newNode;
tail = newNode; //노드의 끝을 tail이 가리키게 함
}
두 번째 노드는 연결리스트의 끝, 다시 말해서 tail이 가리키는 노드의 뒤에 연결이 되어야 하기 때문에 새 노드의 생성 및 초기화 이후에는 else 구문에 담긴 다음 문장을 실행하게 된다.
tail ->next =newNode;
따라서 노드의 끝을 tail이 가리키게 하는 반복문의 마지막 문장까지 실행할경우
head는 첫번째 노드를 가리키고, 첫번째 노드는 방금만든 두번째 노드를 가리키고 , 두번째 노드는 NULL값을 가리키고, tail은 두번째 노드를 가리킨다.
즉 추가되는 노드들은 꼬리에 꼬리를 물어서 저장된다.
이렇게 해서 연결리스트의 '데이터 저장'에 대한 기본개념을 모두 설명하였다. 자료구조는 그림을 그려가면서 공부하는 것이 좋다.
연결리스트에서의 데이터 조회
연결리스트에서 조회와 관련된 코드를 살펴볼텐데 '삽입'과 비교할 수없이 쉬운 것이 '조회'이다.
삽입을 제대로 이해했다면 조회의 기능은 직접 구현가능하다.
if(head ==NULL)
{
printf("저장된 자연수가 존재하지 않습니다.\n");
}
else
{
cur =head; //cur이 리스트의 첫 번째 노드를 가리킨다.
printf("%d ", cur->data); //첫번째 데이터 출력
while(cur ->next !=NULL) //연결된 노드가 존재한다면
{
cur = cur->next; //cur이 다음노드를 가리키게함
printf("%d ", cur->data); //cur이 가리키는 노드의 데이터를 출력
}
}
cur =head 장이 실행되면
head가 가리키고 있는 값을 cur도 가리키게 된다.
즉 cur를 이용한 첫 번째 데이터의 출력이 가능하다 . 그리고 이어서 다음 반복문을 실행하게 된다.
while(cur ->next !=NULL) //연결된 노드가 존재한다면
{
cur = cur->next; //cur이 다음노드를 가리키게함
printf("%d ", cur->data); //cur이 가리키는 노드의 데이터를 출력
}
위의 반복문의 핵심은 다음 문장에 있다.
cur =cur ->next;
위 문장으로 인해서 cur은 모든노드를 차례대로 가리키며 이동하게 된다.
이렇듯 main함수의 앞 부분에서 선언된 포인터 변수 cur은 리스트 안을 돌아다닐 때 사용이 된다.
연결리스트에서의 데이터 삭제
if(head ==NULL)
{
return 0; //해제할 노드가 존재하지 않음
}
else
{
Node *delNode = head; //헤드 노드를 임시 저장
Node *delNextNode = head->next; //헤드의 다음 노드를 임시 저장
printf("%d을(를) 삭제합니다. \n", head->data);
free(delNode); //첫번째 노드 삭제
while(delNextNode !=NULL) //두 번째 이후 노드 삭제
{
delNode = delNextNode; //한칸씩 옮김
delNextNode = delNextNode->next;
printf("%d을(를) 삭제합니다. \n", delNode->data);
free(delNode);
}
}
위의 코드는 모든 노드의 소멸과정을 보이고 있다. 따라서 삭제와 관련이 있기는 하지만 연결리스트의 삭제에 관한 모든 것을 보이지는 않는다. 예를 들어서 중간에 위치한 노드의 삭제 방식은 위와 차이가 있다. 다만 위의코드에서는 head가 가리키는 노드의 삭제 방법을 보일 뿐이다.
Node *delNode = head; //헤드 노드를 임시 저장
Node *delNextNode = head->next; //헤드의 다음 노드를 임시 저장
위의 두문장을 보자.
haed가 가리키는 노드의 삭제를 위해서 두 개의 포인터 변수를 추가로 선언한 사실에 주목하자.
즉 현재
head가 가리키는 첫번째 노드를 delNode가 가리키고 있고, 첫번째 노드의 next인 두번째 노드를 delNextNode가 가리키고 있다.
위와 같이 delNextNode라는 이름의 포인터 변수를 둬서 '삭제될 노드'가 가리키는 다음 노드의 주소 값을 저장하는 이유는 다음과 같다.
"head가 가리키는 노드를 그냥 삭제하면, 그 다음 노드에 접근이 불가능하다"
즉 '삭제될 노드가 가리키는 다음 노드의 주소값'을 별도로 저장해두지 않으면 다음노드의 주소값을 모르기때문에 다음노드에 접근이 불가하다.
그래서 삭제될 노드가 가리키는 다음 노드의 주소값을 별도로 저장하는 것이다.
free(delNode); //첫번째 노드 삭제
이 문장이 실행되면 ,첫번째 노드가 소멸된다. 참고로 haed가 가리키는 노드는 소멸되었으니 head가 다음 노드를 가리키게하도록 하는 것이 원칙이지만, 본 삭제과정의 목적은 연결리스트의 전체소멸에 있으므로 굳이 head가 다음노드를 가리키게 하지 않는다.
현재 delNode는 첫번째 노드를 가리키고있다, 하지만 delNode가 가리키는 첫번째 노드는 할당 해제가 되어서 소멸이 되었다.
이제 위의 상태에서 , 다시 말해 free함수 호출 이후에 다음의 반복문을 실행하게 된다.
while(delNextNode !=NULL) //두 번째 이후 노드 삭제
{
delNode = delNextNode; //한칸씩 옮김
delNextNode = delNextNode->next;
printf("%d을(를) 삭제합니다. \n", delNode->data);
free(delNode);
}
포인터 변수 delNextNode를 참조하며 추가로 삭제할 노드가 있는지 확인한다음, 반복문 내에서 다음 두문장을 실행한다.
delNode = delNextNode; //delNextNode가 가리키는 값을 delNode가 가리키게 한다.
delNextNode= delNextNode->next; //delNode의 next를 delNextNode로 변경한다.
즉 한칸씩 이동을 한다.
이어서 반복문의 끝에서 free함수의 호출을 통해 delNode가 가리키는 대상을 소멸하게 한다.
여기까지가 반복문의 한 싸이클 이다. 즉 반복문 내에서 하는 일은 delNode와 delNextNode를 한칸씩 이동시키면서 delNode가 가리키는 대상을 소멸하는 것이 전부이다 .그리고 이 과정을 마지막 노드를 소멸할 때까지 계속 진행하니 결과적으로 모든 노드가 소멸되는 것이다.
지금까지 링크드리스트를 분석하였는데, 문제점이 있다.
1.연결리스트의 ADT를 정의하지 않았다.
2. 삽입,삭제,조회의 기능이 별도의 함수로 구분되어 있지 않다.
즉 앞서 제시한 예제에서는 연결리스토아 관련된 코드를 모조리 main함수에다 집어넣었기 때문에 필요할 때 가져다 쓸 수 있는 형태가 아니다.
자료구조를 제대로 공부하려면 이 순서를 지키는 것이 좋다.
1. 자료구조의 ADT정의
2. 정의한 ADT구현
3. 구현이 완료된 자료구조의 활용
ADT의 정의를 생략하면 ,구현도 활용도 이상한 형태로 흘러가기 쉽다.
'휴지통 > 자료구조-C' 카테고리의 다른 글
| 연결리스트 3 (0) | 2021.02.14 |
|---|---|
| 연결리스트2 (0) | 2021.02.13 |
| 배열 기반의 리스트(List)2 (0) | 2021.02.09 |
| 배열 기반의 리스트(List)1 (0) | 2021.02.08 |
| 재귀 함수 (0) | 2021.02.05 |