[알고리즘] Linked List(연결 리스트)

https://kks227.blog.me/220781402507

리스트(List), 배열(Array), 연결 리스트(Linked List)

(이분 블로그를 정리하기 위해 쓰는 글입니다.)

 

list란 선형적으로 값을 가지고 있는 자료구조이다.

linked list란 배열과 같이 어떤 자료구조를 구현하는 프로그래밍 기법이다.

linked list나 배열을 이용해서 list를 구현할 수 있으며, 두 방법 모두 각각의 장단점을 가지고 있다.

 

배열로 구현할 때

장점: 랜덤 액세스가 가능하다(O(1)의 시간복잡도)

단점: 삽입, 삭제 연산이 오래걸린다(삽입, 삭제 연산하는 위치 뒤의 요소들을 전부 옮겨줘야 하므로) 크기가 고정적이다.

 

linked list로 구현할 때

장점: 포인터로 가리키는 지점의 삽입, 삭제 연산 시 O(1)의 시간복잡도를 보장한다. 크기가 가변적이다.

단점: 랜덤 액세스가 불가능하다(head부터 포인터를 따라가서 접근해야 한다)

 

C++에서는 STL의 <list> 헤더파일에 구현이 되어 있다.

 

#include <iostream>
using namespace std;

class InvalidIndexException {};

template<typename T>
class ListNode {
public:
	T value;
	ListNode<T> *next;

	// 생성자
	ListNode<T>() : next(nullptr) {}
	ListNode<T>(T value1, ListNode<T> *next1) : value(value1), next(next1) {}
};

template<typename T>
class LinkedList {
public:
	int size;
	ListNode<T> *head;

	// 생성자
	LinkedList<T>() : size(0), head(nullptr) {}

	// 소멸자
	~LinkedList<T>() {
		ListNode<T> *t1 = head, *t2;
		while (t1 != nullptr) {
			t2 = t1->next;
			delete t1;
			t1 = t2;
		}
	}

	// 멤버 함수
	void insert(int k, T value) {
		try {
			//예외 처리: 잘못된 인덱스
			if (k < 0 || k > size) throw InvalidIndexException();

			if (k == 0) { // 처음에 삽입
				head = new ListNode<T>(value, head);
			}
			else { // k번째 원소 앞에 삽입
				ListNode<T> *dest = head;
				for (int i = 0; i < k - 1; i++) dest = dest->next;
				dest->next = new ListNode<T>(value, dest->next);
			}
			size++;
		}
		catch (InvalidIndexException e) {
			cerr << "잘못된 인덱스입니다." << endl;
			exit(1);
		}
	}

	void erase(int k) { // k번째 원소를 제거
		try {
			//예외 처리: 잘못된 인덱스
			if (k < 0 || k >= size) throw InvalidIndexException();

			if (k == 0) { // head를 삭제
				ListNode<T> *temp = head->next;
				delete head;
				head = temp;
			}
			else { // k번째 원소 삭제
				ListNode<T> *dest = head, *temp;
				for (int i = 0; i < k - 1; i++) dest = dest->next;
				temp = dest->next->next;
				delete dest->next;
				dest->next = temp;
			}
			size--;
		}
		catch (InvalidIndexException e) {
			cerr << "잘못된 인덱스입니다." << endl;
			exit(2);
		}
	}

	int search(T value) { // 값을 찾아 첫번째 인덱스 리턴, 없으면 -1 리턴
		ListNode<T> *temp = head;
		for (int i = 0; i < size; i++) {
			if (temp->value == value) return i;
			temp = temp->next;
		}
		return -1;
	}
};

template<typename T>
ostream& operator << (ostream &out, const LinkedList<T> &LL) { // 원소들을 한 줄에 차례대로 출력
	ListNode<T> *temp = LL.head;
	out << "[";
	for (int i = 0; i < LL.size; i++) {
		out << temp->value;
		temp = temp->next;
		if (i < LL.size - 1) out << ", ";
	}
	out << "]";
	return out;
}

int main() {
	LinkedList<int> LL;
	LL.insert(0, 1); cout << LL << endl;
	LL.insert(1, 2); cout << LL << endl;
	LL.insert(2, 3); cout << LL << endl;
	LL.insert(0, 4); cout << LL << endl;
	LL.insert(0, 5); cout << LL << endl;
	LL.insert(5, 6); cout << LL << endl;
	LL.insert(4, 7); cout << LL << endl;
	LL.insert(1, 8); cout << LL << endl;
}

 

수업시간에도 몇번 다뤘던거라 그냥 대충보고 넘어가려고 했지만 생소한 C++ 문법들 때문에 한번 되짚어보는 시간을 가졌다.

 

