알고리즘 특강 - 2. 링크드리스트

배열

데이터를 빈번하게 접근해야 될 때 배열을 사용

• 조회: O(1)의 조회시간.
• 삽입 & 삭제:
  배열 끝에서 추가 및 삭제는 O(1).
  끝이 아닌 다른 곳에서 원소를 삽입 혹은 삭제 할 경우에는 O(n) -> 배열은 특정 원소를 삭제하거나 null로 만들어도 그 흔적은 그대로 남아있기 때문에 기존 배열 원소들의 위치를 다시 재정렬하는 과정이 필요함 
• 정렬: 정렬 알고리즘에 따라 시간복잡도가 다 다름 
• 검색: 일반적으로는 O(N). 정렬이 되어있는 배열이면 O(log N)이 가능

 

링크드리스트

배열이 빠르게 값을 갖고 오는 것이 장점이라면 

링크드리스트는 원소의 삽입/삭제에 강점이 있는 자료구조.

유동적으로 연결고리를 떼었다가 붙였다가 할 수 있음.

하지만, 링크드리스트는 삽입/삭제에 강점이 있는 대신에 조회에는 다소 약함 -> 최초 노드부터 끝까지 순차적으로 돌아야하기 때문에 링크드리스트 조회 성능은 O(N)

데이터를 빈번하게 삽입/삭제해야 될 때 링크드리스트 사용

 

예제) train_compartments = ["기관실"] -> ["시멘트"] -> ["자갈"] -> ["밀가루"] -> ["우편"]

• 노드:  위의 예제에서 각 화물 칸들이 노드가 됨
• Head: 맨 앞의 노드
• Tail: 맨 뒤의 누드(포인터가 NULL)
• 포인터: 현재 노드가 가리키는 다음 화물칸.
  기관실의 포인터는 시멘트, 시멘트의 포인터는 자갈, 자갈의 포인터는 밀가루, 밀가루의 포인터는 우편, 우편의 포인터는 NULL

 

// 노드를 클래스로 정의해보기

class Node {

    constructor(data) {

        this.data = data;

        this.next = null; // 처음 생성시엔 다음 노드가 아직 없어서

    }

}

class LinkedList {

    // 링크드리스트 자료구조를 클래스로 정의해보기

    constructor(value) {

        this.head = new Node(value); // 시작하는 Node를 head에 연결

        this.nodeCount = 1; // index 유효성 검사용

    }

    // 링크드리스트 끝에 새로운 노드를 추가하는 함수

    // LinkedList 가장 끝에 있는 노드에 새로운 노드를 연결하려면 끝이 어딘지 알아야 함

    append(value) {

        let curr = this.head; // 시작 노드. 그래야 헤드부터 볼 수 있음

        while (curr.next !== null) {

            //사이즈를 알때는 for loop가 직관적인데, 끝까지 돌아봐야할때는 while loop

            curr = curr.next; // 마지막꺼 나올때까지 curr에 넣는 과정

        }

        const newNode = new Node(value);

        curr.next = newNode; // 마지막의 .next에서 연결

        this.nodeCount++; // index 유효성 검사용

    }

    // 원하는 위치의 노드를 찾아내는 함수

    // 전체 중 index번째 인덱스에 있는 노드를 가지고 오고 싶어

    getNode(index) {

        // 엄밀히 말을 하자면 이 인덱스가 전체 크기를 벗어나는지를 검사해야 됩니다.

        // this.nodeCount를 근거로 index가 유효한지를 판단해야 됩니다.

        // 하지만, 우선은 유효한 index라고 가정을 하겠습니다.

        let node = this.head; // LinkedList의 Head를 처음 노드로 지정

        for (let i = 0; i < index; i++) {

            node = node.next; // 원하는 index가 될 때까지 다음 노드로 이동

        }

        return node;

    }

    // 원하는 위치에 새로운 노드를 추가하는 함수

    addNode(index, value) {

        const newNode = new Node(value);

        // 0번째에 추가하는 경우!

        if (index === 0) {

            newNode.next = this.head; // 원래 Head였던 노드를 새 노드의 next로 지정해요!

            // 새로운 노드의 다음 단계를 처음으로 지정? 뭔소릴냐 이게

            this.head = newNode; // 그리고, Head를 새 노드로 바꾸어줍니다!

            return;

        }

        const node = this.getNode(index - 1); // 직전 노드 정보

        const nextNode = node.next; // 원하는 자리의 노드를 임시저장 해놓고,

        node.next = newNode; // 원하는 자리에 새로운 노드로 포인터 지정

        newNode.next = nextNode; // 임시저장한 기존의 노드를 다음 노드로 걸어줌

    }

}