[자료구조] [5] 포인터, 연결리스트

* 포인터는 내가 중요하다고 생각되거나, 까먹었거나, 확실하게 알지 못했던 부분만 정리.

 

포인터

- 포인터의 활용

• void* p;          // 임의 자료형의 주소를 저장하기 위한 포인터

void* p는 아무것도 가리키지 않는 포인터를 의미. void 포인터는 필요할 때 마다 다음과 같이 다른 포인터로 바꾸어서 사용한다.

void* p;
int* pi; 
pi = (int*)p;          // p를 정수 포인터로 변경해 pi로 대입 

 

- 포인터 연산

다음의 문장들을 잘 구분하여 사용하여야 한다.

• p : 포인터
• *p : 포인터가 가리키는 값
• *p++ : 포인터가 가리키는 값을 가져온 다음, 포인터를 한 칸 증가
• *p-- : 포인터가 가리키는 값을 가져온 다음, 포인터를 한 칸 감소
• (*p)++ : 포인터가 가리키는 값을 증가시킴

 

- 포인터와 배열

배열 이름은 첫 번째 배열 원소의 주소와 같다. 배열의 이름은 상수 포인터이기 때문에 주소를 바꿀 수는 없다.

아래와 같이 포인터에 인덱스 연산자를 적용해 배열과 같이 사용할 수도 있다.

 

int A[5];
p = A;          // 배열 주소 p에 복사
p[3] = 20;     // 포인터를 배열처럼 사용 할 수 있다(A[3]=20과 동일)

 

 

- 포인터 사용시 주의점

• 포인터가 어떤 값을 가리키고 있지 않을 때는 NULL,nullptr로 설정
• 초기화가 안 된 포인터 변수가 가리키는 곳에 자료를 저장하면 절대 안된다.

char* pc;    // 초기화 안된 포인터 pc
*pc = 'E';   // 이러면 안 됨!

• 자료형이 다른 포인터 끼리 변환할 때는 명시적 형 변환 사용.

int* pi;
float* pf;
pf = (float*)pi;   // 명시적 형 변환

 

 

- 자체 참조 구조체

자체 참조 구조체(self-referential structure)는 멤버 중에 자기 자신을 가리키는 포인터가 한 개 이상 존재하는 특별한 구조체.

예) 연결 리스트에서 사용되는 노드 구조체

typedef struct ListNode {
 char data[10];
 struct ListNode* link;
} Node;

 

 

- 포인터와 동적 메모리 할당

- C 스타일 동적 메모리 할당/해제

• void* malloc(int size)

size 크기(단위: byte)의 메모리 블록을 할당하고, 이 메모리 블록 시작 주소를 반환. 반환 주소가 void* 형이므로 적절한 자료형으로 형변환시켜 사용. 메모리 확보가 불가능하면 NULL을 반환.

char* pc = (char*)malloc(5);     // 문자 5개 저장할 공간 할당. char형은 1byte이므로 size인자로 5.
int* pi = (int*)malloc(sizeof(int));   // int를 저장할 공간 할당.

 

• void* calloc(int num,int size) 

배열 형식의 메모리를 할당. 배열 요소의 크기는 size 바이트, 개수는 num. 요소들이 0으로 초기화 된다는 점만 malloc()과 다르다.

 

• void free(void* ptr)

동적으로 할당되었던 메모리 블록을 시스템에 반납. ptr은 할당되었던 메모리 블록을 가리키는 주소값.

free(pc);
free(pi);

 

- 주의점

동적으로 할당된 메모리는 반드시 포인터에 저장해야 한다! 그래야 주소를 알고 할당된 메모리를 사용할 수 있고 해제할 수 있다.

 

 

---

 

 

연결 리스트

- 연결된 표현

데이터와 링크로 구성되어 있고 링크가 노드들을 연결하는 역할.

용량이 고정되지 않으므로 연결된 표현은 스택,큐,리스트,덱,트리,그래프 등 여러 가지 자료구조를 구현하는데 사용.

 

- 연결 리스트

이와 같이 물리적으로 흩어져 있는 자료들을 서로 연결하여 하나로 묶는 방법.

• 데이터를 한군데 모아두지 않는다.
• 데이터들은 메인 메모리상의 어디에나 흩어져서 존재할 수 있다.
• 순서를 유지하기 위해 각각의 데이터는 다음 데이터를 가리키는 포인터를 갖는다.
• 첫 데이터에서부터 순서대로 포인터를 따라가면 모든 데이터를 방문할 수 있다.
• 연결 리스트는 메모리를 할당할 수 있는 한 크기가 고정되지 않고 계속 자료를 넣을 수 있다.
• 중간에 자료를 삽입하는 것이 용이하다. 삭제 연산도 마찬가지이다.

만약 배열에서 중간에 어떤 자료를 추가하려면 그 위치 이후의 모든 자료들을 뒤로 하나씩 복사한 후 그자리에 자료를 넣어야 한다.

하지만 연결리스트는 데이터 B와 C사이에 데이터 N을 삽입하고자 한다면,

데이터 B에서 N을 가리키도록 하고 N이 C를 가리키도록 링크만 수정해 주면 된다.

삭제 연산도 마찬가지로 데이터들을 옮길 필요 없이 데이터들을 연결하는 포인터만 수정하면 된다.

• 데이터 저장을 위한 메모리를 공간이 필요할 때 마다 동적 할당해 쉽게 추가할 수 있다. 배열은 사용하지 않더라도 한꺼번에 많은 공간을 할당해야 한다.

 

