[13] C review < 연결리스트의 순회 >

연결리스트에서 노드의 추가와 삭제에대해 알아보았으니 이제 연결리스트를 순회하는 방법에대해 생각해 봅시다. 

당연하게도 어떤 노드가 어느 위치에 존재하는지 , 존재는 하는지 등 알아보기 위해서는 순회가 필요합니다. 

위 함수는 특정 노드의 주소를 반환하는 함수입니다. 첫번째 노드부터 찾기 시작해 운이 좋지않으면 맨 마지막 노드까지 순회하는 방식입니다. 

특정 노드의 인덱스를 찾아서 그 노드의 주소를 반환 

전에는 add_first, add_after 함수를 만들어 살펴보았는데 이제는 index에 추가하는 함수를 만들어 보았습니다.

여기서 중요한 점은 index가 0이냐 0이 아니냐의 차이인데 이는 추가하거나 삭제할 노드가 맨 앞에 있는지 그렇지 않은지를 판단하는 조건입니다. 

자, 이제 index를 통한 제거를 알아봤으니 특정 데이터를 주고 그 데이터를 찾아 삭제하는 방법에 대해 알아보겠습니다. 

위 코드는 노드를 가리키는 p와 p가 가리키는 노드의 데이터가 인자로 입력받은 데이터와 같은지 비교하는 구문입니다. 이다음에서 문제점이 일어나는데 우리가 어떤 데이터를 삭제하려면 그 전 노드의 주소가 필요합니다. 왜냐하면 그 전 노드의 next필드에 다음 노드의 주소의 정보가 필요하기 때문이죠 즉, ??? 줄에는 이러한 주소를 알수있게하는 방법이 필요합니다. 

이런 상황에서 해결하는 전형적인 방법은 포인터를 2개 쓰는 것입니다. 밑의 그림을 살펴봅시다. 

 

포인터 변수 q를 새롭게 만들어 p가 한칸 앞으로 계속 전진하기 직전에 p를 q에 저장하여 그 전 노드의 주소를 계속 기억하게끔 하는것 입니다. 

 

정렬되어 있는 연결리스트

요일이 아니라 단어라고 가정 합시다.