6. Lists Plus

이세진·2022년 4월 3일

자료구조

Computer Science

목록 보기

9/74

생성일: 2021년 10월 29일 오후 11:18

앞에서 배운 Sorted List를 다양한 형태로 구현해보는 파트이다.

Sorted List를 기준으로 설명되어 있지만 다른 Data Type (예를들어 Stack)에도 같은 개념이 적용 될 수 있다.

💡 주의해야 할 점

1. list의 제일 첫 자리에 노드를 넣거나 뺄 때
2. list의 제일 마지막 자리에 노드를 넣거나 뺄 때
3. list가 비어있는 상태에서 노드를 넣거나 뺄 때

위의 주의해야할 사항들에 대해 함수를 구현할 때 조건문으로 처리를 해줘야 한다.

⇒ 너무 번거러운 것 아닌가 ? ⇒ 해결방법 : Headers and Trailers

Headers and Trailers 란 더미 데이터를 list의 양 끝단에 채워 넣어서 작업 할 때 양 끝단에 대한 예외처리를 안해도 되게 한다. (자주 사용하는 방법은 아님)

더미 데이터를 양 끝단에 미리 만들어 놓고 시작하는 모습

Circular Linked List

기존의 Sorted Linked list 에서는 이미 정렬되어 있는 데이터를 list에 넣을 때 또 다시 스스로 정렬을 하여 올바른 위치를 찾아 넣는 불필요한 작업을 하게 된다. (O(n^2))

이를 해결하기 위해서 list의 마지막 노드가 list의 맨 앞 노드를 가리키게 하고 listData는 제일 마지막 노드를 가리키게 한다. 이것이 Circular Linked List 이다.

Doubly Linked List

기존의 Linked list는 자신의 다음 노드를 가리키는 주소만 가지고 있었지만 Doubly Linked List에서는 각 노드가 자신의 앞 노드와 뒷 노드를 각각 가리키는 총 두개의 주소를 가지게 된다. (back, next)

insert 할 때 작업의 순서가 중요하다

위 그림의 1~4번 순서로 진행되어야 낭비되는 메모리없이 노드를 insert 할 수 있다.

InsertItem 함수 구현

새 노드를 가장 마지막 자리에 넣어야 할 때 location 이 NULL이 된다. 따라서 이부분의 오류 방지를 위해 if(location→next ≠ NULL) {location = location→next;} 를 추가 해야 한다.
새 노드를 가장 처음 자리에 넣어야 할 때 3번 작업에서 location→back이 NULL이기 때문에 오류가 발생한다. 따라서, 제일 첫 자리에 넣어야 할 경우 3번 작업 대신 제일 첫 번째 노드라는 의미로 listData = newNode; 를 추가한다.

Array로 동적 할당 없이 Linked List 만들기

동적 할당으로 Linked List를 만드는 것이 아닌 Linked 형식이긴 하지만 Array를 베이스로 list를 구현 할 수 있다.

이러한 형식이다. list변수가 첫 노드를 가리키고 free는 Array에서 비어있는 인덱스 번호를 가진다. ⇒ 새 노드를 insert 할 때에는 free인 자리에 넣는다. 이 것을 doubly 형태로도 만들 수 있다.

예를 들어, 1번 자리에 새 아이템을 insert한다 ⇒ list[1].next 값인 5는 free인 칸이므로 free = list[1].next 로 바꾸어 주고 list[1].next = NUL 로 설정한다.
예를 들어, 2번자리에 있는 Miriam 을 delete 한다 ⇒ 7번자리가 predLoc이 된다 ⇒ list[7].next = list[2](지우고자 하는 자리).next 로 변경한다. 그리고 list[2].info = NUL로 설정한다. ⇒ 빈자리임을 기록해야 하므로 list[2].next = free, free = 2 로 설정한다.

Copy Constructor

아래의 부가설명에서 제시하는 문제점을 해결하기 위해 Deep copy 기능을 수행하는 copy constructor를 만들 수 있다.

💡 파라미터로 들어갈 복사될 객체는 무조건!! pass by reference 여야 한다. 왜냐하면, pass by value로 들어갈 때 생기는 shallow copy 문제를 해결하기 위한 함수인데 여기서도 pass by value로 받으면 무한 루프처럼 계속 copy constructor를 불러와야한다. (대신 복사될 객체의 변형을 막기 위해 const를 붙여준다.)

부가 설명

지금까지 만든 여러 Data Type 객체를 복사할 때 생길 수 있는 문제가 있다.

//예를들어 Stack에서
StackType<int> A;
A.push(1);
A.push(2);
...
StackType<int> B;
B = A; // 이렇게 B에 A를 복사하려 시도

위의 코드처럼 객체를 복사하려 할 때 (pass by value) 생기는 문제점은 B에서 topPtr을 이용해 여러 작업들을, 예를 들어 Pop()이나 Push(), 하게 되면 B의 Stack에만 변화가 생기는 것이 아니라 A에도 변화가 생긴다.

Why?

B = A; 와 같이 assign하면, 그림처럼 topPtr이 그대로 복사가 되어 같은 주소인 7000번(heap 공간)을 가리키게 된다.

이 때 복사한 새로운 스택에서 Pop()을 통해 노드 하나를 지우게 되면 이 스택에서는 topPtr이 그 다음 노드를 가리키게 되어 문제가 없지만 복사를 해준 원본의 스택의 topPtr은 여진히 7000번을 가리키고 있기 때문에 비어있는 공간을 가리키게 된다. (이것을 Dangling Pointer 라고 한다.)

이러한 복사를 얕은 복사(shallow copy)라고 하고 반대되는 개념으로는 깊은 복사 (deep copy)가 있다.