연결리스트 - 요소 추가 시 배열보다 훨씬 편리하다 !

들어만 봤던 Linked List를 드디어 보게 되었다!!
개인적으로 C++에서 가장 매력적으로 다가온 TOOL

array의 한계를 해결할 수 있는 Linked List
데이터 입력 시 주소가 순차적이지 않아 요소를 메모리의 어느 곳에나 둘 수 있음 (크기를 동적으로 할당 가능)

 

연결리스트 구현에서 유념해야 할 것
1. 연결리스트의 연결을 끊지 않게 주의하자.
2. 연결리스트에서 next link의 pointer를 지정할 때 아예 노드의 저장소 자체를 변화시키지 않도록 주의하자.

1번은 그냥 실수를 안 하면 되는 문제이고, 
2번의 경우 개념에서 헷갈릴 수 있다.

class ChainNode {
	friend class Chain<T>;
    public:
    	ChainNode (int element=0, ChainNode *next=0)
           {data = element; link = next;}
}

연결리스트의 강점은 삽입이 간단하다는 것이다. 항목 생성 후 포인터 값만 변경해주면 된다. 
이 때 연결리스트의 Node 모양이 위에서 보이는 코드와 밑에 그림 그려놓은 것처럼

 

자기 자체의 data와 내 뒤에 연결되는 Node의 주소가 연결되어 있다. 이 때 그러면 first->link랑 *second가 같다고 착각할 수 있는데, 
first-> link 값을 바꿀 때는 first라는 노드 속에 next라는 변수 값만 바뀌는 거고(10이라는 node 뒤에 연결되는 애가 달라지는 거다)
이 때 접근 방법: first->link=다른 주소 값; 
*second 값을 바꿀 때는 아예  second가 들어있는 pointer 주소값을 바꾸는 것을 의미한다.
이 때 실수할 수 있는 접근 방법: second=다른 주소 값; 

 

아래는 학교 과제로 썼던 LinkedList 카드 정렬인데,,
개인적으로는 LinkedList로 node를 swap하는 알고리즘을 구현하는 것이 pointer를 바꿔주는 것보다 그냥 data값을 switch해주면 해결되는 과제였기 때문에 좀 이상(??)했다.. (교수님 그게 아니구여..)
LinkedList의 핵심적인 내용을 배우기에 내가 과제의 의도를 잘 파악하지 못한 것 같아

혹시나 LinkedList에 대해 배우고자 이 글을 본다면 다음 예제를 보는 것을 비추합니다..🤣🤣

LinkedList에 삽입/삭제하는 과정의 코드를 구현하는 것이 더 도움될 듯!!

 

LinkedListQueue.cpp

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

//노드 struct 구현 (data값과 nextNode가 존재)
//링크드 리스트 클래스 생성
class LinkedList{
class node { 
	public:
		int data=NULL; //해당 노드의 data 값
		node* nextNode=NULL; //포인터로 nextNode를 가리킨다
		
	};
private:
	node* head;  //노드의 머리부분에 해당하는 포인터를 생성
	node* tail; //노드의 꼬리부분에 해당하는 포인터 또한 생성
public:
	LinkedList() {
		//head 와 tail의 포인터를 초기화;
		head = NULL;
		tail = NULL;
	}
	//첫번째의 node 추가
	void addFrontNode(int n) {
		node* temp = new node; //새로운 노드 하나 생성
		temp->data = n; //temp의 데이터는 n
		//LinkedList가 비어있으면
		if (head == NULL) {
			//첫 head의 포인터를 temp로 가져오기
			head = temp;
			//tail도 똑같이! 그래서 총 하나의 노드만이 만들어지는 거임(대신 head든 tail이든 찾을 때 같은 값을 도출하게 됨
			head->nextNode = tail;
		}
		//LinkedList에 데이터가 있으면 맨 앞에 있는 애랑 연결해주면서 맨 앞에다가 넣기
		else {
			//temp의 nextNode는 head
			temp->nextNode = head;
			//head는 다시 temp의 포인터로 가져온다.
			head = temp;
		}
		display(head);
	}
	//정렬해주는 함수
	
