Doubly Linked List와 Iterator

개요

노드의 sequence를 담은 자료구조.

 

더 일반화 된 List ADT를 구현할 수 있다.

 

 

DLL의 성질

각 노드는 이전 노드와 다음 노드에 대해 양방향으로 연결한다.

 

두 더미 노드 trailer, header를 활용하면 구현에 용이하다.

 

 

Node

SLL에 추가로 이전 노드의 주소를 가진다.

 

아래는 앞으로 사용할 노드의 예시이다.

 

struct Node {
    int data;
    Node* next;
    Node* prev;
}

 

Doubly Linked List

SLL보다 일반적인 함수 구현에 유리하다.

 

예를 들면, 다음과 같은 ADT를 구성할 수 있다.

 

struct DLL {
    Node* head;
    Node* tail;
    Iter it;
    
    void insert(Node* target, int e);
    void erase(Node* target);
}

 

Iterator

DLL에 대해 더 알아보기 전 iterator가 무엇인지 대강 알 필요가 있다.

 

정확한 내용은 여기에서 보자.

 

iterator는 position에 대한 ADT이고, "iterating over a collection of elements" 같은 일을 할 수 있다.

 

어떤 자료구조 V 가 iteratable 하다면, 다음과 같이 iterator it 를 이용해 모든 element에 접근할 수 있다.

 

for (it = V.begin(); it != V.end(); it = V.next())

 

여기서 { begin, end, next }는 Array-based implementation에선 { 0, n, i + 1 }, Linked List-based implementation에선 { header, trailer, next }이다.

 

앞으로 iterator를 줄여서 it으로 부르기로 하자.

 

 

Insertion

insert(e); it이 가리키는 노드 p 앞에 원소 e를 삽입하자.

 

다음과 같은 순서로 const time에 할 수 있다.

 

새 노드 N 할당 > N의 element 지정 > N의 prev, next가 각각 p의 이전 노드, p를 가리키게 함 > p의 이전 노드의 next, p의 prev가 N을 가리키게 함

 

아래는 구현 예시이다.

 

void insert(int e) {
    Node* newNode = new Node();
    Node *u = it.p->prev, *v = it.p; // 각각 p의 이전 노드, p
    newNode->data = e;
    newNode->prev = u; newNode->next = v;
    u->next = newNode; v->prev = newNode;
}

 

Deletion

delete(); it이 가리키는 노드 p를 삭제하자.

 

다음과 같은 순서로 const time에 할 수 있다.

 

p 이전 노드의 next, p 다음 노드의 prev가 각각 서로를 가리키게 함 > p 삭제

 

아래는 구현 예시이다.

 

void erase() {
    Node *u = it.p->prev, *v = it.p->next;
    delete it.p;
    u->next = v; v->prev = u;
    it.p = v;
}

 

Implementation

아래는 이론에서 배운 내용을 구현한 코드이다.

 

#include <bits/stdc++.h>
using namespace std;

/*

# Linked list-based implementation is shown below

# insert(e)		O(1)
# erase()		O(1)
# insert2(p, e)		O(n)
# size()		O(1)
# empty()		O(1)
# print()		O(n)

*/

struct Node {
	int data;
	Node* next;
	Node* prev;

	Node(int e) {
		data = e;
		next = nullptr;
		prev = nullptr;
	}
};
struct Iter {
	Node* p;
	Iter() { p = nullptr; }
	Iter(Node* ptr) { p = ptr; }
	int& operator *() {
		return p->data;
	}
	Iter& operator++() {
		p = p->next;
		return *this;
	}
	Iter& operator--() {
		p = p->prev;
		return *this;
	}
};

struct DLL {
	Node* head;
	Node* tail;
	Iter it;
	int sz;

	DLL() {
		head = new Node(0);
		tail = new Node(0);
		head->next = tail;
		tail->prev = head;
		it.p = tail;
		sz = 0;
	}
	~DLL() {

	}
	int size() {
		return sz;
	}
	bool empty() {
		return (size() == 0);
	}
	void insert(int e) {
		Node* newNode = new Node(e);
		Node* u = it.p->prev;
		Node* v = it.p;
		u->next = newNode; newNode->prev = u;
		newNode->next = v; v->prev = newNode;
		sz++;
	}
	void insert2(int p, int e) {
		Node* newNode = new Node(e);
		Iter i(head->next);
		for (; p-- > 0; ++i) if (!i.p->next) return;
		Node* u = i.p->prev;
		Node* v = i.p;
		u->next = newNode; newNode->prev = u;
		newNode->next = v; v->prev = newNode;
		sz++;
	}
	bool erase() {
		if (empty()) return false;
		Node* u = it.p->prev;
		Node* v = it.p->next;
		delete it.p;
		u->next = v; v->prev = u;
		it.p = v;
		sz--;
		return true;
	}
	void print() {
		if (empty()) {
			cout << "Empty\n"; return;
		}
		for (Iter i(head->next); i.p != tail; ++i) {
			cout << *i << " ";
		}
		cout << "\n";
	}
	void reversePrint() {
		if (empty()) {
			cout << "Empty\n"; return;
		}
		for (Iter i(tail->prev); i.p != head; --i) {
			cout << *i << " ";
		}
		cout << "\n";
	}

};

int main() {
	DLL A;
	int TEST; cin >> TEST; while (TEST--) {
		string oper; int p, q; cin >> oper;
		if (oper == "insert") {
			cin >> p; A.insert(p);
		}
		else if (oper == "insert2") {
			cin >> p >> q; A.insert2(p, q);
		}
		else if (oper == "erase") {
			cout << (A.erase() ? "" : "Empty\n");
		}
		else if (oper == "begin") {
			A.it.p = A.head->next;
		}
		else if (oper == "end") {
			A.it.p = A.tail;
		}
		else if (oper == "++") {
			++A.it;
		}
		else if (oper == "--") {
			--A.it;
		}
		else if (oper == "print") {
			A.print();
		}
		else if (oper == "reversePrint") {
			A.reversePrint();
		}
		else if (oper == "size") {
			cout << A.size() << "\n";
		}
	}
}