[자료구조]배열과 연결리스트의 차이

배열

• 정적인 자료구조
• 이미 지정된 크기의 연속된 메모리 주소를 할당받는다.
  - 따라서 크기 수정이 불가능하다.
  • 탐색을 하는데 있어, 인덱스를 가지고 있기 때문에 O(1)의 시간복잡도를 가진다.
  • 추가 및 삭제의 경우, 맨 뒤의 데이터가 아니라면 기존 데이터들을 옮겨야 하기 때문에 O(n)의 시간복잡도를 가진다.

링크드 리스트(연결 리스트)

• 동적인 자료구조
• 노드라는 공간에 저장한 데이터와 다음 값의 메모리 주소를 가지고있다.
  - 따라서 데이터를 추가하고 삭제하는 연산이 자유롭다.
  • 탐색을 하는데 있어, 앞에서부터 순차적으로 진행할 수 밖에 없어 O(n)의 시간복잡도를 가진다.
    - 데이터를 추가 삭제하는데, 다음 값의 메모리 주소만 바꾸면 되기 때문에 O(1)의 시간 복잡도를 가진다.
    • 하지만 추가 및 삭제하려는 위치가 맨 앞이 아니라면, 변경되는 곳까지 탐색을 해야하므로 O(n)의 시간복잡도를 가진다.