[자료구조 with JS] 연결 리스트(Linked List) (3) 반복문과 알고리즘

이전글:

[자료구조 with JS] 연결 리스트(Linked List) (1) 개념과 클래스

[자료구조 with JS] 연결 리스트(Linked List) (2) 삽입, 검색, 삭제

 

 

연결 리스트의 반복문

for...of 반복문

*[Symbol.iterator]() {
    let node = this.head;
    while(node) {
        yield node;
        node = node.next;
    }
}

[Symbol.iterator]이 왜 사용되었는지 알고 싶다면 MDN의 Iteration Protocols를 확인하면 된다. 또한 yield 키워드는 제너레이터를 사용한 것이다. 

 

forEach 반복문

forEach(func) {
    let node = this.head;
    let counter = 0;
    while(node) {
        func(node, counter);
        node = node.next;
        counter++;
    }
}

 

반응형

 

알고리즘 문제

중간점 찾기

연결 리스트의 중간점을 찾아라. 만약 연결 리스트가 짝수 개의 노드를 가지고 있으면, 중간에 있는 두 개의 노드 중 앞의 것을 반환하라. counter 변수와 연결 리스트의 size를 사용하면 안 된다. 그리고 반복문을 한 번만 사용하여라.

//Buffer를 사용하는 경우
function midpoint(list) {
    const listBuffer = Object.assign(list);
    let node = listBuffer.head;
    
    //연결 리스트에 노드가 없는 경우
    if(!node) return null;
    
    //연결 리스트에 헤드 노드 하나만 있는 경우
    if(!node.next) return node;
    
    while(node) {
        //버퍼 리스트의 첫 번째 노드와 마지막 노드를 제거한다.
        listBuffer.removeLast();
        listBuffer.removeFirst();
        if(!listBuffer.head) {
            //노드가 없게 된 경우, 첫 번째 노드를 반환한다.
            return node;
        } else if (!listBuffer.head.next) {
            //노드가 하나만 남은 경우, 그 노드를 반환한다.
            return listBuffer.head;
        } else {
        	//노드가 아직 두 개 이상 남은 경우, 다음 노드를 node에 할당한다.
            node = node.next;
        }
    }
}

function midpoint(list) {
    //slow와 fast 변수를 사용한다.
    //slow와 fast 둘 다 head 노드에서 출발하지만, slow 노드는 매 번 다음 노드로 이동하고 fast 노드는 다다음 노드로 이동한다.
    //fast가 마지막 노드에 도착하면 slow는 중간점 노드에 도착한다.
    //짝수개의 노드가 있는 경우에도 똑같이 활용 가능하다.

    let slow = list.head;
    let fast = list.head;
    
    while(fast.next && fast.next.next) {
        slow = slow.next;
        fast = fast.next.next;
    }
    
    return slow;

}

 

순회하는 연결 리스트인지 확인하기

주어진 연결 리스트가 순회하는 연결 리스트라면 true, 아니면 false를 반환하라. 순회하는 연결리스트란 tail 노드가 없는 리스트이다. 즉, 어느 한 부분에서 계속하여 같은 구간을 반복하여 순회하는 리스트이다.

//연결 리스트의 노드를 배열에 저장한 후 반복되는 부분이 있는지 알아보는 방법
function circular(list) {
    const nodeArray = [];
    let node = list.head;

    while(node) {
        if(!nodeArray.includes(node)){
            nodeArray.push(node);
            node = node.next;
        } else {
            return true;
        }
    }

    return false;
}

//slow와 fast 변수를 사용하는 방법
function circular(list) {
    let slow = list.head;
    let fast = list.head;

    if(!slow) return false;

    //만약 slow와 fast가 중간에 만나게 된다면 순회하는 연결 리스트이다.
    while(fast.next && fast.next.next) {
        slow = slow.next;
        fast = fast.next.next;
        if(slow === fast) {
            return true;
        }
    }
    return false;
}

 

tail 노드에서 n번째 전의 노드 찾기

연결 리스트와 정수 n이 주어졌을 때, 리스트의 마지막 노드에서 n번째 떨어진 노드를 반환하라. 단, size 메소드를 사용하면 안되고, n은 항상 연결 리스트의 크기보다 작을 것이라고 가정하라.

function fromLast(list, n) {
    let slow = list.head;
    let fast = list.head;

    //fast를 먼저 n개 노드 뒤로 옮겨 놓는다.
    for(let i = 0; i < n; i++) {
        fast = fast.next;
    }
    
    //fast 노드가 마지막 노드에 도착할 때 까지 slow와 fast 모두 한 노드씩 계속하여 뒤로 옮긴다.
    while(fast.next) {
        slow = slow.next;
        fast = fast.next;
    }
    
    return slow;
}

 

 

 

 

참고: The Coding Interview Bootcamp: Algorithms + Data Structures (Udemy Course)