자료구조 - 연결리스트

• 연결리스트(Linked List)
  연결 리스트는 데이터의 정보와, 다른 데이터의 위치를 포함하는
  구조체(node)들을 연결해놓은 리스트이다.
  
• 단일 연결 리스트 : 하나의 구조체에 데이터 정보와 다음 구조체의 주소를 포함하는 한방향 연결리스트
• 이중 연결 리스트 : 데이터의 정보와 이전 구조체, 다음 구조체의 주소를 포함한 양방향 연결리스트
• 원형 연결 리스트 : 단일 연결 리스트에서 마지막 구조체가 첫 번째(head node)를 다음으로 가르키는 원형 리스트

이중 연결 리스트의 간단한 구현

구조체

멤버 변수:
1. 정보 저장 변수
2. 다음 노드 포인터, 이전 노드 포인터

연결리스트

멤버 변수:
1. 사이즈
2. 시작노드
3. 끝 노드


멤버 함수:

맨 앞으로 노드 추가

맨 끝으로 노드 추가

맨 앞 노드 삭제

맨 끝 노드 삭제

리스트 출력 함수

실행 화면

전체 코드

#include <iostream>
using namespace std;
struct node {
	int data;
	node* next;
	node* prev;
	node(int n) {
		this->data = n;
		this->next = this->prev = nullptr;
	}
};
class linked_list {
private:
	node* start;
	node* tail;
	int size;
public:
	linked_list() {
		this->size = 0;
		this->start = nullptr;
		this->tail = nullptr;
	}
	node* create_node(int n) {
		node* new_node = new node(n);
		return new_node;
	}
	void insert_front(int n) {
		node* new_node = create_node(n);
		if (this->size == 0) {
			this->start = new_node;
			this->tail = new_node;
			size++;
		}
		else {
			this->start->prev = new_node;		// 원래 시작노드의 이전포인터로 추가
			new_node->next = this->start;		// 새로운 노드의 다음포인터에 원래 시작노드
			this->start = new_node;				// 시작노드 변경
			size++;
		}
	}
	void insert_back(int n) {
		node* new_node = create_node(n);
		if (this->size == 0) {
			this->start = new_node;
			this->tail = new_node;
			size++;
		}
		else {
			this->tail->next = new_node;		// 원래 끝 노드의 다음 포인터로 설정
			new_node->prev = this->tail;		// 새로운 노드의 이전포인터에 원래 끝 노드
			this->tail = new_node;				// 끝 노드 변경
			size++;
		}
	}
	void delete_front() {
		if (size == 0) {
			cout << "Error: empty list\n";
			return;
		}
		else {
			node* del_node = this->start;
			this->start = this->start->next;	// 시작노드를 맨앞노드의 다음으로 바꿈;
			delete del_node;					// 메모리 해제
			start->prev = nullptr;
			size--;
		}
	}
	void delete_back() {
		if (size == 0) {
			cout << "Error: empty list\n";
			return;
		}
		else {
			node* del_node = this->tail;
			this->tail = this->tail->prev;		// 끝 노드를 맨 끝 노드의 이전으로 바꿈;
			delete del_node;					// 메모리 해제
			tail->next = nullptr;
			size--;
		}
	}
	void print_list() {
		node* cur_node = start;
		while (cur_node != nullptr) {
			cout << cur_node->data << " ";
			cur_node = cur_node->next;
		}
		cout << "\n";
	}
};
int main() {
	linked_list* ll = new linked_list();
	int cmd;
	while (1) {
		cout << "Insert command number(To see manual, input number 1):";
		cin >> cmd;
		if (cmd == -1) break;
		if (cmd == 1) {
			cout << "-1: break, 1: command manual, 2: insert front, 3: insert back, 4: pop_front, 5: pop_back, 6: print list\n";
			continue;
		}
		else if (cmd == 2) {
			int k;
			cout << "Insert Integer to add: ";
			cin >> k;
			ll->insert_front(k);
		}
		else if (cmd == 3) {
			int k;
			cout << "Insert Integer to add: ";
			cin >> k;
			ll->insert_back(k);
		}
		else if (cmd == 4) {
			cout << "Complete pop_front \n";
			ll->delete_front();
		}
		else if (cmd == 5) {
			cout << "Complete pop_back \n";
			ll->delete_back();
		}
		else if (cmd == 6) {
			cout << "List Status: \n";
			ll->print_list();
		}
		else {
			cout << "Insert again\n";
		}
	}
	return 0;
}