연결 리스트(C++)

연결 리스트 : 노드들이 비연속적으로 힙 메모리 상에 연결되어 있는 구조

노드가 힙 메모리 상에 연속해서 존재하지 않는다. 

리스트는 첫 번째 노드의 주소값만 가지고 있는다.

 

노드 : 데이터를 저장하는 기본 단위 

struct Node {
	int data;
	struct Node* nextNode;
};

struct List {
	Node* headNode; // 리스트의 첫 번째 노드의 주소
	int count; // 노드 개수
};

 

가변배열은 데이터가 들어갈 공간을 미리 만들어야 되는데 연결 리스트는 데이터가 추가될 때 힙 메모리에 공간을 생성한다. 

// 초기화
void InitList(List* list) {	
	list->headNode = nullptr;
	list->count = 0;
}

 

리스트의 맨 마지막 노드뒤에 새로운 노드를 연결

void PushBack(List* list, int data) {

	Node* newNode = (Node*)malloc(sizeof(Node)); // 노드 size 만큼의 공간을 힙 메모리 영역에 생성한다. 
	newNode->nextNode = nullptr;
	newNode->data = data;

	if (list->headNode == nullptr) {
		list->headNode = newNode;
	}
	else {
		// 리스트 안에 데이터가 1개 이상 있음 
		// 리스트 안에 있는 마지막 노드를 찾아야 됨 
		Node* node = list->headNode;
		while (node->nextNode != nullptr) {
			node = node->nextNode;
		}
		node->nextNode = newNode;
	}
	
	list->count++;
}

 

※ 연결 리스트의 노드들이 힙 메모리 영역에 저장되는 이유는 

stack 영역은 컴파일시 크기가 결정되기 때문에 노드가 계속 생성되서 stack 영역의 크기를 초과하면 stack overflow가 발생 할 수 있기 때문에 heap 메모리 영역에 노드를 생성한다. 

heap 메모리 영역은 스택 메모리 보다 데이터를 할당 할 수 있는 공간이 많지만 

포인터로 메모리 영역을 접근하므로 속도가 느리다.