doubly linked list (이중 연결 리스트)

구현한 코드

#include<iostream>
using namespace std;

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

class linkedList {
public:
	linkedList();
	void append(int inputValue);
	void deletion(int idx);
	void insertion(int idx, int inputValue);
	void print();
	void at(int idx);
	bool isEmpty();
private:
	node* header;
	node* trailer;
	int listSize;
};

linkedList::linkedList() {
	header = new node;
	trailer = new node;
	header->data = NULL;
	trailer->data = NULL;
	header->next = trailer;
	header->prev = NULL;
	trailer->next = NULL;
	trailer->prev = header;
	listSize = 0;
}

void linkedList::append(int inputValue) {
	node* newNode = new node;
	newNode->data = inputValue;

	newNode->prev = trailer->prev;
	newNode->next = trailer;
	trailer->prev->next = newNode;
	trailer->prev = newNode;

	listSize++;
}

void linkedList::deletion(int idx) {
	node* curNode = header->next;
	node* preNode = header;
	if (idx != 0) {
		for (int i = 0; i < idx - 1; i++) {
			preNode = curNode;
			curNode = preNode->next;
		}
	}
	preNode->next = curNode->next;
	curNode->next->prev = preNode;
	delete curNode;

	listSize--;
}
void linkedList::insertion(int idx, int inputValue) {
	node* newNode = new node;
	if (isEmpty()) {
		append(inputValue);
		return;
	}
	node* curNode = header->next;
	node* preNode = header;
	newNode->data = inputValue;
	if (idx != 0) {
		for (int i = 0; i < idx - 1; i++) {
			preNode = curNode;
			curNode = preNode->next;
		}

	}
	preNode->next = newNode;
	newNode->prev = preNode;
	newNode->next = curNode;
	curNode->prev = newNode;

	listSize++;
}
void linkedList::print() {
	if (isEmpty()) {
		return;
	}
	node* curNode = header->next;
	for (int i = 0; i < listSize-1; i++) {
		cout << curNode->data << ' ';
		curNode = curNode->next;
	}
	cout << curNode->data << endl;

}
void linkedList::at(int idx) {
	node* curNode = header->next;
	node* preNode = header;
	if (idx != 0) {
		for (int i = 0; i < idx - 1; i++) {
			preNode = curNode;
			curNode = preNode->next;
		}
	}
	cout << curNode->data << endl;
}

bool linkedList::isEmpty() {
	if (listSize == 0) {
		return true;
	}
	else {
		return false;
	}
}



int main() {
	linkedList lList;
	string inputCommand = "";
	int inputValue = 0;
	int idx = 0;
	while (true) {
		cin >> inputCommand;
		if (inputCommand == "insertion") {
			cin >> idx >> inputValue;
			lList.insertion(idx,inputValue);
		}
		else if (inputCommand == "append") {
			cin >> inputValue;
			lList.append(inputValue);
		}
		else if (inputCommand == "print") {
			lList.print();
		}
		else if (inputCommand == "deletion") {
			cin >> idx;
			lList.deletion(idx);
		}
		else if (inputCommand == "at") {
			cin >> idx;
			lList.at(idx);
		}

	}
	return 0;

}

 

이중 연결 리스트는 단일 연결 리스트의 탐색 기능을 개선한 자료구조로 단일 연결 리스트의 노드가 다음 노드뿐만아니라 이전 노드를 가리키는 포인터를 추가적으로 가지고 있다. 단일 연결 리스트와는 달리 양방향 탐색이 가능하다.