제 4 장 연결 리스트

4.1 단순 연결 리스트 순차(sequential) 표현 연결된(linked) 표현 연속된 원소들이 일정한 거리만큼 떨어져서 저장 테이블에서 임의 원소 접근, 스택이나 큐의 원소 삽입/삭제에 적합 순서 리스트에서 임의 원소의 삽입/삭제 비용 큼 연결된(linked) 표현 각 원소들이 기억 장소 내의 어떤 곳에나 위치 노드 데이타 링크(포인터)

비순차 리스트 표현 first = 8 data[8] = BAT : 데이타 link[3] = 4 : 주소 data[link[3]] = EAT

연결 리스트를 그리는 일반적인 방법 first BAT CAT EAT WAT

노드 삽입 (1) 삽입 절차 (예: GAT 삽입) 삽입할 때 리스트에 있는 다른 원소들의 이동이 불필요 노드 a의 data 필드에 GAT 설정 a의 link 필드가 FAT 다음 노드, 즉 HAT를 가리키도록 FAT를 포함한 노드의 link 필드가 a를 가리키도록 삽입할 때 리스트에 있는 다른 원소들의 이동이 불필요 link 필드를 위한 저장 공간이 추가로 사용

노드 삽입 (2) HAT CAT EAT GAT WAT BAT FAT VAT 15 4 9 1 3 5 7 2 6 8 10 11 3 5 7 2 6 8 10 11 data link (a) Data[5]에 GAT 삽입 (b) 리스트에 노드 GAT 삽입 first BAT CAT EAT FAT HAT x GAT

노드 삭제 GAT 바로 앞에 있는 원소 FAT 찾기 FAT의 link를 HAT의 위치로 설정 리스트에서 GAT 삭제 first BAT CAT EAT FAT GAT HAT WAT 리스트에서 GAT 삭제

