이중 연결 리스트를 구현해 보자

씹어먹는 C를 배우는 중에 연결 리스트를 구현하는 예제가 있었다. 구조체와 동적 할당을 배우기 아주 좋은 예제다. 하지만 나는 이미 STL의 뽕맛을 본 몸이라서 그냥 연결 리스트로는 만족할 수가 없었다. 그래서 STL list 의 흉내라도 낸, 양쪽에서 삽입/삭제가 O(1)에 가능한 이중 연결 리스트를 구현해 보았다. 리스트가 잘 작동하는지 확인하기 위해 BOJ 5397번 : 키로거(https://www.acmicpc.net/problem/5397) 를 풀었고 AC를 받았다. 이중 연결 리스트 구현은 더미 노드(header, trailer)를 만들어서 했으며 STL list의 push_front, push_back, pop_front, pop_back, size, front, back, empty 를 구현했다. 삽입/삭제의 구현을 위해서는 insert_between과 delete_node 함수를 만들었다. 문제를 푼 코드를 첨부하겠다.

#include <stdio.h>
#include <stdlib.h>

struct node {
	struct node* prev;
	struct node* next;
	int val;
};

struct LinkedList {
	struct node* header;
	struct node* trailer;
	int s;
};

void init(struct LinkedList*);
void insert_between(struct LinkedList*, struct node*, struct node*, int);
int delete_node(struct LinkedList*, struct node*);
void push_front(struct LinkedList*, int);
void push_back(struct LinkedList*, int);
int pop_front(struct LinkedList*);
int pop_back(struct LinkedList*);
int size(struct LinkedList*);
int front_val(struct LinkedList*);
int back_val(struct LinkedList*);
int empty(struct LinkedList*);
void make_answer();

int main() {
	int t;
	scanf("%d", &t);
	for (int z = 0; z < t; z++) {
		make_answer();
	}
	return 0;
}

void make_answer() {
	char s[1000005];
	scanf("%s", s);
	struct LinkedList front, rear;
	init(&front); init(&rear);
	for (int x = 0; s[x]; x++) {
		if (s[x] == '<') {
			if (!empty(&front)) {
				push_front(&rear, pop_back(&front));
			}
		}
		else if (s[x] == '>') {
			if (!empty(&rear)) {
				push_back(&front, pop_front(&rear));
			}
		}
		else if (s[x] == '-') {
			pop_back(&front);
		}
		else {
			push_back(&front, s[x]);
		}
	}
	while (!empty(&front)) {
		push_front(&rear, pop_back(&front));
	}
	while (!empty(&rear)) {
		printf("%c", pop_front(&rear));
	}
	printf("\n");
}

void init(struct LinkedList* l) {
	l->header = (struct node*)malloc(sizeof(struct node));
	l->trailer = (struct node*)malloc(sizeof(struct node));
	l->header->prev = NULL;
	l->header->next = l->trailer;
	l->trailer->prev = l->header;
	l->trailer->next = NULL;
	l->s = 0;
}

void insert_between(struct LinkedList* l, struct node* pre, struct node* suc, int data) {
	struct node* n = (struct node*)malloc(sizeof(struct node));
	n->prev = pre;
	n->next = suc;
	n->val = data;
	pre->next = n;
	suc->prev = n;
	(l->s)++;
}

int delete_node(struct LinkedList* l, struct node* n) {
	struct node* pre = n->prev;
	struct node* suc = n->next;
	int e = n->val;
	pre->next = suc;
	suc->prev = pre;
	(l->s)--;
	free(n);
	return e;
}

void push_front(struct LinkedList* l, int data) {
	insert_between(l, l->header, l->header->next, data);
}

void push_back(struct LinkedList* l, int data) {
	insert_between(l, l->trailer->prev, l->trailer, data);
}

int pop_front(struct LinkedList* l) {
	if (l->s == 0) return 0;
	int v = delete_node(l, l->header->next);
	return v;
}

int pop_back(struct LinkedList* l) {
	if (l->s == 0) return 0;
	int v = delete_node(l, l->trailer->prev);
	return v;
}

int size(struct LinkedList* l) { return l->s; }
int front_val(struct LinkedList* l) { return l->header->next->val; }
int back_val(struct LinkedList* l) { return l->trailer->prev->val; }
int empty(struct LinkedList* l) { return (l->s == 0 ? 1 : 0); }

그런데 C는 구조체 멤버 함수도 지원하지 않고,  구조체 타입 앞에 언제나 struct 를 붙여 줘야 하는 등 다양한 제약들이 많다. 또 함수마다 함수의 대상이 되는 링크드 리스트를 인수로 줘야 한다니 얼마나 불편한가? 그냥 링크드 리스트를 찍어낼 수 있는 클래스나 구조체가 있으면 정말 좋겠다. 그래서 C++에서도 링크드 리스트를 클래스로 구현해 봤다. 원리는 완전히 똑같다.

class node {
public:
	node* prev;
	node* next;
	int val = 0;
};

class list {
private:
	int s = 0; //size

public:
	node* header;
	node* trailer;

	list() {
		s = 0;
		header = new node();
		trailer = new node();
		header->next = trailer;
		trailer->prev = header;
	}

	void insert_between(node* pre, node* suc, int data) {
		node* n = new node();
		n->prev = pre;
		n->next = suc;
		n->val = data;
		pre->next = n;
		suc->prev = n;
		s++;
	}

	int delete_node(node* n) {
		node* pre = n->prev;
		node* suc = n->next;
		pre->next = suc;
		suc->prev = pre;
		s--;
		int e = n->val;
		return e;
	}

	node* previous(node* n) {
		return n->prev;
	}

	node* following(node* n) {
		return n->next;
	}

	void push_front(int data) { 
		list::insert_between(header, header->next, data);
	}

	void push_back(int data) { 
		list::insert_between(trailer->prev, trailer, data); 
	}

	int pop_front() {
		if (s == 0) return 0;
		int v = list::delete_node(header->next);
		return v;
	}
	int pop_back() {
		if (s == 0) return 0;
		int v = list::delete_node(trailer->prev);
		return v;
	}
	int size() { return s; }
	int front() {
		node* fnode = header->next;
		return fnode->val;
	}
	int back() {
		node* bnode = trailer->prev;
		return bnode->val;
	}

	int empty() {
		return (s == 0 ? 1 : 0);
	}

};

굳이 구구절절 설명하지 않더라도 코드가 확실히 깨끗해졌다는 걸 한눈에 알 수 있다. 하지만, 역시 가장 좋은 건

#include <list>

이 한줄만 기억하자. 물론 이 코드의 원리를 이해하고 자신만의 이중 연결 리스트를 짜보는 건 좋은 일이다. 그렇지만 리스트 문제 하나 풀려고 120줄 코드를 쓰는 건 너무 미련한 짓이 아니겠는가?..