- 연결리스트의 구조

• 노드(Node) : 데이터를 담는 상자. 연결리스트는 노드들의 집합이며 이들은 데이터를 저장하고 서로 연결되어 있다.

일반적인 노드는 데이터 필드와 링크 필드로 구성되어 있다.

• 데이터 필드 : 저장하려는 자료형의 데이터가 들어간다.
• 링크 필드 : 다른 노드를 가리키는, 즉 다른 노드의 주소를 저장하는 포인터 변수가 있다. 이 포인터로 현재 노드에 연결된 다음 노드를 알 수 있다.

 

• 헤드 포인터(Head Pointer) : 연결리스트에서 첫 번째 노드의 주소를 저장하는 포인터.

연결리스트는 첫번째 노드를 알면 링크로 매달려 있는 모든 노드에 순차적으로 접근할 수 있기 때문에 이 주소를 반드시 저장해야 한다.

마지막 노드는 더 이상 연결할 노드가 없기에 링크 필드의 값을 NULL로 설정해 이 노드가 마지막임을 표현.

 

 

- 연결 리스트의 특징

• 노드들은 메모리의 어느 곳에나 위치할 수 있다. 인접한 노드가 인접한 메모리에 있지도 않다. 즉, 노드들의 주소가 연결리스트 상의 순서와 동일하지 않다.
• 연속적인 기억공간이 없어도 데이터 저장이 가능하고 미리 공간을 확보할 필요도 없다. 필요할 때 마다 동적으로 노드를 생성해 연결하기 때문이다.
• 링크 필드를 위한 추가 공간이 필요하다.
• 동적 할당과 해제가 너무 빈번하게 일어나면 메모리 관리를 위한 처리시간이 길어져 프로그램이 느려질 수 있다는 단점.

 

- 연결 리스트의 종류

 

1. 단순 연결 리스트 : 하나의 방향으로만 연결, 맨 마지막 노드 링크필드는 NULL값
2. 원형 연결 리스트 : 단순 연결 리스트와 같지만 맨 마지막 노드의 링크 값이 다시 첫 번째 노드를 가리킴.
3. 이중 연결 리스트 : 각 노드마다 링크 필드(포인터)가 2개씩 존재. 각각의 노드는 선행/후속 노드를 모두 가리킬 수 있다.

 

 

 

연결리스트로 int 저장 스택 구현

연결된 스택은 크기가 제한되지 않고 필요한 메모리만 사용한다는 장점과, 링크 필드 때문에 메모리 공간을 조금 더 사용하는 단점이 있다.

 

• 연결리스트로 구현한 스택에서 top은 헤드 포인터. 이것은 연결된 스택의 유일한 데이터 이다.
• push(),pop() 구현할 때 노드의 동적 할당과 해제에 주의
• size() 구현할 때 연결리스트는 전체 노드를 방문하려면 top 부터 하나씩 다음 노드를 따라가면서 몇 개의 노드가 연결되었는지 확인해야 함. 마지막 노드는 링크필드가 NULL 인것으로 알 수 있다.

 

- 코드

#include <iostream>

using namespace std;

typedef int Element;
typedef struct LinkedNode{
	int data; // 데이터 필드
	LinkedNode* link; // 링크 필드 : 다음 노드 가리킴
}NODE;

NODE* top = nullptr; // 스택의 top == 연결리스트의 헤드포인터

void init_stack() {
	top = nullptr; // 공백상태로 만드는 것
}
bool empty() {
	return top == nullptr;
}
void push(Element e) {
	NODE* node = new NODE;
	node->data = e;
	node->link = top; // 1.push한 노드가 스택의 top에 있던 노드(혹은 nullptr)를 가리키고
	top = node; // 2.top 헤드포인터가 push한 노드를 가리키게
}
Element pop() { // 가장 최근에 삽입된 요소를 꺼내 반환.
	if (empty()) {
		printf("스택이 공백상태");
		return -1;
	}
	
	NODE* node;
	Element e;
	
	node = top; 
	//1. pop할 노드의 다음 노드를 top이 가리키고
	top = node->link;
	//2. pop할 노드의 데이터를 복사
	e = node->data;
	//3. pop할 노드 동적 할당 해제
	delete node;
	return e; //4. 복사해둔 데이터 return
}

Element peek() { // 삭제하지 않고 top만 반환
	if (!empty()) {
		return top->data;
	}
}

int size() { // 스택의 원소 개수
	NODE* tmp = top;
	int cnt = 0;
	while (tmp != nullptr) {
		tmp = tmp->link;
		++cnt;
	}
	return cnt;
}

void destroy_stack() { // 연결된스택 사용 끝날 때 동적할당 해제
	while (!empty())
		pop();
}

void print_stack(const char* msg) {
	printf("%s --> size=%2d : ", msg, size());
	for (NODE* p = top; p != nullptr; p = p->link) // 연결리스트 특성상 가장 최근에 삽입된 데이터부터 출력
		printf("%2d", p->data);
	printf("\n");
}


void main() {
	init_stack();
	for (int i = 0; i < 10; ++i)
		push(i);

	print_stack("연결된스택 push 9회");
	pop();
	pop();
	pop();
	print_stack("연결된스택 pop 3회");
	destroy_stack();
	print_stack("연결된스택 delete");
}

연결된 스택 구현 실행 결과