[JS]연결리스트와 연속 배열의 차이

1. 연결리스트 vs 연속배열

1-1. 연결리스트란?

- 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터 저장 자료 구조

1-2. 연속배열이란?

- 연속적인 메모리 상 동일한 데이터 타입 요소들을 순차적으로 일렬로 저장하는 자료구조

 

### 1-3. 장단점

- 연속배열은 추가/삭제가 느리지만, 인덱스 조회는 빠르다.
- 연결리스트는 추가/삭제 빠르지만, 인덱스 조회는 느리다.
- 즉, 연결리스트는 추가/삭제 O(1), 데이터 검색은 O(n)가 걸린다.

## 2. 참조

- A 메모리를 통해 B 메모리에 접근할 수 있다 -> B는 A에 참조된다
- 자바스크립트 오브젝트는 prototype을 암시적으로 참조

var x = {
  a: {
    b: 2
  }
};
// 2개의 오브젝트가 생성되었습니다. 하나의 오브젝트는 다른 오브젝트의 속성으로 참조됩니다.
// 나머지 하나는 'x' 변수에 할당되었습니다.
// 명백하게 가비지 콜렉션 수행될 메모리는 하나도 없습니다.


var y = x;      // 'y' 변수는 위의 오브젝트를 참조하는 두 번째 변수입니다.

x = 1;          // 이제 'y' 변수가 위의 오브젝트를 참조하는 유일한 변수가 되었습니다.

var z = y.a;    // 위의 오브젝트의 'a' 속성을 참조했습니다.
                // 이제 'y.a'는 두 개의 참조를 가집니다.
                // 'y'가 속성으로 참조하고 'z'라는 변수가 참조합니다.

y = "mozilla";  // 이제 맨 처음 'y' 변수가 참조했던 오브젝트를 참조하는 오브젝트는 없습니다.
                // (역자: 참조하는 유일한 변수였던 y에 다른 값을 대입했습니다)
                // 이제 오브젝트에 가비지 콜렉션이 수행될 수 있을까요?
                // 아닙니다. 오브젝트의 'a' 속성이 여전히 'z' 변수에 의해 참조되므로
                // 메모리를 해제할 수 없습니다.

z = null;       // 'z' 변수에 다른 값을 할당했습니다.
                // 이제 맨 처음 'x' 변수가 참조했던 오브젝트를 참조하는
                // 다른 변수는 없으므로 가비지 콜렉션이 수행됩니다.