4강 - 연결리스트

목차

• 1. 단순 연결 리스트와 체인

• 2. C++에서의 체인 표현

• 3. 템플릿 클래스 체인

• 4. 원형 리스트

• 5. 가용 공간 리스트

• 6. 연결 스택과 큐

• 7. 다항식

• 8. 동치 관계

• 9. 희소 행렬

• 10. 이중 연결 리스트

• 11. 범용 리스트

• 12. 가상 함수와 동적 바인딩

1. 단순 연결 리스트와 체인

 

List = [ CAT, HAT, EAT, BAT, RAT, SAT,...]

다음과 AT로 끝나는 순서 리스트가 있다고 생각해보자.

지금까지 공부했던 배열은 삽입과 삭제에 불필요한 동작들이 많아 많은 시간이 소모되었었다. 

이런 데이터들의 이동적인 측면에서의 문제점을 해결하기 위해서는 연결 리스트라는 자료구조가 도움이 된다.

연결 리스트의 표현 방법으로는 pointer(포인터)와 link(링크)가 연관되어 있다.

쉽게 생각하면 배열인데 그 배열 안에 데이터와 링크 이 두 부분으로 나뉜다고 생각하면 된다.

이런 데이터와 링크를 가지고 있는 배열을 노드라고 하며 이런 노드들이 링크로 묶여 있는 것을 연결 리스트라고 한다.

데이터 부분에는 많은 예시가 들어갈 수 있지만 링크는 다음 노드를 가리키는 것이기 때문에 데이터와는 다르다.

 

연결 리스트에서도 삽입과 삭제가 간단하지만은 않다. 

하지만 일반적인 배열보다는 훨씬 빠르게, 데이터의 이동 없이 해결할 수 있다.

먼저 노드의 삽입에 대해서 보면

1. 현재 사용하고 있지 않은 노드(av 노드, 또는 새로운 노드를 동적 할당으로 생성해도 됨)를 가져온다.
2. 노드 a의 data필드에 내가 삽입하고 싶은 데이터를 입력한다.
3. 노드 a의 link가 삽입돼야 될 부분의 다음 노드를 가리키게 한다.
4. 노드 a가 삽입되야 될 부분의 전 노드가 a를 가리키게 한다.

이 순서를 지키지 않으면 a가 삽입될 때, 다음 노드를 지정해 주어야 하는데 그다음 노드들에 대한 정보가 없어진다.

 

삽입에 비해 삭제는 간단하다. 여러 방법이 있지만 뒤에 가서 배울 av노드에 반환하는 방법이 가장 메모리적 효율이 좋다고 한다.

 

2. C++에서의 체인 표현

 

체인을 표현하기 위해서는 먼저 포인터에 대해 알아야 한다.

포인터를 표현하는 방법에는 여러 가지가 있다. 예를 들면

ThreeLetterNode *p ==> p = new ThreeLetterNode 등등이 있다.

내가 코드를 짜면서 이해한 포인터는 이런 노드들을 가리키는 포인터를 주로 생성해서 사용하고, 

그 포인터 변수들을 통해 p->link, p->data 등과 같이 가리키고 있는 노드의 데이터 필드나 link영역 등을 연산할 수 있다.

ex)

8

BAT

3

3

CAT

4

 

first = 8;                        first->link = 3;

* first = ( 'BAT', 3 )           *first->link = ('CAT', 4 )

 

이제 체인을 구현해 보면 먼저 Chain을 구현하기 위한 ChainNode가 필요하다. (노드들)

그 후 Chain 클래스를 설계하면 되는데 중첩 클래스로 선언이 가능하지만 나는 복합 클래스로 구현하였다.

후에 나올 Chain 반복자(ChainIterator)만 중첩 클래스로 선언하였다.

 

여기서 미리 짚고 넘어갈 점은 뒤의 장에서도 계속해서 여러 방법으로 연결 리스트를 구현하는 방법들이 나오는데

나는 처음에 연결리스트를 구현할 때 많이 어려웠다.

하지만 다 구현하고 생각해보면 결국 연결 리스트를 생성하는 것은 InsertBack()이란 함수였고, (뒤에 설명하겠음)

나머지 멤버 함수들, 클래스들은 이를 뒷받침하기 위한 코드들이었던 것 같다. 

연결 리스트의 구현은 아래의 링크에 구현해 놓았다.

 

3. 템플릿 클래스 체인

 

템플릿 클래스 체인은 말 그대로 체인을 어떤 형태의 노드를 가진 체인으로 구현할 것인지를 사용자가 정의할 수 있게 만들어 주는 것이다.