	void swapsort(int index) {
		//맨 처음 카드를 정렬하는 함수와 그다음부터 swap하는 함수를 따로 분리했다.
		//그 이유는 head부분을 할당해줄 때 맨 처음에 swap을 하는가/ 하지않는가로 쉽게 할당해줄 수 있기 때문.
		node* p = head;
		if (p->nextNode != tail and p != tail) { 
			if (p->nextNode->data < p->data) {
				cout << "정렬합니다.\n"; //입력으로 받은 카드와 2번째 카드를 비교할 시 swap을 해야하는 상황이라면 정렬을 시작한다.
				node* r = new node; //새로운 노드인 r을 만든다.
				r = p->nextNode; //r은 입력으로 받은 카드의 nextNode로 할당해준다.
				p->nextNode = (p->nextNode)->nextNode; //입력받은 카드의 nextNode는 그 다음다음 카드로 할당해준다. 
				r -> nextNode = p; //swap해야 하는 대상이 되는 카드의 nextNode는 우리가 입력으로 받은 카드로 지정한다.
				head = r; //이렇게 p와 r을 바꿨으므로 head는 무조건 r이 된다. 
				display(head); //head부터 차근차근 보여주는 함수
			}
		}
		sortiterator(p,index);//이후 두번째 카드부터도 swap할 수 있는지 판단하러 들어간다.
	}
	void sortiterator(node* p, int index) {
		if (p-> nextNode != tail and p != tail) { //판단하려는 카드, 또는 그 다음 카드가 tail이라면 의미가 없어진다.
			if (p->nextNode->data < p->data) { //만약 카드의 다음카드값이 카드값보다 작다면
				node* s = p->nextNode; //s라는 노드포인터는 앞쪽 카드의 nextNode
				node* q = s->nextNode; //q라는 노드포인터는 뒷쪽 카드의 nextNode
				node* bridge = new node; //새로운 node bridge를 만든다
				bridge->data = p->data; //bridge의 data에는 p의 data를 넣어 p의 복제 노드를 하나 만든다
				bridge->nextNode = q; //bridge의 다음 노드는 q를 가리키게 한 후
				int bridge_s = s->data; //bridge_s라는 변수에 s의 값을 넣는다.
				s = p; //s를 p로 바꾸면 포인터 자체가 바뀌게 된다.
				s->data = bridge_s; //s의 data를 bridge_s로 바꿔준다.
				s->nextNode = bridge; //s의 nextNode를 bridge로 할당해준다.
				display(head); //head부터 print해준다.
				sortiterator(bridge, index); //재귀함수로 bridge부터 다시 swap해준다.
			}

		}
	}
	//첫번째 노드 가져오기

	//LinkedList 출력
	void display(node* head) {
		if (head == NULL) { //값이 NULL이 나온다면 끝난 것을 의미한다.
			cout << endl;
		}
		else {
				if (head->data / 13 == 1) { //S 카드에 해당하는 숫자 검열해서 출력
					int num = (head->data + 1) % 13;
					if (num == 0) { num = 13; }
					cout << 'S' << num;
				}
				else if (head->data / 13 == 2) { //D
					int num = (head->data + 1) % 13;
					if (num == 0) { num = 13; }
					cout << 'D' << num;
				}
				else if (head->data / 13 == 3) {//H
					int num = (head->data + 1) % 13;
					if (num == 0) { num = 13; }
					cout << 'H' << num;
				}
				else if (head->data / 13 == 4) { //C
					int num = (head->data + 1) % 13;
					if (num == 0) { num = 13; }
					cout << 'C' << num;
				}
				else {
					cout << 0;
				}
				cout << ' ';

			display(head->nextNode); //재귀함수로 그 다음 노드를 또 출력하러 들어간다.
		}
		
	};
};

main.cpp

#include <random>
using namespace std;
#include "LinkedListQueue.cpp"

//메인 함수
int main() {
	LinkedList a;

	int index = 0;
	while (index < 5) {
		cout << "\n랜덤으로 카드를 선택해 집어넣습니다.\n";
		std::random_device rd;
		std::mt19937 gen(rd());
		std::uniform_int_distribution<int> dis(13, 64);//카드 숫자는 13부터 64 중 랜덤으로 받는다.
		a.addFrontNode(dis(gen));
		a.swapsort(index);
		index++;
	}
}