[자료구조] 이중연결리스트 remove 함수(메서드) 만들기

들어가기 전

이제 이중연결리스트의 remove 함수 구현에 대한 부분까지 도전하는 시기가 되었다. 사람들은 연결리스트가 쉬운 자료구조라고 하는 것 같은데, 내가 보기에는 참조 관계를 이어주고 끊어주는 것 부터, 리스트의 특정 위치에 노드를 추가함으로써 생기는 여러 문제들을 해결하는게 그리 쉬운 것 같지는 않다.

 

계속 뜯어보고, 원리를 생각하며 공부해보니 조금씩 해당 자료구조의 필요성과 이점, 단점 등이 보이기 시작하고 있는데, 이것이 구현 능력으로 이어지기 위해서는 꾸준히 노력해야 함을 인지하고 들어가 본다.

 

 

 

이중 연결리스트에서 노드를 제거하려면?

이중 연결리스트에서 노드를 제거하는 방법은 첫 번째 노드를 제거하거나, 마지막 노드를 제거하거나, 아니면 중간에 있는 노드를 제거하는 등 응용에 따라서 다양하게 구현이 가능하다. 

 

이번에는 중간 노드를 제거하는 것을 제외하고, 첫 번째 노드와 마지막에 있는 노드를 제거하는 함수를 구현해볼 것이다.

 

removeFirst : 첫 번째 노드 제거

우선 첫 번째 노드를 제거하려면, 헤드 자리(this.head) 에 노드(node) 가 있다면, 해당 노드의 이전 참조를 null 로 지정하고, 리스트의 길이를 1 빼주면 된다(this.length--).

 

즉, 다음과 같이 로직을 작성한다.

removeFirst(){

	// 헤드가 없다는 것은 리스트가 비어있다는 의미이므로 바로 탈출
	if(this.head === null) {
    	return null;
    }
    // 삭제된 노드가 참조하는 다음 노드를 현재 헤드(this.head = removeNode.next)로 지정
    const removeNode = this.head;
    this.head = removeNode.next;
    
    // 다음 노드가 null 이 아니라면 해당 노드가 참조하는 이전 노드의 참조를 null 로 지정한다.
	if(this.head !== null) {
    	this.head.prev = null
    }
    
    // 삭제된 노드를 반환하고, 리스트 길이를 1 빼준다.
    this.length--;
    return removeNode;

}

 

 

처음에 이른 반환을 하는 이유는 리스트가 비어있는데 리스트 내부를 들여다 볼 필요가 없기 때문이다. 따라서 return null; 을 통해서 아래 로직을 실행하기 전에 함수를 탈출하여 종료한다.

 

 

 

앞서 로직에서 리스트가 비어있지 않다는 것을 검증했기 때문에, 그 다음에는 삭제할 노드를 removeNode 변수에 담는다. 그리고 삭제할 노드의 다음 노드에 대한 참조(removeNode.next)를 this.head 에 할당함으로써 헤드를 .next 가 참조하고 있는 다음 노드로 옮기는 작업을 수행한다.

 

 

 

마지막으로 this.head 가 존재하는 경우에는 삭제된 노드를 참조하는(.prev) 포인터를 this.head.prev 에 담고 있기 때문에, 이를 null 초기화하여 참조관계를 끊어준다. 이 부분의 처리 이유는 당연히 헤드 자리에 있는 노드가 리스트의 첫 번째 노드가 되므로 .prev 가 null 이 되어야 하기 때문이다.

 

 

 

removeLast() : 마지막 노드 삭제하기

리스트의 앞 노드를 제거하는 것은 비교적 단순하지만, 마지막 노드를 삭제하는 것은 리스트를 순회해야 하기 때문에 약간의 추가적인 로직이 들어간다. 다행인 것은 횡단으로만 가능한 단일 링크리스트에 비해서 이전 참조 포인터를 사용할 수 있기 때문에, 비교적 수월하게 구현할 수 있다.

 

removeLast(){
    // 리스트가 비어있으면 함수 바로 종료
	if(this.head === null) return null;
    
    // 리스트가 차 있으면 순회해서 헤드를 끝지점으로 이동
    let currentNode = this.head;
    
    while(currentNode.next !== null) {
    	currentNode = currentNode.next // 헤드 옮기기 작업
    }
    // 삭제 노드가 참조하는 이전 노드(.prev) 에서 참조하는 삭제노드와의 포인터(.next)를 끊는다.
	currentNode.prev.next = null;
    this.length--

}

 

 

이 친구도 마찬가지로 리스트가 처음부터 비어 있으면 순회를 돌 필요가 없으므로 이른 반환을 통해서 일찍 함수를 벗어나게 한다.

 

 

만일 리스트 내에 이미 거주하고 있는 노드가 있다면, 마지막에 위치한 노드를 찾기 위해 리스트 전체를 순회한다. 참고로 let currentNode 에 왜 별도로 this.head 를 할당하는지 궁금할 수도 있는데, this.head 는 클래스 내의 영역 전체에서 공유되기 때문에, this.head 를 직접적으로 건드리게 되면, 예기치 못한 충돌이 발생할 수 있다. 이 부분은 직접 this.head 만을 사용해서 순회해보면 바로 알 수 있다.

 

순회를 다돌고 나서 리스트의 끝지점에 도착 했다면, currentNode 를 출력 시 리스트의 마지막에 위치한 노드가 출력되는 것을 확인 할 수 있다.

 

따라서, 마지막 노드(삭제할 노드)의 이전 참조(.prev)의 다음 참조(.prev.next) 를 null 로 지정하게 되면, 현재 currentNode 와 이전 노드 간에 참조관계가 깨지게 된다.

 

그 후 this.length -- 를 통해 리스트의 길이를 줄여주면 끝이다.

 

 

다 만들고 나니, 동작이 이상하다. 

리스트의 마지막 노드를 삭제하는 것은 정상적으로 동작하고 있는데, 만일 마지막 노드가 첫 번째 노드이기도 한다면, 즉, this.head  === lastNode 와 같은 경우에 어떻게 처리할지를 로직에 포함시키지 않았다.

 

따라서, currentNode의 .prev 가 null 인 경우에는 this.head 를 null 로 지정하여 즉시 노드를 삭제할 수 있도록 로직을 추가로 작성하였다.

removeLast(){
    // 리스트가 비어있으면 함수 바로 종료
	if(this.head === null) return null;
    
    // 리스트가 차 있으면 순회해서 헤드를 끝지점으로 이동
    let currentNode = this.head;
    
    while(currentNode.next !== null) {
    	currentNode = currentNode.next // 헤드 옮기기 작업
    }
    // (추가) 현재 리스트의 첫 번째 노드가 마지막 노드이기도 하다면 현재 헤드를 null 로 지정
    if(currentNode.prev === null) {this.head = null} 
    else {
    	// 삭제 노드가 참조하는 이전 노드(.prev) 에서 참조하는 삭제노드와의 포인터(.next)를 끊는다.
		currentNode.prev.next = null;
    }
   
   this.length--    
 }

 

 

다음은 Search 구현과 현재 이중 연결리스트의 비효율성에 대한 언급(공부중)