연결 리스트의 구조
연결 리스트에서는 각 데이터 항목들이 기억장소내의 어떤 위치에 어떤 항목이 있는 지를 표시해 주어야 한다. 이를 위해 데이터 항목에는 값뿐만 아니라 다음 항목의 위치 정보도 함께 저장해둔다. 위치정보의 저장에는 포인터가 사용된다.
연결 리스트에서의 포인터
연결 리스트에서 포인터는 각 항목의 다음 순서인 항목이나 앞 순서인 항목의 위치를 가르키는 지시자이다. 연결 리스트의 마지막 노드에는 다음 순서인 항목이 없고, 첫번째 노드에는 이전 순서인 항목이 없으므로 이들 포인터는 null로 해주어야 한다.
포인터는 연결 리스트의 핵심이다. 연결 리스트에서 공통적인 사항은 데이터 항목 간의 결합이 데이터 항목 자체 내에 포함되어 있는 정보에 의해 포인터의 형식으로 정의된다는 것이다. 이런 사실은 데이터 항목 간의 결합이 배열의 배치와 저장을 기반으로 하는 배열과 링크드 리스트를 분명히 구분하는 기준이다.
배열과 연결 리스트의 가장 큰 차이점은 포인터 이다. 배열은 자신 옆에 있는 데이터로 순차적 접근 하지만, 연결 리스트는 자신이 가르키는 데이터(포인트)로 순차 접근한다.
옆의 그림에서 입력자료는 4칸의 분량인데, 저장장치에 연속된 공간은 최고 3칸밖에 없다. 이럴 경우 배열로는 입력자료를 수용하지 못한다. 그러나 연결리스트를 이용하면 연속되지 않은 빈 공간들을 효율적으로 사용할 수 있다. 다음 그림을 보자.
모든 입력자료는 자신의 데이터와 다음 데이터가 있을 위치를 가르키고 있다. 그렇기 때문에 배열과 다르게 일렬로 데이터가 저장될 필요가 없고 공간의 효율이 좋다.
배열과 비교하여 또다른 장점도 있다.
항상 정렬 상태가 유지되어야만 할 어떠한 배열이 있다고 하자. 새 값이 중간에 들어가야 할 경우, 배열은 다음의 모든 데이터를 뒤로 한칸씩 밀어야만 한다. 막대한 낭비가 아닐 수 없다. 소규모의 정보를 다룰 때는 사실 별로 문제가 되지 않을 것이다. 하지만 대용량의 정보를 다룰 때는 문제가 매우 심각해진다.
그러나 단점도 있다. 이러한 링크는 실제적으로 다음 번 저장장소의 주소값인데, 그 값을 저장하기 위해 추가로 저장장소가 필요하게 된다. 따라서 본연의 데이터 외에 추가로 Overhead가 발생한다.정부에서 국민의 주민등록정보를 배열로 저장했다고 치자. 누군가가 태어나고 죽을 때마다 움직여야 할 배열의 수는 천문학적일 것이다. 하드는 쓸데없는 자료이동에 대부분의 시간을 소모할 것이고, 막상 데이터를 읽으려면 많은 시간을 기다려야 할 것이고 공무원의 흰머리만 늘어날 것이다.따라서 이러한 것은 연결리스트를 이용하는 것이 훨씬 낫다. (그러나 앞으로 배우게 될 더 나은 자료구조들이 실제로는 이 일에 더 적합하다.)
※ 앞의 예제에서의 핵심은 데이터의 추가 또는 삭제가 빈번히 일어날 수 있다는 것이다.앞의 예제 말고도 다양한 상황이 존재 할 수 있다. 어떤 경우가 있을지 한번씩 생각해보자.
연결리스트의 효율 계산
대학교 다닐때 처음으로 자료구조를 배우고 약 3년만에 다시 복습하는 마음가짐으로 내 블로그에 정리한다. 이자료는 http://internet512.chonbuk.ac.kr/datastructure/ 에서 구했고 추가로 도움이 될만한 정보를 정리할 생각이다.
'algorithm' 카테고리의 다른 글
| 정렬알고리즘(Sort algorithm source) (1) | 2008.02.18 |
|---|---|
| 대학시절에 내 머리를 꽝! 때린 기막힌 이론이 있었다. (1) | 2008.01.21 |
| 자료구조 - 스택(Stack) (1) | 2007.12.17 |
| 자료구조의 종류 (0) | 2007.12.17 |
| 자료구조의 구성 (0) | 2007.12.17 |