1. 단일 연결리스트 vs 원형 연결리스트 구분
(1) 단일 연결 리스트
하나의 방향으로만 연결되어 있는 연결 리스트, 체인(chain)이라고 한다. 마지막 노드의 링크 값은 NULL. 거꾸로 갈 수 있는 방법이 없다.
-
메모리 활용 유연성
순차 선형 리스트는 연속된 메모리 공간을 확보해야한다. 하지만 연결 리스트는 이전의 노드가 다음 노드의 주소를 가지고 있어서 메모리 공간 어디는 값을 저장할 수 있다. -
읽기 연산 효율성
첫번째 노드의 메모리 주소만 알기 때문에 특정 인덱스를 값을 알기 위해서는 첫 번째 인덱스부터 순차적으로 연산해야 한다. 예를 들어 인덱스 2를 찾는다면 인덱스 0부터 시작하여 인덱스 0에 있는 인덱스 1의 주소를 찾은 뒤 인덱스 1에 있는 인덱스 2의 주소를 찾아야 한다.
효율성은 O(N)이다. 효율성이 O(1)인 순차 선형 리스트와 크게 효율성이 떨어진다. -
검색 연산 효율성
첫번째 인덱스부터 일치하는 값을 찾을 때까지 순차적으로 모든 노드를 뒤져야 한다. 찾는 값이 없는 최악의 경우에 효율성은 O(N)이다. -
삽입 연산 효율성
순차 선형 리스트와 달리 단순 연결 리스트의 삽입 연산에는 물리적 순서를 유지하기 위해 노드들을 이동시키지 않는다. 링크 필드의 참조값에 대한 연산만으로 쉽게 삽입 연산을 수행할 수 있다.
하지만 삽입하려는 위치 한단계 전 노드를 찾기 위해 첫 번째 노드부터 차례대로 검색을 해야 해서 O(N)이 걸린다. -
삭제 연산 효율성
삽입과 매우 유사하다. 노드들이 이동하지 않고 필드의 참조값에 대한 연산으로 삭제연산을 수행할 수 있다. 삭제하고자 하는 노드를 찾는다. 그다음 한 단계 전의 노드가 가리키는 주소를 삭제될 노드의 다음 노드로 변경한다. 효율성은 O(N)이다.
(2) 원형 연결 리스트
단순 연결 리스트와 유사하나 마지막 노드의 링크가 첫 번째 노드를 가리킨다.
(3) 이중 연결 리스트
각 노드마다 2개의 링크가 존재하는데, 하나는 앞 노드, 하나는 뒷 노드를 가리킨다.
2. 손코딩 문제
(1) 스택 두개로 큐 구현해보기
데이터 삽입용 스택, 데이터 추출용 스택을 둔다. 데이터 삽입용 스택에는 삽입만, 데이터 추출용 스택에서는 추출만 한다. 만약 추출용 스택이 비어있으면, 삽입용 스택의 모든 데이터를 추출용 스택으로 옮긴다. (이 때, 가장 먼저 삽입용 스택에 들어간 데이터가 추출용 스택의 제일 상단에 위치하게 되어, 먼저 추출대상이 되는 것!)
#include <iostream>
#include <stack>
using namespace std;
class Queue {
private:
stack<int> inStack;
stack<int> outStack;
public:
// 큐에 데이터를 삽입하는 함수
void enqueue(int value) {
inStack.push(value);
}
// 큐에서 데이터를 추출하는 함수
int dequeue() {
if (outStack.empty()) {
// outStack이 비어있으면 inStack의 데이터를 모두 outStack으로 이동
while (!inStack.empty()) {
outStack.push(inStack.top());
inStack.pop();
}
}
// outStack에서 데이터 추출
int value = outStack.top();
outStack.pop();
return value;
}
// 큐가 비어있는지 확인하는 함수
bool empty() {
return inStack.empty() && outStack.empty();
}
};(2) 원형 큐 직접 구현해보기
하나의 자리를 비워 놓고 구현하는 것이 일반적인데, 이렇게 하면 공백 상태(front == rear)와 포화 상태(front%M == (rear+1)%M)를 구분하기 쉽다. (추가적인 변수를 사용하여 count하면 한 자리를 비워 놓지 않아도 되긴 함)
큐의 데이터를 저장하는 배열과 큐의 크기, 그리고 front와 rear 변수를 멤버 변수로 가지는 Queue 구조체를 정의한다. 이 구조체를 사용하여 큐의 생성자, 소멸자, 비어있는지 확인하는 함수, 가득 찼는지 확인하는 함수, 데이터를 삽입하는 함수, 데이터를 추출하는 함수, 첫 번째 요소를 반환하는 함수를 구현한다.
#include <iostream>
#define MAX_SIZE 5 // 큐의 최대 크기
int front = 0; // 큐의 첫 번째 요소의 인덱스
int rear = 0; // 큐의 마지막 요소 다음 위치의 인덱스
int data[MAX_SIZE]; // 큐의 데이터를 저장하는 배열
// 큐가 비어있는지 확인하는 함수
bool isEmpty() {
return front == rear;
}
// 큐가 가득 찼는지 확인하는 함수
bool isFull() {
return (rear + 1) % MAX_SIZE == front;
}
// 큐에 데이터를 삽입하는 함수
bool enqueue(int value) {
if (isFull()) {
return false;
}
data[rear] = value;
rear = (rear + 1) % MAX_SIZE; // rear 값을 1 증가시키면서 size로 나눈 나머지 값을 새로운 rear 값으로 함
return true;
}
// 큐에서 데이터를 추출하는 함수
int dequeue() {
if (isEmpty()) {
return -1;
}
int value = data[front];
front = (front + 1) % MAX_SIZE; // front 값을 1 증가시키면서 size로 나눈 나머지 값을 새로운 front 값으로 함
return value;
}
// 큐의 첫 번째 요소를 반환하는 함수
int peek() {
if (isEmpty()) {
return -1;
}
return data[front];
}