정의
연결 리스트는 일정한
순서를 가지는 데이터
항목들을 표현하는
방법중의 하나이다.
배열과 같은 순차적
표현 방법과는 달리
데이터 항목들의 논리적인
순서만 유지되고 기억장소
내에서는 각 항목들의
임의의 위치를 가지도록
하는 자료구조이다.
구조
연결 리스트에서는 각 데이터 항목들이 기억장소내의 어떤 위치에 어떤 항목이 있는 지를
표시해 주어야 한다. 이를 위해 데이터 항목에는 값뿐만 아니라 다음 항목의 위치 정보도
함께 저장해둔다. 위치정보의 저장에는 포인터가 사용된다.
연결 리스트에서의 포인터
연결 리스트에서 포인터는 각 항목의 다음 순서인 항목이나 앞 순서인 항목의 위치를
가르키는 지시자이다. 연결 리스트의 마지막 노드에는 다음 순서인 항목이 없고,
첫번째 노드에는 이전 순서인 항목이 없으므로 이들 포인터는 null로 해주어야 한다.
포인터는 연결 리스트의 핵심이다. 연결 리스트에서 공통적인 사항은 데이터 항목 간의
결합이 데이터 항목 자체 내에 포함되어 있는 정보에 의해 포인터의 형식으로 정의된다는
것이다. 이런 사실은 데이터 항목 간의 결합이 배열의 배치와 저장을 기반으로 하는 배열과
링크드 리스트를 분명히 구분하는 기준이다.
위의 그림에서 입력자료는 4칸의 분량인데, 저장장치에 연속된 공간은 최고 3칸밖에 없다.
이럴 경우 배열로는 입력자료를 수용하지 못한다. 그러나 연결리스트를 이용하면 연속되지
않은 빈 공간들을 효율적으로 사용할 수 있다. 다음 그림을 보자.
링크를 통해 데이터의 연결성이 보장된다.
배열과 비교하여 또다른 장점도 있다.
항상 정렬 상태가 유지되어야만 할 어떠한 배열이 있다고 하자.
새 값이 중간에 들어가야 할 경우, 배열은 다음의 모든 데이터를 뒤로 한칸씩 밀어야만 한다.
막대한 낭비가 아닐 수 없다. 소규모의 정보를 다룰 때는 사실 별로 문제가 되지 않을 것이다.
하지만 대용량의 정보를 다룰 때는 문제가 매우 심각해진다. 정부에서 국민의
주민등록정보를 배열로 저장했다고 치자. 누군가가 태어나고 죽을 때마다 움직여야 할
배열의 수는 천문학적일 것이다. 하드는 쓸데없는 자료이동에 대부분의 시간을 소모할
것이고, 막상 데이터를 읽으려면 많은 시간을 기다려야 할 것이고 공무원의 흰머리만
늘어날 것이다. 따라서 이러한 것은 연결리스트를 이용하는 것이 훨씬 낫다.
(그러나 앞으로 배우게 될 더 나은 자료구조들이 실제로는 이 일에 더 적합하다.)
그러나 단점도 있다. 이러한 링크는 실제적으로 다음 번 저장장소의 주소값인데,
그 값을 저장하기 위해 추가로 저장장소가 필요하게 된다.
따라서 본연의 데이터 외에 추가로 Overhead가 발생한다.
연결 리스트의 효율 계산
각 노드는 사용자 데이터와 다음 노드를 가리키는 포인터로 이루어진다.
이 때 효율성을 따져 보아야 한다. 예를 들어 어떤 환경에서 이 포인터가 4 바이트를
차지한다면 데이터는 4보다 훨씬 큰 용량이어야 한다. 예를 들어 데이터의 크기가
2 바이트라면 하나의 노드에 필요한 공간은 최소 6 바이트가 될 것이고,
실제 10 바이트를 저장하기 위해서는 10 / 2 = 5 개의 노드가 필요할 것이며,
이는 메모리 공간을 최소 5 * (2 + 4) = 40 바이트를 필요로 한다.
생각해 볼 필요도 없이 10 바이트를 저장하기 위해 40 바이트를 쓴다는 것은
메모리의 낭비일 것이다.
낭비되는 공간을 퍼센트로 나타내면 30 / 40 * 100 = 75(%)가 된다.
따라서 한 노드에 더 많은 데이터를 저장하여 이러한 손실을 상대적으로 줄일 수 있다.
예를 들어 한 노드에 40 바이트 크기의 데이터를 저장한다면
80 바이트를 저장하기 위한 노드의 개수는 80 / 40 = 2가 될 것이고,
필요한 메모리 공간은 최소 2 * (40 + 4) = 88이 된다.
즉 80 바이트를 저장하기 위해 88 바이트가 필요한 셈이므로 낭비되는 공간은
8 / 88 * 100 = 9(%) 정도이다.
그러나 여기에서는 리스트 구현 방법에 중점을 두고 설명할 것이기 때문에
이러한 효율성은 무시할 것이다.
단일 연결 리스트
선형리스트에서 발생하게 되는 원소들의 이동문제를 해결해주는 방법은 리스트를
구성하는 연속된 순서의 원소들이 기억장소내에서 어느곳에나 저장 가능하도록
원소들의 위치와 무관하게 원소들을 연결하여 표현하는 방법이다.
연결리스트에서는 원소들의 값이외에 포인터값이 포함되므로
리스트의 한원소의 노드(node)는 원소값을 저장하는 자료(data)부분과
다음 원소를 지적하는 포인터값을 저장 하는 링크(link) 부분으로 구성된다.
환형 연결 리스트
단일 연결 리스트에서는 리스트의 마지막 노드의 링크 값이 NULL 이었지만,
환형 연결 리스트(circular linked list)는 마지막 노드의 링크의 링크 값이 NULL 이 아닌
리스트의 첫 번째 원소의 주소를 가리키도록 하는 구조로 되어 있다.
환형 연결 리스트에서는 노드의 시작과 끝을 구별하지 않음으로써
마지막 노드와 처음 노드가 연결되어 있음으로 임의의 노드에서
다른 모든 노드로의 접근이 가능하여 임의 노드의 검색이 가능하게 된다.
단순 연결 리스트의 경우 정보가 끊어지면 그 다음은 찾을 수가 없는데
환형 연결 리스트는 그것을 극복할 수 있다.
이중 연결 리스트
단일 연결 리스트(single linked list)와 환형 연결 리스트(circular linked list)는
각 노드에 다음 노드를 가리키는 한 개의 링크 필드만을 사용하기 때문에
특정한 노드를 검색하거나, 삽입 또는 삭제를 할 경우 한 쪽 방향으로만 해당 노드의 위치를
찾을 수 있는 구조이다.
그러나 임의의 노드를 찾을 때 양쪽 방향으로 해당 노드를 검색하면 쉽게 찾을 수 있다.
그러므로 이중 연결 리스트(double linked list)는 노드의 선행 노드를 가리키는
좌링크(LLINK), 자료(DATA)필드, 후행 노드를 가리키는 우링크(RLINK)의
세 개 영역으로 각 노드를 구분하여 양방향으로 특정 노드를 검색할 수 있도록 한 구조이다.
이중 연결 노드 삽입 알고리즘
데이터 항목 B와 D사이에 새로운 데이터 항목 C를 삽입하는 과정은 다음과 같다.
- 새로운 노드를 생성한 후, 생성된 노드에 데이터 항목 C를 대입한다. 이 경우 데이터 항목 C를 저장한 노드를 가리키는 것은 Z이다.
- B노드의 RLINK 값을 Z의 RLINK에 저장한다. 여기서 B 노드의 주소를 X가 가지고 있으므로, B노드의 RLINK는 X의 RLINK가 될 수 있다.
- B노드의 주소, 즉 X의 값을 Z의 LLINK에 대입한다.
- X의 RLINK가 가리키는 노드인 D 노드의 LLINK에 Z의 값을 대입한다.
- X의 RLINK에 Z의 값을 저장한다.
이중 연결 노드 삭제 알고리즘
이중 연결 리스트를 구성하는 임의의 노드 X를 삭제하는 알고리즘 DELETE는 다음과 같다.
- B노드의 RLINK에 C노드의 RLINK 값을 대입한다. 여기서 B 노드의 RLINK 값은 C노드를 가리키는 X의 LLINK가 가리키는 노드(B노드)의 RLINK 값이다.
- D노드의 LLINK에 C노드의 LLINK 값을 대입한다. 여기서 D노드의 LLINK 값은 C노드를 가리키는 X의 RLINK가 가리키는 노드(D노드)의 LLINK 값이다.
- X가 가리키고 있는 C노드를 가용 기억공간으로 되돌린다. 즉 C노드는 이중 연결 리스트에서 삭제된다.
이중 환형 연결 리스트
이중 환형 연결 리스트(doubly circular linked list)는 이중 연결 리스트와
원형 연결 리스트를 혼합한 형태이다. 즉, 각 노드가 선행 노드와 후속 노드를
가리키기 위한 두 개의 포인터를 가지고 있으며,
마지막 노드의 RLINK는 처음 노드의 위치를 가리킨다.
또한 처음 노드의 LLINK는 마지막 노드의 위치를 가리키는 형태를 취한다.
이중 환형 연결 리스트는 어떠한 노드도 널 링크를 갖지 않는다는 특징이 있다.
출처 : http://internet512.chonbuk.ac.kr
'Financial Tech.' 카테고리의 다른 글
| 다음 아고라 미네르바 추천도서 및 미디어 참고자료 (0) | 2008/11/01 |
|---|---|
| 펀드 관련 용어 잔고수량 평가금액 (0) | 2008/01/22 |
| Doxygen 소개와 설치하기 (0) | 2007/12/13 |
| ‘분양가 상한’ 파주신도시 1순위 청약 미달 (0) | 2007/11/30 |
| 링크드 리스트 (0) | 2007/11/22 |
| 용인 흥덕지구 향후 전망.. (0) | 2007/11/09 |
| 왜 신생기업은 망하는가? 성공적인 비즈니스를 위한 전문가의 조언 (0) | 2007/10/02 |
| '72법칙'으로 수익률 따져보자 (0) | 2007/09/30 |
| 투자는 전쟁이다 (0) | 2007/09/21 |
| 청약자들의 위험한 발상 (0) | 2007/09/21 |
| 투자성공의 기본은 투자공부다 (0) | 2007/09/21 |
댓글을 달아 주세요