배열
- 배열 : 프로그래밍 언어에서 기본적으로 제공하는 자료구조
프로그래밍 언어에서 배열을 선언할 때 배열의 크기를 알려준다
| int arr[10] = {1,2,3,4,5}; |
위와 같이 배열을 선언할 때 운영체제는 메모리에서 숫자 10개가 들어갈 수 있는 연속된 빈공간을 찾아 배열의 값을 할당한다. 할당하지 않은 부분은 의미없는 값이 저장되어있다.
- 배열의 장점 : 배열의 인덱스 참조는 길이에 상관없이 한 번에 가져오기 때문에 O(1)의 성질을 가진다. 따라서 배열은 참조에서 좋은 성능을 보인다.
- 배열의 단점 : 배열의 참조 성능은 좋지만, 데이터의 삭제, 삽입 성능은 좋지 않다. 배열의 크기가 계속 커진다면 메모리가 늘어난 만큼의 연속된 공간을 다시 찾아야 하기 때문. 즉, 연속된 메모리 공간이 필요하고, 크기 예측이 힘들어 메모리 낭비가 발생한다.
-> 배열의 크기를 처음부터 엄청 크게 만든다면 배열 하나가 메모리를 많이 차지하고 사용하지 않는 부분을 낭비함.
- 자바스크립트에서의 배열 : 일반 배열과 달리 대부분 불연속적으로 할당된 메모리를 내부적으로 연결해서 사용자에게 배열인것처럼 보인다.
연결리스트
- 연결리스트 : 배열의 단점을 해결하기 위해 저장하려는 데이터들을 메모리공간에 분산해 할당하고 이 데이터들을 서로 연결. 이를 노드라는 것을 만들어 해결.
- 노드의 구조 : 데이터를 담는 변수 하나, 다음 노드를 가리키는 변수 하나를 가지고 있다. 데이터가 필요하다면 필요한 데이터만큼 노드를 만들어 데이터를 저장하고 다른 노드를 가리켜 연결한다. 이러한 구조로 인해 '연결리스트'라고 불린다.
연결리스트는 첫 노드의 주소만 알고 있으면 다른 모든 노드에 접근이 가능하다.
- 연결리스트의 장점 : 데이터 추가, 삭제 시 빈메모리 공간에 데이터를 추가, 삭제하고 연결만 하면된다. 따라서 배열에서 문제되었던 초기 크기를 알아야 하는 단점이 없다.
- 연결리스트의 단점 : 배열의 경우 메모리에 연속된 공간에 할당되어 시작주소만 알면 이후 데이터의 접근이 매우 쉽지만, 연결리스트의 경우 데이터들이 모두 떨어져있기 때문에 앞에서부터 해당노드까지 접근해야해 조금 더 느리다. (3번째를 찾으려면 1->2->3)
| |
배열 |
연결리스트 |
| 크기 |
고정
(초기 선언 시 크기 고정 - 자바스크립트 제외) |
동적
(데이터가 필요할때마다 노드를 만들어 연결) |
| 주소 |
연속 |
불연속 |
| 데이터 참조 |
O(1)
(메모리에 연속된 공간에 할당-메모리 접근이 빠름) |
O(n)
(데이터 참조를 위해 앞에서부터 해당 노드까지 접근) |
| 삽입과 삭제 |
O(n)
(기존 모든 데이터를 옮겨야함) |
O(n)
(삽입, 삭제하려는 노드까지 노트를 계속 타고 들어감) |
프로그램 만들 때 데이터의 수가 잘 바뀌지않고 참조가 자주일어난다 -> 배열을 사용하는 것이 성능이 좋음
데이터의 삽입, 삭제가 많이 일어난다 -> 메모리 절약을 위해 연결리스트를 사용하는 것이 좋음