이 글은 <홍정모의 따라하며 배우는 C언어 (부록)>을 공부하고 정리한 내용입니다. 링크
Array (배열) : 연속된 메모리 공간에 1차원으로 쭉 나열된 같은 크기의 데이터
Linked List (연결 리스트) : 한 데이터가 임의의 공간에 위치한 다음 데이터의 위치를 가리킴.
Array는 연속된 메모리 공간에 같은 크기의 데이터가 나열되어 있으므로, 포인터 연산을 통해 임의접근이 가능하다. 또한, 캐쉬를 사용할 경우 Array는 더 빠르게 처리가 가능하다.
그러나 연속된 메모리 공간에 나열되어 있다는 것 때문에, 중간에 데이터를 추가하기 위해서는 전체 데이터를 복사하고 옮겨야 한다. 따라서, 삽입/삭제 등의 작업이 상당히 느리다. 또한, 이때 복사를 위해 비효율적으로 메모리가 사용된다.
Linked List는 배열의 장/단점을 완전히 반대로 가지고 있다.
Linked List는 임의의 공간에 데이터가 존재하고, 다음 데이터의 위치를 포인터로 가지고 있다. 이때, 첫 데이터는 Head Pointer로 가리킨다.
Linked List는 이러한 특성때문에, 가리키는 위치만 바꿔주면 중간에 데이터를 삽입하고 삭제하기 아주 쉽다. 또한, 필요한 만큼 노드를 동적으로 관리할 수 있고, 데이터 삽입과 삭제에 포인터 값만 바꿔주면 되기 때문에 메모리 사용도 효율적이다.
그러나, 특정 데이터를 읽어내기 위해서는 첫 데이터부터 순차적으로 읽어들여야 한다는 단점이 있다. 또한, 각 노드마다 포인터 크기만큼 데이터가 필요하다는 단점이 있으나, 이는 포인터에 아주 큰 데이터를 다룰 경우에는 무시할만한 수준이 된다.
