3-2강 - 자료구조 & C, C++ programming 2 (Linked List management, Stack & Queue)

3. Linked List Management

구현은 크게 2가지입니다. (array로 구현, dynamic memory allocation)

0) Singly Linked List 기본 구조 

typedef struct _SLL {
	int i;
	struct _SLL *p;
} SLL

1> 필요한 field가 더 있다면 더 추가해도 된다. (양방향성을 구현할 수도 있다.)

2> 위 구조를 이용해서 stack, queue 등을 구현할 수 있다.

3> 단점 :  탐색에 O(n)의 시간 복잡도가 발생한다.

 

1) Linked List Management의 필요성 

allocation/deallocation 함수인 malloc과 free는 속도가 빠른 함수가 아니다. (new와 delete도)

또한, 이를 호출하는데도 많은 시간이 필요하다. 

→ 메모리를 효율적으로 관리할 필요가 있다. 

 

2) Storage Pool을 이용한 SLL 메모리 관리

사용하지 않는 메모리를 storage pool이라는 곳에서 linked list 형태로 보관한다.

1> allocSLL()

• storage pool에 미사용 메모리가 있으면 이를 프로그램에 가져다 주고
• storage pool에 미사용 메모리가 없으면 system memory에서 malloc으로 프로그램에 가져다 준다.

2> freeSLL()

• free()가 아니라 storage pool에 메모리를 저장한다. 

 

3) C로 구현

1> 헤더 파일

#include <stdlib.h>
#define NONE -1

- stdlib.h : exit() 함수 사용하기 위해 선언

- NONE : 메모리 할당과 함께 -1로 초기화 한다. 이 때, 값을 가지지 못하는 data를 디버깅할 때 사용할 수 있다. (단 data value가 모두 양수라는 전제 필요)

2> global function

extern void errorExit (const char *s);

- 심각한 오류 부분에 호출해서 error message를 출력한다.

3> global variables

SLL *SLL_pool = NULL;
unsigned long SLL_cnt = 0;
unsigned long UsedMemoryForSLLs = 0;

- SLL *SLL_pool = NULL : storage pool의 header

- SLL_cnt : SLL에 저장된 element의 개수 (allocSLL에서 +1, freeSLL에서 -1) (수행을 완료하면 이 값은 0이 된다.)

- UsedMemoryForSLL : 현재 메모리를 얼마나 쓰고 있나를 저장 (굳이 쓰지 않아도 된다.) 

 

4> allocSLL()

SLL *allocSLL(void) { // allocate an SLL storage
	SLL *ptr;
	if (SLL_pool == NULL) {// pool is empty
		ptr = (SLL *)malloc(sizeof(SLL)); // call malloc
		if (ptr == NULL)
			errorExit("Error in Alloc_SLL");
		UsedMemoryForSLLs += sizeof (SLL)
		ptr->i = NONE;
	}
    
	else {
		ptr = SLL_pool;
		SLL_pool = ptr->p;
	}
    
	ptr->p = NULL ; // clear ptr
	++SLL_cnt;
	return ptr;
}

 

- if : storage pool에 SLL이 없는 경우

• ptr이라는 변수로 SLL 메모리를 할당 받고
• 할당이 안 된 경우에 errorExit()을 이용해 error message를 출력하도록 한다.
• 그리고 할당과 동시에 내부 value를 NONE(-1)로 초기화 한다.

- else : storage pool에 SLL이 있는 경우

• [1] SLL_pool이 가리키는 SLL 1개(1번째 SLL)를 ptr이 (p로) 가리키게 한다.
• [2] ptr가 가리키는 SLL (2번째 SLL)를 SLL_pool이 가리키게 한다.

- 그 이후

• [3] ptr는 storage pool의 원소를 가리키게 하지 않는다.
• SLL_cnt를 1 증가시킨다.
• SLL의 pointer인 ptr를 return한다.

5> freeSLL()

