[C/C++ 자료구조] 단일 연결리스트(Linked list) - 출력, 검색, 메모리 해제

안녕하세요

이번 포스팅에서는

지난 포스팅에 이어서

출력함수

검색함수

메모리 해제 함수

를 구현해보도록 하겠습니다!

지난시간의 코드에서 조금 수정, 삭제를 해봅시다.

함수 선언 부분에 위와같이 3개의 함수를 선언해줍니다.

함수 이름은 원하시는걸로 하셔도 됩니다.

저는 알기 쉽게하기 위해 관련 단어로 조합하였습니다.

선언해두었으면 맨 아래에 구현 부분을 위와같이 작성해줍니다.

메인함수는 위처럼 간단히 수정해줍니다.

기존의 출력 부분은 복사해서 출력함수에

아래와 같이 붙여넣기해주세요

출력함수는 벌써 구현이 끝났습니다!

이전시간에 이미 다 만들어놓은것을 함수로 나누기만 했습니다.

이번 포스팅에서 실제 구현할 부분은

검색과 메모리 영역 해제(free) 부분입니다.

검색기능 구현 전에 아래 그림으로 어떻게 구현할지 생각해봅시다.

일단 리스트의 시작은 HEAD 노드인것은 모두 아실겁니다.

HEAD노드부터 다음노드로 하나씩 이동해나가면서 값을 찾기만 하면 될것입니다.

출력은 하나씩 이동하면서 출력만 했지만 검색은

하나씩 이동하면서 검색할 값과 매번 비교만 하면 됩니다!

정말 간단합니다.

printf 대신 if문이 들어가있네요

curr->data = data

함수로 전달된 data와 노드가 가지고 있는 data 값을 비교하여 만약 참일경우 해당 노드를 반환합니다.

반복을 모두 마쳤는데 찾지 못한다면 NULL을 반환하도록 구현하였습니다.

벌써 검색 함수도 구현이 끝났습니다!

이제 마지막으로 연결리스트 전체 메모리 공간을 해제하는 기능만 구현하면 됩니다.

아래 그림을 통해 알아봅시다.

앞 노드부터 하나씩 free() 를 통해 메모리 공간을 해제하도록 구현할 예정입니다.

먼저 HEAD를 해제해야하는데

섣불리 HEAD노드 공간을 해제해버리면 다음 노드 주소를 알 수 없게 되겠죠?

HEAD 노드를 해제하기 전에 미리 다음 노드를 temp 변수에 저장해둡니다.

그리고 난 다음에 head를 해제하면 아무런 문제없이 진행할 수 있죠

해제할 노드의 주소를 저장하는 변수를 target

해제할 노드의 다음 노드 주소는 temp 변수에 저장하여 구현해봅시다.

먼저 첫 노드는 head 이므로 target에 head를 대입해줍니다.

그리고 temp에는 target(head)를 대입해줍니다.

위 그림에서는 temp에는 다음 노드값을 저장한다고 했는데 왜 target, temp 둘다 head일까요?

이에 대한 해답은 반복문 안에서 찾으실 수 있습니다.

반복문은 target에 저장된 데이터(해제할 노드)가 NULL이 아닐경우 반복을 계속합니다. 

코드를 보면 free() 함수를 호출하기 전 temp 변수에 temp->next 를 통해 다음 노드주소를 미리 저장하는 모습을 볼 수 있습니다.

다음 노드주소는 무사히 건졌으니 target 노드는 free()를 통해 메모리에서 해제(소멸)시켜줍니다.

그리고 다음 반복을 위해 target에는 temp 값으로 대입해줍니다.

temp에는 free() 전에 다음 노드의 주소를 미리 저장했었죠?

target이 소멸된 이후에 다음 노드를 대입하여 다시 반복문 처음으로 돌아갑니다.

이렇게되면 노드가 처음부터 1개씩 소멸(free)되어 결국에는 마지막 NULL이 될 때 까지 메모리 공간에서 사라질 수 있게 됩니다.

조금 복잡할수도 있지만 천천히 생각해보시면 금방 이해하실 수 있습니다!

출력, 검색, 해제 3가지의 기능(함수)를 구현하였습니다.

이제 한번 구현한 기능을 테스트해봅시다!

노드를 여러개 추가해보세요!

그리고 노드도 몇 개 지워보세요

연결리스트의 결과가 궁금하니 방금 구현한 출력함수로 출력도 해봅시다.

그리고 검색 기능이 잘 동작하는지도 테스트해보세요!

(검색기능은 노드 주소를 반환하기 때문에 node* 변수를 하나 선언해서 받아야합니다. 

저는 result 라는 변수 선언 후 받아와서 if문으로 NULL인지 아닌지 비교하여 printf로 결과를 출력하도록 했습니다)

마지막으로는 메모리 영역을 해제하시면 됩니다!

어래 사진은 실행 결과입니다.

이로써 기본적인 기능은 모두 구현되었습니다!

개념을 잡기위해 아주 간단한 예제로 구성되었는데

이보다 더 다양한 방법, 효율성, 기능을 구현할 수도 있습니다.

또는 HEAD 바로 뒤에만 있는 노드만 삭제하는게 아니라 지정한 노드를 삭제할 수도 있고 원하는 위치에 노드를 추가할 수도 있습니다!

노드의 값을 수정한다거나 단일 연결리스트가 아닌 양방향으로도 구현이 가능합니다.

이러한 개선사항, 기능들은 여러분들이 직접 구현해보면서 익혀보세요!

연결리스트에 대한 포스팅은 여기서 마치도록 하겠습니다.

감사합니다.