[자료구조] Array vs Linked List

Array (배열)

Search (검색)

• Random Access를 지원하므로 element들을 index를 통해 직접적으로 접근 가능
• index를 안다면 시간복잡도는 O(1)

Insert (삽입) / Delete (삭제)

• 데이터들이 순차적으로 저장되어있으므로 데이터가 추가될 경우 그 뒤에 있는 데이터들을 모두 한 칸씩 뒤로 미뤄야함
• 시간복잡도
  배열의 끝 : O(1)
  나머지 : O(n)

장점

• 특정한 위치의 원소에 즉시 접근이 가능

단점

• 메모리가 낭비될 수 있음
• 원하는 위치로의 삽입 또는 삭제가 비효율적

Linked List (연결리스트)

Search (검색)

• Sequential Access를 지원하므로 element/node에 접근할 때 처음부터 순차적으로 접근하여 찾아야함
• 시간복잡도는 O(n)

Insert (삽입) / Delete (삭제)

• 데이터를 추가/삭제하는 행위 자체의 시간복잡도는 O(1)
• 탐색하는 시간복잡도는 O(n)
• 시간복잡도
  연결리스트의 처음에 삽입 : O(1)
  나머지 : O(n)

장점

• 단순한 구조로 이루어져 있어서 구현이 편하고 데이터의 추가, 삽입, 삭제가 쉬움
• 현재 노드가 가지고 있는 포인터 정보를 사용하여 추가적인 연산 없이 다음 노드를 가져올 수 있음

단점

• 노드에는 다음 노드를 가르키는 포인터가 필요하기 때문에 메모리가 추가로 필요
• 헤드 노드의 정보만 가지고 있기 때문에 특정 위치에 있는 노드를 탐색하는데 많은 연산이 필요함

❓ 언제 어떠한 자료구조를 사용하는 것이 유리할까?

👉 배열 : 데이터가 정해져 있을 때, 삽입 삭제 연산을 적게 하고 검색을 많이 할 경우
연결리스트 : 삽입과 삭제 연산이 잦고, 검색 빈도가 적을 때