위에서 얘기했던 체인은 data와 link를 가진 ChainNode형의 Chain을 구현했던 것이고, 

앞으로 구현해야 할 체인들은 매우 매우 다양하다.

그렇기에 템플릿 클래스로 Chain을 선언할 수 있어야 한다.

구현은 아래의 링크에 해 놓을 것이다.

 

C++에서의 반복자 

C++에서의 반복자는 객체의 원소에 대한 포인터라고 정의된다. 

이 반복자는 객체들을 하나하나 반복해서 지나가며 사용된다.

반복자에는 다섯 가지 부류가 있는데 이는 입력, 출력, 전방, 양방, 임의 접근이다.

모든 반복자는 *연산뿐만 아니라 ==,!=와 같은 동등 연산자도 지원한다.

 

반복자에 대한 구현도 Chain의 구현에 중첩 클래스로 구현해 놓았다. 

사용법은 Chain <T>::ChainIterator ai = poly.begin()과 같이 미리 정의된 반복자 클래스의 멤버 함수들로 사용 가능하다.

만약 ++연산(사후 증가 또는 사전 증가)에 대해 오버 로딩이 되어있다면

ai++ 는 ai=ai->link와 같은 형태로도 사용이 가능하다.

 

InsertBack() 함수

내 개인적으로 체인, 연결 리스트를 구현하는 데에 있어서 가장 중요한 함수라고 생각하기에 정리해 보았다.

이 함수를 통해 연결 리스트를 생성하게 되는데, 이름 그대로 뒤에다가 삽입하는 함수이다.

노드가 생성되어 있다면 노드의 뒤에 삽입하게 될 것이고, 노드가 없다면 새로운 노드를 만들고 그 노드가 헤드 노드(맨 앞의 노드) 임을 알려줄 것이다. 코드는 아래와 같다.

//리스트 맨 뒤에 노드 삽입
//head노드를 이중포인터로 전달하는 이유 : head노드의 값이 아니라 주소값이 필요하기 때문.
void Chain::InsertBack(ChainNode** head, int c, int e) {
    //입력 노드 정의 
    ChainNode* insertNode = new ChainNode;
    //insertNode에 data 저장(data파트 저장)
    insertNode->data.exp = e;
    insertNode->data.coef = c;
    //만약 head가 없으면 
    if (*head == NULL) {
        ChainNode* header = new ChainNode;
        header->link = insertNode;
        //입력된 노드를 head노드로 지정(첫 노드) 
        *head = header;
        //insertNode의 next를 null값 지정(head노드로 지정) 
        insertNode->link = header;
        first = *head;
        last = insertNode;
    }
    //head노드가 존재하면.
    else {
        //insertNode가 맨 마지막 노드가 되어야 하므로, next에 head노드 위치 지정
        insertNode->link = *head;
        //맨 마지막 노드가 insertNode가 되어야 하므로 
        last->link = insertNode;
        //last포인터를 insertNode를 가리키게 변경
        last = last->link;
    }
}

먼저 새로운 노드를 동적 할당으로 생성해주고 관련 데이터들을 입력해 준다.

그 후 노드가 존재한다면 맨 마지막 노드의 뒤에 삽입해주고, 노드가 존재하지 않는다면 새로운 체인을 만들어준다.

 

4. 원형 리스트

 

연결 리스트의 마지막 노드가 원래는 0, 즉 NULL값을 가리키고 있다. 

이 뜻은 마지막 노드를 찾으려면 다음 노드, 즉 node->link 가 NULL이 되는 값을 찾으면 된다는 의미이다.

이때 원형 리스트는 마지막 노드가 NULL이 아니라 제일 처음 노드를 가리키고 있는 형태를 원형 리스트라고 한다.

 

여기서 만약 원형 리스트의 맨 앞에 노드를 삽입시켜 준다고 생각해보자.

만약 first라는 포인터가 리스트의 맨 앞을 가리키고 있다면 쉽겠지만 그렇지 않다면 모든 리스트를 돌며 node->link가 헤더인 것을 찾아야 한다.

이때 원형 리스트에 대한 접근 포인터가 마지막 노드를 가리킨다면 훨씬 빠르게 첫 노드를 찾을 수 있다.

 

이전까지는 리스트가 공백 일 때를 항상 예외 처리를 해줬어야 한다. 

이때 만약 모든 리스트가 처음부터 공백인 리스트를 하나 가지고 있다면 이런 예외처리의 과정이 필요 없게 된다.

이러한 개념에서 나온 원형 리스트가 바로 헤더 노드를 갖는 원형 리스트이다.

