[자료구조] Linked List(연결 리스트) 와 Array(배열)의 차이

 

크기

• Array 의 size는 반드시 array 선언 시점에 지정되어있어야 합니다.
• LinkedList 의 size는 다양할 수 있습니다.
  • node 들이 추가될 때 runtime 시점에서 LinkedList size 는 커질 수 있기 때문입니다.

메모리 할당

• Array 에서, Memory 는 Array 가 선언되자 마자 Compile time 에 할당되어집니다.
  • 이것을 Static Memory Allocation 이라고 부릅니다.
  • Stack section 에 memory 할당이 이루어집니다.
• LinkedList 에서, Memory 는 새로운 node 가 추가될 때 runtime 에 할당되어집니다.
  • 이것을 Dynamic Memory Allocation 이라고 부릅니다.
  • Heap section 에 memory 할당이 이루어집니다.

요소 접근

• Array 는 Random Access 를 지원합니다.
  • element 들을 index 를 통해 직접적으로 접근할 수 있습니다.
    • ex) arr[0], arr[1]
  • 따라서, 특정 element 에 접근하는 시간 복잡도는 O(1) 입니다.
• LinkedList 는 Sequential Access 를 지원합니다.
  • 어떤 element 에 접근할 때, 처음 부터 순차적으로 접근하면서 찾아야 합니다.
  • 따라서, 특정 element 에 접근할 때의 시간 복잡도는 O(N) 입니다.

삽입 및 삭제

• Array
  • 인덱스로 접근 후 삽입 및 삭제 O(1) + 전체 배열 요소를 1씩 Shift O(N)
• LinkedList
  • 삽입하려는 위치 접근 후 삽입 및 삭제 O(N)
  • 만약, 맨 앞과 뒤에 삽입 및 삭제한다면 O(1)

결론

• 데이터 접근이 주 업무일 경우 → Array
• 데이터 수정이 주 업무일 경우 → Linked List

•