[C++]Shuffle Doubly linked list

1. 알고리즘 설명

: 연결리스트를 반으로 나누어진 두 개의 연결리스트를 shuffle시키는 알고리즘

ex) 1234567890 → 6172839405

 

1-1. 알고리즘 동작

Ⅰ. 연결리스트를 반으로(1st half + 2nd half) 나누는 중간 노드를 찾는다

한동대 2023-2 데이터 구조 강의자료

 

Ⅱ. 기존 연결리스트에서 1st half 연결리스트는 떼고 2nd half 연결리스트만 연결시킨다

한동대 2023-2 데이터 구조 강의자료

 

Ⅲ. 1st half 연결리스트가 끝에 다다를때까지 기존 연결리스트에 끼워넣는다

한동대 2023-2 데이터 구조 강의자료

 

 

1-2. 알고리즘 구현

1-2-1. Doubly linked list with sentinel nodes

2023.11.29 - [C++/자료구조] - [C++]Doubly linked list with sentinel nodes

 

[C++]Doubly linked list with sentinel nodes

 

1-2-2. Shuffle 알고리즘 구현

//연결리스트 반으로 나누었을 때 그 기준 노드 반환하는 함수

Node * half() {
	//가운데 있는 노드 반환
	Node* turtle;
	Node* rabbit;
	turtle = rabbit = begin();
	while (rabbit != end() && rabbit != last()) {
		rabbit = rabbit->getNext()->getNext();
		turtle = turtle->getNext();
	}
	return turtle;

}​

//shuffle동작 수행하는 함수

void shuffle() {
	Node* mid = half();
	
	//1st half를 독립적인 연결리스트로 떼놓기
	Node* front = begin();
	front->setPrev(NULL);
	mid->getPrev()->setNext(NULL);

	//2nd half를 기존 연결리스트에 연결시키기
	head->setNext(mid);
	mid->setPrev(head);

	Node* front_cur = front;
	Node* back_cur = mid;
	while (front_cur != NULL) {
		Node* front_next = front_cur->getNext();
		Node* back_next = back_cur->getNext();

		back_cur->setNext(front_cur);
		back_next->setPrev(front_cur);
		front_cur->setNext(back_cur);
		front_cur->setNext(back_next);

		back_cur = back_next;
		front_cur = front_next;
	}

}​

 

1-2-3. 전체 소스코드

main.cpp

int main() {
	LinkedList list;
	for (int i = 1; i <= 9; i++) {
		list.push_back(i);
	}
	list.push_back(0);
	cout << "[원본 연결 리스트]" << endl;
	list.traverse();

	list.shuffle();
	cout << "[Shuffle 알고리즘 적용한 후]" << endl;
	list.traverse();
	return 0;

}​

 

LinkedList.h

#pragma once
#include <iostream>
#include <unordered_set>
using namespace std;

class Node {
private:
	int data;
	Node* prev;
	Node* next;
public:
	Node(int item, Node* pre, Node* link) : data(item), prev(pre), next(link) {}
	Node(int item) : data(item), prev(NULL), next(NULL) {}
	int getData() {
		return data;
	}
	Node* getPrev() {
		return prev;
	}
	Node* getNext() {
		return next;
	}
	void setPrev(Node* pre) {
		prev = pre;
	}
	void setNext(Node* link) {
		next = link;
	}
	friend class LinkedList;
};

