[자료구조] 연결 리스트와 배열 비교

배열

선형 리스트는 1차원 배열이나 연결 리스트로 표현할 수 있다. 배열을 사용할 경우 리스트 요소들의 순서를 배열의 index를 이용해 나타낼 수 있다. 이 방법은 요소마다 링크를 저장할 필요 없이 값만 저장해주면 되므로 연결 리스트보다 간단하다는 장점이 있다. 문제는 데이터 삭제·추가시 삭제되거나 추가되는 원소 뒤의 모든 원소들의 자리를 이동해주어야 한다는 점이다. 이것은 성능 면에서 비효율적이다. 따라서 데이터의 삭제나 추가가 빈번할 것으로 예상된다면 배열을 사용하기보다 연결 리스트를 사용하는 편이 낫다.

연결 리스트

연결 리스트는 요소간의 순서 관계를 링크 필드를 통해 표현하며 해당 노드 다음에 올 노드의 주소를 저장하는 단일 연결 리스트와, 선행 노드 후행 노드 모두의 주소를 저장하는 이중 연결 리스트로 나뉜다. 배열에 비해 저장해야 하는 데이터의 양이 더 많다는 점이 단점이지만 데이터 삽입·삭제 시 그 데이터의 바로 앞과 뒤의 데이터의 주소만 수정해주면 되므로 데이터 삽입·삭제가 빈번할 때 훨씬 효율적이다.