[자료구조] Array & Linked List

Q. Array는 어떤 자료구조 인가요?

Array는 연관된 data를 메모리상에 연속적이며 순차적으로 미리 할당된 크기만큼 저장하는 자료구조 입니다.

✨
Array와 Linked List의 가장 큰 차이점 :
메모리에 저장되는 방식과 이에 따른 operation의 연산 속도(time complexity)

Array의 특징

• 고정된 저장 공간(fixed-size)
• 순차적인 데이터 저장(order)

Array의 장점

• lookup과 append가 빠르다는 것
  -> 따라서 조회를 자주 해야되는 작업에서는 Array 자료구조를 많이 씀

Array의 단점

• fixed-size 특성상 선언시에 Array의 크기를 미리 정해야 된다는 것
  -> 메모리 낭비나 추가적인 overhead가 발생할 수 있음

시간복잡도

Q. Dynamic Array는 어떤 자료구조 인가요?

Array의 경우 size가 고정되었기 때문에 선언시에 설정한 size보다 많은 갯수의 data가 추가되면 저장할 수 없습니다. 이에 반해 Dynamic Array는 저장공간이 가득 차 게 되면 resize를 하여 유동적으로 size를 조절하여 데이터를 저장하는 자료구조 입니다.

---

---

Q. Linked List에 대해서 설명해 주세요.

Linked List는 Node라는 구조체로 이루어져 있는데, Node는 데이터 값과 다음 Node의 address를 저장합니다. Linked List는 물리적인 메모리상에서는 비연속적으로 저장이 되지만 Linked list를 구성하는 각각의 Node가 next Node의 address를 가리킴으로써 논리적인 연속성을 가진 자료구조입니다.

시간복잡도

Array의 경우 중간에 데이터를 삽입/삭제하게 되면 해당 인덱스의 뒤에 있는 모든 원소들은 shift를 해야만 했음. 그러다 보니 $O(n)$의 시간복잡도를 갖게 됐음.
하지만 Linked list를 물리적으로 옮길 필요없이 next address가 가리키는 주소값만 변경하면 되기 때문에 $O(1)$의 시간복잡도로 삽입/삭제가 가능!

---

---

Q. Array vs Linked list를 비교해서 설명해주세요

Array는 메모리 상에서 연속적으로 데이터를 저장하는 자료구조 입니다. Linked List는 메모리상에서는 연속적이지 않지만, 각각의 원소가 다음 원소의 메모리 주소값을 저장해 놓음으로써 논리적 연속성을 유지합니다.
그래서 각 operation의 시간복잡도가 다릅니다. 데이터 조회는 Array의 경우 $O(1)$, Linked list는 $O(n)$의 시간복잡도를 갖습니다. 삽입/삭제는 Array $O(n)$, Linked list $O(1)$의 시간복잡도를 갖습니다.
따라서 얼마만큼의 데이터를 저장할지 미리 알고있고, 조회를 많이 한다면 Array를 사용하는 것이 좋습니다. 반면에 몇개의 데이터를 저장할 지 불확실하고 삽입 삭제가 잦다면 Linked list를 사용하는 것이 유리합니다.