class LinkedList
{
private:
	Node* head;
	Node* tail;
	int size;

public:
	LinkedList() :head(new Node(0,NULL,NULL)),tail(new Node(0,NULL,NULL)),size(0) {
		head->setNext(tail);
		tail->setPrev(head);
		
	}
	Node* begin() {
		return head->getNext();
	}
	Node* end() {
		return tail;
	}
	bool isEmpty() {
		return begin() == end();
	}
	Node* last() {
		return end()->getPrev();
	}
	int Size() {
		int cnt = 0;
		for (Node* cur = begin(); cur != end(); cur = cur->getNext()) {
			cnt++;
		}
		return cnt;
	}
	Node* find(int item) {
		Node* cur = begin();
		while (cur != end() && cur->getData() != item) {
			cur = cur->getNext();
		}
		if (cur == end()) {
			cout << "해당 노드는 존재하지 않습니다\n";
			return NULL;
		}
		return cur;
	}
	Node* erase(Node* item) {
		if (item == end() ) {
			return NULL;
		}
		item->getPrev()->setNext(item->getNext());
		item->getNext()->setPrev(item->getPrev());
		

		return item->getPrev();
	}
	void pop(int item) {
		Node* delNode = find(item);
		if (delNode != end() && delNode != begin()) {
			erase(delNode);
		}
		else {
			cout << "해당 노드는 존재하지 않습니다\n";
		}
	}
	void insert(Node* pos, int item) {
		//pos 앞에 삽입
		if (pos==NULL ) {
			cout << "삽입할 수 없습니다\n";
			return;
		}
		Node* newNode = new Node(item, pos->getPrev(), pos);
		pos->getPrev()->setNext(newNode);
		pos->setPrev(newNode);
	}
	void push_front(int value) {
		insert(begin(), value);
	}
	void push_back(int value) {
		insert(end(), value);
	}
	void push(int value, int target) {
		insert(find(target), value);
	}
	void pop_front() {
		if (!isEmpty()) {
			erase(begin());
		}
	}
	void pop_end() {
		if (!isEmpty()) {
			erase(last());
		}
	}
	void pop_all(int item) {
		for (Node* curNode = begin(); curNode != end(); curNode = curNode->getNext()) {
			if (curNode->data == item) {
				curNode = erase(curNode);
			}
		}
	}
	void unique() {
		unordered_set <int> set;
		for (Node* curNode = begin(); curNode != end(); curNode = curNode->getNext()) {
			if (set.find(curNode->data) == set.end()) {
				//중복 없는 상태
				set.emplace(curNode->data);
			}
			else {
				curNode = erase(curNode);
			}
		}
	}


	void traverse() {
		
		Node* curNode = begin();
		while (curNode != end()){
			cout << curNode->data;
			if (curNode->getNext()!= end()) {
				cout << " -> ";
			}
			curNode = curNode->getNext();
		}
		cout << endl << endl;
	}

	void reverse() {
		Node* curNode = begin();
		// head 4 5 6 7 tail
		// head 7 6 5 4 tail
		while (curNode != end()) {
			Node* temp_next = curNode->getNext();
			curNode->setNext(curNode->getPrev());
			curNode->setPrev(temp_next);
			curNode = temp_next;
		}
		Node* firstNode = begin();
		Node* lastNode = last();
		head->setNext(lastNode);
		tail->setPrev(firstNode);
		begin()->setPrev(head);
		last()->setNext(tail);
		
	}

	Node * half() {
		//가운데 있는 노드 반환
		Node* turtle;
		Node* rabbit;
		turtle = rabbit = begin();
		while (rabbit != end() && rabbit != last()) {
			rabbit = rabbit->getNext()->getNext();
			turtle = turtle->getNext();
		}
		return turtle;

	}

	void Split(Node * half,LinkedList * front, LinkedList * back) {
		Node* curNode = begin();
		while (curNode != half) {
			front->push_back(curNode->data);
			curNode = curNode->next;
		}
		while (curNode != end()) {
			back->push_back(curNode->data);
			curNode = curNode->next;
		}
	}

	

	void shuffle() {
		Node* mid = half();
		
		//1st half를 독립적인 연결리스트로 떼놓기
		Node* front = begin();
		front->setPrev(NULL);
		mid->getPrev()->setNext(NULL);

		//2nd half를 기존 연결리스트에 연결시키기
		head->setNext(mid);
		mid->setPrev(head);

		Node* front_cur = front;
		Node* back_cur = mid;
		while (front_cur != NULL) {
			Node* front_next = front_cur->getNext();
			Node* back_next = back_cur->getNext();

			back_cur->setNext(front_cur);
			back_next->setPrev(front_cur);
			front_cur->setNext(back_cur);
			front_cur->setNext(back_next);

			back_cur = back_next;
			front_cur = front_next;
		}

	}
};​

(좌) 노드의 개수가 짝수인 경우 / (우) 노드의 개수가 홀수인 경우