연결 리스트

용어 정의

연결 리스트에서 각 요소는 노드라고 함. 노드는 다음 노드를 가리키는 포인터를 가짐

구현 예시

// 양방향 구현 예시
struct Node {
	Node *prev, *next;
	string name;
	Node(string name_="") : prev(NULL), next(NULL), name(name_) {}
}
Node *nil;
void Init() {
	nil = new Node();
	nil->prev = nil;
	nil->next = nil;
}
void PrintNode() {
	Node *cur = nil->next;
	for(; cur != nil; cur=cur->next) cout << cur.name << endl;
}
void Insert(Node *node, Node *parent = nil) {
	node->next = parent;
	parent->next->prev = node;
	node->prev = parent;
	parent->next = node;
}
void Erase(Node *node){
	if(node == nil) return;
	node->prev->next = node->next;
	node->next->prev = node->prev;
	delete node;
}

참고자료

문제 해결력을 높이는 알고리즘과 자료 구조