C++로 구현하는 자료구조 (2) - LinkedList

C++로 구현하는 자료구조

두번째 포스팅은 대표적인 선형 자료구조인 연결리스트이다. 알고리즘과 자료구조를 공부하면서 장벽이었던 녀석이기도 하다. 구현과 더불어 연결리스트를 알고리즘 문제에서 다룰 때 하지 말아야할 실수를 정리한다.

 

---

1. LinkedList (연결리스트)

연결리스트는 자료를 저장하고 포인터를 이용해서 다음 자료를 가르키는 형식으로 구성된 선형 자료구조이다. 처음 연결리스트를 공부할 때 동적배열과 차이점을 파악하지 못했다. 가장 큰 차이점은 바로 메모리에 저장방식에 있다.

배열 혹은 동적배열의 경우 메모리에 자료를 저장할때 순서대로 저장된다. 연결리스트는 현재 메모리에 비어있는 곳에 랜덤하게 저장되고 자료를 접근할 때에는 포인터로만 접근을 한다.

 

2. 연결리스트를 다룰 때 주의할 점

연결리스트를 다룰 때 주의할 점은 데이터를 추가하는 등의 연산을 수행할 때 포인터를 잘 신경써줘야 하는 점이다. 다음 자료를 추가할 때 포인터에 끝까지 가서 추가하면 안된다.

// 끝 노드에서 자료를 추가하면 포인터에 연결해준 것이 아니게된다.
last = new Node(data)

// 이와 같은 방식으로 next 포인터에 자료를 할당해야 한다!
previous.next = new Node(data)

자료를 추가하거나 제거할 때 꼭 제거하려는 대상의 포인터로 진행해서 연산을 하는 것이 아니라, 이전이나 이후에서 연결을 조작해줘야 하는 점이 연결리스트 문제의 핵심이라고 볼 수 있겠다.

 

3. 소스코드

#pragma once

#include <iostream>
using namespace std;

template <typename T>
class Node {
public:
    T value;
    Node<T>* next;
    Node(T value) : value(value) {}
};

template <typename T>
class LinkedList {
private:
    int size = 0;
    Node<T>* head;
public:
    void add(T value) {
        if (this->head) {
            Node<T>* cursor = this->head;
            while (cursor->next) {
                cursor = cursor->next;
            }
            cursor->next = new Node<T>(value);
        }
        else {
            this->head = new Node<T>(value);
        }
        this->size++;
    }

    T get(const int& index) {
        if (index < 0 || index > this->size) {
            throw std::out_of_range("범위초과");
        }

        int idx = 0;
        Node<T>* cursor = this->head;
        while (idx != index) {
            cursor = cursor->next;
            idx++;
        }

        return cursor->value;
    }

    void remove(const int& index) {
        if (index < 0 || index > this->size) {
            throw std::out_of_range("범위초과");
        }
        if (this->size == 0) return;

        if (index == 0) {
            Node<T>* cursor = this->head;
            this->head = this->head->next;
            delete cursor;
        }
        else {
            int idx = 0;
            Node<T>* cursor = this->head;
            while (idx != index - 1) {
                cursor = cursor->next;
                idx++;
            }

            Node<T>* tmp = cursor->next;
            cursor->next = cursor->next->next;
            delete tmp;
        }

        this->size--;
    }

    int length() {
        return this->size;
    }
};

#include <string>
#include <iostream>
#include "datastructure/LinkedList.h"

using namespace std;

int main() {

    LinkedList<string>* list = new LinkedList<string>();
    list->add("abc");
    list->add("bca");
    list->add("cba");

    for (int i = 0; i < list->length(); i++) {
        cout << list->get(i) << endl;
    }

    cout << endl;
    list->remove(1);

    for (int i = 0; i < list->length(); i++) {
        cout << list->get(i) << endl;
    }

    return 0;
}