배열, 연결리스트

배열, 연결리스트

설명

• 배열



• 정의: 원소들을 연속된 메모리에 저장하는 자료구조
• 장점: index로 메모리에 O(1) 접근 ⇒ 랜덤 접근
• 원리: 시작 메모리 주소 + (참조할 index * 데이터 형에 따른 메모리 크기)
• TMI) js의 array는 객체라 오프셋 연산 x → 히든 클래스로 성능 개선
• 단점: 배열의 크기가 고정
• 런타임 시, 배열의 크기에 변동이 생긴다면? ex) 갑자기 사용자가 늘어나서 10개 추가해야함
• 맨 앞에 새 원소를 넣고싶다면? → 최악의 경우 O(n) 걸림

• 동적배열
• 정의: 런타임에 배열의 크기를 조절할 수 있는 자료구조
• 원리
배열 꽉 찰 경우 → 현재 크기에 2배를 만들고, 값을 복사함
배열 원소가 절반 넘게 빌 경우 → 현재 크기의 / 2로 만들고, 값을 복사함
• 단점: 연속된 메모리 공간이 필요하다

• 연결리스트
• 정의: 포인터를 이용해 연속된 공간이 아니어도 데이터 집합을 표현할 수 있는 자료구조



• 종류
• 이중 연결리스트: 이전 원소, 이후 원소의 주소값을 가짐 → 탐색을 2방향으로 가능
• 원형 연결리스트: 마지막 원소의 포인터 → 첫번째 원소의 주소값
• 장점
• 연속된 공간이 필요없다
• 원소 추가 시, 최선의 경우 O(1) 걸림 ex) 맨 앞에 원소 추가 시, 새 메모리 할당 → head가 가리키는 원소 포인팅
• 단점
• 원소에 랜덤 접근 불가능 → 원소 찾는데 최악의 O(n) 걸림
• 원소 추가, 삭제하는 데는 오래걸리지 않지만, 해당 원소를 찾는데 O(n) → 원소 추가, 삭제 → 최악의 경우 O(n) → 많은 데이터를 다룰경우 치명적, 이를 보완한 트리 자료구조!

언제, 어떤 걸 쓸까?

• 배열 : 데이터 크기가 고정적이고, 특정 데이터 찾는 경우가 많을 때

• 연결리스트 : 데이터 크기가 유동적일 때

스택, 큐

• 스택 : 후입선출, 나중에 들어간 게 먼저 호출되는 자료구조
• push: 마지막에 원소 추가 - O(1)
• pop: 마지막 원소 꺼내기 - O(1)
• 활용: 뒤로가기 버튼

• 큐 : 선입선출, 먼저 들어간 게 먼저 호출되는 자료구조



• 첫번째 원소, 마지막 원소를 포인팅함
• enQueue: 마지막에 원소 추가 - O(1)
• deQueue: 첫번째 원소 꺼내기 - O(1)
• 활용
• 태스크 큐: web api의 결과값을 담아두는 큐 → 이벤트 루프에 의해 콜스택으로 감
• 우선순위 큐: 큐에 원소를 추가/삭제 할 때, 우선순위에 따라 배치하는 자료구조
예제코드

// 최소값 리턴하는 큐 
class priorityQueue {
    constructor(arr) {
        this.arr = arr;
    }
    enqueue(value) {
        this.arr.push(value);
    }

    dequeue() {
        let i = 0;
        let min = this.arr[i];
        for (let idx in this.arr) {
            if (min > this.arr[idx]) {
                min = this.arr[idx];
                i = idx;
            }
        }
        this.arr.splice(i, 1);
        return min;  
    }
}