[자료구조]Array와 Linked List의 차이

Array

1. 연속적인 공간에 요소를 저장한다(인덱스로 한 번에 접근 가능)
2. 배열 크기가 고정되어 있다.
3. 특정 인덱스에 접근하는데 상수시간이 걸린다.
4. 원소를 중간에 삽입, 삭제하면 비용이 많이 든다(인덱스에 맞게 원소들을 이동시켜야 하기 때문)

Array 메모리 구조

일열로 메모리에 저장되어 검색에 유리하다

Linked List

1. 각 요소가 메모리 임의의 위치에 배치될 수 있으며, 각 요소는 다음 요소를 가리키는 링크로 연결이 된다.
2. 배열 크기를 동적으로 조정할 수 있다.
3. 특정 인덱스를 찾으려면 처음부터 순차적으로 탐색해야 한다. (길이가 길수록 오래 걸림)
4. 원소 중간에 삽입, 삭제 비용이 적다 (데이터를 넣고 앞뒤 링크만 연결하면 된다. 단 특정 인덱스를 찾을 때 시간이 소요된다.)

Linkend List

 

다음 요소의 메모리 주소를 통해 리스트를 만든다.