[자료구조] C++로 쉽게 풀어쓴 자료구조 : 5장, Linked List

내돈내고 내가 공부한것을 올리며, 중요한 단원은 저 자신도 곱씹어 볼겸 가겹게 포스팅 하겠습니다.

1) 5장. 연결리스트

 

연결리스트의 개념 자체는 어렵지는 않다. Node마다 데이터를 저장하는 곳과, 다음 node를 가리킬 포인터변수가 있으며, 이를 필요할때마다 추가하면서 기차처럼 이어가는 형태이다. 열혈 자료구조에서도 C로 여러번 구현한 내용이다.

 

Node class안에 Student 객체를 포함시키는 일반적인 방법이 난 가장먼저 떠올랐다. 다음처럼 말이다.

class Node {
	Student st; // 데이터 필드
	Node* link; // 링크 필드
public:
 ...
};

 

열혈 자료구조를 공부할때 이런 형태로 많이 구현해봤기 때문이다. 하지만 C++의 장점을 활용하는 코드가 나의 머리를 강타하였으니..

그방법은 바로

상속!!

을 이용하는 방법이다. Node가 Student를 상속한 derived class가 되면 Node에서는 링크 필드만 생각하면된다. 데이터 필드의 처리를 고민할 필요가 없어진 것 이다. 상속의 강렬함을 여기서한번 느끼고 간다.

 

Student.h

#pragma once
#include <iostream>
#include <string>
using namespace std;

class Student {
	int id;
	string name;
	string dept;
public:
	Student(int i = 0, string n = "", string d = "") { set(i, n, d); }
	void set(int i, string n, string d) {
		id = i;
		name = n;
		dept = d;
	}
	void display() {
		cout << " 학번:" << id << " 성명:" << name << " 학과: " << dept << endl;
	}
};

 

 

Node.h

#pragma once
#include "Student.h"

class Node : public Student {
	Node* link;
public:
	Node(int id = 0, string name="", string dept="") 
		: Student(id, name, dept) {
		link = nullptr;
	}
	Node* getLink() { return link; }
	void setLink(Node* ptr) { link = ptr; }
};

 

간단하게 Student를 상속받고있다. 이 Node를 사용하여 Linked Stack을 구현해 보면 다음과 같다.

 

LinkedStack.h

#pragma once
#include "Node.h"

class LinkedStack {
	Node* top;
public:
	LinkedStack() : top(nullptr) {}
	~LinkedStack() {
		while (!isEmpty())
			delete pop();
	}
	bool isEmpty() { return top == nullptr; }

	void push(Node* p) {
		if (isEmpty()) top = p;
		else {
			p->setLink(top);
			top = p;
		}
	}
	Node* pop() {
		if (isEmpty()) return nullptr;
		Node* temp = top;
		top = temp->getLink();
		return temp;
	}
	Node* peek() {
		if (isEmpty()) return nullptr;
		return top;
	}
	void display() {
		cout << "[LinkedStack]\n" << "\n";
		for (Node* p = top; p != nullptr; p = p->getLink())
			p->display();
		cout << endl;
	}
};

 

참고로 교제에서는 NULL값을 사용하는데 엄밀히 말하면 nullptr을 사용하는것 이 더 좋다. NULL은 사실 정수형 0이다. #define NULL 0 으로 되어있는 메크로에 불과하다. 따라서 정확하게 포인터의 의미를 포함시키려면 nullptr을 사용해주는것이 옳다 배웠다. 이는 C++11 에서부터 추가되었다고 한다.

 

main.cpp

#include "LinkedStack.h"

int main()
{
	LinkedStack stack;
	stack.push(new Node(20210001, "리눅스", "임베디드학과"));
	stack.push(new Node(20210011, "우분투", "우분투학과"));
	stack.push(new Node(20210111, "칼리", "칼리학과"));
	stack.display();

	Node* node = stack.pop();
	cout << "pop_element" << "\n";
	node->display();
	cout << endl;
	delete node;

	stack.display();

	return 0;
}

 

결과는 다음과 같이 정상출력된다.

 

이번에는 Queue를 연결리스트로 구현해 보자. int형 데이터를 갖는 node 로 구현해 보자.

 

Node.h

#pragma once
#include <iostream>

class Node {
	Node* next;
	int data;
public:
	Node(int value = 0) : data(value), next(nullptr) {}
	Node* getLink() { return next; }
	void setLink(Node* p) { next = p; }
	void display() { std::cout << data << " "; }
};

 

 

LinkedQueue.h

#pragma once
#include "Node.h"

class LinkedQueue {
	Node* front;
	Node* rear;
public:
	LinkedQueue() : front(nullptr), rear(nullptr) {}
	~LinkedQueue() { while (!isEmpty()) delete dequeue(); }

	bool isEmpty() { return front == nullptr; }
	void enqueue(Node* p) {
		if (isEmpty()) front = rear = p;
		else {
			(*rear).setLink(p);
			rear = p;
		}
	}

	Node* dequeue() {
		if (isEmpty()) return nullptr;
		else {
			Node* temp = front;
			front = front->getLink();
			if (front == nullptr) rear = nullptr;
			return temp;
		}
	}
	Node* peek() { return front; }
	void display() {
		std::cout << "큐 내용 : " << std::endl;
		for (Node* p = front; p != nullptr; p = p->getLink())
			p->display();
		std::cout << std::endl;
	}
	
};

 

 

main.cpp

#include <iostream>
#include "LinkedQueue.h"
using namespace std;

int main(){
	LinkedQueue que;
	for (int i = 1; i < 10; i++)
		que.enqueue(new Node(i));
	que.display();

	delete que.dequeue();
	delete que.dequeue();

	que.display();

	return 0;
}

 

결과는 다음과 같다.

 

---

2) 나의 현황

◆ 예전에 처음 연결리스트 배웠을때는 진짜 어려웠었는데, 2번째 보는거라 그런지 훅훅 나갔다. 빨리 6장을 들어가 좀더 심화된 연결리스트에 대해서 공부해봐야 겠다.

​

이글의 모든 사진과 내용의 출처는 천인국, 최영규 님께 있습니다.