[자료구조] 배열(Array) vs 연결리스트(Linked List)

배열 (Array)

배열이란 같은 종류의 데이터들이 연속된 메모리 공간으로 이루어져 있는 자료구조를 말한다.

 

예를 들어 크기가 8인 배열 하나를 생성한다고 하면 컴퓨터는 연속된 빈 공간을 찾아 데이터를 할당하게 된다.

장점 

컴퓨터는 위 메모리에서 배열의 시작과 끝이 어디인지 알고 있기 때문에 내가 배열의 3번 인덱스를 참조할 때  0...1...2 순차적으로 찾는 게 아니라 3번 인덱스에 바로 참조할 수 있다. 그래서 시간 복잡도는 O(1)이 된다.

 

즉, 읽기 쓰기와 같은 참조에서는 O(1)의 좋은 성능을 가졌다.

 

단점

하지만 배열에 데이터를 빈번하게 추가하거나 삭제하는 경우에는 비효율적이다.

배열 중간에 값을 추가하게 되면 추가하려는 부분의 자리를 비우고, 기존 데이터는 복사되어 한 칸씩 미뤄지게 된다.

삭제도 마찬가지로 중간에 삭제된 부분을 메꾸기 위해 삭제된 뒷부분의 데이터들이 한 칸씩 당겨지게 된다.

 

즉, 데이터 추가 및 삭제가 비효율적이다.

그리고 배열의 크기 예측이 어려울 경우 메모리의 낭비가 발생할 수 있다.

 

연결리스트 (Linked List)

연결리스트란 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식들로 데이터를 저장하는 자료구조이다.
출처: 위키백과

 

즉, 저장하려는 데이터들을 노드를 통해 메모리 공간에 분산해 할당하고 이 노드들을 서로 연결해주는 방식이다.

 

Node

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

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

 

만약 크기가 3인 연결리스트를 생성한다면 비어 있는 메모리 공간에 3개의 노드가 분산되어 할당된다.

 

장점

연결리스트로 데이터를 추가할 때는 빈 메모리 공간 아무 곳에 데이터를 생성하고 연결해줄 수 있기 때문에 초기에 크기를  정해줄 필요가 없다.

연결리스트 중간에 데이터를 추가 또는 삭제를 하게 되면 다음을 가리키는 노드만 변경하면 되기 때문에 배열의 추가, 삭제보다 훨씬 효율적이다.

 

즉, 데이터의 삽입과 삭제가 배열에 비해 성능이 효율적이다.

 

단점

연결리스트는 데이터가 메모리 공간에 전부 떨어져 있긴 때문에 처음 노드에서 다음 노드를 찾고 그다음 노드를 찾고.. 이 과정을 반복해서 찾는 데이터를 참조하게 된다.

 

즉, 데이터 참조에 대해서는 배열에 비해 비효율적이다.

 

 

배열과 연결리스트의 차이

	배열	연결리스트
크기	고정	동적
주소	연속	불연속
데이터 참조	O(1)	O(n)
삽입과 삭제	O(n)	O(n)

 

데이터가 자주 바뀌지 않고, 참조가 자주 일어난다면 배열을 사용하고,

데이터의 삽입과 삭제가 자주 일어나는 경우에는 연결리스트는 사용해보도록 하자