[Data Structure] 자료구조(3강) - Linked List

• 수식이 제대로 보이지 않는다면, 새로고침(F5)을 해주시기 바랍니다.

자료구조 포스팅은 여러 자료 구조의 개념 및 c++로의 프로그래밍을 다룰 예정입니다. 자료 구조는 비교적 널리 알려져있고, 다른 곳에서도 잘 설명된 곳이 많기 때문에 자료구조에 한해서는 간단한 개념 및 구현만을 다루겠습니다. 간단히 정리된 것을 볼 수 있는 용도로 적합할 것 같습니다.
경쟁적 프로그래밍 문제 풀이에 유용한 c++의 STL의 헤더파일도 함께 다루겠습니다.

Linked List

아래에 구현한 코드는 단일 연결 리스트입니다. 즉, 앞에서 뒤쪽으로만 탐색이 가능한 리스트입니다. Node 클래스가 존재하고, Node 안에는 data와 next라는 멤버 변수가 존재합니다. data는 값을 저장하는 변수, next는 그 다음 노드를 가리키는 Node*입니다.
연결 리스트는 배열보다 동적으로 자료를 할당하기 좋습니다.

#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node* next;

    Node(int val) {
        data = val;
        next = nullptr;
    }
};

class LinkedList {
private:
    Node* head;
    Node* tail;

public:
    LinkedList() {
        head = nullptr;
        tail = nullptr;
    }

    ~LinkedList() {
        while (head != nullptr) {
            Node* temp = head;
            head = head->next;
            delete temp;
        }
    }

    void push_front(int val) {
        Node* newer = new Node(val);
        newer->next = head;
        head = newer;
        if (tail == nullptr) tail = newer;
    }

    void push_back(int val) {
        Node* newer = new Node(val);
        if (tail == nullptr) {
            head = newer;
            tail = newer;
        } else {
            tail->next = newer;
            tail = newer;
        }
    }

    void pop_front() {
        if (head == nullptr) return;
        Node* temp = head;
        head = head->next;
        delete temp;
        if (head == nullptr) tail = nullptr;
    }

    void pop_back() {
        if (head == nullptr) return;
        if (head == tail) {
            delete tail;
            head = nullptr;
            tail = nullptr;
            return;
        }
        Node* temp = head;
        while (temp->next != tail) {
            temp = temp->next;
        }
        delete tail;
        tail = temp;
        tail->next = nullptr;
    }

    void insert(int pos, int val) {
        if (pos == 0) {
            push_front(val);
            return;
        }
        Node* temp = head;
        for (int i = 0; i < pos - 1 && temp != nullptr; ++i) {
            temp = temp->next;
        }
        if (temp == nullptr) return;
        Node* newer = new Node(val);
        newer->next = temp->next;
        temp->next = newer;
        if (newer->next == nullptr) tail = newer;
    }

    void remove(int pos) {
        if (head == nullptr) return;
        if (pos == 0) {
            pop_front();
            return;
        }
        Node* temp = head;
        for (int i = 0; i < pos - 1 && temp->next != nullptr; ++i) {
            temp = temp->next;
        }
        Node* to_delete = temp->next;
        if (to_delete == nullptr) return;
        temp->next = to_delete->next;
        if (to_delete == tail) tail = temp;
        delete to_delete;
    }

    bool empty() const {
        return head == nullptr;
    }

    int size() const {
        int cnt = 0;
        Node* temp = head;
        while (temp != nullptr) {
            ++cnt;
            temp = temp->next;
        }
        return cnt;
    }

    void print() const {
        cout << "[";
        Node* temp = head;
        while (temp != nullptr) {
            cout << temp->data;
            if (temp->next != nullptr) cout << ", ";
            temp = temp->next;
        }
        cout << "]\n";
    }
};

int main() {
    LinkedList list;
    list.push_back(10);
    list.push_back(20);
    list.push_front(5);
    list.insert(1, 15); // [5, 15, 10, 20]
    list.print();

    list.pop_front();  // [15, 10, 20]
    list.pop_back();   // [15, 10]
    list.print();

    list.remove(1);    // [15]
    list.print();

    cout << "Size: " << list.size() << '\n';
    cout << (list.empty() ? "Empty" : "Not empty") << '\n';

    return 0;
}

C++ <list> 사용법 요약

list 헤더에 구현되어 있는 것은 이중 연결 리스트(doubly linked list)입니다. 양 방향 접근이 가능합니다.

함수	설명
push_front(val)	리스트 맨 앞에 요소 삽입
push_back(val)	리스트 맨 뒤에 요소 삽입
pop_front()	맨 앞 요소 제거
pop_back()	맨 뒤 요소 제거
insert(pos, val)	pos 위치에 요소 삽입 (iterator 필요)
erase(pos)	pos 위치의 요소 제거 (iterator 필요)
remove(val)	특정 값과 일치하는 모든 요소 제거
clear()	모든 요소 제거
empty()	리스트가 비어 있는지 여부 확인
size()	현재 요소 개수 반환
begin() / end()	반복자 반환 (순회용)
reverse()	리스트 순서를 뒤집음
sort()	리스트 정렬

#include <iostream>
#include <list>
using namespace std;

int main() {
    list<int> lst;

    lst.push_back(10);
    lst.push_front(5);
    lst.push_back(20);

    for (int val : lst)
        cout << val << ' ';  // 출력: 5 10 20
}