ADT (Abstract Data Type)

이 방법으로 대표적인 방법에는 ADT, 추상 데이터 타입을 만드는 것이 있습니다.

우선 컴퓨터는 한번에 하나의 동작만 할 수 있습니다. 즉, 예를 들어 어떤 배열에서 가운데에 있는 원소를 빼고싶다고 생각해 봅시다. 그렇다면 우리가 해야할 일은 이 원소의 뒤의 원소들을 하나씩 앞으로 땡겨서 다시 저장해야겠죠?

이 경우 당연히 불필요한 시간이 많이 걸리게 될 것입니다.

하지만 ADT, 즉 단순한 배열이 아닌 새로운 데이터의 타입을 만들어서 이 문제를 해결할 수 있다면 사용할 만한 가치가 있겠죠??

Stack

한쪽에서만 추가 삭제가 가능한 배열구조

Queue

한쪽은 삭제만 담당, 다른 한쪽은 추가만 담당하는 배열구조

Deque

(Double Ended Queue)
양쪽 모두 삭제, 추가가 가능한 배열 구조.

추가

이제 이 list를 이용하여 Stack, Queue를 구현하기 위해서는 먼저 다음 중 어떤것을 시용할지 결정해야 합니다.

물론, Stack이나 Queue를 만드는 목적이 아닌 다른 목표가 있을 경우 아래와 같은 예시 이외의 push()와 pop()구현도 가능할 것입니다.

예를 들어 head나 tail이 아닌 중간에 push()와 pop()을 구현하는는 방법이 있을 것이겠죠?

Singly Linked List의 push()와 pop()

Singly Lineked List의 경우 push()와 pop()을 할 때 다음과 같은 선택지가 있을 것입니다.

따라서 Singly Linked List의 특징을 고려하여 다음과 같이 구현해볼 수 있을 것입니다.

1) head에 push()하기

Node* temp = new Node("hello" ,head);
head = temp;
size++;

2) tail에 push()하기

Node* temp = new Node("World", NULL);
tail->next = temp;
tail = temp;
size++;

3) head를 pop()하기

Node* temp = head->next;
delete head;
head = temp;
size--

4) tail을 pop()하기

Node* temp = head;
while(temp->next != tail) {
    temp = temp->next;
}
delete tail;
tail = temp;

위에서 볼 수 있듯이 tail을 pop()하는 것은 많은 시간이 걸리게 됩니다.
즉, pop()을 구현할 때는 head를 pop()하기로 합시다.

Doubly Linked List의 push()와 pop()

마찬가지로 Doubly Lineked List의 경우에는 push()와 pop()을 할 때 다음과 같은 선택지가 있을 것입니다.

따라서 Doubly Linked List의 특징을 고려하여 다음과 같이 구현해볼 수 있을 것입니다.

삽입

• head에 push()하기

Node* temp = new Node();
temp->prev = header;
temp->next = header->next;
header->next = temp;
header->next->prev = temp;
size++;

• tail에 push()하기

Node* temp = new Node();
temp->prev = trailer->prev;
temp->next = trailer;
trailer->prev->next = temp;
trailer->prev = temp;
size++;

삭제

삭제시에는 포인터 2개를 사용하여 연결과 삭제를 도와주는 것이 편리합니다.

• head를 pop()하기

Node* temp1 = header->next;
Node* temp2 = header->next->next;
header->next = temp2;
temp2->prev = header;
delete[] temp1;
size--

• tail을 pop()하기

node* temp1 = trailer->prev->prev;
node* temp2 = trailer->prev;
trailer->prev = temp1;
temp1 -> next = trailer;
delete temp2;
size--;

Tree

참고

Quadratic-Time: O(n2) 알고리즘
Operand: 피연산자
Operator: 연산자