[자료구조] Array와 List

CS스터디를 시작하면서 한동안 못썼던 블로그를 자주 써볼려고 합니다!!

 

예전 개발자들이 개발을 시작하면서 데이터를 다룰때 하나의 데이터만 다루는 것은 아니겠죠?

여러가지 데이터가 모인 집합을 형성하게 되는데 먼저 Array라는 녀석부터 살펴봅시다.

 

Array란?

순차적으로 데이터를 저장하는 형태로 물리적주소도 순차적으로 저장된다.(크기를 미리 지정해줘야 한다.)

index라는 것이 존재해 빠르게 값을 찾아낼때 유용하다.(원하는 데이터 한번에 접근가능O(1))

하지만 삽입과 삭제에는 취약하다. (해당 위치에 접근하고O(1), shift O(n)해주는 작업까지 걸려 O(n)이 걸린다.)

 

예를 들어 중간녀석을 삭제하려면 배열의 연속성이 깨져 이후 뒤에것들을 모두 앞으로 땡겨줘야 한다.

 

그렇다면 어떻게 저런 시간복잡도를 줄일 수 있을까?

그래서 바로 List라는 것이 나오게 된다.

 

 

 

List란?

크기를 미리 정하지 않아도 되는 데이터의 집합이다.

Array에서는 index가 중요하다면 List에서는 데이터의 순서가 중요하다.

 

그렇다면 List를 구현하는 방법은 어떤 것이 있을까?

LinkedList에 대해 알아보자

 

LinkedList란?

각각의 데이터를 노드라고 부르고 각 노드들은 다음에 어떤 노드가 올지만 알고 있다.

 

간단하다!

 

이렇게 되면 Array에서 느렸던 삽입,삭제 과정이 빠르게 이루어 질 수 있게 된다.

가리키는 곳만 바꿔주면 되므로 O(1)이 된다!

Array보다 훨씬 빠르게 삽입,삭제가 가능하다.

 

하지만 LinkedList에도 단점은 있다.

삽입 혹은 삭제할 위치를 찾는 과정이 매우 길다..

첫 번째 노드부터 타고타고 원하는 위치까지 가야하므로 O(n)이 걸린다.

 

따라서 탐색에도 O(n), 삽입,삭제에도 결과적으로는 O(n)이 걸린다.

 

 

그럼 느린데 LinkedList는 왜써?

Array에 비해 LinkedList는 배열의 크기를 고정시키지 않아도 된다는 장점이 있다.(크기를 동적으로 선언가능)

 

 

하지만 여기서 의문이 든다.

크기와 상관없이 흔히 삽입,삭제가 많은 경우는 LinkedList를 쓴다고 하는데 어차피 탐색을 해야 삽입,삭제가 가능한데 왜 이런말이 나왔을까?

 

LinkedList는 보통 그 자체의 자료구조로 사용하지 않고 Queue나 다른 형태의 자료구조를 구현할때 이용되는 개념이기 때문이다!!

큐를 예로 들면 삽입과 삭제가 어디서 이루어지는지 명확하기 때문에 O(1)의 장점이 극대화 되게 된다!

 

끝!