링크드 리스트

링크드 리스트란 해석하면 연결 리스트로 자료구조의 일종이다. 

자료값을 갖는 Node를 계속해서 이어가는 구조를 뜻하는데, 동적 배열과 비교해서 삽입, 삭제가 간편하다. 

동적배열은 삽입을 하거나 삭제할 때 해당 위치 이후의 자료들을 한 칸씩 당기거나 밀어야 하는데, 

링크드리스트는 포인터를 이용하기 때문에 그런 번거로움이 없고 중간에 이어주기만 하면 된다.

하지만 배열에 비해 접근이 불편하다는 단점이 있다. 배열은 인덱스에 해당하는 크기만큼 시작위치에서 더해서 접근하면 되지만

링크드 리스트는 인덱스가 없기때문에 Head부터 차례대로 조사하며 모든 리스트를 검색해야한다. 최악의 경우 O(N)이 걸린다는 말이다.

그럼에도 삭제, 삽입에서의 메리트가 크기 때문에 사용한다. 

C++ STL의 list를 사용해도 되지만 구조를 잘 이해하기위해 오랜만에 직접 코딩해봤고 도움이 됐다.

 

 

list를 사용함에 있어서 정적 할당과 동적 할당의 다른 방식으로 생성했다. 차이점이라면 정적할당으로 생성한 list는 스택 영역에 크기를 차지하고 동적 할당으로 생성한 list2는 힙 영역에 생성된다. 따라서 delete list2를 하기 전엔 메모리가 해제되지 않는다. 

---

코드 원본 : https://github.com/chosh95/STUDY/blob/master/Algorithm/%EB%A7%81%ED%81%AC%EB%93%9C%EB%A6%AC%EC%8A%A4%ED%8A%B8.cpp

chosh95/STUDY

#include <iostream>
using namespace std;

class Node {
	private:
		Node* next;
		int num;
	public:
		Node(int n) : num(n) { next = NULL; }
		friend class linkedList;//friend 선언이 번거로우면 struct로 선언할 것.
};

class linkedList {
	private:
		Node* head;
		Node* tail;

	public:
		int size;
		linkedList(int);
		void pushBack(int);
		void deleteNode(int);
		void show();
		void popFront();
		void popBack();
		void insert(int, int);
		int Size() { return this->size; }
};

linkedList::linkedList(int n){
	head = tail = new Node(n);
	size = 1;
}
void linkedList::pushBack(int n) {
	Node* tmp = new Node(n);
	if (head == NULL) head = tail = tmp;
	else tail->next = tmp;
	tail = tmp;
	size++;
}
void linkedList::deleteNode(int value) {
	Node* tmp = head;
	Node* tmp2 = head;
	while (tmp2 != NULL) {
		if (tmp2->num == value) break;
		else {
			tmp = tmp2;
			tmp2 = tmp2->next;
		}
	}
	if (tmp2 == NULL) cout << value << "값을 갖는 노드가 없습니다.\n";
	else {
		tmp->next = tmp2->next;
		delete tmp2;
		size--;
	}
}
void linkedList::show() {
	if (head == NULL) cout << "Empty\n";
	else {
		Node* tmp = head;
		for (int i = 1; i <= size; i++) {
			cout << tmp->num << " -> ";
			tmp = tmp->next;
		}
		cout << "사이즈는 : " <<size<<"입니다.\n";
	}
}
void linkedList::popFront() {
	Node* tmp = head;
	head = head->next;
	delete tmp;
	size--;
}
void linkedList::popBack() {
	Node* tmp = head;
	Node* tmp2 = head;
	while (tmp2->next != NULL) {
		tmp = tmp2;
		tmp2 = tmp2->next;
	}
	size--;
	tail = tmp;
	tmp->next = NULL;
	delete tmp2;
}
//idx위치에 value 값을 갖는 노드를 삽입
void linkedList::insert(int idx, int value) {
	Node* tmp = head;
	int cnt = 1;
	while (true) {
		if (cnt == idx) {
			Node* newNode = new Node(value);
			newNode->next = tmp->next;
			tmp->next = newNode;
			break;
		}
		else {
			cnt++;
			tmp = tmp->next;
		}
	}
	size++;
}
int main()
{
	//정적할당
	linkedList list(1);
	list.pushBack(2);
	list.pushBack(3);
	list.pushBack(4);
	list.pushBack(5);
	list.show();

	list.popFront();
	list.insert(1, 10);
	list.popBack();
	list.show();

	list.deleteNode(4);
	list.deleteNode(50);
	list.show();

	//동적할당
	linkedList* list2 = new linkedList(10);
	list2->pushBack(20);
	list2->pushBack(30);
	list2->pushBack(40);
	list2->show();
}