배열 (Array)

• 구조: 메모리의 연속적인 공간에 데이터 요소를 저장, 각 요소는 인덱스를 통해 접근 가능
• 크기: 배열의 크기는 처음 생성할 때 정하며 이후에는 변경 불가 (동적 배열에서는 크기 조절 가능)
• 접근 속도: 배열은 인덱스 기반 접근을 통해 O(1) 시간 복잡도로 요소에 접근할 수 있어, 읽기 성능이 매우 빠름
• 메모리: 메모리가 연속적으로 할당되기 때문에 캐시 메모리 효율성이 높으나 크기를 변경할 수 없기 때문에, 메모리 낭비 발생 가능

시간 복잡도

• 탐색: O(1) 단, 접근하고자 하는 인덱스를 알고있어야 한다. 순차적으로 탐색시에는 O(n)
• 삽입 및 삭제:
  • 배열의 처음 또는 중간에 삽입 및 삭제: O(n) (삽입 지점 이후의 데이터를 옮겨야 하기 때문)
  • 배열의 끝에 삽입 및 삭제: O(1)

연결 리스트 (Linked List)

• 구조: 각 요소(노드)가 데이터와 다음 노드에 대한 포인터를 포함하는 구조, 메모리의 비연속적인 공간에 데이터 저장 가능
• 크기: 동적으로 크기를 조정 가능, 노드 추가 및 제거 시 메모리 재할당 불필요
• 접근 속도: 요소에 대한 접근이 O(n) 시간 복잡도를 가지므로, 인덱스 기반 배열에 비해 접근 속도 느림
• 메모리: 각 노드가 추가적인 포인터를 필요로 하므로 메모리 오버헤드 발생하나 크기를 유동적으로 조정할 수 있어 메모리 관리 용이

시간 복잡도

• 탐색: O(n)
• 삽입 및 삭제: 삽입과 삭제 자체는 O(1) 이다.
  • 연결 리스트의 처음에 삽입 및 삭제: O(1)
  • 연결 리스트의 중간에 삽입 및 삭제: O(n) 탐색시간 소요
  • 연결 리스트의 끝에 삽입 및 삭제:
    • 끝을 가리키는 별도의 포인터를 갖는 경우: O(1)
    • 끝을 가리키는 별도의 포인터를 갖지 않는 경우: O(n) 탐색시간 소요

배열과 연결 리스트 비교

배열

• 장점 : 인덱스를 통한 빠른 접근이 가능하다.
• 단점 : 삽입과 삭제가 오래 걸린다. 배열 중간에 있는 데이터가 삭제되면, 공간 낭비가 발생한다.
• 용도 : 빠른 접근이 요구되고, 데이터의 삽입과 삭제가 적을 때

연결 리스트

• 장점 : 삽입과 삭제가 용이하다.
• 단점 : 임의 접근이 불가능하여, 처음부터 탐색을 진행해야 한다.
• 용도 : 삽입과 삭제 연산이 잦고, 검색 빈도가 적을 때