06. Lists Plus

dain·2023년 3월 25일
자료구조
1

자료구조

목록 보기
6/8
post-thumbnail

순환 연결 리스트 (Circular Linked List)

  • 모든 노드들이 후속 노드(successor)를 가지고 있으며, 첫번째 요소가 마지막 요소의 뒤를 잇는 연결 리스트
  • 리스트에 요소가 한 개만 있는 경우, 자기 자신을 가리킨다.

✏️ 일반적인 연결 리스트
: 첫번째 노드와 마지막 노드를 제외한 모든 노드들이 유일한 후속 노드를 가지는 연결 리스트


이중 연결 리스트 (Doubly Linked List)

  • 각 노드가 전임 노드와 후속 노드를 모두 갖는 연결 리스트
    • 이때 전임 노드(successor)과 후임 노드(predecessor)은 포인터이다.
  • 이중 연결 리스트의 노드의 구조
    template<class ItemType>
struct NodeType {
	ItemType info;
    NodeType<ItemType>* next;
    NodeType<ItemType>* back;
};
  • 연산
    • FindItem
      : 찾고자하는 item을 입력으로 받아서, 해당 item의 발견 여부 및 위치를 돌려주는 함수
      template<class ItemType>
void SortedType::FindItem(NodeType<ItemType>* listData, ItemType item, NodeType<ItemType>*& location, bool& isFound)
{
	//pre: list is not empty and sorted in ascending order by key
	location = listData;
	isFound = false;

	while (!isFound) {
		if (item < location->info) 
			return;
		else if (item == location->info)
			isFound = true;
		else { //item > location->info
				if (location->next == NULL) // 끝까지 갔는데 못 찾은 경우
					return;
				else
					location = location->next;
		}
	}
}
    • InsertItem
      : FindItem으로부터 얻은 location에 새로운 아이템을 삽입하는 함수 (순서 유지)
      template<class ItemType>
void SortedType<ItemTYpe>::InsertItem(ItemType item)
{
    NodeType<ItemType>* newNode;
    NodeType<ItemType>* location;

    newNode = new NodeType<ItemType>;
    newNode->info = item;

    if (listData != NULL) 
    {
        FindItem(listData, item, location); // item이 삽입될 location을 돌려줌

        if (location->info > item) {
            newNode->back = location->back;
            newNode->next = location;
            if (location != listData) 
                (location->back)->next = newNode;
            else { // location == listData. 
								// 첫번째 노드의 앞에 새로운 노드를 추가하는 경우
                listData = newNode;
                location->back = newNode;
            } 
        }
        else { // location->info < item
            // 리스트 내에 item보다 큰 요소가 존재하지 않아 item을 리스트의 맨 뒤에 삽입하는 경우)
            newNode->back = location;
            location->next = newNode;
            newNode->next = NULL;
        }
    }
    else { //listData == NULL, empty list인 경우
        listData = newNode;
        newNode->next = NULL;
        newNode->back = NULL;
    }
    length++;
}

      ✏️ InsertItem에서의 location

      • item보다 큰 요소가 있는 위치 (InsertItem에서는 리스트 내에 삽입하려는 item과 같은 요소가 없다고 가정)
      • 만약 리스트 내에 item보다 큰 요소가 없을 경우, 리스트의 마지막 노드의 위치
    • DeleteItem
      : 입력으로 받은 item을 리스트 내에서 삭제하는 함수 (순서 유지)
      // 기본 원리
(location->back)->next = location->next;
(location-next)->back = location->back;
delete location;

Headers and Trailers

  • 리스트의 첫번째 또는 마지막 노드를 다루는 경우 예외가 발생하기 때문에, 해당 부분에 대한 예외 처리가 필요하다. 만약 리스트의 양 극단에서는 삽입이나 삭제가 발생하지 않는다는 것이 보장된다면, 구현을 단순화할 수 있다. 이는 가능한 범위 값을 벗어나는 값으로 더미 노드 설정함으로써 실현될 수 있다.
  • 더미 노드
    • 헤더 노드 (Header Node)
      : 가능한 리스트의 모든 요소보다 작은 값을 가진 노드
    • 트레일러 노드 (Trailer Node)
      : 가능한 리스트의 모든 요소보다 큰 값을 가진 노드

