안녕하세요
이번 포스팅에서는 이전 시간에 구현하였던 간단한 연결리스트 예제에서
노드 추가, 삭제 함수를 구현해보도록 하겠습니다!
연결리스트에 대해 개념만 잘 이해하셨다면 금방 이해하실 수 있습니다!
지난번 소스코드를 약간 수정하고 추가를 해봅시다.
메인함수 안의 코드는 머리노드 생성 부분과
출력 부분만 남기고 지워주시구요
구조체 선언 아래에 함수 선언을 해주시면 됩니다!
그리고 맨 아래처럼 선언한 함수를 구현하기 위해 준비를 해주세요
지난 시간에도 간단히 설명했던 노드 추가 부분 입니다.
처음 노드는 HEAD 노드라고 칭합니다.
처음 HEAD 노드를 생성하면 다음 노드는 없습니다(NULL)
그래서 HEAD 노드는 다음 노드 주소로 NULL을 가리키고 있죠.
HEAD 노드 다음에 새로운 노드를 추가를 한다면 아래와 같은 과정으로 표현할 수 있습니다.
추가하기 전 HEAD노드는 NULL을 가리키고 있었지만
새로운 노드가 생성되고 HEAD는 NULL 대신 새로운 노드를 가리키고
새로 생성된 노드는 HEAD가 가리키던 NULL을 가리키게 됩니다.
끼어들기와 비슷한 과정이죠
이 부분을 코드로 구현하면 아래와 같습니다.
인자로는 머리노드 주소와 새 노드에 저장할 데이터를 받습니다.
(1)
newNode 포인터 변수에 새로운 노드를 할당하여 주소를 저장합니다. (새로운 노드 생성)
(2)
newNode에 인자로 받아온 data를 저장하고
newNode의 다음 노드 주소는 HEAD노드의 다음주소(현재 NULL)을 가리킵니다.
(3)
마지막으로 새로운 노드가 완성되었으니
HEAD노드는 NULL이 아닌 방금 생성한 노드를 가리키게 합니다.
2번 과정과 3번 과정은 순서가 변경되면 안됩니다.
왜냐하면 새로운 노드를 생성하자 마자 바로 HEAD 노드가 방금 생성한 노드를 가리키게 된다면
newNode->next = head->next
부분에서 HEAD 노드는 이미 newNode를 가리키고 있기 때문에
newNode도 본 노드를 가리키게되기 때문입니다.
노드 추가 함수를 모두 구현했다면 메인 함수에서 addNode 함수를 호출하여 노드를 추가해 봅시다!
위와같이 head 노드와 저장하고싶은 정수 값을 함께 함수로 전달하면 됩니다.
위와 같이 코드를 작성하면 아래와 같은 구조일 것 입니다.
HEAD -> 30 -> 20 -> 10
왜 10, 20, 30순서로 저장했는데 30, 20, 10이 되는지에 대해서는
위의 노드 추가 과정사진에서 해답을 찾으실 수 있습니다.
실행시켜보면 아래와 같은 결과를 보실 수 있습니다.
정상적으로 출력이 되는 모습입니다.
이제 추가함수는 구현해보았으니 이제 노드 삭제함수를 구현해봅시다!
삭제는 추가하는 과정보다 조금 복잡하다고 느끼실수도 있습니다.
크게 어렵지 않으니 아래 사진으로 이해해 보세요!
노드삭제는 아래와 같은 과정으로 나타낼 수 있습니다.
위와같이 연결리스드가 쭉 있다고 가정합시다.
HEAD의 다음 주소는 1번노드
1번 노드의 다음 주소는 2번노드
2번 노드의 다음 주소는 3번노드..
줄줄이 이어져있습니다.
HEAD 노드 다음의 1번 노드를 삭제한다고 하면
HEAD가 가리키는 주소를 1번 노드가 가리키던 주소(2번 노드)로 바꿔주어야합니다.
노드 추가를 끼어들기라고 본다면
노드 삭제는 다른길로 빠져나간다고 보시면 됩니다.
내가 빠지면 뒤에 있던 사람은 내 앞에 있던사람과 이어지게 되죠
이제 코드로 HEAD 노드의 다음노드를 삭제하는 기능을 구현해봅시다!
deleteNode 함수는 인자로 head의 주소 1개만 받습니다.
머리노드 뒤의 노드를 삭제하는 기능을 구현할것이기 때문에 head의 주소만 있으면 다음노드의 주소도 구할 수 있기 때문입니다.
(1)
targetNode는 삭제할 노드의 주소가 들어갈 임시 변수입니다.
head->next 를 통해 머리노드의 다음 노드를 저장하죠
(2)
임시변수에 삭제할 노드 주소를 받아놨으니 이제 머리노드의 다음노드 주소를 바꿔봅시다.
target->next는 삭제할 노드의 다음 노드 주소가 저장되어있습니다.
head->next에 대입해줍니다
(3)
머리노드의 다음 주소를 삭제할 노드의 다음 주소로 변경해 줬으니 이제 노드를 삭제해도 연결리스트는 정상적으로 유지됩니다.
free로 삭제할 노드의 메모리 영역을 해제해줍니다.
크게 어려운부분은 없습니다!
위와같이 deleteNode 함수를 호출하여 테스트해봅시다.
HEAD -> 30 -> 20 -> 10
에서 머리노드의 다음 노드를 삭제한다면
HEAD -> 20 -> 10
이 되겠죠?
정상적으로 출력이 되는 모습을 보실 수 있습니다.
추가, 삭제 함수를 구현해보았는데 연결리스트에 대해 이해가 잘 되었다면 크게 어렵지 않으실겁니다.
다음 포스팅에서는 노드 검색, 출력, 메모리 영역 해제 기능을 함수로 구현해보도록 하겠습니다.
감사합니다.