template<typename T>
class ListNode {
public:
	T value;
	ListNode<T> *next;

	// 생성자
	ListNode<T>() : next(nullptr) {}
	ListNode<T>(T value1, ListNode<T> *next1) : value(value1), next(next1) {}
};

 

template<typename T>란? C++에서 제네릭 프로그래밍을 구현하는 방법이다.

그렇다면 제네릭 프로그래밍이 무엇인가? 데이터 형식에 의존하지 않고, 하나의 값이 여러 다른 데이터 타입들을 가질 수 있는 기술에 중점을 두어 재사용성을 높일 수 있는 프로그래밍 방식이라고 한다.

즉, 위의 코드에서는 ListNode에 여러가지 데이터 타입을 넣기 위해 template을 사용한 것이다.

ListNode 클래스를 선언해줄 때, ListNode<int> 이렇게 선언을 해 주면, 클래스 내부의 T가 int형으로 선언된다.

 

클래스 템플릿에 대한 설명: https://blockdmask.tistory.com/45

[C++] template(템플릿)에 관하여 2 (클래스 템플릿, 템플릿 특수화)

그리고 생성자 초기화리스트를 사용해서 생성자를 선언했다.

value(value1), next(next1) <- 여기서 변수 value에 value1 값을 넣고, next에 next1 값을 넣겠다는 뜻이다.

초기화리스트를 사용하지 않고 대괄호 안에 변수를 대입해주는 방법도 있으나, 가급적 초기화리스트를 사용하는 것을 권장한다고 한다.

 

생성자 초기화리스트에 대한 설명: https://blog.naver.com/sipack7297/220276724965

[C++] 생성자 초기화리스트

 

class InvalidIndexException {};

// 중략

try {
	//예외 처리: 잘못된 인덱스
	if (k < 0 || k > size) throw InvalidIndexException();

	if (k == 0) { // 처음에 삽입
		head = new ListNode<T>(value, head);
	}
	else { // k번째 원소 앞에 삽입
		ListNode<T> *dest = head;
		for (int i = 0; i < k - 1; i++) dest = dest->next;
		dest->next = new ListNode<T>(value, dest->next);
	}
	size++;
}
catch (InvalidIndexException e) {
	cerr << "잘못된 인덱스입니다." << endl;
	exit(1);
}

 

C++에서 예외처리를 하기 위해서는 try catch문을 사용한다.

위의 예제에서는 InvalidIndexException이라는 예외를 직접 만들어서 사용했다. 예외 클래스 안에 아무 내용도 없어서 왜 굳이 저렇게 처리하는지 헷갈렸는데 예외 클래스 안에는 에러 메세지 등을 선언해서 사용한다고 생각하면 될 것 같다.

 

C++에서 예외처리 구현: https://www.sapphosound.com/archives/414

[C++] 자신만의 예외처리를 구현하는 방법 – Roughness Leads To Perfection

 

template<typename T>
ostream& operator << (ostream &out, const LinkedList<T> &LL) { // 원소들을 한 줄에 차례대로 출력
	ListNode<T> *temp = LL.head;
	out << "[";
	for (int i = 0; i < LL.size; i++) {
		out << temp->value;
		temp = temp->next;
		if (i < LL.size - 1) out << ", ";
	}
	out << "]";
	return out;
}

 

(모르는 문법이 너무 많아서 슬프다..ㅠㅠ)

위의 코드는 연산자 재정의하는 코드이다.

cout << 뒤에 여러가지 데이터타입이 올 수 있는 것은 << 연산자에 여러 가지 데이터 타입에 대한 연산이 오버로딩 되어 있기 때문이다. 그러나 우리가 따로 만들어준 LinkedList 클래스에 대한 << 연산자는 있을리가 만무하므로.. 직접 정의해서 사용해주는 것이다.

연산자 재정의에 대해서는 조금 더 공부해야할 듯 하지만, 일단은 << 연산자는 위와 같이 오버로딩 한다고만 기억해두자!

 

마지막으로 NULL과 nullptr의 차이점

C++에서 NULL은 정수 0에 해당한다. 따라서 실제론 NULL인데 컴파일러가 정수 0에 매칭시키는 것을 방지하기 위해 nullptr을 사용한다. (간단한건데 몰랐다..)

 

#include <iostream>
using namespace std;

int main() {
	cout << NULL;
	cout << nullptr;
}

 

위의 코드에서, NULL은 0으로 출력이 되지만 nullptr을 출력하면 에러가 발생한다.

 

이 글은 linked list에 대한 포스팅인가.. C++ 문법에 대한 포스팅인가..