void freeSLL (SLL *ptr) {
	//free *ptr (move it to SLL_pool
	if (ptr->i == NONE) {
	errorExit("This is already freed(freeSLL)");
	}
	ptr->i = NONE;
	ptr->p = SLL_pool; // p->p points to SLL_pool
	SLL_pool = ptr ; // p becomes the 1st element in the SLL_pool
	--SLL_cnt ; // reduce # of active SLLs by one
}

• parameter로 받은 p(SLL pointer)가 할당받은 값이 없는 경우 error message 출력
• free 하는 경우에도 내부 값을 NONE(-1)로 초기화
• ptr의 p(pointer)가 SLL_pool이 되도록 한다. (ptr이 SLL_pool의 첫 번째 원소를 가리키게 한다. -> 그로 인해 ptr의 i가 첫 번째 원소가 된다.)
• SLL_pool은 현재 2번째 원소를 가리키고 있는 상황이므로 첫 번째 원소를 가리키고 있는 ptr이 되도록 한다.
• SLL_cnt는 1 감소

6> freeSLL_pool() 

pool storage를 비워내는 기능을 합니다.

void freeSLL_pool(void) { // clear SLL_pool
	SLL *ptr = SLL_pool;
    
	while (ptr!= NULL) {
	SLL_pool = ptr->p; // get the next pointer
    free(p); // free *p
	UsedMemoryForSLLs -= sizeof(SLL);
	p = SLL_pool; // repeat while p != NULL
	}
    
	if (SLL_cnt != 0) {
	errorExit("Non zero SLL_cnt after cleanup");
	}
}

 

 

4.  Singly Linked List로 Queue, Stack 구현

1) Stack Implementation

1> pushSLL()

void pushSLL (SLL **ST, SLL *ptr) {
	// insert p to the top of stack ST
	ptr->p = *ST;
	*ST = ptr;
}

ST는 stack의 top 부분 pointer를 의미한다.

• [1] ptr의 p(pointer)에 ST가 가리키는 (stack의 top을 가리키는) *ST를 할당한다. (그러면 ptr도 stack의 top SLL을 가리킨다.)
• [2] 그리고 ST(주소, pointer)가 가리키는 부분이 ptr이다. (ST가 ptr을 가리킨다.)

 

2> popSLL()

SLL popSLL(SLL **ST) {
	// remove and return p at the top of ST
	SLL *p = *ST;
    
	if ( (* ST)->p == NULL ) // 괄호 주의
		*ST = NULL ; // p the only elm in ST
	else
		*ST = (*ST) -> p ; // ST points next elm
	
    return p;
}

• *ST처럼 stack의 top을 가리키는 SLL pointer인 p 정의
• if : p가 비어있다면 *ST도 똑같이 비어있고
• else : p가 비어있지 않다면 *ST가 가리키는 pointer(다음 원소 가리키는 중)가 *ST가 되게 한다. (*ST는 2번째 원소를 가리키게 된다.)
• 복사된 p를 return한다.

2) Queue Implementation

1> Add at end

void enqueueSLL(SLL **Q, SLL **Q_end, SLL *p) {
	// p->p == NULL 이어야 한다.
	if (*Q == NULL)
		*Q = p; // Q = ∅인 경우 . Q_end 는 아래에서 설정
	else
		(*Q_end)->p = p; // Q ≠ ∅이면 Q_end 다음에 연결
	
    *Q_end = p ; // 어떤 경우 든 Q_end = p
	return;
}

 

2> pop

SLL dequeueSLL(SLL **Q, SLL Q_end) {
	SLL*p = *Q ; 						// p 를 Q 의 첫 element 로 설정
	if ((* Q)-->p == NULL )  			// p is the only element
		*Q = * Q_end = NULL ; 			// in Q

	else
		*Q = (*Q)->p ; 					// Q 를 Q 다음 원소로 . Q_end 는 불변
	
    return p;
}

 

5. ADT