[자료구조] 단일 연결 리스트에서 특정 노드를 제거하는 함수를 구현해보자

이전 시간까지 단일 연결 리스트에서 노드를 찾아서 조회하는 기능을 구현하였는데, 이번에는 타겟이 되는 노드를 검색해서 삭제하는 기능을 구현해볼 것이다.

 

단일 연결리스트에서 특정 노드를 삭제하려면

단일 연결리스트에서 특정 노드를 삭제하려면 우선적으로 연결 리스트 전체를 순회해야 한다. 왜냐 하면, 단일 연결리스트의 참조는 단방향이기 때문에 전체 노드를 순회해야 타겟 노드를 찾을 수 있기 때문이다.

 

또한, 타겟이 되는 노드를 제거하기만 하면 되는 것은 아니며, 타겟 노드를 이전 노드가 가리키는 다음 노드의 참조를 타겟 노드의 다음 노드에 해당하는 노드로 변경해주어야 한다.

예를 들어 5 -> 3 -> 1 이라는 연결리스트가 있다고 가정할 때, 2 라는 노드를 제거한다면 5 -> null -> 1 와 같은 형태가 될 것인데, 여기서 5의 다음 노드에 대한 참조를 1 노드와 이어 주어 5 -> 1 과 같은 형태로 만들어 주어야 한다는 소리이다.

 

제거하기 위한 remove 함수 구현하기

우선 아래와 같은 틀을 만들어 주었다.

remove(data) {

}

 

여기서, remove 함수를 구현할 때 핵심이 되는 노드는 이전 노드와 현재노드이다. 이 두 가지 포인터를 활용해야 타겟 노드를 사냥하고 빠진자리를 매꿀 수 있다.

 

따라서 우선적으로 이전노드와 현재노드를 담을 변수를 다음과 같이 초기화한다.

remove(data) {
  let prevNode = null;
  let currentNode = this.head;
}

 

 

그 다음에는 앞서 언급했듯이 연결리스트 전체를 순회하는 반복문을 구성해야 한다. 여기서는 while 문을 활용한다. 

remove(data) {
 let prevNode = null;
 let currnetNode = this.head;
 
 while(currentNode !== null) {
 
 }
}

 

위 로직에 따르면, 현재 노드(헤드)가 null 이 아닌 경우. 즉, 리스트의 끝 지점이 될 때까지 블록 내 로직을 반복하도록 설정한다. 만일 현재 노드(헤드)가 null 이라면 리스트가 비어 있거나 끝 지점에 도달해 있다는 소리이므로 연산을 수행할 필요가 없다.

 

---

 

삭제할 노드(타겟 노드)가 리스트의 헤드라면 

그 다음에는 현재 노드가 담고 있는 data 와 타겟 노드의 data 가 일치하고, prevNode(이전 노드)가 비어있는 경우, 현재 노드(헤드)를 제거하는 로직을 작성한다(즉, 첫 번째 노드가 찾고자 하는 노드인 경우).

remove(data) {
  let prveNode = null;
  let currentNode = this.head;
  
  while(currentNode !== null) {
  	if(currnetNode.data === data) {
    	if(prevNode === null) {
          this.head = currentNode.next // 다음 헤드는 현재 노드가 참조하는 다음 노드가 된다.
        }
    }
    return currentNode.data; // 삭제한 데이터 반환
  }
}

 

이러한 로직이 작성된 이유는 제거하려는 Node 가 바로 연결리스트의 헤드에 해당하는 경우라면 굳이 더 이상 순회할 필요가 없기 때문이다. 따라서 타겟이 되는 노드를 제거함과 동시에 제거된 노드의 다음 노드에 대한 참조를 헤드(this.head = currentNode.next) 로 지정해야 한다.

 

마지막으로 삭제한 데이터가 정확히 무엇인지 확인하기 위해서 return 으로 currentNode.data 를 반환하면, 그 이후 로직은 실행하지 않고 함수를 종료하게 된다.

 

일단 여기까지만 해보고, 해당 함수가 정상적으로 동작하는지 확인해보면, 첫 번째 노드(헤드)인 5가 제거되고, 4가 담긴 노드가 헤드가 되어 다음 참조를 이어가는 것을 볼 수 있다.

 

 

 

삭제할 노드가 리스트의 헤드가 아니라면?

만일 타겟이 되는 노드가 헤드가 아니라면, 타겟 노드가 위치한 영역으로 리스트의 처음부터 끝까지 순회를 돌아야 한다. 앞서 첫 번째 노드가 타겟인 경우에는 if 문 내에서 처리하고 바로 탈출했지만, 그런 경우가 아닌 경우에는 else { } 를 사용하여 이전 노드의 다음 노드를 현재 노드의 다음 노드로 지정하여 삭제한 노드로 인해 단절된 노드 사이에 참조 관계를 이어주어야 한다.

remove(data) {
	let prevNode = null;
    let currentNode = this.head;
    
    while(currentNode !== null ) {
    	if(currentNode.data === data) {
        	if(prevNode === null) {
            	this.head = currentNode.next
                
            } else {
            	prevNode.next = currentNode.next;
				            
            }
        }
    }
}

 

이렇게 되면, 5 -> 3 -> 1 이 있고, 삭제할 노드가 3 이라고 가정한다면, 다음과 같게 되는데,

prevNode = 5 // .next = 3  -> 여기서 3 은 삭제된 노드를 가리킴
currentNode = 3 // .next = 1 -> 여기서 1은 삭제된 노드의 다음 노드를 가리킴

// 고로 타겟 노드의 이전 노드와 다음 노드 사이에 참조 관계를 형성해줄 필요가 있다.

 

여기서 prevNode.next 를 currentNode.next 로 할당한다면,  다음과 같이 prevNode의 다음 참조가 타겟 노드의 다음 노드에 대한 참조를 가지게 된다.

prevNode.next = 1;

 

제일 중요한 한 가지

앞서 로직에서 제일 중요한 것이 빠져 있다. 그건 순회를 돌기 위해서 이전노드를 참조하는 포인터와 현재노드를 참조하는 포인트를  변경시켜 나가야 하는데, 그 로직이 빠져 있기 때문이다.

 

만일 while 문 에서 로직이 모두 실행되고, 탈출하는 순간 그 다음에 해주어야 하는 것은 prevNode 의 자리에는 currentNode 가 들어가고, currentNode 의 자리에는 currentNode의 .next(다음 노드에 대한 참조)가 들어가야 한다. 

remove(data) {
	let prevNode = null;
    let currentNode = this.head;
    
    while(currentNode !== null) {
    	if(currentNode.data === data) {
        	if(prevNode === null) this.head = currentNode.next; // 타겟 노드가 첫 번째 노드
            else prevNode.next = currentNode.next; // 이전 노드의 다음 참조를 삭제 노드의 다음 참조로 설정.
            
            return currentNode.data; // 삭제한 노드 반환
        }        
    }
    prevNode = currentNode; 
    currentNode = currentNode.next;

}

 

정리하자면

위와 같이 로직을 작성한 후 돌려보면, 첫 번째 노드와 일치하는 data를 찾는 경우에는 순회를 돌지 않고 즉시 제거한 값을 반환한다.

 

반대로 리스트를 순회해야 하는 경우에는 이전노드에 대한 포인터와 현재노드에 대한 포인터를 뒤로 이동시켜 가면서 타겟노드를 찾을 때 까지 리스틑 순회하고, 만일 타겟 노드를 찾게된다면, 해당 노드를 제거한 뒤 이전 노드와 타겟 노드의 다음 노드 간에 참조관계를 이어주게 된다.