4.2 C++에서의 체인 표현 C++에서의 노드 정의 체인 구조를 위한 노드 구조 노드 구조 NodeA와 NodeB에 대한 예 class ThreeLetterNode { private: char data[3]; ThreeLetterNode *link; }; class NodeA { int data1; char data2; float data3; NodeA *linka; NodeB *linkb; } ; class NodeB{ int data; nodeb *link; 55 ‘c’ 22 3.14 data1 data2 data3 linka linkb data link NodeA NodeB 노드 구조 NodeA와 NodeB에 대한 예

C++에서의 체인 클래스 설계 (1) 설계 시도1 ThreeLetterNode *first; 변수 선언 first→data, first→link first를 이용한 데이타 멤버 참조 first→data[0], first→data[1], first→data[2] data의 요소 참조 컴파일 오류 data와 link는 private로 선언 → 클래스 밖에서 접근 불가 *first first→data first first→data[0] first→data[1] first→data[2] first→link

C++에서의 체인 클래스 설계 (2) 설계 시도2 설계 시도3 리스트 조작 연산을 수행하는 함수에 대해서만 클래스 ThreeLetterNode의 데이타 멤버에 접근할 수 있도록 허용 설계 시도3 전체 체인에 대응하는 클래스 구현 ThreeLetterNode와 ThreeLetterChain를 조합하여 사용 ThreeLetterChain을 ThreeLetterNode 객체로 구성  ThreeLetterChain HAS-A ThreeLetterNode

C++에서의 체인 클래스 설계 (3) 정의 만일 A가 개념적으로 B를 포함하거나 또는 B가 A의 일부분이라면, 타입 A의 객체가 HAS-A 타입 B의 객체라고 한다. 타입 A의 객체가 일정한 수의 타입 B의 객체를 포함하고 있는 경우 ThreeLetterChain ThreeLetterNode first BAT CAT WAT ThreeLetterChain HAS-A ThreeLetterNode

C++에서의 체인 클래스 설계 (4) 클래스 ThreeLetterChain은 리스트의 첫 번째 노드를 지시하는 접근 포인터, first만 포함하도록 정의 ThreeLetterChain에 포함될 ThreeLetterNode의 수를 미리 아는 것은 불가능 ThreeLetterChain을 ThreeLetterNode의 friend로 선언 ThreeLetterChain과 ThreeLetterNode의 멤버 함수들만 ThreeLetterNode의 private 데이타 멤버에 접근 가능 ThreeLetterChain ThreeLetterNode first BAT CAT WAT ThreeLetterChain과 ThreeLetterNode사이의 실제 관계성

C++에서의 체인 클래스 설계 (5) 중첩 클래스 하나의 클래스가 다른 클래스 정의 안에서 정의 ThreeLetterNode 객체가 클래스 ThreeLetterChain의 외부로부터 접근될 수 없도록 보장 ThreeLetterNode의 데이타 멤버들은 public class ThreeLetterChain { public: //리스트 조작 연산 . private: class ThreeLetterNode{ //중첩 클래스 char data[3]; ThreeLetterNode *link; }; ThreeLetterNode *first;

C++에서의 포인터 조작 노드 생성: new 노드 삭제: delete 포인터 변수에 널 포인터 상수 0(NULL) 지정 가능 ThreeLetterNode* f; f = new ThreeLetterNode; NodeA* a; a = new NodeA; NodeB* b; b = new NodeB; 노드 삭제: delete 예) delete f; delete a; delete b; 포인터 변수에 널 포인터 상수 0(NULL) 지정 가능 체인의 마지막 노드에 있는 link 공백 리스트 x a a x b x y b b y b y (a) (b) x = y (c) *x = *y 포인터 지정문의 효과

체인 조작 연산 (1) 2-노드 리스트 생성 2-노드 리스트 10 20 first void Chain::Create2() { //두 번째 노드를 생성하고 초기화 ChainNode* second = new ChainNode(20,0); //첫 번째 노드를 생성하고 초기화 first = new ChainNode(10,second); } 10 20 first

체인 조작 연산 (2) 노드 삽입 공백 리스트와 공백이 아닌 리스트에서의 노드 삽입 50 first x (b) (a) void Chain::Insert50(ChainNode *x) { if(first) //x 다음에 삽입 x→link = new ChainNode(50, x→link); else //공백 리스트에 삽입 first = new ChainNode(50); } 50 first x (b) (a)

4.3 템플릿 클래스 체인 체인의 템플리트 정의 정수로 구성된 공백 체인 정의 Chain<int> intlist; template <class T> class Chain; // 전방 선언 template <class T> class ChainNode { friend class Chain<T>; private: T data; ChainNode<T> *link; }; class Chain { public: Chain() {first = 0;}; // first를 0으로 초기화하는 생성자 // 체인 조작 연산들 . ChainNode<T> *first;

체인 반복자 (1) 반복자(iterator) 사용 대상 연산(컨테이너 클래스 C) 코드 형태 컨테이너 클래스의 모든 원소를 순회하는데 사용되는 객체 사용 대상 연산(컨테이너 클래스 C) (1) C에 포함된 모든 정수를 출력하라. (2) C에 포함된 모든 정수의 최대, 최소, 평균, 중간 값을 계산하라. (3) C에 포함된 모든 정수의 합, 곱, 제곱의 합을 계산하라. (4) C에 포함된 모든 정수 중에서 어떤 성질 P를 만족하는 것을 검색하라. (5) 어떤 함수 f(x)의 값이 최대값이 되는 C의 원소 x를 찾으라. 코드 형태 초기화 단계; for C의 각 원소에 대해{ currentItem = C의 현재 원소; currentItem으로 어떤 작업 수행; } 후처리 단계; int x = std::numberic_limits<int>::min(); for each item in C { currentItem = current item of C; x = max(currentItem x); } return x; 최대값을 찾는 의사 코드

체인 반복자 (2) 컨테이너 클래스의 멤버 함수로 최대값 같은 연산 구현 단점 Chain<T>는 템플릿 클래스이므로, 그의 모든 연산은 T가 인스턴스화되는 객체의 타입과는 독립적이어야 한다. Chain<T>가 지원하는 연산이 매우 많아 클래스 정의가 볼품 없다. 컨테이너 클래스의 원소를 일정한 순서로 배열하는 방법을 배워야 한다. → 객체의 원소들에 대한 체계접 접근을 제공하는 반복자 필요

C++ 반복자 (1) 반복자 배열 반복자 이용 STL copy 함수에 대한 코드 객체의 원소에 대한 포인터 객체의 원소를 하나씩 지나가도록 지원 배열 반복자 이용 STL copy 함수에 대한 코드 void main() { int x[3] = {0,1,2}; //배열 x에서 반복을 하기 위해 포인터 y를 사용 for(int* y=x; y!=x+3;y++) cout<<*y<<“ “; cout << endl; } template <class Iterator> void copy(Iterator start, Iterator end, Iterator to) {//[start, end]에서 [to, to+end-start]까지 복사 while(start != end) {*to = *start; start++; to++;} }

C++ 반복자 (2) C++ STL 반복자의 부류 반복자 지원 연산 입력 출력 전방 양방 임의접근 참조 연산자 * 동등 연산자 ==, != 추가로 지시된 원소에 대한 판독 접근 원소에 출력 접근 제공 반복자 전진 ++ , 감소 -- 포인터 산술 연산, 임의의 양 점프

체인 연산 재사용 가능한 클래스에 포함될 연산 체인 연산 생성자(기정 및 복사 생성자) 파괴자 지정 연산자(operator =) 동등 검사 연산자(operator == ) 클래스 객체 입출력 연산자(operator>>, operator<<) 체인 연산 삽입, 삭제, 기타 조작 연산이 필요 last : 리스트의 마지막 노드를 가리킴 리스트의 뒤에 노드 삽입 template<class T> void Chain<T>::InsertBack(const T& e){ if(first){//공백이 아닌 체인 last→link = new ChainNode<T>(e); last = last→link; } else first = last = new ChainNode<T>(e);

클래스의 재사용 필요한 경우에만 재사용 클래스의 재사용보다 새로 설계하는 유리한 경우 (1) 클래스(C1)를 재사용하여 다른 클래스(C2)를 구현하는 것보다 C2를 직접 구현하는 것이 더 효율적일 때 (2) 응용에서 요구하는 연산이 복잡하고 특수한 것이어서 클래스에서 지원하지 못하는 경우

4.4 원형 리스트 (1) 원형 리스트(circular list) 원형 리스트 원형 리스트 예 체인에서 마지막 노드의 link 필드가 첫 번째 노드를 가리킴 단순 연결 원형 리스트(singly-linked circular list) 원형 리스트 원형 리스트 예 BAT CAT EAT first WAT x1 x2 x3 first data link

원형 리스트 (2) 리스트 앞에 새 노드 삽입 마지막 노드의 link를 변경해야 하므로 접근 포인터가 마지막 노드를 가리키는 편이 더 편리 O(1) 시간에 삽입 가능 x1 x2 x3 data link last template <class T> void CircularList<T>::InsertFront(const T& e) {//원형 리스트 *this의 앞에 원소 e를 삽입, // last는 리스트의 마지막 노드를 가리킨다. ChainNode<T> *newNode = new ChainNode<T>(e); if(last) { // 공백이 아닌 리스트 newNode→link = last→link; last→link = newNode; } else {//공백 리스트 last = newNode; newNode→link = newNode;

원형 리스트 헤더 노드 모조 노드 공백 리스트를 특별한 경우로 처리할 필요 없음 BAT CAT EAT WAT head

4.5 가용 공간 리스트 (1) 자유(삭제된) 노드의 체인 노드 획득 ◆ 노드 반환 파괴자의 실행 시간 O(1)로 감소 새 노드가 필요할 때는 자유 노드 체인 검사 자유 노드 체인이 공백일 때만 new 호출 노드 획득 ◆ 노드 반환 template <class T> ChainNode<T>* CircularList<T>::GetNode() {//사용할 노드 생성 ChainNode<T>* x; if(av) {x =av;av=av→link;} else x = new ChainNode<T>; return x; } template <class T> void CircularList<T>::RetNode(ChainNode<T>*& x) {//x가 가리키는 노드 반환 x→link=av; av = x; x = 0; }

가용 공간 리스트 (2) 원형 리스트의 삭제 점선 화살표가 원형 리스트 삭제에 관련된 변경 표현 template <class KeyT> void CircularList<T>::~CrivularList() {//원형 리스트 삭제 if(last){ ChainNode<T>* first = last→link; last→link = av; //마지막 노드가 av에 연결 av = first; //리스트의 첫 번째 노드가 av리스트의 첫 번째 노드가 됨 last = 0; } 점선 화살표가 원형 리스트 삭제에 관련된 변경 표현

4.6 연결 스택과 큐 (1) 연결 스택 톱에서 노드 삽입/삭제 용이 top : 스택의 톱 노드를 가리키는 전용 데이타 멤버 data link top

4.6 연결 스택과 큐 (2) 연결 큐 리어에서 노드 삽입 용이 프런트에서 삽입 삭제 용이 front : 큐의 처음 노드를 가리키는 전용 데이타 멤버 rear : 큐의 마지막 노드를 가리키는 전용 데이타 멤버 초기엔 front와 rear를 0으로 설정 data link front rear

4.7 다항식 (1) 다항식 ai : 0이 아닌 계수 ei : 음수가 아닌 정수 지수 em>em-1> ... >e2>e1≥ 0 리스트를 사용해서 클래스 Polynomial 구현 Polynomial은 List에 IS-IMPLEMENTED-BY관계 List가 Polynomial의 구현에 중추적 역할 3x14+ 2x8 +1 8x14 + 3x10 + 10x6

다항식 (2) coef exp link data : Polynomial : Chain : Term struct Term {//Term의 모든 멤버는 묵시적으로 public int coef; //계수 int exp; //지수 Term Set(int c, int e){coef=c; exp=e; return *this;}; }; class Polynomial{ public: //정의된 공용 함수들 private: Chain<Term> poly; coef exp link data : Polynomial : Chain : Term

다항식의 덧셈 (1) 덧셈 알고리즘 두 다항식 a, b 만일 두 항의 지수가 같으면 계수를 더하고, 그 합이 0이 아니면 결과에 대한 새로운 항을 만든다. b의 현재 항의 지수보다 a의 현재 항의 지수가 작으면, b의 항과 똑같은 항을 만들어 Polynomial 객체에 첨가, b는 다음 항으로 이동 반대의 경우는 a에 대해 수행 새로운 노드의 첨가를 위해 InsertBack()을 사용

다항식의 덧셈 (2) C=a+b의 처음 세 항을 생성

다항식의 덧셈 (3) operator+의 분석 O(m+n) , 계수 덧셈 지수 비교 체인 끝에 항의 삽입 0 ≤ 계수 덧셈의 횟수 ≤ min{m,n} 지수 비교 m+n을 경계 체인 끝에 항의 삽입 최대 m+n O(m+n)

다항식의 원형 리스트 표현 원형 리스트 표현 헤더 노드 사용 3x14+2x8+1 0인 다항식을 특수 경우로 처리 해야 함 3 first 3 14 2 8 1 head - 3 14 2 8 1 (a) 제로 다항식 (b) 3x + 2x + 1

4.8 동치 관계 (1) 관계  의 특성 동치 관계(equivalence relation) (1) 반사적(reflexive) : 다각형 x에 대해서, x≡x가 성립 (2) 대칭적(symmetric) : 다각형 x,y에 대해서, x≡y이면 y≡x (3)이행적(transitive): 다각형 x, y, z에 대해서, x≡y이고 y≡z이면 x≡z 동치 관계(equivalence relation) 집합 S에 대하여 관계 ≡ 가 대칭적, 반사적, 이행적 동치부류(equivalence class) x≡y이면 x, y는 같은 동치부류 ex) 0≡4, 3≡1, 6≡10, 8≡9, 7≡4, 6≡8, 3≡5, 5≡11, 11≡0 { 0, 2, 4, 7, 11}, {1, 3, 5}, {6, 8, 9, 10}

동치 관계 (2) 동치 결정 알고리즘 동치 쌍(equivalence pair) (i,j)를 읽어 기억 0에서부터 시작해서 (0,j) 형태의 모든 쌍을 찾는다. (j,k)가 있으면 k도 0과 같은 동치부류에 포함시킨다. 0이 포함된 동치 부류의 모든 객체를 찾아 표시하고 출력 아직 출력되지 않은 객체가 있으면, 새로운 동치 부류이므로 전과 같은 방법으로 수행하여 출력

동치 관계 (3) Boolean 배열을 사용 한 동치 알고리즘 pairs[i][j]= true : i와 j가 입력쌍 m : 동치 쌍의 수 n : 객체 수 pairs[i][j]= true : i와 j가 입력쌍 배열의 극히 일부 원소만 사용 : 기억 장소 낭비 배열의 초기화를 위해 Θ(n2)시간 필요 void Equivalence() { 초기화; while 나머지 쌍 다음 쌍 (i,j)를 읽음; 이 쌍을 처리; } 출력을 위해 초기화; for (출력이 안된 객체에 대해) 이 객체를 포함하고 있는 동치 부류를 출력;

동치 관계 (4) 체인을 사용한 동치 알고리즘 first[n] : n개의 리스트 헤더 노드 저장 out[n] : 이미 출력된 객체 표시 void Equivalence() { read n; //객체의 수를 읽어들임 first[0:n-1]를 0,out[0:n-1]를 false로 초기화; while more pairs //입력 쌍 다음 쌍 (i,j)를 판독; j를 체인 first[i]에 삽입; i를 체인 first[j]에 삽입; } for(i=0;i<n;i++) if(!out[i]){ out[i] = true; 객체 i를 포함하고 있는 동치 부류 출력;

동치 관계 (5) 쌍들이 입력된 뒤의 리스트 0≡4, 3≡1, 6≡10, 8≡9, 7≡4, 6≡8, 3≡5, 5≡11, 11≡0 11 3 5 7 8 4 6 1 10 9 2 [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] first data link

4.9 희소 행렬 (1) 희소 행렬에 대한 연결 표현 방법 0이 아닌 각 항은 행 원형 리스트와 열 원형 리스트에 위치 모든 원형 리스트는 헤더 노드를 포함 헤더 노드 down : 열 리스트 연결에 사용 right : 행 리스트 연결에 사용 next : 헤드 노드들을 서로 연결 원소 노드 down: 같은 열에 있는 0이 아닌 다음 항 연결 right : 같은 행에 있는 0이 아닌 다음 항 연결

희소 행렬 (2) 5*4 희소 행렬 a 필요한 노드 수 r개의 0이 아닌 항을 가진 n*m 희소 행렬이라면 max{n,m}+ r + 1 개

희소 행렬 a의 연결 표현 (노드의 head 필드는 표시되지 않았음)

희소 행렬 입력 (1) 첫번째 입력 라인 다음 입력 라인 행렬에 있는 행의 수, 열의 수, 0이 아닌 항의 수 (i,j,aij)형식의 3원소 쌍 행렬의 0이 아닌 항들의 row, col, value 데이타 멤버로 구성 행으로 정렬되고 행 내에서는 열로 정렬

희소 행렬 삭제 가용 공간 리스트를 이용한 파괴자 ~Matrix()의 분석: 계산 시간은 O(n+m) Matrix::~Matrix() {//모든 노드들을 av 리스트로 반환. 이 리스트는 right 필드로 연결된 체인 //av는 av리스트의 첫 번째 노드를 가리키는 정적 변수 if(~headnode) return ;//삭제할 노드 MatrixNode *x = headnode→right; headnode→right = av; av= headnode; //return headnode while(x!=headnode){//행별로 삭제 MatrixNode *y = x→right; x→right = av; av = y; x=x→next;//다음 행 } headnode =0; ~Matrix()의 분석: 계산 시간은 O(n+m)

4.10 이중 연결 리스트(1) 이중 연결 리스트(doubly linked list) 각 노드는 전방과 후방을 가리키는 두개의 링크를 가짐 - first 헤더 노드를 가진 공백 이중 연결 원형 리스트 - Left data Right 헤더노드 헤더 노드가 있는 이중 연결 원형 리스트

이중 연결 리스트 (2) 이중 연결 리스트의 클래스 정의 이중 연결 원형 리스트로부터 삭제 - first x Before class DblList; class DblListNode { friend class DblList; private: int data; DblListNode *left, *right; }; class DblList { public: // 리스트 조작 연산 DblListNode *first; // 헤더 노드를 가리킴 void DblList::Delete(DblListNode *x) { if ( x == first ) throw "Deletion of header node not permitted“; else { x→left→right = x→right; x→right→left = x→left; delete x; } - first x Before After

이중 연결 리스트 (3) 이중 연결 원형 리스트에 삽입 p x void DblList::Insert(DblListNode *p, DblListNode *x) {// 노드 x의 오른편에 노드 p 삽입 p→left = x; p→right = x→right; x→right→left = p; x→right = p; } x p

4.11 범용 리스트 (1) 범용 리스트(generalized list) 표현 4.11 범용 리스트 (1) 범용 리스트(generalized list) n 0 개 원소의 유한 수열, 즉, a0 ,…, an-1 ai는 원자이거나 리스트 원자가 아닌 원소 ai (0in-1)는 A의 서브리스트 표현 리스트 A =(a0 ,…, an-1 ) A는 리스트 의 이름 n은 리스트의 길이 모든 리스트의 이름은 대문자로 표기 소문자는 원자를 표현 n1일 때, a0 는 A의 헤드 (a1 ,…, an-1 ) 는A의 테일

범용 리스트 (2) 범용 리스트의 예 A = () : 널 또는 공백 리스트 ; 길이는 0 B = (a,(b,c)) : 길이는 2 　‘ 원소는 원자 a와 선형 리스트 (b,c) C = (B,B,()) : 길이는 3 　‘ 원소는 두 B와 널 리스트 D = (a,D) : 길이가 2인 순환 리스트 D는 무한 리스트 (a,(a,(a,…)

범용 리스트 (3) 범용 리스트를 이용한 다변수 다항식 표현 PolyNode 타입의 노드 정의 P(x,y,z)=x10y3z2 + 2x8y3z2 + x4y4z + 6x3y4z + 2yz = ((x10 + 2x8)y3 + 3x8y2 )z2 + ((x4 +6x3)y4 + 2y)z =Cz2+Dz C(x,y) = Ey3 +Fy2 PolyNode 타입의 노드 정의 enum Triple { var, ptr, no }; class PolyNode { PolyNode *next; //연결 필드 int exp; Triple trio; union { char vble; PolyNode *down; //연결 필드 int coef; };

범용 리스트 (4) 노드의 종류 (3x2y)의 표현 trio == var trio == ptr trio == no 리스트의 헤더 노드 trio == ptr 계수는 그 자체가 리스트이고, down 필드가 지시 trio == no 계수는 정수이고, coef 필드에 그 값이 저장 (3x2y)의 표현

범용 리스트 (5) ((x10+2x8)y3+3x8y2)z2+((x4+6x3)y4+2y)z의 표현

범용 리스트 (6) 범용 리스트의 노드 구조 자료 구조 정의 tag=false/true data/down next template <class T> class GenList; //전방 선언 template <class T> class GenListNode{ friend class GenList<T>; private: GenListNode<T> *next; bool tag; union{ T data; GenListNode<T> *down; }; template <class T> class GenList{ public: //리스트 조작 연산 private: GenListNode<T> *first; };

범용 리스트 (7) data/down 필드 head(A)가 원자 head(A)가 리스트 원자를 유지

리스트를 위한 순환 알고리즘 (1) 순환적으로 정의된 객체 → 순환 알고리즘이 유용 순환 알고리즘의 구성 리스트의 복사 순환 함수 자체(workhorse) 순환 함수를 호출하는 함수(driver) 구현 Driver는 공용, workhorse는 전용 멤버 함수로 정의 리스트의 복사 //드라이버 void GenList<T>::Copy(const GenList<T>& l) const {//l을 복사한다. first = Copy(l.first); } //작업 함수 GenListNode<T>* GenList<T>::Copy(GenListNode<T>* p) {//비공용 서브리스트 p를 가진 비순환 리스트 복사 GenListNode<T> *q =0; if(p){ q=new GenListNode<T>; q→tag = p→tag; if(p→tag)q→down = Copy(p→down); else q→data = p→data; q→next = Copy(p→next); return q;

리스트를 위한 순환 알고리즘 (2) 복사 알고리즘의 연산 시간 리스트 A=((a,b),(c,d),e)) tag = false인 노드는 2번 방문, tag = true인 노드는 3번 방문 → 총 m개의 노드를 가진 리스트 : 3m번 이하 방문 O(m) f a b c d t e first s u v w x r

리스트를 위한 순환 알고리즘 (3) 리스트 깊이 0 s가 원자인 경우 depth(s)= 1+ max(depth(x1),…,depth(xn) s가 리스트 (x1,…,xn)이고, n1 depth(s)= // 드라이버 template <class T> int GenList<T>::Depth() {// 비순환 리스트의 깊이를 계산 return Depth(first); } // 작업함수 int GenList<T>::Depth(GenListNode<T> *s) { if (!s) return 0; //공백 리스트 GenListNode<T> *current = s; int m = 0; while (current) { if (current→tag) m=max(m,Depth(current→down)); current = current→next; return m+1;

참조 계수, 공유 순환 리스트 (1) 리스트의 정의 확장 리스트의 공유는 노드의 삽입과 삭제에 문제를 야기 리스트의 정의 내에 나타나는 서브리스트는 그 리스트 바로 앞에 이름을 붙인다. 리스트의 공유는 노드의 삽입과 삭제에 문제를 야기 헤드 노드를 사용하여 해결 data/down: 참조계수(리스트를 참조하는 포인터수)

참조 계수, 공유 순환 리스트 (2) t.~GenList<T>() GenListNode<T>의 정의 t.first의 참조계수를 하나 감소 참조계수가 0이 될 때만 t의 노드들 삭제 GenListNode<T>의 정의 template <class T> class GenListNode<T> { friend class GenList<T>; private: GenListNode<T> *next; int tag; // data는 0, down은 1, ref는 2 union{ T data; GenListNode<T> *down; int ref; };

참조 계수, 공유 순환 리스트 (3) b.~GenList<T>() 호출 : b의 참조 계수를 2로 감소 그 다음에 c.~GenList<T>() 호출 c의 참조 계수가 0이 됨 그 다음 노드가 처리되고 b.first →ref가 1로 감소 다시 b.first→ref는 0이 되고 리스트 B(a,(b,c))의 노드들이 가용 공간 리스트로 반환 c의 톱 레벨 노드들이 가용 공간 리스트에 연결 순환 리스트의 참조 계수: 0이 될 수 없음 d.~GenList<T>() : d.first →ref를 1로 감소. 반환은 되지 않으나 접근 불가능

참조 계수, 공유 순환 리스트 (4) r.~GenList(), s.~GenList() 다음에 r.first→ref는 1, s.first →ref는 2. 접근 불능, 반환 불능 → 쓰레기(garbage) 순환 리스트를 언제 물리적으로 삭제해야 할 지 결정할 수 있는 간단한 방법이 없음