[백엔드TIL] Array, LinkedList에 대해 설명(79일차)

Array (배열)

• 정의: 배열은 고정된 크기의 연속적인 메모리 공간에 원소들을 저장하는 자료구조입니다.
• 특징:
  • 고정된 크기: 배열은 생성 시에 크기가 정해지며, 이후 크기를 동적으로 변경하기는 어렵습니다.
  • 인덱싱: 배열의 원소에는 인덱스를 사용해 접근할 수 있으며, O(1) 시간에 해당 원소를 찾을 수 있습니다.
  • 메모리 사용: 연속적인 메모리 공간을 사용하므로 메모리 관리에 용이합니다.
• 주요 작업의 시간 복잡도:
  • 원소 조회 (인덱싱): O(1)
  • 원소 추가/삭제 (끝에서): O(1)
  • 원소 추가/삭제 (중간): O(n)

LinkedList (연결 리스트)

• 정의: 연결 리스트는 노드(Node)들의 집합으로, 각 노드는 데이터와 다음 노드를 가리키는 포인터로 구성됩니다.
• 특징:
  • 동적 크기: 연결 리스트는 동적으로 크기를 변경할 수 있습니다. 노드를 추가하거나 삭제하면서 크기를 조절할 수 있습니다.
  • 포인터 사용: 각 노드는 데이터와 함께 다음 노드를 가리키는 포인터를 가지고 있습니다.
  • 메모리 사용: 비연속적인 메모리 공간을 사용합니다.
• 주요 작업의 시간 복잡도:
  • 원소 조회: O(n)
  • 원소 추가/삭제 (시작 또는 끝에서): O(1) - 단, 끝에서의 작업은 이중 연결 리스트 또는 꼬리 포인터가 있는 경우에만 O(1)
  • 원소 추가/삭제 (중간): O(n)

어떤 것을 사용할까?

배열과 연결 리스트는 각각의 장단점이 있으므로, 사용 사례에 따라 적절한 자료구조를 선택해야 합니다. 예를 들어, 중간에 자주 원소를 추가하거나 삭제해야 하는 경우 연결 리스트가 유용할 수 있습니다. 반면, 원소에 빠르게 접근해야 하는 경우 배열이 더 적합합니다.

면접에서 할 대답

배열: 고정된 크기의 연속적인 메모리 공간을 사용합니다.
배열은 O(1) 시간에 인덱싱으로 원소에 접근합니다.
배열의 중간 원소 추가/삭제는 O(n) 시간이 걸립니다.
연결 리스트: 노드들의 집합으로, 노드는 데이터와 다음 노드를 가리키는 포인터로 구성됩니다.
연결 리스트는 동적으로 크기를 조절할 수 있습니다.
연결 리스트의 원소 조회는 O(n) 시간이 걸립니다.
연결 리스트의 노드 추가/삭제는 위치에 따라 O(1) 또는 O(n) 시간이 걸립니다.
사용 사례에 따라 배열 또는 연결 리스트 중 적합한 것을 선택합니다.