자료구조(리스트) - 배열 구조 vs 연결된 구조

1. 배열 구조와 연결된 구조

 리스트는 배열 구조와 연결된 구조로 구현할 수 있습니다.

 

 먼저 배열 구조인 경우 중간에 빈자리가 없어야 하며 반드시 메모리의 연속된 공간에 저장되어야 합니다. 이 점 때문에 원하는 위치의 요소를 빠르게 참조하고 관리할 수 있습니다.

 연결된 구조인 경우는 요소들이 메모리의 여기저기 흩어져서 저장이 됩니다. 이 요소들을 관리하기 위해 링크를 사용해야 한다. 자료들을 링크를 통해 일렬로 나열할 수 있는 연결된 구조를 연결리스트라고 합니다. 연결된 구조에는 노드라는 것이 있는데 이 노드에 데이터와 링크가 저장됩니다.

배열 구조와 연결된 구조

---

2. 비교해 보기

 연결된 구조와 배열 구조는 여러 차이점이 있습니다. 그 점을 비교해 봅시다.

 

1. 리스트 요소들에 대한 접근

 배열 구조는 모든 요소듸 크기가 같고 연속된 메모리 공간에 있습니다. 요소의 위치는 어떻게 찾을까요? 배열 구조의 경우에는 어떠한 한 주소는 한 요소의 크기에 원하는 위치를 곱해 시작주소에 대해주면 바로 구해줍니다.

 다만 연결된 구조의 경우에는 찾기 위해선 좀 더 복잡합니다. 요소를 찾기 위해서 어쩔수 없이 시작 노드 부터 계속 링크를 따라 이동해야 합니다. 작은 값이라면 금방 끝나겠지만 큰 값이라면 오래 걸릴 수 밖에 없습니다.

 

2. 리스트의 용량

 배열 구조는 기본적으로 용량이 고정 됩니다. 그러므로 한번 선언한 배열은 거기서 늘리거나 줄이는 것이 어렵습니다. 배열을 무턱대고 할당하면 메모리 낭비가 심해집니다. 반면에 너무 적게 할당하면 빨리 포화상태가 되어 새로운 요소를 넣지 못할 수 있다.

 반면에 연결된 구조 같은 경우에는 용량이 자유롭습니다. 필요할 때 필요한 크기만큼 새로 할당해서 사용할 수 있습니다. 그러므로 메모리를 효율적으로 쓸 수 있습니다.

 

3. 리스트 삼입 연산

 배열 구조는 요소 하나를 삼입할 때 그 위치 이후에 있는 모든 요소들 한칸씩 뒤로 밀려납니다. 즉 배열 구조는 많은 요소의 이동이 필요합니다.

 그러나 연결된 구조는 삼입할 위치를 안다면 그냥 추가하면 됩니다. 무슨 말이냐면 삼입을 한다고 해서 배열 구조처럼 다른 요소들이 영향을 받지 않는다는 것입니다. 그리고 링크만 수정하면 되는 것이죠. 결국 삼입할 위치의 바로 앞의 노드를 알고 있다면 배열 구조보다 더욱 효율적인 삼입을 할 수 있습니다.

 

3. 리스트 삭제 연산

 삭제 연산도 삼입 연산의 원리가 같습니다. 배열 구조는 삭제할 요소 뒤에 있는 모든 요소들이 한칸씩 앞으로 당겨집니다. 하지만 연결된 구조의 경우에는 요소를 삼입할 때에, 삭제한 요소 앞에 있는 노드의 링크만 수정하면 되고 다른 것을 영향을 받지 않습니다.