C++ 기초 : 리스트 (3)

---

Linked List(연결형 리스트)와

가변 배열의 큰 차이점은 메모리의 구조입니다.

 

가변 배열은 메모리가 연속적으로 할당되어 있고

연결형 리스트는 메모리의 공간이 모두 떨어져 있으나

포인터를 통해 연결하고 있는 형태이죠.

 

그래서 가변 배열은 n번째 데이터에 접근하는 게 쉽습니다.

메모리가 연속적으로 할당되어 있어 3번째 데이터에

접근하고 싶다면 주소 연산(+3)을 통해 접근하기가 용이하죠.

 

그러나 단점도 있습니다. 만약 가변 배열의 맨 앞 공간에 

데이터를 추가하고 싶다면 기존 데이터를 모두 뒤로 한 칸씩

복사하여 붙여넣고 맨 앞에 공간이 생기면 그제서야 비로소

데이터를 넣을 수 있죠.

 

만약 데이터가 1000개가 있다고 하면 이 1000개의 데이터를

하나씩 뒤로 밀고 데이터를 넣어야 하는 것입니다.

하나의 데이터를 뒤로 미는데 걸리는 시간이 a라고 하고 

존재하는 데이터를 n이라고 하면 

a * n이라는 긴 시간이 소요되겠죠.

 

이를 시간 복잡도를 나타내는

Big-O notation(빅 오 표기법)으로 나타내면

O(a * n), 여기서 계수를 뺀 나머지 O(n)입니다.

 

 

반면 리스트는 맨 앞에 데이터를 넣는다고 하면

노드를 하나 만들어 데이터를 넣고 리스트가 해당 

노드를 가리키게 하면 그 노드가 맨 앞에 있는

데이터가 되죠.

 

이 경우 즉 데이터의 개수(n)에

상관없이 항상 같은 시간이 들죠. 

 

이를 Big-O notation으로 나타내면 O(1)입니다.

 

그러나 Linked List도 최악의 경우가 있습니다. 

바로 맨 끝에 있는 데이터에 접근할 때이죠.

(맨 끝 데이터의 주솟값을 저장하는 포인터 Tail이 없을 경우)

 

List가 갖고 있는 Head 포인터를 통해 첫 번째 노드에 

접근하고 해당 노드가 가리키는 두 번째 노드에 접근하는

방식이므로 1000번째 노드에 접근한다고 하면 이를 1000번 

반복해야 합니다.

 

그럼 여기서 맨 끝 데이터의 주솟값을 저장하는 포인터 Tail이

존재한다고 하였을 때 어떤 경우가 가장 시간이 오래 걸릴까요?

 

바로 중간에 있는 데이터에 접근할 때일 것입니다.

이 경우 1/2 * n만큼의 시간이 걸릴 겁니다. Big-O notation으로 

나타내면 계수를 무시하기 때문에 O(n)으로 나타낼 수 있네요.

 

 

 

---

 

 

 

 

 

Linked List가 관리하는 Node를 추가할 건데 이 Node가

가장 맨 앞에 위치하도록 하는 함수를 구현하겠습니다.

 

LinkedList.h에 

 

PushFront 함수를 선언하고 

 

LinkedList.cpp에 

 

PushFront 함수를 정의하였습니다.

 

48

연결형 리스트 역할을 할 tLinkedList형 객체를

하나 받고 노드에 저장할 값을 하나 받습니다.

 

 

51

Heap 영역에 동적 할당할 공간을 만듭니다.

동적 할당한 해당 공간이 바로 Node가 됩니다.

 

딱 Node 한 개만큼 크기로 선언하면 되므로

sizeof 함수를 이용하여 tNode 크기만큼 할당합니다.

 

 

52

할당한 공간을 tNode형 포인터 pNode를 통해

임시로 가르키도록 하겠습니다.

 

 

55

새로 동적 할당한 공간이 가장 앞에 위치해야 하므로

새로 동적 할당한 공간은 원래 첫 번째 노드였던

공간을 가르켜야 하겠죠? 첫 번째 노드의 주솟값은

tLinkedList형 객체가 pHeadNode를 통해 저장하고 있습니다.

 

따라서 새로 동적 할당한 노드의 다음 노드의 주솟값을

저장해야 하는 pNextNode에 tLinkedList형 객체의

pHeadNode가 저장하고 있는 주솟값을 대입합니다.

 

 

58

새로 할당한 노드를 가장 첫 번째 노드로 할 것이기 때문에

Linked List는 새로 할당한 노드의 주솟값을 pHeadNode에

저장해야 합니다. 

 

새로 할당한 노드인 pNode를

Linked List에서 첫 번째 노드의 주솟값을

저장하는  pHeadNode에 대입합니다.

 

 

61

노드가 하나 추가되었으니

노드의 개수를 나타내는 Linked List의 멤버

iCount의 값을 하나 올립니다.

 

 

---

 

 

결과를 확인해 보겠습니다.

 

PushFront 함수를 통해

100, 200, 300이 들어간 노드를 만들었습니다.

 

그리고 tNode형 포인터 cNode를 만들어

객체 list가 가리키는 첫 번째 노드의 주솟값을 저장합니다.

 

이후 list가 갖고 있는 노드 수만큼

반복문을 돌며 노드가 갖고 있는 값을 출력하죠.

 

처음엔 첫 번째 노드의 값이 출력된 후

cNode에 다음 노드 주솟값,

즉 두 번째 노드의 주솟값이 저장됩니다.

 

두 번째 노드의 값이 출력된 후 

cNode에 다음 노드 주솟값인

세 번째 노드의 주솟값이 저장되고

세 번째 노드에 저장된 값이 출력됩니다.

 

 

100, 200, 300순으로 노드를 구성하였지만

PushFront 함수를 통해 구성하였기 때문에

300, 200, 100순으로 출력되는 것을 볼 수 있습니다.

 

 

 

 

강의 출처 : https://www.youtube.com/watch?v=PFc4g8mxOiI&list=PL4SIC1d_ab-aOxWPucn31NHkQvNPHK1D1&pp=iAQB

---