후에 나올 4-7 다항식에서 다항식의 연산을 헤더 노드를 갖는 원형리 스트로 구현하는 과정에서 왜 헤더 노드를 갖는 원형 리스트가 더 편리한지를 알 수 있다.

 

5. 가용 공간 리스트

 

체인과 원형 리스트의 메모리를 돌려주는(삭제하는) 파괴자는 노드 한 개 단위로 삭제를 한다.

이 때문에 반환하는 시간은 리스트의 길이 만큼이 걸리게 되는데 길이가 긴 리스트를 반환하는데 비효율적이다.

가용 공간 리스트(av 리스트)는 이러한 비효율적 측면을 많이 줄여준다.

개념은 필요 없는 메모리 공간은 av 리스트에 계속해서 연결하는 식으로 반환하고, 메모리 공간이 필요하다면 av 리스트에서 가져와서 쓰는 방법이다. 

쉽게 말해 예비 리스트를 만들어 필요할 땐 가져와 쓰고, 필요 없으면 다시 리스트에 붙여주는 방식이다. 

따라서 가용 공간 리스트를 사용하면 일정 시간 안에 노드 수와 관계없이 리스트를 삭제할 수 있다.

 

6. 연결 스택과 큐

 

3장에서 배열로 스택과 큐를 구현할 수 있었고, 연결 리스트로도 구현이 가능하다.

코드는 아래의 링크에 구현해 놓았다.

 

7. 다항식

 

3장에서 배열로 다항식을 연산하는 클래스를 구현해 보았었다. 

4장에서는 연결 리스트로 구현해 볼 건데, 이때 앞서 말했듯이 헤더 노드를 갖는 원형 연결 리스트와 헤더 노드를 갖지 않는 원형 열결 리스트의 구현은 살짝 다르다. 

+연산자 오버 로딩을 살펴볼 건데 아래는 헤더 노드를 갖지 않는 원형 연결 리스트로 구현한 코드이다.

Polynomial Polynomial::operator+(const Polynomial& b) const {
	//다항식 b와 *this(a)를 더하는 + 연산자 오버로딩
	Polynomial c;
	Term temp;
	Chain<Term>::ChainIterator ai = poly.begin();
	Chain<Term>::ChainIterator bi = b.poly.begin();
	while (ai && bi) {  //ai와 bi둘다 마지막 노드가 아니여야 함. 그래야 비교 가능하기 때문
		if (ai->exp == bi->exp) {
			int sum = ai->coef + bi->coef;
			if (sum)c.poly.InsertBack(temp.Set(sum, ai->exp));
			ai++, bi++;
		}
		else if (ai->exp > bi->exp) {
			c.poly.InsertBack(temp.Set(ai->coef, ai->exp));
			ai++;
		}
		else {
			c.poly.InsertBack(temp.Set(bi->coef, bi->exp));
			bi++;
		}
	}
	while (ai) { //a다항식에 남은 항들을 c에 추가
		c.poly.InsertBack(temp.Set(ai->coef, ai->exp));
		ai++;
	}
	while (bi) {  //b다항식에 남은 항들을 c에 추가
		c.poly.InsertBack(temp.Set(bi->coef, bi->exp));
		bi++;
	}
}

여기서 ai와 bi는 Chain의 반복자이다.

헤더노드를 갖지 않는 원형 연결 리스트로 구현하면 a 나 b 다항식이 마지막 노드라면 while문을 빠져나오게 된다.

즉 더 이상 비교 연산이 불가하기 때문에 남은 항들을 그냥 c에 추가시켜 주는 것이다.

그렇다면 이제 헤더 노드를 갖는 원형 연결 리스트로 구현해 보자.

Polynomial Polynomial::operator+(const Polynomial& b) const {
	//다항식 b와 *this(a)를 더하는 + 연산자 오버로딩
	Polynomial c;
	Term temp;
	Chain<Term>::ChainIterator ai = poly.begin();
	Chain<Term>::ChainIterator bi = b.poly.begin();
	while (1) {
		if (ai->exp == bi->exp) {
			if (ai->exp == -1) return c;
			int sum = ai->coef + bi->coef;
			if (sum)c.poly.InsertBack(temp.Set(sum, ai->exp));
			ai++, bi++;
		}
		else if (ai->exp > bi->exp) {
			c.poly.InsertBack(temp.Set(ai->coef, ai->exp));
			ai++;
		}
		else {
			c.poly.InsertBack(temp.Set(bi->coef, bi->exp));
			bi++;
		}
	}
}

딱 봐도 코드가 짧아진 걸 알 수 있다.

주의할 점은 헤더 노드의 데이터 필드의 exp는 -1로 초기화해야 한다.

