연결 리스트 (Linked List)

연결리스트란?

연결 리스트는 노드를 사용하여 구현하는데, 노드란 어떤 자료구조를 구성하기 위해 사용되는 각 요소를 의미한다. 값을 래핑하는 역할을 한다.

사용하려는 자료 구조에 따라 노드를 연결하기위해 next, prev 등의 포인터를 사용한다.

일반적으로 연결 리스트에서는 노드에 next 포인터(다른 노드를 참조)를 추가하여 구현한다.

연결 리스트

연결 리스트는 이미지처럼 노드의 next 필드가 다음 노드를 참조하고 있다. 따라서 값을 추가 할때 마다 현재의 최상위 노드와 새로운 노드를 연결해줘야 한다.

이는 대략적으로 다음과 같은 구조가 된다.

//노드
class Node<T> is
    T data
    Node<T> next
    
//연결 리스트
class LinkedList<T> is
    Node<T> head;
    Node<T> tail;
    ...

연결 리스트에 새로운 값을 추가하려면 새로운 노드의 next를 head로 설정하고, head를 새로운 노드로 설정한다.

연결 리스트에 새로운 노드를 추가

반대로 제거할 때도, head를 다음 노드로 설정하고, 제거할 노드를 해제한다.

연결 리스트는 여러 종류가 있지만, 단방향의 경우 head는 가장 마지막에 들어온 요소를 의미한다.

연결 리스트의 필수기능 구현

값 추가 (push_back)

method push_back(Item item) is
    Node newNode = new Node(item)
    newNode.next = head
    head = newNode
    
    size++;

값 제거 (pop_back)

method pop_back(): Item is
    if is_empty() then
        throw EmptyListException
    
    Node temp = head
    Item item = temp.data
    head = temp.next
    
    size--;
    
    return item

공백 확인 (is_empty)

method is_empty(): boolean is
    return size == 0

연결 리스트의 구현

Node Class

template <typename U>
struct Node {
    U data;
    Node *next;

    explicit Node(const U& data): data(data), next(nullptr) {}
};

LinkedList Class

template <typename T>
class LinkedList {
private:
    Node<T>* head;
    size_t size;
public:
    LinkedList(): head(nullptr), size(0) {}
    ~LinkedList();
    void push_back(T value);
    T pop_back();
    bool is_empty() const;
    friend ostream& operator<<(ostream& os, const LinkedList<T>& list) {
        os << "[";
        Node<T>* current = list.head;
        while (current != nullptr) {
            os << current->data;
            current = current->next;
            if (current != nullptr) {
                os << ", ";
            }
        }
        os << "]";
        return os;
    }
};

push_back 구현

template<typename T>
void LinkedList<T>::push_back(T value) {
    auto* newNode = new Node<T>(value);
    newNode->next = head;
    head = newNode;

    size ++;
}

pop_back 구현

template<typename T>
T LinkedList<T>::pop_back() {
    if (is_empty()) throw underflow_error("The linked list is empty");
    auto* current = head;
    T value = current->data;
    head = current->next;
    delete current;
    size --;
    return value;

}

is_empty 구현

template<typename T>
bool LinkedList<T>::is_empty() const {
    return size == 0;
}

클라이언트 코드

LinkedList<int> list;

list.push_back(2);
cout << "add new " << 2 << ": " << list << endl;

list.push_back(7);
cout << "add new " << 7 << ": " << list << endl;

list.push_back(5);
cout << "add new " << 5 << ": " << list << endl;

int removed = list.pop_back();
cout << "remove " << removed << ": " << list << endl;
list.push_back(4);
cout << "add " << 4 << ": " << list << endl;

cout << list << endl;

결과

add new 2: [2]
add new 7: [7, 2]
add new 5: [5, 7, 2]
remove 5: [7, 2]
add 4: [4, 7, 2]
[4, 7, 2]