배열이 메모리에서 어떻게 할당이 되고, 어떻게 동작이 되는지 알아봤다.
여기서 배열은 자바스크립트 배열과는 다르다.
| 배열의 장점 | 배열의단점 |
|---|---|
| 읽기, 쓰기와 같은 참조에는 O(1)의 성능을 가진다. | 크기의 예측이 힘들기 때문에 메모리 낭비가 발생할 수 있다. |
| 데이터 삽입, 삭제가 비효율적이다. |
🤔 배열의 단점을 해결하려면 어떻게 해야할까?
저장하려는 데이터들을 메모리 공간에 분산에 할당하고 이 데이터를 연결해주는데 이는 노드로 수행한다.
-
노드는 데이터를 담는 변수 하나와 다음 노드를 가리키는 변수 하나를 가지고 있다. -
데이터가 필요하다면 필요한 데이터만큼 노드를 만들어 데이터를 저장하고 다른 노드를 가리켜 연결한다.
이러한 구조 때문에 연결 리스트라고 부른다.
-
연결 리스트는 첫 노드의 주소만 알고 있으면 다른 모든 노드에 접근할 수 있다. -
또한 연결이라는 특성 때문에 배열과는 다른 장단점을 가지고 있다.
연결리스트의 장점
연결리스트에서 데이터를 추가한다면 빈 메모리 공간 아무 곳에 데이터를 생성하고 연결만 해주면 되기 때문에 배열에서 초기 크기를 알야아하는 단점이 연결리스트에는 없다.
배열에서는 중간데 데이터를 삽입하면 그 뒤에 있는 데이터들은 모두 뒤로 밀려나기 때문에 오버헤드가 많이 든다.
반면 연결리스트는 중간에 데이터를 삽입하면 다음 가리키는 노드만 바꿔주면 되기 때문에 아주 간단한 작업이다. 데이터의 삭제도 마찬가지다.
연결리스트 단점
배열은 메모리의 연속된 공간에 할당되어 있어서 시작 주소만 알면 뒤에 있는 데이터 접근이 굉장히 쉽다. O(1)의 성능을 가진다.
반면 연결리스트는 데이터들이 전부 떨어져 있기 때문에 바로 접근할 수 없다. 네 번째 데이터에 접근하고 싶으면 첫 번째 노드에서 다음 노드를 찾고, 다음 노드에서 또 그 다음 노드를 찾아서 데이터를 참조한다. 즉 연결리스트에서 데이터 참조는 O(n)의 성능을 가진다.
크키
배열은 초기 선언 시 크기를 지정해줘야 해서 크기가 고정이다. 물론 자바스크립트 배열은 특별하기 때문에 이렇지 않다. 연결리스트는 데이터가 필요할 때마다 노드를 만들어 연결해주기 때문에 크기가 동적이다.
주소
배열은 메모리의 연속된 공간에 할당된다. 연결리스트는 메모리에서 힙이라는 영역에 런타임(프로그램 실행 중)에 불연속적인 빈 공간에 할당한다. 메모리 구조가 궁금하면 운영체제 공부필요 !
데이터 참조
배열은 메모리에 연속된 공간에 할당되기 때문에 메모리 접근이 굉장히 빠르다. O(1) 의 성능을 가진다.
반면 연결리스트는 데이터 참조를 위해선 앞에서부터 해당 노드까지 접근해야 하기 때문에 조금 더 느리다. O(n)의 성능
삽입과 삭제
배열에서 데이터를 삽입하려면 기존 모든 데이터를 옮겨야해서 O(n)의 성능을 가진다.
연결리스트는 삽입하려는 노드까지 노드를 계속 타고 들어가야 하니 O(n)의 성능을 가진다. 삭제도 마찬가지.
| 배열 | 연결리스트 | |
|---|---|---|
| 크기 | 고정 | 동적 |
| 주소 | 연속 | 불연속 |
| 데이터참조 | O(1) | O(n) |
| 삽입과 삭제 | O(n) | O(n) |
배열과 연결리스트의 장단점을 정리해봤으니 앞으로 프로그래밍을 할 때 두 가지 선택권이 생긴다.
🤔 만약 어떤 프로그램을 만드는데 데이터의 수가 자주 바뀌지 않고 참조가 자주 일어난다면 배열과 연결리스트 중에서 어떤 것을 써야할까?
둘 중 아무거나 사용해도 되지만 성능을 생각한다면 배열이 훨신 더 좋은 선택이다.
데이터의 삽입과 삭제가 자주 일어나서 데이터의 수가 자주 바뀐다면 배열은 크기가 고정되어 잇어 메모리 절약을 위해 연결리스트를 사용해야한다.
즉 어떤 자료구조를 선택하느냐에 따라서 데이터의 크기가 작을 경우에는 차이가 별로 없겠지만 데이터가 많아진다면 성능의 차이는 훨씬 더 커질 것이다.
