7. 노드와 포인터
in Study on Data Structure
Overview
데이터에 대한 저급한 표현은 순차 표현과 연결 표현으로 구분할 수 있다.
먼저 연결 데이터 표현에 대해 알아보기 전에 배열을 이용한 순서 리스트의 순차 표현에 대한 특징은 다음과 같다.
순차 표현의 장점은 리스트의 논리적 순서와 저장된 원소의 물리적 순서가 같아 표현이 간단하고 원소의 접근이 빠르다는 것이다.
연속된 메모리에 위치한 원소의 위치를 나타내는 인덱스는 직접 메모리 주소로 변환할 수 있기 때문에 빠른 임의 접근이 가능하다.
반면에 원소들 이 순차적으로 저장되기 때문에 원소의 삽입과 삭제가 어렵고 시간이 많이 걸리는 단점이 있다.
순차 표현에서는 리스트 원소의 순서가 연속적인 물리적 주소로 표현되기 때문에, 원소를 삽입하거나 삭제하기 위해서는 해당 원소의 위치 뒤에 있는 모든 원소를 뒤로 물리거나 앞으로 당겨야 한다.
이런 데이터의 이동은 원소수가 많은 리스트에서는 많은 오버헤드를 일으키게 된다.
또 리스트의 길이(원소의 수)가 임의로 늘어나고 줄어드는 상황에서는 배열의 크기를 미리 결정하기 힘들다.
이로 인해 배열의 오버플로우(overflow)나 과다한 메모리 할당으로 인한 저장 공간의 낭비와 비효율을 가져오기 쉽다.
예를 들어 다음과 같이 알파벳 순서로 된 성씨의 리스트 L이 있다고 하자.
L = (Cho, Kim, Lee, Park, Yoo)
이것을 순차 표현으로 1차원 배열 L[6]에 저장하고 원소 "Han"을 새로 삽입한다고 하면 결과는 다음 그림과 같이 될 것이다.
이 과정을 살펴보면 원소 "Han"은 "Cho" 다음에 삽입되어야 하기 때문에 먼저 "Cho" 다음에 빈 공간을 만들어야 한다.
따라서 "Kim"에서부터 "Yoo"까지를 모두 한 자리씩 뒤로 이동시키는 연산을 수행한 뒤 "Han"을 "Kim"이 있던 자리에 삽입했다.
그 결과로 리스트 L의 길이는 5에서 6으로 늘어났다.
만약 배열 L이 L[5]로 정의되었다면 "Han"을 삽입하려고 할 때 저장공간의 부족으로 오버플로우가 일어났을 것이다.
노드와 포인터
순차 표현에서의 이런 연산 시간과 저장 공간의 문제를 해결할 수 있는 방법으로 비순차 표현(nonsequential representation) 또는 연결 표현(linked representation)이 있다.
이 연결 표현에서는 순차 표현과 달리 원소의 물리적 순서가 리스트의 논리적 순서와 일치할 필요가 없다.
즉, 리스트의 원소는 메모리 어느 곳에 저장되어도 된다.
그러기 위해서는 원소를 저장할 때 그 원소의 다음 원소에 대한 주소도 함께 저장해야 한다.
이런 <원소, 주소>쌍의 저장 구조를 노드(node)라고 한다.
일반적으로 노드는 몇 개의 필드로 구성되는데, 이 필드들은 크게 데이터 필드와 링크 필드로 구분된다.
데이터 필드(data field)는 리스트의 원소(데이터 값)를 저장하는 곳이고 링크 필드(link field)는 포인터(pointer) 즉, 다른 노드의 주소값을 저장하는 곳이다.
이 포인터를 링크(link) 혹은 참조(reference)라고도 하는데, 모두 주소값을 표현한다.
변수 중에는 항상 주소 값만 저장하도록 선언된 것이 있는데 이것을 포인터 변수(pointer variable)라고 하며 링크필드가 이 역할을 한다.
위 그림 (a)는 메모리 위에서의 노드 구조를 보여주고 있다.
노드는 원소 값을 저장하기 위한 데이터 필드와 노드의 주소를 저장할 수 있는 링크 필드로서 각각 여러 개의 메모리 주소 공간을 차지하고 있다.
그러나 이러한 물리적 노드 구조보다는 논리적 노드 구조를 사용하는 것이 편리할 때가 많다.
그림 (b)는 이런 목적을 위해 노드 구조를 논리적으로 간단하게 표현한 것이다.
연결 표현은 바로 이 링크를 이용해 원소의 순서를 유지시켜주기 때문에 실제 원소들이 메모리 어느 곳에 저장되는지 상관할 필요가 없다.
이렇게 실제 주소 값을 무시한 리스트의 논리적 구조는 통상 링크 대신 화살표를 이용한 노드의 열로 표현하고 있다.
연결 리스트
보통 연결 리스트(linked list)라 하면 링크를 이용해 표현한 리스트를 말한다.
앞서 나온 예시의 리스트 L을 연결리스트로 표현하면 위의 그림과 같다.
위 그림에서 리스트 이름 L은 리스트의 첫 번째 노드만 가리키는 포인터 변수로서 실제로 데이터 값 "Cho"가 저장된 노드를 가리키지만, 연결된 리스트 전체를 기리키기도 한다.
따라서 보통 "리스트 L"이라고 하면 위 그림의 전체 리스트를 의미하는 리스트 이름으로 사용되는 것이고, "노드 L"이라고 하면 L이 가리키는 리스트의 노드, 즉 "Cho"가 저장되어 있는 노드를 가리키는 노드 이름으로 사용된다.
이 포스트에서는 편의상 전체를 나타내는 이름으로 사용되는 포인터 변수는 대문자로 시작하며 노드를 나타내는 포인터 변수는 소문자로 시작한다.
여기서 몇 가지 유의해야 할 사항이 있다.
첫째로, 위 그림에서는 링크를 화살표로나타내지만 실제로는 주소 값이 들어있다. 예를 들어 원소 "Cho", "Kim", "Lee", "Park", "Yoo"가 저장된 노드들의 주소를 각각 1000, 1004, 1100, 1110, 1120으로 가정한다면, 각 노드의 링크 필드에는 이 노드들의 주소가 다음 그림과 같이 저장된다.
둘째, 연결 리스트의 마지막 노드는 어떤 노드도 가리키고 있지 않으므로 이런 사실을 명확히 나타내기 위한 링크 값으로 null을 저장한다. 이 null은 어떤 노드도 가리키고 있지 않다는 것을 명시적으로 나타내는 특별 주소 값이다.
셋째, 연결 리스트 전체는 포인터 변수 L로 나타낸다.
실제로 이 포인터 변수 L에는 리스트 첫 번째 노드의 주소 1000이 저장된다.
만일 리스트가 노드를 하나도 가지지 않은 공백 연결 리스트(empty linked list)가 되면 L의 값에 저장된 값은 null이 된다.
이렇게 공백 리스트를 가리키는 포인터를 널 포인터(null pointer)라고 한다.
넷째, 노드의 필드 선택은 점 연산자(. dot operator)를 이용한 점 표기식으로 표현한다.
즉, 리스트 노드를 가리키는 포인터 변수와 그 노드에서 원하는 필드를 점으로 연결하여 표기함으로써 원하는 필드 값을 접근할 수 있다.
예를 들어 L.data 식의 값은 포인터 L이 가리키는 노드의 data 필드 값인 "Cho"가 되고, L.link.data로 표현된 식의 값은 L이 가리키는 노드의 link값이 가리키는 노드의 data 값으로 "Kim"이 된다.
끝으로, 포인터 변수에 대한 연산은 일반적으로 제한되어 있다.
포인터 변수의 값은 항상 주소이기 때문에 일반적인 산술식은 의미가 없고 적합하지 않다.
따라서 포인터 변수 p에 대해 p\(\gets\)p+1과 같은 식은 원칙적으로 허용되지 않는다.
그러나 포인터 변수에 대한 다음 종류의 식은 허용된다. (여기서 p와 q는 모두 주소 값만 나타내는 포인터 변수)
- p = null 또는 p \(\ne\) null : p의 포인터 값이 null인지 검사
- p = q : 포인터 p와 q가 모두 똑같은 주소를 가리키는가 ?
- p \(\gets\) null : p의 포인터 값으로 null을 지정
- p \(\gets\) q : q가 가리키는 노드를 p도 똑같이 가리키도록 지정
- p.link \(\gets\) q : p가 가리키는 노드의 링크 필드에 q의 포인터 값을 지정
- p $$\gets%% q.link : q가 가리키는 노드의 링크 값을 포인터 p의 포인터 값으로 지정
참고 문서
- 이석호. (2004). 자료 구조와 JAVA. 정익사.
