Array VS Linked List

리스트 : 어떤 순서가 있는 데이터의 집합을 의미한다.

 

Array(배열)

 

특징

• Array는 배열로 연속적인 공간에 순차적으로 데이터를 저장할 수 있는 자료구조이다.
• 데이터를 입력할 때 인덱스 순서대로 입력이 되고, 메모리의 저장 위치도 인접한 위치에 저장이 된다.
• 데이터에 접근할 때는 인덱스 번호를 통해 접근하기 때문에 데이터의 양이 얼마나 많든 O(1)의 시간 복잡도로 탐색이 가능하다.
• 특정 인덱스의 데이터 삽입과 삭제에 있어서는 반드시 기존 데이터들의 이동을 필요로 하기에 O(n)의 시간이 소요된다. 
• 배열을 정적으로 할당한 경우
  • 배열의 크기는 Compile time에 할당되기 때문에 한번 사이즈가 정해지면 변경이 불가능하다.
  • 배열은 메모리의 Stack 영역에 저장된다.
• 배열을 동적으로 할당한 경우
  • runtime에 배열의 크기를 정할 수 있다.
  • 메모리의 Heap영역에 저장되기 때문에 사용이 끝나면 메모리 손실이 나지 않도록 해제 시켜주어야 한다.

 

Linked List

 

단방향 연결리스트

양방향 연결리스트

특징

• 비연속적인 공간에 순서대로 데이터를 저장한다.
• 첫번째 노드를 Head 마지막 노드를 Tail이라고 부른다.
• 크기가 정해져 있지 않고 배열처럼 메모리 낭비가 없다.
• 데이터들은 동적할당으로 Heap영역에 저장된다.
• 데이터를 추가하거나 삭제할 때 메모리의 할당,해제가 일어난다.
• 데이터를 추가하거나 삭제하기가 쉽다.(O(1)의 시간 복잡도)
• 데이터의 크기 외에 다음 노드를 가리키는 포인터의 정보도 필요해 배열보다 메모리 사용량이 크다.
• 데이터 탐색이 오래 걸린다.(O(n)의 시간 복잡도)

데이터 추가

 

데이터 삭제

 

결론

데이터의 추가와 삭제가 많을 경우 Linked List를 이용하는 것이 효율적이며, 데이터 탐색의 경우에는 Array가 효율적이다.