배열
▶️ 배열은 연속된 데이터를 저장하는 자료구조이다.
▶️ 배열에서 크기를 정해놓는데 각각에 연속된 주소를 부여받는다
▶️ Javascript 기준, array[0]라는 것이 있으면 []안에 있는 것이 인덱스이다.
- 인덱스를 갖게 된다는 것은 임의 접근이 가능하다는 뜻이다.
- 따라서 접근과 탐색이 용이하다.
▶️ 첫번째 메모리 주소만 알고 있으면 모든 데이터의 값을 바로 접근할 수 있다.
- 배열에서 검색은 O(1)이 된다.
▶️ 배열은 메모리상에 순서대로 저장한 자료구조이기 때문에 데이터가 변경되면 다른 데이터의 물리적 위치도 영향을 받는다. 따라서 배열에서 새로운 데이터를 추가하거나 삭제하려면 메모리 상의 주소를 모두 바꾸어야 한다.
- 배열에서의 추가나 삭제는 O(N)이 된다.
<배열의 장점>
▶️ 배열은 인덱스를 가지고 있기 때문에 값(데이터)에 바로 접근이 가능하다.
▶️ 다른 장점으로는 연속된 메모리 공간에 존재하기 때문에 관리가 수월하다.
<배열의 단점>
▶️ 배열의 단점은 삽입과 삭제가 어렵다. 시간이 오래 걸린다.
▶️ 배열은 처음 생성할 때 그 크기를 선언하기 때문에 크기의 가변이 어렵다.
동적배열
<배열의 문제점과 동적배열의 탄생>
배열은 처음 배열을 선언할 때 크기를 지정해주어야 하며, 그 크기 이상의 자료를 넣을 수 없다. 이 문제를 해결하기 위한 것이 동적 배열이다.
<동적배열의 특징>
▶️ 배열의 특성을 이어받아서 동적배열은 데이터들이 메모리의 연속된 위치에 저장된다
- 메모리상에서 원소들이 연속적으로 붙어있어 인덱스 값을 이용하여 랜덤 접근(Random Access)이 가능
▶️ 배열의 크기를 변경하는 resize() 연산이 가능하다.
=> 배열의 크기에 비례하는 시간이 걸림
▶️ 배열의 맨 끝에 원소를 추가할 수 있는 append() 연산을 지원한다.
연결리스트
▶️ 리스트를 보통 연결리스트(Linked List)라고 부른다.
▶️ 연결리스트는 어떠한 노드가 데이터와 다음 노드에 대한 주소 정보(포인터)를 가지고 노드들끼리 순차적으로 연결되어있는 방식의 자료구조이다.
- 배열에서 원소가 삭제 되어도 인덱스는 유지되기 때문에, 초기에 적절한 크기의 배열을 선언하지 않으면 메모리의 낭비를 초래하게 된다.
연결 리스트는 이런 메모리의 낭비를 줄이기 위해 인덱스를 포기하고 노드를 연결해 데이터를 적재한다. - 연결리스트는 배열의 추가/삭제의 성능을 해결하기 위한 자료구조이다.
▶️ 연결리스트는 메모리 상의 주소를 순서대로 저장하는 것이 아니라 아무 메모리에나 저장하고, 대신에 기존 데이터에 부가 정보로 다음 데이터(Next node)의 주소를 저장한다.
▶️ 만약 5번째 데이터를 찾고 싶으면 처음 주소지에서 다음 데이터의 주소를 건너는 연산이 4번 수행되어야 한다. 그러므로 마지막 데이터를 찾으려면 모든 데이터를 한번씩 봐야 한다.
- 검색의 연산은 배열보다 느린 O(N)이 된다.
▶️ 추가/삭제를 해도 전체 데이터 구조가 변하지 않는다. 한 데이터를 추가한다면, 그 전 데이터의 다음 주소를 바꾸어주기만 하면 된다.
- 연결리스트에서 추가나 삭제 연산은 O(1)이 된다.
<연결 리스트의 장점>
리스트의 가장 큰 장점은 크기가 가변이라는 것이다.
원소의 추가와 삭제에 따라 크기가 동적으로 변하기 때문에
연속적으로 메모리를 할당할 필요가 없다.
또한 사용한 메모리도 재사용이 가능하여 메모리의 낭비가 적다.
<연결 리스트의 단점>
배열과 비교했을때 리스트는 탐색이 순차적으로 이루어지며 그만큼 시간이 소요된다.
또한 별도의 주소를 저장하는 공간을 필요로 하기 때문에 추가적인 메모리가 필요한 점이 있다.
주석
O(1) : 입력과 상관없이 복잡도는 동일하게 유지된다. 즉, 입력값이 증가하더라도 시간이 늘어나지 않는다.
O(N) : 입력이 증가하면, 처리 시간 또는 메모리 사용이 같은 비율로 증가한다.
참고자료
1) https://bigsong.tistory.com/31
2) https://blacklobster.tistory.com/8
3) https://laboputer.github.io/ps/2017/09/05/array-and-list/
