이근둥
근둥이의 블로그
이근둥
전체 방문자
875,057
오늘
0
어제
428

공지사항

  • 전체보기 (107)
    • 웹 (9)
    • 언어 & 프레임워크 (53)
      • JavaScript (7)
      • TypeScript (0)
      • Node.js (11)
      • Vue.js (3)
      • React (0)
      • React Native (0)
      • C & C++ (19)
      • Java & JSP (9)
      • Python (4)
    • 컴퓨터 과학 (3)
      • 알고리즘 (0)
      • 자료구조 (3)
    • 기타 (9)
      • Linux (1)
      • Git (2)
      • DialogFlow (4)
    • 일상 (13)
      • 게임 (13)
    • 칼럼 (9)
      • 회고 (0)
      • 나만의 글 (0)
      • 제품 리뷰 (9)
    • __Dev__ (9)
      • Release (9)
반응형

인기 글

  • 웹 푸시 알림(Web Push Notification)
    2022.06.13
    웹 푸시 알림(Web Push Notification)
  • [Tomcat] 아파치 톰캣 서버 포트 변경하기
    2018.08.24
    [Tomcat] 아파치 톰캣 서버 포트 변경하기
  • [Node.js] 실시간 채팅 서비스 만들기(5) - 채팅⋯
    2018.05.31
    [Node.js] 실시간 채팅 서비스 만들기(5) - 채팅⋯
  • [Vue 3] Composition API와 템플릿 참조(⋯
    2020.10.02
    [Vue 3] Composition API와 템플릿 참조(⋯
  • [Vue 3] Composition API 살펴보기
    2020.03.04
    [Vue 3] Composition API 살펴보기

태그

  • Deemo
  • 자바
  • 이펙트
  • Scanner
  • 이클립스
  • vue3
  • 자바 프로젝트
  • Hello World!
  • ES6
  • spread syntax
  • 출간
  • vue.js
  • 파티클
  • pwa
  • 프로그레시브 웹 앱
  • 전개 구문
  • composition-api
  • WWDC
  • java
  • 웹 확장
  • Vue 3
  • Composition API
  • WWDC20
  • javascript
  • vue
  • self
  • vue-next
  • vuex
  • AstroWar
  • Java FX

최근 댓글

  • 어디에서도 이런 친절한 설명은 받을 수 없었습니다. 응용⋯
    미쳤다...
  • 정말 너무 감사합니다 선생님 많은 도움이 되고있습니다 어떻⋯
    김준태
  • 커서 위치이동 함수까지 했는데 컴파일하면 Makefile.⋯
    Qour94
  • iOS의 경우 애플에서 개발하고 있는 webkit 엔진을 ⋯
    이근둥
  • android, IOS에서 된다고 했는데 Notifica⋯
    삽자루부대

최근 글

  • 웹 푸시 알림(Web Push Notification)
    2022.06.13
    웹 푸시 알림(Web Push Notification)
  • 스택(Stack)
    2022.05.26
    스택(Stack)
  • 배열(Array)
    2022.05.25
    배열(Array)
  • C언어로 배우는 자료구조
    2022.05.24
    C언어로 배우는 자료구조
  • [Vue 3] Composition API와 템플릿 참조(⋯
    2020.10.02
    [Vue 3] Composition API와 템플릿 참조(⋯

블로그 메뉴

  • 홈
  • 미디어로그
  • 방명록
hELLO · Designed By 정상우.
이근둥

근둥이의 블로그

[C/C++ 자료구조] 단일 연결리스트(Linked list) - 출력, 검색, 메모리 해제
언어 & 프레임워크/C & C++

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

2018. 5. 11. 15:09
반응형

안녕하세요



이번 포스팅에서는


지난 포스팅에 이어서


출력함수

검색함수

메모리 해제 함수


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



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


함수 선언 부분에 위와같이 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 바로 뒤에만 있는 노드만 삭제하는게 아니라 지정한 노드를 삭제할 수도 있고 원하는 위치에 노드를 추가할 수도 있습니다!

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


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





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


감사합니다.

반응형
저작자표시 비영리 동일조건
    '언어 & 프레임워크/C & C++' 카테고리의 다른 글
    • [C/C++ 자료구조] 단일 연결리스트(Linked list) - 추가, 삭제
    • [C/C++ 자료구조] 단일 연결리스트(Linked list) - 이해
    • [C/C++] 콘솔 프로그래스바(ProgressBar) 구현하기
    • [C/C++] 콘솔게임 프로그래밍 (13) - 맵 오브젝트 제어[3] [최종]
    이근둥
    이근둥
    새로운 것을 좋아하는 프론트엔드 개발자 ✨
    댓글쓰기

    티스토리툴바