[자료구조] Array와 Linked List

1. Array

• 저장 방식 : element들은 인접한 Memory 위치에 저장된다.
• 종류
  • single dimensional
  • two dimensional
  • multi dimensional
• 크기
  • Array의 size는 반드시 array 선언 시점에 지정되어 있어야 합니다.
• 메모리 할당
  • Array에서, Memory는 Array가 선언되자 마자 Compile time에 할당되어 진다.
    • 이것을 Static Memory Allocation이라고 한다.
    • Stack Section에 memory 할당이 이루어 진다.
• 요소 접근
  • Array는 Random Access를 지원한다.
    
    • element들은 index를 통해 직접적으로 접근가능하다.
    • 따라서, 접근하는 시간 복잡도는 O(1)이다.
• 삽입 및 삭제
  • 인덱스로 접근 후 삽입 및 삭제 O(1) + 전체 배열 요소를 1씩 Shift O(N)

2. Linked List

• 저장 방식 : element들은 Memory 어딘가에 저장된다.
  • 새로운 element 의 memory 위치 주소는, linked list의 이전 node에 저장된다.
• 종류
  • Linear(Singly)
  • Doubly
  • Circular Linked list
• 크기
  • size는 다양할 수 있다. node들이 추가될 때 runtime 시점에서 linkedList size는 커질 수 있다.
• 메모리 할당
  • Memory는 새로운 node가 추가될 때 runtime에 할당되어 진다.
    • 이것을 Dynamic Memory Allocation이라고 부른다
    • Heap Section에 memory 할당이 이루어 진다.
• 요소 접근
  • Array는 Sequential Access를 지원한다.
    
    • 처음부터 순차적으로 접근하면서 찾아야 한다.
    • 따라서 시간 복잡도는 O(N) 이다.
• 삽입 및 삭제
  • 삽입하려는 위치에 접근 후 삽입 및 삭제 O(N)
  • 만약 맨앞과 뒤에 삽입 및 삭제를 한다면 O(1)

3. 결론

• 데이터 접근이 주 업무일 경우 > Array
• 데이터 수정이 주 업무일 경우 > Linked List
• 전반적으로 보면 Linked List가 훨씬 좋아보이지만
• 알고리즘 문제 풀때는 Array가 훨씬 빠르고 편리하다.
• 따라서 배열의 크기를 MAX로 초반에 잡는다면 Array가 훨씬 더 편리하고 빠르다.
  • Linked LIst는 요소를 삽입, 삭제할 때마다 메모리의 할당, 해제가 일어난다.
  • 이런 작업은 시간복잡도에 포함되지는 않지만, 시스템 콜(System Call)을 사용하는 구문은 시간 소요가 꽤 걸린다.