배열/ 동적 배열/ 링크드리스트

TL;DR

구현상 어떤 특징이 있는지, 시간복잡도가 어떤지, 어떤 경우에 사용하면 좋은지 3가지 포인트 기억하기!

• 배열과 링크드 리스트의 가장 큰 차이점은 메모리에 저장되는 방식과 이에 따른 연산 속도다.

---

배열 Array

배열은 정적 자료구조로 연관된 데이터를 연속된 메모리에 미리 할당된 크기만큼 저장하는 자료구조다.

👆 정적이란? 메모리 공간에 미리 사이즈를 할당한다는 의미

ex) 자바의 경우에는 int[] array = new int[5] 와 같이 선언한다. 여기서 []안의 5가 미리 할당하려는 사이즈를 의미한다.

 

• 미리 메모리 공간을 할당받기 때문에 컴파일 단계에서 stack 영역에 메모리 할당이 일어난다.
• 장점 : 메모리 상에서 연속적으로 저장되어 있기 때문에, 인덱스(index) 접근이 가능해 접근이 빠르다.
  Base-address + offset 연산으로 특정 인덱스의 주소를 바로 계산할 수 있다.
• 단점 : 배열 선언 시에 크기를 미리 정해두어야 해서, 크기가 고정되고 이로 인해 메모리 낭비가 있을 수 있다.
• 따라서 배열은 데이터 개수를 알고 있고 메모리를 적게 쓰는게 중요한 상황일 때 또는 조회 작업을 자주 할 때 사용하면 좋다.

 

연산의 시간복잡도

• 탐색 : O(1) → 인덱스로 접근을 수행하므로 인덱스를 모르면 O(N) 소요된다.
• 삽입/삭제 : O(n)
  → 배열 끝에서 삽입/삭제 시 O(1)이지만, 중간에서 이루어질 경우 원소들의 shift 연산이 필요해 O(N) 소요.

 

 

동적 배열 Dynamic Array

배열과 동일하게 연속적인 메모리 공간에 할당되지만 배열의 fixed-size 한계점을 보완할 수 있는 자료구조다. resize를 통해 유동적으로 size를 조절한다. 데이터를 추가하다가 기존 할당된 메모리를 초과하면 사이즈를 늘린 배열(보통 2배 size)을 선언하고 그곳으로 모든 데이터를 옮긴다.

• 런타임 단계에서 새로운 노드가 추가될 때마다 heap 영역에 메모리 할당이 일어난다.
• 배열의 장단점을 그대로 갖는다.

 

연산의 시간복잡도

• 탐색 : Amortized O(1)
  → resize가 필요한 경우 데이터를 옮겨야 하기 때문에 O(N)의 시간 복잡도를 갖게된다. 하지만 이는 가끔씩 일어나는 일이기 때문에 평균적으로 O(1)이라고 볼 수 있다.
• 삽입/삭제 : O(n)

 

 

연결 리스트 LinkedList

연결리스트(a.k.a 링크드리스트)는 노드라는 구조체로 이루어져 있는데, 각 노드는 데이터와 다음 노드의 주소를 저장해 물리적으로는 비연속적이지만 논리적으로는 연속성을 갖는 자료구조다.

• 런타임 단계에서 새로운 노드가 추가될 때마다 heap 영역에 메모리 할당이 일어난다.
• 장점 : 삽입, 삭제가 용이하다. 데이터가 추가 되는 시점에서 메모리를 할당하기 때문에 메모리를 좀 더 효율적으로 사용할 수 있다
• 단점 : 메모리 상에서 연속적으로 저장되어 있지 않아 임의 접근이 불가능하다. 첫번째 노드(head)에서 시작해 특정 노드까지 순차적으로 접근해야 하므로 탐색이 비효율적이다.
• 따라서 링크드 리스트는 데이터 크기가 정해져 있지 않고, 삽입 삭제를 자주 할 때 사용하면 좋다. 추가적으로 조회 작업이 많은 경우에는 적합하지 않다.

 

연산의 시간복잡도

• 탐색 : O(N)
  → 첫번째 노드(head)만 직접적으로 접근이 가능하므로, 특정 노드를 찾으려면 head부터 시작해야 한다.
• 삽입/삭제 : O(1) 삽입/삭제할 인덱스의 주변 노드들 간의 연결된 링크만 수정하면 된다.

 

References

• lunarmoon7/배열 vs 링크드리스트