TIL - 배열과 연결리스트

배열

자바스크립트는 전형적인 배열과 다른 특징이 있다. 

 

일반적인 배열의 특징을 먼저 알아보자. 

 

프로그래밍 언어에서 배열은 기본적으로 제공하는 자료구조이다. 

배열의 이해를 위해서는 배열이 메모리에서 어떤 모습을 하고 있는지 알아야 한다. 

일반적으로 프로그래밍 언어에서는 배열을 선언할 때 배열의 크기를 알려준다. 

 

int arr[10] = {1,2,3,4,5}

이렇게 배열을 선언했다면 운영체제는 메모리에서 숫자 10개가 들어갈 수 있는 연속된 빈 공간을 찾아서 순서대로 1,2,3,4,5를 할당한다.  할당하지 않는 부분은 의미없는 쓰레기 값이 들어가 있다. 

 

그리고 운영체제는 배열의 시작 주소, 즉 숫자 1이 들어간 주소만 기억한다. 

프로그래머가 배열의 세번째 원소에 접근하고 싶다면  arr[2] 이런식으로 인덱스로 한번에 접근할 수 있다. 

운영체제는 배열의 시작주소를 알고 있기 때문에 배열의 시작 주소부터 두번 째 떨어진 주소에서 데이터를 가져온다. 

배열의 인덱스 참조는 길이에 상관없이 한 번에 가져오기 때문에  O(1)의 성능을 가진다. 

 

이렇기 떄문에  배열은 읽기, 쓰기 에서 좋은 참조에서 좋은 성능을 가진다. 

배열의 참조 성능은 좋지만, 데이터의 삽입과 삭제 성능은 좋지 않다.

 

이유는, 앞서 배열을 선언했다면 프로그래머의 요청의 크기만큼 메모리의 연속된 공간을 할당한다고 했다. 

 만일 arr[10] = {1,2,3,4,5} 를 주어지면 차례대로 쓰레기값을 덮어쓰면서 할당된 공간을 차지한다. 

그럼 arr[15] = ....  숫자를 더 담아서 배열의 크기를 넘어 할당한다고 가정했을 경우 문제가 발생한다.  

운영체제는 처음에 프로그래머한테 크기 10인 메모리 공간을 요청받았고 그에맞게 연속된 공간을 찾아서 할당했었다. 

배열의 끝에는 다른 중요한 데이터가 담겨있기 때문에  더 확장할 수 없게 된다. 

그렇게 되면 운영체제는 크기가 15인 연속된 공간의 메모리를 다시 찾아서 할당해야 한다. 

 

기존에 저장되어 있던 1부터 10까지의 데이터를 전부 새로 할당하는 공간에 복사까지 해줘야 한다. 

애초에 이런일이 발생하지 않도록 배열의 크기를 넉넉하게 만들어 놓으면 어떨까? 

 

일시적으로는 괜찮다고 생각하지만, 더 이상의 공간을 원하게 된다면 어떻게 될까? 

배열 하나가 메모리를 엄청많이 차지하게 될 것이며 배열을 전부 사용하지도 않으면 이 부분은 순전히 낭비되는 공간이 되버린다. 

 

배열은 이처럼 데이터를 추가, 제거하려면 내부적으로 필요한 단계가 많이 들기 때문에 성능이 좋지 않다. 

 

자바스크립트는 지금까지 설명한 배열 동작과는 조금 다르게 동작한다.

상황에 따라 연속적, 불연속적으로 메모리를 할당하는데 대부분의 경우 불연속적으로 할당한다.

불연속적으로 할당된 메모리는 내부적으로 연결해서 사용자에게는 배열인것처럼 보이게 된다. 

이러한 이유로 전통적인 프로그래밍언어와는 조금 다르지만, 자료구조의 기능적인 부분만 봤을 때는 

동일하기 때문에 배열이라고 부를 수 있다. 

 

정리하자면 배열은 읽기나 쓰기와 같은 참조에는 좋은 성능을 가진다. 하지만 크기 예측이 힘들기 때문에 메모리 낭비가 초래될 수 있고 데이터 삽입과 삭제가 비효율적이다. 

 

 

자바스크립트 배열은 처음에 크기를 지정하지 않아요!

 

 

---

 

연결리스트

 

배열의 단점은 연속된 메모리공간이 필요하다. 데이터들의 크기를 예측할 수 없어서 메모리 낭비를 초래하고 데이터 삽입과 삭제에 비효율 적인것을 알아봤다. 초기에 배열의 크기를 모를 경우 메모리가 낭비될 수 있다는 점이있다. 

