[자료구조] Array(배열)와 LinkedList

Array (배열)

Array란 데이터를 순차적으로 저장하는 자료구조이다.

 

장점

0부터 시작하는 Index를 이용하여 특정 요소에 접근 및 조작 가능하며,

순차적으로 접근하는 것이 아닌 우리가 원하는 인덱스에 바로 접근 가능하므로 시간복잡도 0(1)이 된다.

 

단점

배열 중간에서 삽입이나 삭제가 이루어질 경우 모든 요소를 한칸 앞당기거나 밀어야하므로 시간복잡도 0(n) 소요되며, 배열의 크기는 고정적이기 때문에 배열의 크기를 예측하기 어려운 경우 메모리 낭비가 발생할 수 있다.

 

LinkedList

각 노드가 데이터와 포인터를 가지고 한줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조이다.

 

장점

데이터 삽입 시 기존 노드의 연결을 끊고 새로운 노드에 연결시켜주면되고, 삭제 시에도 기존 노드의 연결을 끊고 다음 노드에 이어주기만 하면 되므로 배열에 비해 성능 효율적이다.

 

단점

Index가 존재하지 않기 때문에 특정 요소에 접근하기 위해서는 내부 원소들을 모두 탐색해야 하므로 시간복잡도 0(n) 소요.

 

요약

Array(배열)는 특정 요소에 대한 접근을 빠르게 할 수 있지만 삽입과 삭제가 비효율적이다.
LinkedList는 데이터의 삽입과 삭제는 효율적이지만 특정 요소에 대한 접근속도가 느리다.

 

데이터가 자주 바뀌지 않고 특정 요소에 대한 접근이 빈번하다면 Array(배열)를 사용하고,
데이터의 삽입과 삭제가 자주 일어난다면 LinkedList를 사용하면 좋을 것 같다.