[자료구조] Linked List

해당 본문은 학교수업시간에 배운 강의내용을 기반으로 정리하는 요약글 입니다. 정확하지 않은 점이 있으면 지적해주시면 감사하겠습니다.

이번 시간에는 연결리스트(Linked List)에 대하여 배웠다.

 

사실 연결리스트만 해도 내가 직접 구현해본 경험이 이미 여러번 있고 쉬운내용이라 이해하는데 어렵지 않았다.

윤성우 열혈, C++로쉽게풀어쓴 자료구조, 알고리즘책 등등 이미 많은 책에서 자주 접했던 내용이다.

 

구현부분은 조금 대충한 느낌이 있는데... 예전 글에서 더 정성스럽게 구현한 경험이 있으니... 이 글에서는 돌아갈정도만 구현하는걸로....

 

Linked List

연결리스트 란 노드를 data 와 다음 노드를 가리킬 포인터로 구현하여 연속된 노드의 집합으로 만드는 것 이다.

위의 그림에서 처럼 한 노드에 item을 저장하는 부분과 next(다음 노드의 주소를 저장할)포인터 둘다 갖고있다.

 

연결리스트를 구현할때 Node의 시작부분을 가리킬 head 포인터 또한 하나 필요하다.

 

Linked List의 구현

▶ Node의 구현

class Node {
public:
	int data;
	Node* next;
};

 

노드는 위에서 도 말했듯 data를 담는 부분과, 다음 노드를 가리킬 포인터변수 next를 갖고있어야 한다.

 

▶ List의 구현

교수님의 강의에서와는 조금 다르게 구현하였다.

 

우선 생성자는 명시적 생성자로 지정하였다. 암시적 형변환은 막고싶기 때문이다.

 

DS의 주소값은 초기화 리스트를 이용하여 바로 초기화 시켜주었고, 나머지 DS와 DE의 정보들은 우선 생성된 후에 값을 대입하여 주었다. (참고로 DS와 DE는 더미노드 start와 end이다.)

class List {
	Node* head;
	Node DS;
	Node DE;
public:
	explicit List() : head(&DS) {
		DS.next = &DE;
		DS.data = -1;
		DE.next = nullptr;
		DE.data = -2;
	}
	~List() {
		Node* pp, * nn;
		nn = head;
		while (nn != nullptr) {
			pp = nn;
			nn = nn->next;
			delete pp;
		}
	}

	bool Search(int x, Node** PP, Node** LL) const;
	bool Insert(int x);
	bool Delete(int x, Node** D);
};

 

Search, Insert, Delete

코드가 매우 간단하고 직관적이니 한줄한줄 주석을 달지는 않겠다.

 

▶ Search의 구현

교수님이 구현하신 부분에서 일부분만 수정하였다. 우선 int형 반환 보단 bool형 반환이 더 적합하다 생각하여 bool 반환으로 변경하였다.

 

또한 Search는 멤버변수의 값을 변경시킬 수 없기때문에 const를 선언해 주었다.

bool List::Search(int x, Node** PP, Node** LL) const{
	*LL = head;
	while (*LL != nullptr) {
		if ((*LL)->data < x) {
			*PP = *LL;
			*LL = (*LL)->next;
		}
		else if ((*LL)->data == x)
			return true;
		else return false;
	}
	return false;
}

 

▶ Insert의 구현

bool List::Insert(int x) {
	Node* P, * L, * NN;
	if (Search(x, &P, &L) == false) {
		NN = new Node;
		NN->data = x;
		NN->next = L;
		P->next = NN;
		return true;
	}
	else return false;
}

 

만약 search에 실패하면 중복된 값이 아직 없다는 뜻 이다. 따라서 새로운 노드를 동적 할당 받아서 추가해 주면 끝난다.

이후 성공적으로 노드를 추가했음을 true로 return 해주면 끝난다.

 

▶ Delete의 구현

bool List::Delete(int x, Node** D) {
	Node* P, * L;
	if (Search(x, &P, &L) == true) {
		*D = L;
		if (P != nullptr) P->next = L->next;
		else head = L->next;
		return true;
	}
	else return false;
}

 

삭제시 삭제하려는 노드를 탐색 후, 있으면 삭제한다.

위의 코드에서 P가 nullptr인 경우 아직 첫 노드만 있어 P가 가리키는 대상이 없는 상황이다. 이때는 head가 L의 next 즉, NULL을 가리키게 한 후 끝난다.

 

Linked List 의 성능

• Sorted : 탐색 O(n), 삽입 S + O(1), 삭제 S + O(1), 단순 삽입과 삭제의 연산은 상수시간안에 가능하지만, 사전에 Search 연산이 동반되야 하다보니 O(n)이 되버린다.
• Unsorted : 탐색 O(n), 삽입 O(1) 값의 중복을 허용하지 않는다면 S + O(1), 삭제 S + O(1)
• LRU(Least Recently Used, Paper on Desktop) : 각 노드마다 사용되는 빈도가 다를 때 유용하다. A라는 노드를 100번 사용할때 B라는 노드는 1번 사용한다면 A가 연결리스트 앞에 있어야 탐색에 더 용이 하다. 이런 자주 사용하는 노드를 앞에두는 것 이 핵심이다.

- 최악 : 탐색 O(n), 삽입 O(1) 중복거를시 O(n), 삭제 S + O(1)

- 기대 : 사용 빈도에 따라 크게 다름

 

(PS. LRU와 관련된 문제로 카카오에서 2018년에 나온 문제가 있다. 이문제 또한 풀어서 예전 블로그에 정리해 둔적이 있으니 궁금한 분은 다음 문제를 확인해보길! )

[CPS] 37번 - Least Recently Used (카카오 2018) <25>

 

std::vector

• Vector : Variable Size Array (가변길이배열)
• Sorted : 탐색 O(log n), 삽입 S + O(n), 삭제 S + O(n), 다만 정렬되있으니 Search의 경우 이진탐색을 사용하면 logN안에 가능해짐
• Unsorted : 탐색 O(n), 삽입 S + O(1), 삭제 S + O(1)

 

추가내용

더미 노드를 사용하여 리스트의 양 끝에 설치해두면 포인터를 사용할때 편리하다는 장점이 있다.

 

원형연결리스트 또한 있다.

 

Doubly Linked List는 자주 사용되는 편이다.

출처 - Geeks for Geeks