[자료구조] 단일 연결 리스트 | search 구현하기.sub | Index 를 사용하여 노드 찾기

<이전 포스트>

[자료구조] 단일 연결 리스트 | Add 구현하기(2). sub | 뒤로 노드 추가하기

 
 

단일 연결 리스트에서 search

단일 연결 리스트에서 타겟이 되는 노드를 찾는 search 메소드를 구현하는 방법은 다양하다. 실제 head 에 저장된 데이터(data)와 사용자가 입력한 값(target)이 일치하는 경우 true 혹은 false 를 반환하거나 해당 노드의 인덱스를 반환하게 할 수 있고, 아니면 오늘 구현해볼 방법인 인덱스를 기반으로 해당하는 인덱스에 위치한 요소를 찾아서 노드나 노드가 가지고 있는 값을 반환하게 할 수 있다.

 
 

인덱스 기반으로 search 구현

인덱스를 기반으로 search 메소드를 구현하는 것은 해당하는 index에 위치하는 요소를 찾을 때 까지 전체 헤드를 탐색하도록 하면 된다. 

    search(index) {
        let count = 0; // 현재 몇 번째 노드를 순회중인지 체크하는 카운터 변수
        let current =this.head // 현재 헤드
        
        // 찾고자 하는 인덱스에 위치한 노드를 찾을 때 까지 카운터를 증가시키며 순회한다.
        while(count<index) { 
           // 현재 헤드가 참조하고 있는 다음 노드를 헤드로 지정한다. 
            current = current.next
           // 헤드가 바뀌면 현재 회기의 순회를 종료하고, 카운터를 증가 시킨다.              
            count++
        }
        // 찾고자 하는 인덱스에 위치한 노드에 저장된 데이터를 반환한다.
        return current.data 
    }

 
 
count 는 현재 어느 노드를 검색하고 있는지 추적하는 변수이다. 
current 는 현재 리스트에 저장된 헤드를 참조한다. while 문으로 전체 노드를 순회할 때, 찾고자 하는 노드가 존재할 때 까지 해당 변수에는 다음 노드에 대한 참조가 반복되어 할당된다. 

 

풀이순서

여기서 인덱스가 5인 경우를 가정하고 작성한다.
 

변수 초기화

우선적으로, 추적에 사용할 변수를 초기화한다. 여기서 count 변수를 0으로 초기화한다. 이는 처음 순회하기 때문에 초깃값으로  0을 지정하는 것이다.
 
그 후 current 변수를 헤드 노드(this.head)로 설정한다.  current 변수에 this.head 를 할당하는 이유는 이후 while 문을 통해 루프를 돌 때 현재 찾고자 하는 index 에 위치한 노드가 맞는지 확인하고, 틀리면 다음 노드에 대한 참조를 할당하여 재사용하기 위해서이다.

let count = 0; // 현재 노드 순회 카운터
let current = this.head; // 현재 노드를 헤드로 설정

 

노드 순회(검색)을 위한 while 설정

while 루프를 통해 count가 5보다 작을 때까지 순회한다. 각 루프 반복에서 해당하는 노드를 찾지 못하면, current를 다음 노드로 옮긴다. 그리고, 루프를 순회할 때마다 count를 증가시켜 현재 어떤 노드를 참조중인지 추적한다.

while (count < index) { // index = 5
    current = current.next; // 다음 노드로 이동
    count++; // 카운터 증가
}

 

검색된 노드의 데이터 반환

count 변수에 할당된 값이 5와 같거나 커지게 되는 순간 while 의 조건은 falsy 이므로 while 루프가 종료된다, 이 때 current가 인덱스가 5인 노드를 가리키게 되며,  해당 노드의 데이터를 반환하게 된다.

이렇게 해서 인덱스가 5인 노드를 찾게 된다.

return current.data;

 

노드를 리스트의 앞에 추가했을 때 search 메소드 실행 결과

 

시간복잡도와 공간복잡도

우선 연결 리스트에서 search 메소드의 시간복잡도는 O(n) 이다. 왜냐 하면, 리스트에서 타겟이 되는 노드를 찾기 위해 전체 노드를 순회해야 하기 때문에, 그 만큼 연산횟수도 선형적으로 증가하기 때문이다.
 
반면, 공간복잡도는 O(1) 으로 상수시간을 가진다. 공간복잡도는 연산을 수행하는데 있어서 사용되는 메모리상의 공간이 어떻게 증가하느냐에 따라서 달라지는데, search 메소드의 경우에는 별도로 메모리상의 공간을 증가시키는 것이 아니라 처음에 변수를 초기화하는 순간에 할당된 공간을 순회하는 동안 계속해서 사용하므로 아무리 시간이 지나도 메모리를 차지하는 공간은 일정하다. 따라서 공간복잡도는 O(1) 이 된다.
 
사실 위에 구현된 경우에만 위 복잡도가 적용된다. head  와 함께 tail 을 추가하거나, next 와 함께 prev 를 추가하거나 하는 등 응용에 따라서 검색 자체가 O(1) 시간복잡도를 가지게 할 수도 있다. 이는 상황에 따라서 어떻게 응용하느냐에 다름을 알아둘 필요가 있어 보인다.