자료구조 List에 대한 설명과 구현

리스트란?

 

1. 각각의 데이터가 자신의 다음 데이터(또는 이전, 다음 데이터 모두)의 위치를 가지고 있는 자료구조
2. 데이터가 메모리에서 연속적으로 위치하고 있지는 않다.

리스트 종류

1. Singly Linked List - 데이터가 자신의 다음 데이터의 위치만 가지고 있다.
2. Double Linked List - 데이터가 자신의 이전과 다음 데이터의 위치를 가지고 있다.
3. Circular Linked List - 마지막 데이터가 처음 데이터의 위치를 가지고 있다.

리스트 연산의 시간 복잡도

• 데이터를 추가(임의의 위치) - O(1)
• 데이터를 제거(임의의 위치) - O(1)
• 데이터 확인/변경 - O(N)

리스트 구현(Singly Linked List)

#include<iostream>

using namespace std;

template<class T>
class Node
{
private:
    T data; // 데이터
public:
    Node<T> * nextNode; // 다음 노드를 가리키는 포인터
    T GetData()
    {
        return data;
    }
    Node(int k) : data(k), nextNode(NULL) {}
};

// 노드 추가
template<class T>
void AppendNode(Node<T>** Head, Node<T>* NewNode)
{
    if ((*Head) == NULL)
    {
        *Head = NewNode;
    }
    else
    {
        Node<T>* Tail = (*Head);
        while (Tail->nextNode != NULL)
        {
            Tail = Tail->nextNode;
        }
        Tail->nextNode = NewNode;
    }
}

// 노드 위치 반환
template<class T>
Node<T>* GetNodeAt(Node<T>* Head, int location)
{
    Node<T>* current = Head;
    while (current != NULL && (--location) >= 0)
    {
        current = current->nextNode;
    }
    return current;
}

// 노드 삭제
template<class T>
void RemoveNode(Node<T>** Head, Node<T>* Remove)
{
    if (*Head == Remove)
    {
        *Head = Remove->nextNode;
    }
    else
    {
        Node* Current = *Head;
        //처음부터 지우려는 노드의 이전 노드까지 순회
        while (Current != NULL && Current->nextNode != Remove) 
        {
            Current = Current->nextNode;
        }
        if (Current != NULL)
        {
            Current->nextNode = Remove->nextNode;
        }
    }
}

// 노드 삽입
template<class T>
void InsertNode(Node<T>* Current, Node<T>* NewNode)
{
    NewNode->nextNode = Current->nextNode;
    Current->nextNode = NewNode;
}

// 노드 갯수 반환
template<class T>
int GetNodeCount(Node<T>* Head)
{
    int count = 0;
    Node<T>* Current = Head;
    while (Current != NULL)
    {
        Current = Current->nextNode;
        count++;
    }
    return count;
}