[C++] 자료구조 - Single Linked List

🌼Single Linked List🌼

정말 간단한 Single Linked List를 만들어봅니다

기능 구현

• empty() 함수로 List 내부가 비어있는지 확인
• size() 함수로 List의 개수 확인
• front() 함수로 List의 맨 앞 노드 확인
• end() 함수로 List의 맨 뒤 노드 확인
• addFront() 함수로 List의 맨 앞에 새로운 노드 추가
• addEnd() 함수로 List의 맨 뒤에 새로운 노드 추가
• showList() 함수로 List 나열

헤더파일

#include <iostream>
#include <vector>
#include <string>

Node 클래스 생성

Node 하나당 이름, 번호를 가지고 있고,
Node 클래스에 print() 함수를 같이 만들어 줬다.

class Node {
public:
	string name;
	int num;
	Node* next;

	Node(string name, int num) { //생성자 
		this->name = name; 
		this->num = num;
		next = NULL;
	}

	void print() {
		cout << this->name << " " << this->num << endl;
	}

};

List 클래스 생성

List 클래스에는 내장된 함수가 많으니 따로따로 구분했다.

1. 변수와 클래스 생성자

Node* head; //처음 노드
Node* tail; //마지막 노드
int n; //노드의 개수

List() { //생성자
	head = tail = NULL;
	n = 0; 
}

2. size(), empty() 함수

int size() {
	return n;
}

bool empty() {
	return (n == 0);
}

여기서 empty()함수는 bool 형으로,
n이 0이면 1을 반환하고 n이 1이면 0을 반환한다.

3. front(), end() 함수

void front() {
	if (empty()) {
		cout << "empty" << endl;
		return;
	}
	head->print();
}

void end() {
	if (empty()) {
		cout << "empty" << endl;
		return;
	}
	tail->print();
}

front함수는 node가 0개인 경우 empty를 출력하고,
그 외의 경우에는 맨 앞에 있는 노드(head)를 print()해준다.
print()함수는 노드의 name, num을 출력한다.

end함수는 front함수와 동일하게 node가 0개인 경우 empty를 출력하고,
그 외의 경우에는 맨 뒤에 있는 노드(tail)를 print()해준다.

4. addFront() 함수

void addFront(string name, int num) {
	Node* newnode = new Node(name, num); //새로운 노드 생성
	if (head == NULL) { 
		head = tail = newnode;
	}
	else { //else 안 적으면 head가 NULL일 때 아래 구문도 생성해버림 
		Node* temp; //임시 포인터
		temp = head; //temp에 기존 head 저장
		head = newnode; //head에 newnode를 저장
		head->next = temp;  //head의 다음 노드를 temp(기존 head)로 지정 
	}
	n++; //노드의 총 개수 +1
}

5. addEnd() 함수

void addEnd(string name, int num) {
	if (head == NULL) { //리스트에 노드가 한 개도 없는 경우
		addFront(name, num); //addFront로 노드 생성
	}
	Node* newnode = new Node(name, num); //새로운 노드 생성
	tail->next = newnode; //맨 마지막 노드(tail) 다음에 newnode를 저장
	tail = newnode; //맨 마지막 노드(tail)을 newnode로 설정
	n++; //노드의 총 개수 +1
}

6. showList() 함수

void showList() {
	if (empty()) { //List가 빈 경우
		cout << "empty" << endl;
	}
	else { //List에 node가 존재하는 경우
		Node* temp = head; //head부터 출력하기 위해 temp 생성
		for (int i = 0; i < n; i++) {
			temp->print(); //노드 출력
			temp = temp->next; //출력 후 다음 노드로 변경 
		}
	}
}

main() 함수

int main() {
	List list;
	int i;
	string name;
	int num;
	string order;

	cin >> i; //몇 번의 명령어를 입력받을 것인가

	for (int x = 0; x < i; x++) {
		cin >> order;
		if (order == "empty") { //리스트가 비어있는지 확인
			cout << list.empty() << endl; //비어있으면 1
		}
		else if (order == "size") { //리스트의 사이즈 확인
			cout << list.size() << endl; 
		}
		else if(order == "front") { //리스트의 맨 앞 노드 확인
			list.front();
		}
		else if (order == "showList") { //리스트 전체 나열
			list.showList();
		}
		else if (order == "addFront") { //리스트의 맨 앞에 노드 추가 
			cout << "이름과 번호를 입력하세요: ";
			cin >> name >> num;
			list.addFront(name, num);
		}
		else if (order == "end") { //리스트의 맨 뒤 노드 확인
			list.end();
		}
		else if (order == "addEnd") { //리스트의 맨 뒤에 노드 추가
			cout << "이름과 번호를 입력하세요: ";
			cin >> name >> num;
			list.addEnd(name, num);
		}
	}
}

_

이렇게 간단하게 List를 작성해봤는데 노드 삭제 기능을 추가하고, 맨 앞과 맨 뒤에만 노드를 추가하는 것이 아닌 임의의 노드의 앞 뒤에 새로운 노드를 생성하는 기능 또한 추가해야 될 것 같다.