컴퓨터 과학자들은 이 문제를 해결하기 위해 고민했다. 

배열의 단점을 해결하려면 어떻게 해야할까? 간단하다.

 

저장하려는 데이터들을 메모리 공간에 분산해 할당하고 이 데이터들을 서로 연결해주는 것이다. 

이는 노드(Node) 라는 것을 만들어서 수행하는데 노드의 구조는 단순하다. 

 

노드는 데이터를 담는 변수 하나와 다음 노드를 가리키는 변수 하나를 가지고 있다. 

데이터가 필요하다면 필요한 데이터만큼 노드를 만들어 데이터를 저장하고 다른 노드를 가리켜 연결한다. 

 

이런 구조 때문에 "연결리스트" 라고 부르는 것이다. 

 

연결리스트는 첫 노드의 주소만 알고 있으면 다른 모든 노드에 접근 할 수 있다. 

또한 연결이라는 특성 때문에 배열과는 다른 장단점을 가지고 있다. 

 

장점으로는

연결리스트에서 데이터를 추가한다면 빈 메모리공간 아무 곳 에서 데이터를 생성하고 연결만 해주면 되기 때문에 배열에서 초기 크기를 알아야 하는 단점이 연결리스트에서는 없다. 배열에서는 중간에 데이터를 삽입하면 그 뒤에있는 데이터는 모두 그 뒤로 밀려나기때문에 오버헤드가 많이 든다. 

반면 연결리스트는 중간에 데이터를 삽입하면 다음 가리키는 노드만 바꿔주기 되기 때문에 아주 간단한 작업이다. 

데이터의 삭제도 마찬가지이다.

 

 

연결리스트는 단점

배열은 메모리에 연속된 공간에 할당되어 있어서 시작 주소만 알면 뒤에 있는 데이터 접근이 굉장히 쉽다. 

 

만약 arr[3]으로 네번째 데이터에 접근한다면 배열의 시작 주소에서 3을 더한 값에 접근하기 때문에 O(1)의 성능을 가진다. 

반면 연결리스트는 데이터들이 전부 떨어져 있기 때문에 바로 접근할 수 없다. 

네 번째 데이터에 접근하고 싶다면 첫 번재 노드에서 다음 노드를 찾고, 또 그 노드에서 다음 노드를 찾고 다음노드를 찾아서 데이터를  참조한다. 즉 연결리스트에서 데이터 참조는 O(n)의 성능을 가진다. 

 

 

---

 

 

배열과 연결리스트 비교

 

크기 :
- 배열: 고정 (초기 선언 시 지정해줘야 해서 크기가 고정임)
- 연결리스트: 동적 (데이터가 필요할 때마다 노드를 만듬)

주소:
- 배열: 연속 (메모리에 연속된 공간에 할당 됨)
- 연결리스트: 불연속 (메모리에서 힙 영역이라는 곳에 런타임중 불연속적인 빈 공간에 할당 됨) 

데이터참조:
- 배열: O(1) (메모리 연속된 공간에 할당하기 떄문에 메모리 접근이 빠름) 
- 연결리트스: O(n) (앞에서부터 해당 노드까지 접근해야하기 때문에 조금 더 느림)

삽입과 삭제:
- 배열: O(n) 기존 모든 데이터를 옮겨야 함
- 연결리스트:  O(n) 삽입하려는 노드까지 노드를 계속 파고 들어가야 함 

 

 

정리하자면, 

 

1. 어떤 프로그램을 만드는데 데이터의 수가 자주 바뀌지 않고 참조가 자주 일어난다면 배열과 연결리스트 중 어느것을 선택해야 할까?  물론 둘 중아무거나 사용해도 사용에는 이상 없겠지만, 성능을 생각하자면 배열을 사용하는 것이 더 나은 선택이 될 것이다. 

 

2. 이번엔 다른 상황으로 데이터의 삽입과 삭제가 자주 일어나서 데이터의 수가 자주 바뀐다면 ? 

연결리스트가 더 나은 선택이 될 수 있다. 배열은 크기가 고정되어 있어서 메모리 절약을 위해 연결리스트를 사용해야 할 것이다. 

데이터의 크기가 작을 경우에는 차이가 별로 없겠지만 데이터가 많아진다면 성능의 차이는 훨씬 더 커질 것 이다.