[7. 연결리스트] 7.6, 7.7 리스트에서 노드 삭제하기

[해당 문제는 266가지 문제로 정복하는 코딩 인터뷰]
책의 내용의 문제와 풀이를 베이스로 공부하는 내용이다. 

문제를 풀기전에 단순하게 문제를 푸는것이 목적이 아닌
시간복잡도와 공간복잡도의 관계를 계산하며,
자료구조의 이해도와 실력을 향상하는데 목적이 있다.

---

https://msugi.tistory.com/47

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

연결리스트 문제를 풀기전 LinkedList를 위와 같이 직접 구현했다. 위 LikedList를 이용하여 문제를 풀 예정이다.

---

Q 7.6, 7.7 리스트에서 노드 삭제하기
원래는 7.6 단순 연결리스트에서 노드 삭제하기, 7.7 리스트에서 뒤에서 k번째 원소 삭제하기 이다.
하지만 해당 문제 2개가 7.0 연결리스트 기초 작업에서 작업한 LinkedList.h 의 DelNode 부분과 FindNode와 매우 유사해서 해당부분으로 대체 하려고 한다.

---

https://msugi.tistory.com/47 의 내용이지만 한번 더 소스코드를 작성해보면 다음과 같다.

//문제 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<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;
}