Array, Linked List

Array와 Linked List의 큰 차이점은 메모리에 저장되는 방식과 이에 따른 조회 및 삭제의 연산속도이다.   

Array란?

Array는 연관된 데이터를 메모리상에 연속적이며 순차적으로 미리 할당된 크기만큼 저장하는 자료구조이다.

 

Array의 특징

• 고정된 저장 공간
• 순차적인 데이터 저장

Array의 장점은 조회와 마지막 인덱스에 추가가 빠르다.

따라서 조회를 자주 해야되는 작업에서는 Array 자료구조를 많이 사용한다.

 

 

Linked List란?

Linked List는 Node라는 구조체로 이루어져 있다. Node는 데이터 값과 다음 Node의 주소를 저장한다.

Linked List는 물리적인 메모리에서는 비연속적으로 저장되지만 Linked List를 구성하는 각각의 노드가 다음 노드의 주소를 가리킴으로써 논리적인 연속성을 가진 자료구조이다.

Linked List는 데이터가 추가 되는 시점에 메모리를 할당하기 때문에 메모리를 조금 더 효율적으로 사용할 수 있다는 장점이 있다.

 

결국에 next address로 주소를 가리키고 있기 때문에 삽입시 다음 주소만 알고 있으면 됩니다.

삭제시에도 next address만 바꿔주면 됩니다.

 

 

Array 와 Linked List의 차이  

 

Array는 메모리 상에서 연속적으로 데이터를 저장하는 자료구조이다.

Linked List는 메모리상에서 비 연속적이지만 각 원소마다 다음 주소값을 알고있어 논리적인 연속성을 유지한다.

그렇기 때문에 조회, 삽입, 삭제 시 걸리는 시간차이가 있습니다.

데이터의 크기를 알고 있고 조회를 많이 한다면 Array를 사용하고 데이터의 크기를 알 수 없고 삽입, 삭제가 많다면

Linked List를 사용하는것이 좋습니다.