Linked list

연결 리스트는 노드라는 단위로 구성되며 각 노드는 데이터와 다음 노드를 가리키는 포인터를 가지고 있다.

동적으로 메모리를 할당받아서 사용하기 때문에 element 추가 및 삭제가 쉽다.

topPtr는 head라고도 하며 연결 리스트의 시작점을 가리킨다. 리스트가 비어있다면 헤드는 nullptr를 가리킨다.

동적 메모리 할당으로 삽입 및 삭제가 빠르지만 포인터 저장을 위한 추가 메모리가 필요하다.

Struct NodeType {
    ItemType info;
    NodeType *next;
};

Stack Implementation

array를 사용하지 않고 dynamic allocation을 사용해서 stack에 element를 push하도록 내부 구현을 변경할 수 있다. Push, Pop, IsEmpty등 외부적으로는 동일하지만 내부에서는 linked list를 활용해서 구현한다.

new연산자는 heap에다 공간을 할당한 다음 그 위치를 가리키는 포인터를 리턴한다.

linked list는 node를 이어서 만든 list이다. 각 노드는 info와 next로 구성되어있다.

info에는 user가 넣을 데이터가 들어가고 next는 다음 노드의 위치를 가리키는 포인터가 들어간다.

Implementing Push

void StackType::Push(ItemType newItem)
// Adds newItem to the top of the stack.
{
    if (IsFull())
        throw FullStack();
    NodeType *location;
    location = new NodeType<ItemType>;
    location->info = newItem;
    location->next = topPtr;
    topPtr = location;
}

Implementing Pop

void StackType::Pop() // Remove top item from Stack.
{
    if (IsEmpty())
        throw EmptyStack();
    else {
        NodeType *tempPtr;
        tempPtr = topPtr;
        topPtr = topPtr->next;
        delete tempPtr;
    }
}
ItemType StackType::Top()
// Returns a copy of the top item in the stack.
{
    if (IsEmpty())
        throw EmptyStack();
    else
        return topPtr->info;
    39
}