[자료구조] linked list와 array의 차이

요소 접근 (탐색 및 조회)

• array는 random access를 지원한다.
  - random access란?
  : O(1)의 시간에 인덱스를 통해 모든 배열 요소에 액세스 할 수 있는 것을 의미한다.
  
  따라서 배열은 특정 배열 요소에 접근하는 시간 복잡도이 O(1)이다.
• linked list는 sequential access를 지원한다.
  - 어떤 요소에 접근할 때, 처음부터 순차적으로 접근하며 찾아야 한다.
  - 특정 요소에 접근할 때의 시간 복잡도는 O(n)이 된다.

저장 방식

• array에서 요소들은, 인접한 memory의 위치에 저장된다.
• linked list에서 새로운 요소들은, 각각 memory 어딘가에 저장된다.
  새로운 요소의 memory 위치 주소는 linked list의 이전 node에 저장된다.

삽입

• array
  인덱스로 접근 후 삽입 : O(1)
  삽입 후 전체적으로 shift : O(n)
• linked list
  삽입하려는 위치에 접근 후 중간 삽입 : O(n)
  처음 or 마지막 삽입 : O(1)

삭제

• array
  인덱스로 접근 후 삭제 : O(1)
  삭제 후 전체적으로 shift : O(n)
• linked list
  삭제하려는 데이터에 접근 후 삭제 : O(n)
  처음 or 마지막 삭제 : O(1)

메모리 할당

• array에서, memory는 array가 선언되자 마자 compile time에 할당된다.
  - compile time이란?
  : 컴파일 과정을 통해 컴퓨터가 인식할 수 있는 기계어 코드로 변환되어 실행 가능한 프로그램이 되는 과정
  
  이것을 static memory allocation이라고 한다.
  - static memory allocation이란?
  : 프로그램이 수행되기 전에 미리 메모리를 할당하는 것. 특징으로 변수들의 life cycle이 프로그램의 시작과 종료와 일치하는 것이다.
• linked list에서, memory는 새로운 node가 추가될 때 runtime에 할당된다.
  이것을 dynamic memory allocation이라고 한다.
  
  - dynamic memory allocation이란?
  : 프로그램의 실행 시간 동안 사용할 메모리 공간을 할당하는 것. 입력되는 데이터에 맞게 기억 공간을 확보하는 것.

종류

• array는 1, 2, 3차원이 있다.
• linked list는 Linear(singly), dubly, circular linked list가 있다.

크기

• array의 size는 반드시 배열의 선언 시점에 지정되어있어야 한다.
  하지만 js에서 배열은 배열이 아니다..?
• linked list의 size는 다양할 수 있다.
  node들이 추가될 때 runtime 시점에서 linked list size는 커질 수 있기 때문이다.

메모리 할당 Section

• array는 stack section에 memory 할당이 이루어진다.
  stack section이란?
  : 함수 호출 시 생성되는 지역 변수와 매개 변수가 저장되는 영역, 함수 호출이 완료되면 사라진다.
• linked list는 heap section에 memory 할당이 이루어진다.
  필요에 의해 동적으로 메모리를 할당할 때 사용한다.

출처

https://wooono.tistory.com/281

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