[Data Structure] Linked Structure

연결된 구조

• 기존의 자료구조들은 배열을 기반으로 구성되었다. 이러한 배열구조 기반의 단점은 해당 구조의 크기가 동적으로 할당되기 어렵다는 뜻이다. 즉, 크기에 제한이 생긴다는 단점이 존재한다.
• 이러한 단점을 보안하기 위해 구상된 것이 'Linked'이다. 쉽게 생각하면, data부와 pointer부 2개의 공간이 존재하고, pointer부에서 다른 객체를 가리키고 이러한 구조가 반복적으로 이루어 진 것이다.

struct NodeType
{
    ItemType info;
    NodeType* next;
}

1. Linked Stack

• 기존의 Stack 구조에 존재하는 데이터 타입을 구조체로 선언하여 위 사진과 같이 선언한다.
  연결된 스택은 항상 맨 위를 가리키는 topPtr이 존재하고, 이를 이용해 스택의 LIFO를 처리한다.
• 연결된 스택의 Push 연산은 다음의 일련의 과정을 거친다.
  1. 먼저 NodeType을 새로 선언한다. 선언된 새로운 NodeType을 location이라 하자.
     • NodeType* location; 
     • location = new NodeType;
  2. 선언된 location의 데이터부분 (info)에 새로운 newItem을 할당한다.
     • location->info = newItem;
  3. location의 다음을 가리키는 next가 topPtr을 가리키게 만든다.
     • locatiom->next = topPtr;
  4. topPtr에 location의 위치를 할당해준다.
     • topPtr = location;

• 이렇게 하면, 새로운 location이 생성될 때 마다, topPtr은 항상 stack의 꼭대기에 존재할 것이다.
• 다음은 Pop 연산이다.
  1. tempPtr이라는 NodeType의 포인터를 선언한다.
     • NodeType* tempPtr;
  2. tempPtr에 가장 위에 존재하는 topPtr의 주소를 할당한다.
     • tempPtr = topPtr;
  3. topPtr에 topPtr의 다음 주소를 할당한다. 즉, 스택의 다음 요소를 할당한다.
     • topPtr = topPtr->next;
  4. tempPtr 객체를 delete함으로써, 메모리 할당을 삭제한다.
     • delete tempPtr;

2. Linked Queue

• 앞선 Stack에서 항상 스택의 가장 위를 가리키는 topPtr이 존재했다면, Queue의 경우에는 Queue의 가장 앞과 뒤를 가리키는 front와 rear가 존재한다.
• 새로운 요소가 들어오면, rear가 앞선 스택의 Push처럼 작동할 것이고, 요소가 삭제되면, 앞선 스택의 pop 연산을 front에서 실행할 것이다.

2-1. Circular Linked Queue

• Rear가 Front를 가라키게 만드는 Queue이다.

3. Linked Unsorted List

• Linked List의 경우, 요소를 중간에 삽입할 수 도 있고, 특정 요소를 삭제해야 할 경우가 생긴다. 그런 경우를 위해 추가적인 조치가 필요하다.
• 먼저 요소를 삭제할 때를 보자. 특정 요소를 찾기 위해 front에 접근하여 data를 비교하고, 만일 해당하는 요소가 아니라면 next 포인터를 통해 다음 객체에 접근한다.
  • 만일, 해당하는 요소가 맞다면, tempPtr로 현재 지점의 포인터를 할당하고, 이 전 요소의 next를 해당 tempPtr의 next 요소를 가리키게 한 뒤, tempPtr의 할당을 delete해주면 될 것이다.
• 요소를 추가할 때를 생각해 보면, 위와 유사하다.
  • 새로운 객체를 할당하고, 해당 객체를 원하는 위치에 놓는다. 만일 해당 위치에 이미 객체가 존재한다면, 이 전 요소의 next를 자신으로, 자신의 next를 기존 객체로 바꿔주면 될 것이다.
  • front나 rear 위치에 있다 하여도 동일한 방법으로 해주면 된다.

4. Linked Sorted List

• Unsorted List에 정렬만 추가해주면 된다.