Array vs LinkedList

  [ Array(배열) ]  

• 논리적 저장순서와 물리적 저장 순서가 일치한다.
• 인덱스로 해당 원소에 접근이 가능하다.
• 인덱스만 알고 있다면 시간 복잡도 O(1)만에 해당 원소로 접근할 수 있다.
• 즉, Random Access가 가능하다.
• 배열의 원소를 삭제할 경우 삭제한 원소보다 큰 인덱스를 가진 원소들을 옮겨줘야(Shift) 하기 때문에 시간 복잡도 O(n)이 걸린다.
• 삽입의 경우, 새로운 원소를 추가하고 모든 원소들의 인덱스를 1씩 Shift 해줘야 하므로 시간 복잡도 O(n)이 걸린다.
• 제한적인 크기를 갖는다.

즉, 삭제 또는 삽입 과정에서 해당 원소에 접근하여 작업을 완료한 뒤

Shift를 해줘야 하는 cost가 발생해 O(n)의 시간복잡도를 갖는다.

 

 [ LinkedList ]  

• 자료의 주소 값으로 노드를 이용해 서로 연결되어 있는 구조를 갖는다.
• 삽입과 삭제의 경우 LinkedList가 Array보다 속도가 빠르다고 하지만 엄밀히 말하면 경우에 따라 다르다고 하는게 맞다. (아래에서 설명하겠다.)
• 원하는 값을 찾기 위해서 최소 한 번은 리스트를 순회하여야 하므로 O(n)의 시간 복잡도를 갖는다.
• 트리의 근간이 되는 자료구조이다.

LinkedList 역시 삽입과 삭제를 위해서 해당 노드를 찾아가는 동안 O(n)의 시간 복잡도를 갖는다.

추가적으로 데이터를 삽입 / 삭제하기 위한 시간 복잡도까지 계산하면 결국 O(n)의 시간 복잡도를 갖는 셈이다.

 

  [ 차이점 ]  

 

• 삽입의 경우
  일단, LinkedList는 어느 곳에 삽입하던지 O(n)의 시간복잡도를 갖는다. (만약, 중간 삽입이 없다면 즉 맨 앞과 맨 뒤에만 삽입한다면 -> 시간 복잡도 : O(1))
• 삭제의 경우
  삭제의 경우도 삽입과 마찬가지이다. 어느 곳에 삽입하던지 O(n)의 시간 복잡도를 갖는다. (만약, 중간 삭제가 없고 맨 앞과 뒤에서만 삭제한다면 -> 시간 복잡도 : O(1))

  [ Array VS LinkedList ]  

 

# 데이터 접근 속도

Array는 인덱스를 사용해 빠르게 원소에 접근할 수 있다. 따라서 Random Access를 지원한다. 

시간 복잡도 O(1)로 빠르게 찾을 수 있다.

LinkedList는 순차 접근 방식을 사용한다. 특정 원소에 접근하기 위해서는

처음부터 원소에 도달할 때까지 순차적으로 검색하면서 찾는다. 

 

시간 복잡도 O(N)

 

# 데이터의 삽입 속도

경우에 따라 다르다.
만약 배열에 공간이 많이 남아있고 맨 끝에 삽입한다면 삽입 속도 역시 O(1)에 가능하다.

하지만 이런 경우는 발생하기 힘든 케이스이다.

 

Array(배열)의 경우 데이터를 중간이나 맨 앞에 삽입할 경우 그 이후의 데이터를 한 칸씩 미뤄야 하는 추가 과정과 시간이 소요된다.

데이터가 많을 경우 비효율적이다. 그렇기 때문에 LinkedList가 필요하게 되었다.

LinkedList는 어느 곳에 삽입하던지 O(N)의 시간 복잡도를 갖는다.(만약, 중간 삽입이 없다면 O(1)의 시간복잡도를 갖는다.)

이유는 삽입할 위치를 찾고(O(N)) 삽입 연산을 진행하기 때문에 O(N)의 시간 복잡도를 갖는다.

그럼에도 Array보다 빠른 성능을 보인다.

또한 Array의 경우 데이터 삽입 시 모든 공간이 다 차버렸다면 새로운 메모리 공간을 할당받지만 LinkedList는 그럴 필요가 없다.

추가할 때마다 동적으로 할당하는 것으로 알고 있다.

 

# 데이터의 삭제 속도

이 부분도 경우에 따라 다르다.
Array는 데이터 삭제의 경우 그 위치의 데이터를 삭제 후, 전체적으로 Shift 해줘야 한다. (O(N))

LinkedList의 경우 삭제할 원소를 찾기 위해서 O(N)의 시간 복잡도를 갖고 삭제를 한다.

결국 O(N)의 시간 복잡도를 갖는다. 하지만 Array 보다 빠르게 삭제 연산을 수행한다.

 

# 메모리 할당

• Array에서 메모리는 Array가 선언되자 마자 Compile time에 할당되어 진다. 이것을 정적 메모리 할당이라고 한다.
• Stack 영역에 메모리 할당이 이루어진다.
• LinkedList에서 메모리는 새로운 node가 추가될 때 runtime에 할당되어 진다. 이것은 동적 메모리 할당이라고 한다.
• Heap 영역에 메모리 할당이 이루어진다.

# size

Array의 size는 반드시 선언 시점에 지정되어있어야 한다.

LinkedList의 size는 다양할 수 있다.

node들이 추가될 때 runtime 시점에서 LinkedList의 size가 커질 수 있기 때문이다.

 

  [ 결론 ]  

- 삽입과 삭제가 빈번하다면 LinkedList를 사용하는 것이 더 좋다.

- 데이터의 접근하는 게 중요하다면 Array를 사용하는 것이 좋다.

---

[Data Structure] Array vs LinkedList