함수 호출시 발생하는 문제

  • C++에서 객체가 인자(argument)로 넘어갈 때, 'pass by value'가 기본이다. 따라서 함수의 지역 변수와 관련해서 문제가 발생한다.

    ✏️ C++의 함수 인자 전달 방식

    • pass by value
      • 함수 호출 시, 인자로 전달된 값의 복사본이 함수 내부로 전달된다.
      • 함수 내부에서 인자 값이 변경되더라도, 호출자(함수 외부)엔 영향을 미치지 않는다.
    • pass by reference
      • 함수 호출 시, 인자로 전달된 변수의 참조(reference)가 함수 내부로 전달된다.
      • 함수 내부에서 인자 값의 변경이 일어나면, 호출자의 변수 값도 변경된다.
  • 예) 동적 연결 리스트로 구현된 스택
    • StackType 클래스의 멤버 변수인 topPtr은 지역 변수로 메모리의 스택 영역에 존재하지만, 동적으로 할당된 노드들은 지역 변수가 아니며 메모리의 힙 영역에 존재한다.
    • C++에서는 인자로 전달된 값의 복사본이 함수 내부로 전달된다. (pass by value) 따라서 스택을 복사할 경우 MyStack의 topPtr이 가리키고 있는 노드의 메모리 주소인 7000이 SomeStack의 topPtr에 복사되므로, 두 스택의 topPtr이 같은 노드를 가리키게 된다.
    • 만약 위와 같은 상황에서 SomeStack.Pop()을 호출하면, SomeStack의 top에서는 아이템(20)이 삭제되고 topPtr 포인터가 다음 노드를 가리키도록 수정된다. 그러나 MyStack에는 반영되지 않기 때문에, MyStack의 topPtr이 이미 삭제된 노드를 가리키는 댕글링 포인터가 되게 된다.

    • 이러한 문제를 얕은 복사(shallow copy) 문제라고 한다. 데이터 멤버 포인터가 동적 데이터를 가리킬 때 발생하는 얕은 복사 문제를 해결하기 위해, 깊은 복사(deep copy)를 만드는 복사 연산자(copy constructor)를 사용한다.

      • 깊은 복사의 예

얕은 복사와 깊은 복사

  • 얕은 복사
    • 클래스의 데이터 멤버만을 복사하고, 멤버가 가리키고 있는 다른 데이터들은 복사하지 않는다.
    • 가리키고 있는 데이터를 원래의 클래스 객체와 공유한다.
  • 깊은 복사
    • 클래스 데이터 멤버뿐만 아니라, 멤버가 가리키고 있는 모든 데이터의 복사본을 별도로 저장한다.
    • 가리키고 있는 데이터의 자체 복사본을 원래 클래스 객체의 데이터와 다른 위치(메모리)에 저장한다.

복사 연산자 (Copy Constructor)

  • 복사 연산자가 호출되는 상황

    정의된 복사 연산자는 특수한 상황에서 암시적으로 호출된다.

    • 객체를 다른 객체로 초기화하는 경우
    • 함수에 객체를 값으로 전달(pass by value)하는 경우
    • 함수에서 객체를 반환하는 경우

  • 코드 (동적 연결 리스트로 구현된 스택 기준)
    template<class ItemType>
class StackType {
public:
	StackType(); //default constructor
	StackType(const StackType<ItemType>* anotherStack); //copy constructor
	...
	~StackType(); //destructor
private:
	NodeType<ItemType>* topPtr;
};  
    template<class ItemType>
StackType<ItemType>::StackType(const StackType<ItemType>& anotherStack) {
	NodeType<ItemType>* ptr1;
	NodeType<ItemType>* ptr2;

	if(anoterStack.topPtr == NULL) //복사하고자 하는 스택이 비어 있을 때
		topPtr = NULL;
	else {
		topPtr = new NodeType<ItemType>; //1️⃣
		topPtr->info = anotehrStack.topPtr->info; //2️⃣
		
		ptr1 = anotherStack.topPtr->next; //3️⃣
		ptr2 = topPtr; //4️⃣
		
		while (ptr1 != NULL) {
			ptr2->next = new NodeType<ItemType>; //5️⃣
			ptr2 = ptr2->next; //6️⃣
			ptr2->info = ptr1->info; //7️⃣
			ptr1 = ptr1->next; //8️⃣
		}
		ptr2->next = NULL; //9️⃣
	}
}

    이때 복사 생성자의 매개변수는 참조(&)로 받아야 한다.

    만약 복사 생성자가 객체를 참조(&)로 받지 않는다면, 객체를 복사하기 위해 새로운 객체를 생성하고, 생성된 객체에 값을 복사한 후, 복사본을 반환하게 된다. 이러한 과정에서 많은 비용이 들고, 복사된 객체를 변경할 경우 원본 객체에 영향을 주는 얕은 복사 문제가 발생한다.


대입 연산자 (Assignment Operator)

  • C++ 대입은 객체의 메모리 값을 복사해서 할당하는 방식으로 이루어진다. 따라서 두 객체가 같은 메모리를 공유하기 때문에, 동적 데이터를 다루는 경우 얕은 복사 문제가 발생하다.
  • 이를 해결하기 위해 대입 연산자가 깊은 복사를 수행하도록 오버로딩할 수 있다.
    void operator= (StackType<ItemType>);

✏️ C++ 연산자 오버로딩 가이드

  • ::/ ./ szieof/ ?:/ '->'를 제외한 모든 연산자는 오버로딩될 수 있다.
  • 하나 이상의 피연산자가 클래스 인스턴스여야 한다.
  • 우선 순위/ 연산자 기호/ 피연산자의 수는 변경할 수 없다.
  • 일반적으로 ++와 --를 오버로드하려면 접두사 형식을 사용해야 한다.
  • =/()/[]를 오버로딩하려면 멤버 함수가 사용되어야 한다.
  • 피연산자의 데이터 타입이 다를 경우 연산자에 여러 의미를 부여할 수 있다.
profile
dain
자라나는 감자
이전 포스트

05. Linked Structures

다음 포스트

07. Programming with Recursion

0개의 댓글