[7. 연결리스트] 7.0 연결리스트 기초 작업

/*
@ 최종 수정 25. 02. 26

• DelNode 의 TailNode가 제대로 주소를 가리키도록 수정
  
  
• AddNode가 기본적으로 순환구조를 가지도록 수정
  
  
• ListPivoting 의 PrevNode 와 NextNode의 연결 문제 수정
• ListPivoting 의 RightList에 bool연산을 추가하여 문제 없이 작동하도록 수정
• ListPivoting 의 TailNode가 제대로 마지막 주소를 가리키도록 수정
• ListPivoting 의 동적할당된 LeftList를 제대로 delete하도록 수정
• ListPivoting 의 LeftList의 첫 주소가 0으로 시작되는 점을 nullptr을 가리키도록 수정
  
  
• RemoveDuplicates 의 PrevNode가 이전주소를 가리키도록 수정
• RemoveDuplicates 의 TailNode의 위치를 마지막으로 제대로 수정
• RemoveDuplicates 의 중복된 원소 삭제시 바로 delete가 되도록 설정
  
  
• CyclicallyRightShfitList 의 불필요한 내용들 전부 삭제후 간단하게 다시 수정
• CyclicallyRightShfitList 에서 HeadNode와 TailNode를 사용해 문제를 해결하도록 수정
  
  
• EvenOddMerge 에서 PrevNode와 TailNode가 주소를 제대로 가리키도록 수정
• EvenOddMerge 에서 예외 조건 추가 및 홀수 짝수를 제대로 구분하도록 변경
• EvenOddMerge 의 내부의 Node들의 타입을 Node<T>타입에서 Node<int> 타입으로 변경

*/

연결리스트 단원의 문제를 풀기전에 연결리스트 STL을 이용하지 않고 문제를 풀기위한 기초 작업이다.
해당 내용은 다음과 같다.

//LinkedList.h#pragma once
#include<iostream>
 
template <typename T>
struct Node
{
    T data;
    Node* PrevNode;
    Node* NextNode;
};
 
template <typename T>
struct List
{
    Node<T>* HeadNode;
    Node<T>* TailNode;
    int Count;
};
 
template <class T>
class LinkedList
{
public:
 
    List<T>* list;
 
    LinkedList();
    void InitList(List<T>* list);
 
    Node<T>* CreateNode(T data);
    Node<T>* FindNode(List<T>* list, T data);
 
    void AddNode(List<T>* list, Node<T>* node);
 
    void PrintAllNode(List<T>* list);
    void DelNode(List<T>* list, T data); // 7.6 7.7
 
    void RemoveDuplicates(List<T>* L); //7.8
    void CyclicallyRightShfitList(List<T>* L, int k); //7.9
    void EvenOddMerge(List<T>* L); //7.10
 
    void ListPivoting(List<T>* L, int x); //7.12
 
private:
    
};
 
template<typename T>
LinkedList<T>::LinkedList()
{
    list = nullptr;
    InitList(list);
}
 
template<typename T>
void LinkedList<T>::InitList(List<T>* list)
{
    list = new List<T>();
    list->HeadNode = nullptr;
    list->TailNode = nullptr;
    int count = 0;
    this->list = list;
}
 
template<typename T>
Node<T>* LinkedList<T>::CreateNode(T data)
{
    Node<T>* node = new Node<T>();
    node->data = data;
    node->PrevNode = nullptr;
    node->NextNode = nullptr;
    return node;
}
 
// 기본적으로 순환구조로 만듬
template<typename T>
void LinkedList<T>::AddNode(List<T>* list, Node<T>* node) 
{
    if (!(list) || !node) { return; }
 
    if (list->Count == 0)
    {
        list->HeadNode = list->TailNode = node;
        node->NextNode = node->PrevNode = node;
    }
    else
    {
        node->PrevNode = list->TailNode;
        node->NextNode = list->HeadNode;
    
 
        list->TailNode->NextNode = node;
        list->HeadNode->PrevNode = node;
        list->TailNode = node;
    }
    list->Count++;
}
 
template<typename T>
void LinkedList<T>::PrintAllNode(List<T>* list)
{
    if (!list) { return; }
    std::cout << std::endl;
    if (list->Count == 0)
    {
        std::cout << " List is empty " << std::endl;
        return;
    }
 
    std::cout << " Print All Node " << std::endl;
    int idx = 1;
    int cnt = list->Count;
    Node<T>* n = list->HeadNode;
    while (idx <= cnt)
    {
        std::cout << "[" << idx << "]" << n->data << std::endl;
        n = n->NextNode;
        idx++;
    }
    std::cout << std::endl;
}
 
//문제 7.6, 7.7이 해당 함수와 유사하여 대체.
template<typename T>
void LinkedList<T>::DelNode(List<T>* list, T data) 
{
    Node<T>* n = LinkedList<T>::FindNode(list, data);
    Node<T>* temp = list->HeadNode;
    if (!(list) || !n) { return; }
    while (n->data != temp->data)
    {
        temp = temp->NextNode;
    }
    std::cout << "Delete Node data : " << n->data << std::endl;
    if (list->Count == 1)
    {
        list->HeadNode = list->TailNode = nullptr;
        delete(n);
    }
    else
    {
        if (list->HeadNode == n)
        {
            list->HeadNode = n->NextNode;
            list->HeadNode->PrevNode = n->PrevNode;
            delete(n);
        }
        else if (list->TailNode == n)
        {
            list->TailNode = n->PrevNode;
            list->TailNode->NextNode = n->NextNode;
            delete(n);
        }
        else
        {
            temp = temp->PrevNode;
            temp->NextNode = n->NextNode;
            temp = temp->NextNode;
            temp->PrevNode = n->PrevNode;
            delete(n);
        }
    }
    list->Count--;
}
 