(지수가 -1이 될 수 없기 때문에 이 노드가 헤더 노드임을 알려주는 중요한 표시임. -1 말고도 여러 가지로 표현 가능)

헤더 노드를 갖는다면 a나 b의 다항식이 남아있는 경우를 따로 예외처리 해주지 않아도 된다.

왜냐하면 if(ai->exp==-1) return c; 이 코드 때문이다.

ai 또는 bi는 마지막 노드가 헤더노드를 가리키기 때문에 한 바퀴 돌면 헤더 노드로 돌아오게 된다.

이때 헤더 노드의 exp는 -1이고 어떤 지수보다도 작게 되기 때문에 ai 또는 bi의 남아있는 다항식들이 전부 c에 입력된다.

그리고 ai->exp==bi->exp==-1 인 경우가 위의 반복문이므로 모든 다항식을 더해주는 것을 알 수 있다.

 

나머지 다항식의 멤버 함수 코드들은 아래의 링크에 구현해 놓았다.

 

8. 동치 관계

기호 ≡ 가 임의의 관계를 나타내고, 아래와 같은 특징을 만족한다고 가정하자.

1. 반사적(reflexive) : x ≡ x 가 성립한다
2. 대칭적(symmetric) : x ≡ y 이면 y ≡ x가 된다.
3. 이행적(transitive) : x ≡ y이고 y ≡ z 이면 x ≡ z이다.

집합 S에 대하여 관계 ≡ 가 반사적, 대칭적, 이행적이면 관계 ≡ 를 집합 S에 대해 동치 관계라 한다. 역도 성립한다.

 

아래의 링크에 동치 부류를 찾는 C++함수를 구현해 놓았다.

 

9.  희소 행렬

 

희소 행렬을 원형 연결 리스트로 표현해보자.

먼저 max(행의 수, 열의 수) 만큼의 헤더 노드들이 필요하다. 이유는 각 행과 열의 헤더 노드의 down, right link에 각각 행과 열들이 저장될 것이기 때문이다. 이때 주의할 점은 행 i의 헤더 노드는 열 i의 헤더 노드이기도 하다.

다음으로 헤더 노드들의 헤더 노드가 필요하다. 

이를 통해 만약 r개의 원소를 가진 n*m크기의 희소 행렬을 원형 연결 리스트로 표현하려면

max(n, m) + r + 1(헤더 노드의 헤더 노드) 개의 노드가 필요하다는 것을 알 수 있다.

 

이제 각각의 노드들은 head, down, right, value, row, col 총 6가지의 필드를 가지게 되고, 설명해 보자면

1. head : boolean 타입으로 이 노드가 헤더 노드인지 아닌지를 구분
2. down : 같은 열의 다음 원소를 가리키는 필드
3. right : 같은 행의 다음 원소를 가리키는 필드
4. row, col, value : 몇 행 몇 열의 원소인지와 그 원소의 값을 저장하는 필드들

헤더 노드들은 head필드가 true로 정의되고, 다른 노드들과 다르게 row, col, value 값 대신 next란 필드를 가지게 된다.

 

희소 행렬의 입력과 삭제 코드는 아래의 링크에 구현해 놓았다.

 

10. 이중 연결 리스트

 

위의 연결 리스트들은 한 방향으로만 이어져 있었다. 

이때 가장 큰 문제점은 p라는 노드의 전위 노드를 찾으려면 한 바퀴를 다시 돌아야지만 찾을 수 있다.

이러한 문제를 해결할 수 있는 구조가 이중 연결 리스트(doubly linked list)이다.

 

원래의 연결 리스트들이 right의 링크 필드만 가졌다면, 이중 연결 리스트는 적어도 left와 right 이 두 가지를 가진다.

 

아래는 이중 연결 리스트에서의 삭제를 나타낸 코드의 일부이다.

if(x==first){ return false; } // 헤더 노드는 지울 수 없음
else{
	x->left->right=x->right; //x의 왼쪽노드가 x의 오른쪽 노드를 가리키게 함
    	x->right->left=x->left;  //x의 오른쪽노드가 x의 왼쪽 노드를 가리키게 함
	delete x;}

 

코드를 보면 x->left->right와 같이 자신의 이전 노드를 x->left, 다음 노드를 x->right로 표현할 수 있다.

 

11. 범용 리스트

 

정의 : 범용 리스트는 n>=0 개 원소의 유한 수열, 즉 a0,..., an-1이고, 여기서 ai는 원자이거나 리스트이다. 원자가 아닌 원소(ai)는 서브 리스트(sublist)라고 한다.

 

