[C] 배열(array)과 연결리스트(linked list)

배열과 연결리스트의 차이에대해 알아보겠습니다.

두 자료구조 모두 데이터를 나열한다는 점에서는 거의 비슷합니다.
그러나 두 자료구조는 엄연히 다르기 때문에 아래의 내용을 참고하셔서 사용 목적에 부합하는 것을 사용하시면됩니다.

1. 배열

배열은 데이터를 입력하게되면 순차적으로 입력이 되고, 물리적 주소 또한 순차적입니다.
배열의 크기는 처음 결정이 되고, 변경이 불가능합니다.
크기가 고정이고, 인덱스를 가지고 있어 원하는 곳에 접근, 검색이 쉽고, 속도가 빠릅니다.
그러나 배열의 특성상 삽입/삭제는 매우 불편합니다.
배열 중간에 값을 넣는다면, 그 뒤에 있는 모든 값들을 이동시켜야되고, 배열이 꽉 차있을 경우, 메모리를 재할당하거나, 최악의 경우는 삽입이 불가능합니다.
즉, 데이터의 이동(복사)가 매우 자주 일어납니다.

 

 

 

 

2. 연결리스트

데이터를 입력하더라도, 연결리스트의 물리적인 주소는 순차적이지 않습니다.
언제든지 메모리 할당/해제를 하여 크기를 변경할 수 있습니다.
배열이 인덱스를 가지고 있다면, 연결리스트는 위치를 기억하고 있습니다.
데이터에 접근을 하려면 각각의 연결되어 있는 위치들을 따라서 접근을 하기때문에 배열에 비해서 속도는 느립니다.
그러나 삽입/삭제시에는 리스트의 위치만 바꿔주면 되기 때문에 속도가 빠르고, 용이합니다.

표로 간단히 정리해보겠습니다.

 

 

오늘 포스팅은 여기까지입니다.