geminanolja 님의 블로그

Node* RemoveNode(Node* node){ Node* prevNode = node->prev; Node* nextNode = node->next; prevNode->next = nextNode; nextNode->prev = prevNode; delete node; return nextNode;}void InsertNode(Node* posNode, int data){ Node* node = new Node(data); Node* prevNode = posNode->prev; prevNode->next = node; node->prev = prevNode; node->next = posNode; posNode->prev = node;}

자료구조&알고리즘/C++ 2024. 12. 11. 10:48

Noded 삽입 삭제 코드 구현 #pragma once#include using namespace std;class Node{ //typedef int T; Old style using T = int;public : //constructor :int타입의 변수를 받아서 T data에 넣어주고 //prev & next는 nullptr로 초기화 Node(int data) : data(data), prev(nullptr), next(nullptr) { }public: T data; Node* prev; Node* next;};class List{public: List() { //더미 노드 두개를 앞뒤로 만들기 _head = new Node(0); _tail = new Node(0); _head->ne..

자료구조&알고리즘/C++ 2024. 12. 11. 09:00

이중 연결 리스트 는 각 노드가 이전 노드와 다음노드에 대한 포인터를 포함한 연결 리스트이다.리스트를 앞족과 뒤쪽 모두에서 탐색가능하여 노드 삽입과 삭제가 단일 연결 리스트(singly Linked List)보다 효율적이다 시간 복잡도 측면에서 탐색(Search)는 O(N), 삽입(Inserion)의 경우에는 헤드에 삽입시 O(1)의 상수 시간에 처리 가능하며, 맨 뒤에 삽입(Tail)시에도 O(1)의 시간이 소요 된다. 다만 중간에 삽입할 경우에는 삽일할 위치가 탐색되었다는 가정하에 O(1)의 탐색 시간이 소요된다. (만약 탐색까지 포함한다면 O(N) + O(1)의 시간 복잡도를 가지게 된다.삭제도 동일하다. DDL 연산 시간 복잡도 요약연산시간 복잡도설명탐색O(N)O(N)O(N)최악의 경우 리스트 전..

자료구조&알고리즘/C++ 2024. 12. 11. 08:49