쉽게 풀어써보면 원래의 선형 리스트의 원소들은 원자들로 제한되어 있었다. 

따라서 선형 리스트의 원소들은 위치에 대한 제약이 존재한다. (배열을 예로 생각해보면 이해하기 쉽다.)

범용 리스트는 이를 완화해주고, 원소들이 자신들의 구조를 가질 수 있게 해 준다.

즉 범용 리스트는 원소가 리스트의 형태도 가능하다.

 

A = (a0, a1, a2,..., an) 일 때 a0는 A의 head, an은 A의 tail이라 표현한다.

이제 범용 리스트의 몇 가지 예를 살펴보면

 

• A() : 널, 공백 리스트
• B = (a, (b, c)) : 길이는 2이고, 원소가 원자 a와 선형 리스트(b, c)로 이루어진 범용 리스트
• C = (B, B, () ) : 길이가 3이고, 처음, 두 번째 원소는 리스트 B이고, 마지막 원소는 널 리스트이다.
• D = (a, D) : 길이가 2인 순환 리스트 - 자기 자신을 계속해서 불러오므로 무한 리스트

ex) 

1. head(B) = (a)
2. tail(B) = ((b, c))   //괄호가 두개임을 주의!!
3. head(tail(B)) = (b,c)
4. tail(tail(B)) = ()

순환 알고리즘

 

순환 함수 자체를 workhorse, 순환 함수를 가동하는 함수를 driver 라 하며, driver는 public(공용)으로, workhorse는 private(전용) 멤버 함수로 구현한다.

 

처음에는 재귀 함수랑 같다고 생각했었는데 다른 점이 있다. 재귀 함수는 재귀 함수 내에서 자신을 다시 불러오는 식으로 구현되지만 순환 알고리즘으로 구현한 함수는 workhorse와 dirver 이 두 가지로 나누어진다는 게 가장 큰 차이이다.

 

참조 계수 : 리스트 노드에 대한 포인터 수, 헤더 노드의 data

 

12. 가상 함수와 동적 바인딩

 

기본 클래스와 그 클래스의 파생 클래스가 있다고 가정해보자.

기본 클래스 타입의 포인터가 기본 클래스 타입의 객체를, 파생 클래스 타입의 포인터가 파생 타입의 객체를 가리키고 있다면 문제가 되지 않는다.

심지어 파생 클래스 타입의 포인터가 기본 클래스 타입의 객체를 가리키고 있어도 기본 클래스 타입을 참조하기 때문에 큰 문제는 되지 않는다. (동적 바인딩 : 파생 클래스 = 기본 클래스 but 기본 클래스!= 파생 클래스) 

만약 기본 클래스 타입의 포인터가 파생 클래스 타입의 객체를 가리킨다면, 어느 클래스를 참조하게 될까?

정답은 기본 클래스이다. 

쉽게 예를 들어보면 기본 클래스 Polygon에게 Rectangle이라는 파생 클리스가 존재한다고 가정해보자.

Polygon *ptr1;
Rectangle *ptr2;
Polygon p;
Rectangle r;
*ptr1 = &p // 가능, 기본 클래스 참조
*ptr2 = & r // 가능, 파생 클래스 참조
*ptr1 = &r // 기본 클래스 포인터지만 파생 클래스를 가리키기 때문에 
           // 기본 클래스 멤버함수들을 호출하게 됨

만약 Polygon 클래스에도 다각형의 둘레를 반환하는 멤버 함수가 있고, Rectangle에도 rectangle의 둘레를 반환하는 멤버함수가 같은 이름으로 존재한다면, ptr1은 기본 클래스, 즉 Polygon 클래스의 멤버 함수를 실행하기 때문에 오류가 발생할 가능성이 있다.

 

이때 참조되는 객체의 클래스에 정의된 함수를 불러오고 싶다면 가상 함수(virtual)를 사용하면 된다.

 

사용 방법은 멤버 함수의 선언 앞에 virtual을 붙여주면 된다. 

virtual을 붙여주면, 기본 클래스 포인터가 파생 클래스 객체를 참조하고 있어도 참조되는 객체의 함수, 즉 파생 클래스의 멤버 함수를 불러 올 수 있다.

 

순수 가상 함수란 기본 클래스에서 멤버함수를 정의하지 않고 자식 클래스에게 넘기는 것으로 표현 방법은 다음과 같다.

ex) virtual void func_name() = 0 ;

 

추상 클래스는 이러한 순수 가상 함수로만 이루어진 클래스를 말하며 이 클래스는 포인터 선언만 가능하고 객체 선언은 불가능하다.

 

https://github.com/kimtaehyun98/-

kimtaehyun98/-