ArrayVSLinkedList.md

Array vs Linked List

Array

순차적으로 데이터를 저장하는 자료구조

• 인덱스를 통해 해당 원소에 접근할 수 있다. (O(1))
  • 즉 random access가 가능하다.
• 고정된 크기를 갖는 같은 자료형의 원소들이 연속적인 형태로 구성된 자료구조
  • cache hit rate가 높다.
  • 배열을 생성하려면 메모리 상에 연속한 구간을 할당해야해서 할당에 제약이 걸릴 수 있다.
  • 연속된 메모리 상에 원소들이 존재하므로 처음 배열을 선언한 크기만큼 데이터를 저장하지 않는다면 메모리 낭비가 발생한다.
• Array의 중간 요소를 삭제/삽입 하는 경우, 뒤에 있는 데이터를 삭제/삽입 한 요소 수 만큼 shift해줘야 하는 비용이 발생한다. (O(n))

Dynamic Array 문제

데이터를 새로 추가할 때 Resizing 문제(메모리의 사이즈를 다시 조정하는 문제)가 생길 수 있다. - 기존의 배열은 그대로 두고 - 새로운 길이로 지정된 배열을 따로 할당 후 - 순차적으로 데이터의 복사를 진행하고 - 기존의 배열을 삭제

List

순서가 있는 데이터의 모임이다. 다른 말로는 시퀀스(sequence)라고도 부른다.

ArrayList

배열을 이용해서 리스트를 구현한 것을 의미한다. 장점: 내부적으로 배열을 사용하기 때문에 인덱스를 이용해서 접근하는 것이 빠르다. 단점: 데이터의 추가와 삭제가 느리다. + Dynamic Array 문제

LinkedList

배열은 미리 특정한 연결된 공간을 확보하고 데이터를 쓰고 있는 자료구조이고, 링크드 리스트는 필요할 때 마다 데이터를 추가할 수 있는 구조이다. 배열의 단점을 극복한 자료구조가 링크드 리스트라고 볼 수 있다.

• 각 노드는 연속된 공간에 저장되어 있지 않고 메모리의 여러 부분에 분포되어 있다.
  • 순차성을 보장하지 못하기 때문에 spacial locality 보장이 되지 않아 cache hit가 어렵다.
• 각 노드에 다음 노드의 주소를 저장함으로써 다음 노드를 탐색할 수 있다.
• 동적으로 메모리 사용이 가능하다.
• 순차 접근 방식을 사용하기 때문에 어떤 한 데이터를 찾기 위해서는 처음부터 순차적으로 탐색해야 한다. (O(n))
• 삽입/삭제: O(1)
• 원하는 노드에 접근 + 삽입/삭제: O(n)

Array vs LinkedList

- Array는 Random Access를 지원한다. 요소들을 인덱스를 통해 직접 접근할 수 있다. 따라서 특정 요소에 접근하는 시간 복잡도는 O(1)이다. 반면 Linkedlist는 Sequential Access를 지원한다. 어떤 요소를 접근할 때 순차적으로 검색하며 찾아야 한다. 따라서 특정 요소에 접근할 때 시간 복잡도는 O(N)이다.

• 저장 방식도 배열에서 요소들은 인접한 메모리 위치에 연이어 저장된다. 반면 Linkedlist에서는 새로운 요소에 할당된 메모리 위치 주소가 linkedlist의 이전 요소에 저장된다.

• 배열에서 삽입과 삭제는 O(N)이 소요되지만, Linkedlist에서 삽입과 삭제는 O(1)이 소요된다.

• 배열에서 메모리는 선언 시 컴파일 타임에 할당이 된다. (정적 메모리 할당) 반면 Linkedlist에서는 새로운 요소가 추가될 때 런타임에 메모리를 할당한다. (동적 메모리 할당)

• 배열은 Stack 섹션에 메모리 할당이 이루어진다. 반면 Linkedlist는 Heap 섹션에 메모리 할당이 이루어진다.