안녕하세요
C언어(C++)에서의 연결리스트 예제를 통해 어떻게 동작하는지
하나씩 알아보도록 합시다!
연결리스트(Linked list)란?
연결 리스트, 링크드 리스트
는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조이다. 이름에서 말하듯이 데이터를 담고 있는 노드들이 연결되어 있는데, 노드의 포인터가 다음이나 이전의 노드와의
연결을 담당하게 된다.
https://ko.wikipedia.org/wiki/%EC%97%B0%EA%B2%B0_%EB%A6%AC%EC%8A%A4%ED%8A%B8
간단히 말하자면 하나의 노드(집)가 다른노집드의 주소를 가리키며
이어져나가는 형태로 데이터(사람)를 저장하는 자료구조입니다.
1번집에는 철수
2번집에는 짱구
3번집에는 훈이
가 살고있습니다.
여기서 집이 노드(Node)에 해당하구요
노드안에 있는 사람이 데이터에 해당합니다.
각각의 노드는 다음 노드 또는 이전노드를 가리킵니다.
철수네집은 짱구집을 가리키고,
짱구네집은 훈이집을 가리킵니다.
훈이집 다음에는 노드(집)이 없으므로
훈이집이 가리키는 노드는 없습니다(NULL)
연결리스트의 장점은 원하는만큼 노드를 동적으로
추가/삭제할 수 있습니다.
단점은 배열처럼 메모리공간에 정렬되어있지 않고 사방에 흩어져있어서
배열의 인덱스처럼 특정 노드에 바로 접근할 수 없습니다.
1~10번 노드가 있는데 4번노드에 접근하려고하면
1번부터 4번까지 탐색해야만합니다.
그리고
먼저, 연결리스트에는 간단하게 종류를 나누자면
이중 연결리스트(양방향), 단일 연결리스트(단방향)가 있습니다.
또, 마지막노드가 처음 노드를 가리키는 원형연결리스트가 있습니다.
본 포스팅에서는 단일 연결리스트에 대한 예제를 작성할까 합니다.
단일연결리스트를 이해하신다면 양방향, 원형연결리스트 구현은
금방 하실 수 있습니다.
본격적으로 들어가기전에
먼저 알아야할 필수 지식이 있습니다.
"포인터와 동적메모리할당"
는 꼭 알고 계셔야합니다.
또한 구조체에 대해서도 기초적인 개념은 알고계셔야합니다.
그럼 시작합니다!
단일 연결리스트는 첫 노드가 다음노드를 가리키고,
다음노드가 또 그다음 노드를 가리키고... 쭉 이어나가는 방식입니다.
첫번째 노드는 Head(헤드)노드라고 부릅니다.
마지막 노드는 Tail(테일)노드라고 부릅니다.
머리와 꼬리. 처음과 끝.
이해하기 쉽죠?
노드는 기본적으로 데이터를 저장할 공간, 주소를 저장할공간으로 나뉩니다.
(데이터를 여러개 저장하도록 할 수도 있습니다.)
(양방향 연결리스트의 경우 주소 저장변수가 2개입니다)
데이터저장할 부분은 모두 같지만 단일(단방향) 연결리스트의 경우,
이전노드의 주소를 저장하지 않습니다.
Head -> Tail
방향으로만 데이터를 저장하죠
양방향의 경우
Head <-> Tail
다음노드의 주소, 이전노드의 주소를 함께 저장할 수 있습니다.
단일 연결리스트를 C언어로 간단하게 구현해봅시다!
먼저 노드를 구현해봅시다.
노드는 데이터를 저장할 변수와
다음 노드의 주소를 저장할
"자기참조 구조체 포인터변수"를 하나 가지고있습니다.
말이 길고 생소할수도 있습니다.
자기자신의 타입을 참조하는 포인터변수입니다.
NODE 라는 구조체안에
int형 데이터를 저장할 변수 하나,
다음 노드의 주소를 저장할 자기참조 구조체포인터 변수가 하나 있습니다.
struct NODE* next 에는
"선언한 노드 구조체의 주소"를 저장할 수 있습니다.
길다고 어렵게 생각하지마시고 struct NODE 타입의 주소값을 저장하는
포인터변수라고 생각하세요. 머릿속에 각인시키면 전혀 어렵지 않습니다.
아래부터는 main 함수에 작성하시면 됩니다.
메인함수 첫줄에 머리노드를 하나 생성해봅시다.
노드를 메모리 동적할당으로 생성합니다.
malloc 함수로 sizeof(node)크기만큼 동적할당을 합니다.
node구조체 크기만큼 할당이 되겠죠?
반환되는 주솟값을 (node*) 자기참조 구조체 포인터형으로
형변환을 해줍니다.
그리고 아래에
head->next = NULL;
코드를 작성해줍니다.
머리노드의 next값은 null이다(없다). 라는 의미입니다.
머리노드를 처음 생성했을때의 구조입니다.
방금 생성했고 Data와 주소를 저장하는 포인터변수에는 null값이 들어있습니다.
그러니 머리노드가 가리키는 다음노드는 NULL 즉, 없습니다.
머리노드는 데이터를 저장하지 않습니다.
출발점이라고 보시면 되겠네요.
이제 머리노드 다음에 새 노드를 하나 추가해봅시다.
node1 이라는 새로운 노드를 새로 할당했습니다.
동적할당 하는방법은 머리노드와 동일합니다.
노드를 생성만 해두고 서로 연결시키지 않으면 아무런
동작도 하지못합니다.
머리노드와 node1을 이어봅시다.
머리노드는 NULL을 가리키고 있었습니다.
NULL과 머리노드 사이에 node1 이라는 새 노드를 추가하려고 합니다.
node1 의 다음 주소는 머리노드가 가리키던 다음주소(NULL)를 저장
node1의 데이터에는 10을 저장
머리노드의 다음노드는 node1 의 주소를 저장.
포인터에서 각각의 원소들(위에선 변수)에 직접적으로 접근하여
값을 수정할때에는 -> 연산자를 사용해야합니다.
node1->next 의 의미는
node1의 next 변수에 접근하라는 뜻입니다.
위 코드의 과정을 마치면 아래의 구조로 될것입니다.
시작노드는 항상 머리노드,
끝 노드는 항상 꼬리노드.
현재 노드가 2개밖에 없으므로 위와같은 상황입니다.
이제 머리노드 다음에 노드를 하나더 추가해봅시다.
같은 형태로 node2를 할당했습니다.
node2의 다음노드 주소는 head가 가리키던 주소(node1)를 넣었습니다.
node2에는 20이라는 데이터를 저장했고,
head의 다음주소는 node2로 저장했습니다.
위의 과정이 끝나면 아래 그림과같습니다.
총 3개의 노드가 생성된 모습입니다.
원하는 갯수만큼 노드를 추가하고 삭제할 수 있습니다.
(삭제는 다음에 포스팅하겠습니다.)
노드삭제는 노드추가의 반대입니다.
해당 노드를 삭제하기 전에
그 노드가 가지고있던 다음노드 주소를
삭제할 이전노드의 next에다 집어넣어주면 쏙 삭제할 수 있습니다.
이해가 안가시겠지만 다음에 자세히 알아보도록 하겠습니다.
노드 3개를 생성하고 데이터를 넣어봤습니다.
이제 잘 할당되고 이어졌는지 확인해봅시다!
먼저 노드를 쭉 스캔할 curr 구조체포인터를 하나 만들었습니다.
그리고 그곳에 머리노드가 가리키는 노드의 주소를 넣었습니다.
curr은 node2의 주소를 대입받은 상태입니다.
즉, curr은 node2입니다.
(node2 메모리주소에 직접 접근)
curr->data를 하면 node2->data 와 같습니다.
while(curr != NULL)
curr에 저장된 값이 NULL이 아닐때 반복합니다.
현재 curr에는 node2의 주소가 저장되어있으므로 반복을 시작합니다.
printf() 함수로 curr->data를 출력하는 모습입니다.
curr은 현재 node2의 주소를 가지고있고
node2의 데이터는 20이므로 20이 출력됩니다.
curr=curr->next
curr는 현재 node2과 같은상태입니다.
node2->next 값이 curr에 대입됩니다.
node2->next에는 node1의 주소가 들어있습니다.
curr은 이제 node1가 되었습니다.
또 반복하여 값을출력하고 node1->next를 curr에 대입합니다.
node1->next는 NULL 이므로 반복문을 탈출하게됩니다.
이로써 추가한 node1, node2의 데이터를 잘 찾아서 출력하는 모습입니다.
노드는 3개가 있지만 두개만 출력된 이유는
머리노드는 데이터를 가지지 않기때문이죠.
이제 마지막 작업을 해줘야합니다.
malloc 함수의 짝꿍
free입니다.
할당한 메모리공간을 해제해줍시다.
머리노드와 node1, node2를 free함수로 해제해주고
프로그램을 종료합니다.
컴파일해서 실행해보면 아래와 같습니다.
node1과 node2가 가지고있던 데이터를 출력하고 종료하는 모습입니다.
노드생성함수, 노드삭제함수를 따로 만들어서 관리하면 매우 유용합니다.
하지만 오늘 포스팅에서는 따로 함수로 만들지 않고 기본적인,
쉽게 이해하기위해 나누지않고 메인함수에 모두 작성했습니다.
다음포스팅에서는 노드추가함수, 노드삭제함수를 구현한 예제와함께
설명하도록 하겠습니다.
linked_list_1.c감사합니다.