//정렬이 되어있을때 적용가능하다.
template<class T>
inline void LinkedList<T>::RemoveDuplicates(List<T>* L) // 문제 7.8 해당 함수로 대체
{
    Node<T>* iter = L->HeadNode;
    int count = L->Count;
    while(iter && --count > 0)
    {
        auto NextDistinct = iter->NextNode;
        while (NextDistinct && NextDistinct->data == iter->data)
        {
            NextDistinct = NextDistinct->NextNode;
            delete iter->NextNode;
            L->Count--;
        }
        iter->NextNode = NextDistinct;
        NextDistinct->PrevNode = iter;
        iter = iter->NextNode;
        L->TailNode = iter;
    }
}
 
//문제에서 시작과 끝은 nullptr을 갖도록 요구
template<class T>
inline void LinkedList<T>::CyclicallyRightShfitList(List<T>* L, int k) //문제 7.9
{
    if (!L || k==0) { return; }
 
    Node<T>* moveHead = L->HeadNode;
    Node<T>* moveTail = L->TailNode;
 
    moveTail->NextNode = moveHead;
    moveHead->PrevNode = moveTail;
    for (int i = 0; i < k; i++)
    {
        moveTail = moveTail->PrevNode;
    }
    moveHead = moveTail->NextNode;
    L->HeadNode = moveHead;
    L->TailNode = moveTail;
 
    moveHead->PrevNode = nullptr;
    moveTail->NextNode = nullptr;
}
 
//마지막이 nullptr인 단순연결에서 가능
template<class T>
inline void LinkedList<T>::EvenOddMerge(List<T>* L) //문제 7.10
{
    if (!L) { return; }
    Node<int>* temp = L->HeadNode->NextNode;
    Node<int>* EvenDummyHead = nullptr;
    Node<int>* OddDummyHead = nullptr;
 
    if (temp->data % 2 == 0)
    {
        EvenDummyHead = temp;
        OddDummyHead = L->HeadNode;
        EvenDummyHead->PrevNode = nullptr;
    }
    else if (temp->data % 2 == 1)
    {
        EvenDummyHead = L->HeadNode;
        OddDummyHead = temp;
        EvenDummyHead->PrevNode = nullptr;
    }
    else
    {
        return;
    }
    
    while (temp->NextNode != nullptr && EvenDummyHead->NextNode != nullptr)
    {
        EvenDummyHead->NextNode = EvenDummyHead->NextNode->NextNode;
        if (EvenDummyHead->NextNode != nullptr)
        {
            EvenDummyHead->NextNode->PrevNode = EvenDummyHead;
            EvenDummyHead = EvenDummyHead->NextNode;
        }
 
        temp->NextNode = temp->NextNode->NextNode;
        if (temp->NextNode != nullptr)
        {
            temp->NextNode->PrevNode = temp;
            temp = temp->NextNode;
        }
    }
    EvenDummyHead->NextNode = OddDummyHead;
    OddDummyHead->PrevNode = EvenDummyHead;
    L->TailNode = temp;
}
 
//마지막이 nullptr인 단순구조에서의 피벗
template<class T>
inline void LinkedList<T>::ListPivoting(List<T>* L, int x) // 문제 7.12
{
    Node<T>* DummyHead = new Node<T>();
    Node<T>* LeftList = new Node<T>();
    Node<T>* CenterList = new Node<T>();
    Node<T>* RightList = new Node<T>();
    Node<T>* TempTail = new Node<T>();
    
    DummyHead->NextNode = L->HeadNode;
    DummyHead = DummyHead->NextNode;
    bool bRightTail = true;
 
    while (DummyHead)
    {
        if (DummyHead->data < x)
        {
            LeftList->NextNode = DummyHead;
            DummyHead->PrevNode = LeftList;
            LeftList = LeftList->NextNode;
        }
        else if (DummyHead->data == x)
        {
            CenterList->NextNode = DummyHead;
        }
        else if (DummyHead->data > x)
        {
            RightList->NextNode = DummyHead;
            DummyHead->PrevNode = RightList;
            if (bRightTail)
            {
                TempTail = DummyHead;
                bRightTail = false;
            }
            RightList = RightList->NextNode;
        }
        DummyHead = DummyHead->NextNode;
    }
 
    LeftList->NextNode = CenterList->NextNode;
    CenterList->NextNode->PrevNode = LeftList;
    CenterList->NextNode->NextNode = TempTail;
    TempTail->PrevNode = CenterList->NextNode;
    RightList->NextNode = nullptr;
    L->TailNode = RightList;
    L->HeadNode->PrevNode = nullptr; // 위에서 LeftList를 바로사용하여 초기data값 0 이 계속 남아있는것을 삭제
    
    TempTail = nullptr;
    CenterList = CenterList->PrevNode;
    RightList = RightList->NextNode;
 
    while (LeftList) //동적할당된 LeftList를 지우기위한 작업
    {
        LeftList = LeftList->NextNode;
    }
    delete LeftList;
    delete TempTail;
    delete RightList;
    delete CenterList;
    delete DummyHead;
}
 
template<typename T>
Node<T>* LinkedList<T>::FindNode(List<T>* list, T data)
{
    if (!list) { return nullptr; }
 
    int idx = 1;
    int cnt = list->Count;
    Node<T>* n = list->HeadNode;
 
    while (idx <= cnt)
    {
        if (n->data == data)
        {
            std::cout << "Find Node data : " << data << std::endl;
            return n;
        }
        n = n->NextNode;
        idx++;
    }
    std::cout << "Can't find data" << std::endl;
    return nullptr;
}