★연결리스트 LinkedList

라이님과 챗gpt를 통해 LinkedList 템플릿을 정리해보았다. 

https://blog.naver.com/PostView.naver?blogId=kks227&logNo=220781402507&parentCategoryNo=&categoryNo=299&viewDate=&isShowPopularPosts=false&from=postList'

리스트(List), 배열(Array), 연결 리스트(Linked List)

 

라이님 블로그에서 unique_ptr 를 사용해서 좀 더 간단하고 안전한 코드가 되도록 chat gpt한테 시켰다.ㅎㅎ

 

아래 템플릿이 상당히 마음에 들어서 외워놓고 쓸 듯 하다. 

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

template<typename T>
class ListNode {
public:
    T value;
    unique_ptr<ListNode<T>> next;
    ListNode(T value, unique_ptr<ListNode<T>> next = nullptr) : value(value), next(move(next)) {}
};

template<typename T>
class LinkedList {
public:
    unique_ptr<ListNode<T>> head = nullptr;
    int size = 0;

    // 삽입 함수
    void insert(int k, T value) {
        if (k == 0) head = unique_ptr<ListNode<T>>(value, head);
        else {
            unique_ptr<ListNode<T>>* current = &head;
            while (k--) current = &((*current)->next);
            *current = make_unique<ListNode<T>>(value, move(*current));
        }
        size++;
    }

    // 삭제 함수
    void erase(int k) {
        if (k == 0) head = move(head->next);
        else {
            unique_ptr<ListNode<T>>* current = &head;
            while (k--) current = &((*current)->next);
            *current = move((*current)->next);
        }
        
        size--;
    }

    // 검색 함수
    int search(T value) const {
        auto current = head.get();
        for (int i = 0; i < size; ++i, current = current->next.get()) {
            if (current->value == value) return i;
        }
        return -1;
    }

    // 출력 함수
    friend ostream& operator<<(ostream& out, const LinkedList& list) {
        out << '[';
        for (auto current = list.head.get(); current != nullptr; current = current->next.get()) {
            out << current->value;
            if (current->next != nullptr) out << " , ";
        }
        out << ']';
        return out;
    }
};

int main() {
    LinkedList<int> list;
    list.insert(0, 1);
    cout << list << endl;
    list.insert(1, 2);
    cout << list << endl;
    list.insert(2, 3);
    cout << list << endl;
    list.insert(0, 0);
    cout << list << endl;
    list.erase(2);
    cout << list << endl;

    return 0;
}

insert 함수

unique_ptr<ListNode<T>>* current = &head;

current:  unique_ptr<ListNode<T>>* 타입의 포인터로 current를 head의 주소를 가리키는 포인터의 포인터로 초기화

 

WHY? 연결리스트에서 노드를 삽입하거나 삭제할 때 간접 참조를 통해 현재 가리키고 있는 노드의 포인터(즉, next 포인터)를 변경하기 위함이다. 이 방식을 사용하면, 특정 노드를 가리키는 포인터를 업데이트하거나 노드 사이의 연결을 변경할 때 코드를 명확하게 할 수 있다. 

 

current = &((*current)->next);

current 포인터를 다음 노드의 next 포인터로 업데이트한다.

 

operator <<

ostream& out : 출력 스트림 객체에 대한 참조로 std::cout뿐만 아니라 std::ostream 객체에 대해 데이터를 출력할 수 있다.

void printToStream(ostream& out, const string& message) {
    out << message;
}

printToStream(std::cout, "Hello, World!"); // 콘솔에 출력
ofstream fileStream("example.txt");
printToStream(fileStream, "Hello, file!"); // 파일에 출력

다음과 같이 ostream& out을 사용하면 출력 대상을 유연하게 할 수 있어 코드 재사용성과 범용성을 높인다.

 

양방향 연결 리스트

추가로 양방향 연결 리스트도 구현을 시켜보았다.

(참고로 이 리스트는 circular linked list가 아니다!!) 

 

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

template <typename T>
class ListNode {
public:
    T value;
    unique_ptr<ListNode<T>> next;
    ListNode<T>* before;

    ListNode(T value, unique_ptr<ListNode<T>> next = nullptr, ListNode<T>* before = nullptr) 
        : value(value), next(move(next)), before(before) {}
};

template <typename T>
class LinkedList {
public:
    unique_ptr<ListNode<T>> head = nullptr;
    ListNode<T>* tail = nullptr;
    int size = 0;

    // 삽입 함수 수정
    void insert(int k, T value) {
        if (k < 0 || k > size) {
            cout << "Invalid index." << endl;
            return;
        }

        if (k == 0) { // 리스트의 시작 부분에 삽입
            auto newNode = make_unique<ListNode<T>>(value, move(head), nullptr);
            if (newNode->next) {
                newNode->next->before = newNode.get();
            }
            head = move(newNode);
            if (size == 0) {
                tail = head.get();
            }
        } else { // 중간 또는 끝 부분에 삽입
            auto current = head.get();
            for (int i = 0; i < k - 1; ++i) {
                current = current->next.get();
            }
            auto newNode = make_unique<ListNode<T>>(value, move(current->next), current);
            if (newNode->next) {
                newNode->next->before = newNode.get();
            }
            current->next = move(newNode);
            if (k == size) {
                tail = current->next.get();
            }
        }
        size++;
    }

    // 삭제 함수 수정
    void erase(int k) {
        if (k < 0 || k >= size) {
            cout << "Invalid index." << endl;
            return;
        }

        if (k == 0) { // 첫 번째 노드 삭제
            head = move(head->next);
            if (head) {
                head->before = nullptr;
            } else {
                tail = nullptr; // 리스트가 비었다면 tail도 nullptr로 설정
            }
        } else {
            auto current = head.get();
            for (int i = 0; i < k - 1; ++i) {
                current = current->next.get();
            }
            auto toDelete = move(current->next);
            current->next = move(toDelete->next);
            if (current->next) {
                current->next->before = current;
            } else {
                tail = current; // 마지막 노드를 삭제한 경우 tail 업데이트
            }
        }
        size--;
    }

    int search(T value) const {
        auto current = head.get();
        for (int i = 0; i < size; ++i, current = current->next.get()) {
            if (current->value == value) return i;
        }
        return -1;
    }
};

여기서 주목할 점은 before에는 unique_ptr을 사용하지 않는다는 점!

노드의 생성과 소멸은 next 포인터가 전적으로 관할하게 하고, before 포인터는 단순 참조만 할 수 있도록 구현한 점이 매우 인상적이다.

 

단방향 순환 연결 리스트(Circular linked list)

연결된 순환 연결 리스트는 아래와 같다.

(사실 이 코드를 원했는데, 위 코드를 줬다. 뭐가 잘못 되었는지 한참 뜯어보다 깨닫게 되었다^0^)

 

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

template<typename T>
class ListNode {
public:
    T value;
    shared_ptr<ListNode<T>> next;

    ListNode(T value, shared_ptr<ListNode<T>> next = nullptr) : value(value), next(move(next)) {}
};

template<typename T>
class CircularLinkedList {
public:
    shared_ptr<ListNode<T>> head = nullptr;
    shared_ptr<ListNode<T>> tail = nullptr;
    int size = 0;

    CircularLinkedList() {}

    void insert(int k, T value) {
        auto newNode = make_shared<ListNode<T>>(value);
        if (size == 0) {
            head = tail = newNode;
            newNode->next = head;
        } else {
            if (k == 0) {
                newNode->next = head;
                head = newNode;
                tail->next = head;
            } else {
                auto current = head;
                for (int i = 0; i < k - 1 && current->next != head; i++) {
                    current = current->next;
                }
                newNode->next = current->next;
                current->next = newNode;
                if (current == tail) {
                    tail = newNode;
                }
            }
        }
        size++;
    }

    void erase(int k) {
        if (size == 0 || k >= size || k < 0) {
            cout << "Invalid position." << endl;
            return;
        }

        if (k == 0) {
            head = head->next;
            tail->next = head;
            if (size == 1) {
                head = nullptr;
                tail = nullptr;
            }
        } else {
            auto current = head;
            for (int i = 0; i < k - 1; i++) {
                current = current->next;
            }
            current->next = current->next->next;
            if (k == size - 1) { // If deleting the last node
                tail = current;
            }
        }
        size--;
    }

    void print() {
        auto current = head;
        for (int i = 0; i < size; i++) {
            cout << current->value << " ";
            current = current->next;
        }
        cout << endl;
    }
};

int main() {
    CircularLinkedList<int> list;
    list.insert(0, 1);
    list.insert(1, 2);
    list.insert(2, 3);
    list.print(); // Should print: 1 2 3

    list.erase(1);
    list.print(); // Should print: 1 3

    return 0;
}

잘 보면 shared_ptr을 사용했다는 걸 알 수 있다!!!

 

▼ 이건 내 나름의 설명... ▼

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

template <typename T>
class ListNode {
public:
	T value;
	shared_ptr<ListNode<T>> next;

	ListNode(T value, shared_ptr<ListNode<T>> next = nullptr) :
		value(value), next(move(next)) {}
};

template <typename T>
class CircularLinkedList {
public:
	shared_ptr<ListNode<T>> head = nullptr;
	shared_ptr<ListNode<T>> tail = nullptr;
	int size = 0;

	CircularLinkedList() {}

	void insert(int k, T value) {
		auto newNode = make_shared<ListNode<T>>(value);
		if (size == 0) {
			head = newNode;
			tail = newNode;
			newNode->next = head;
		}
		else {
			// 만약 제일 처음에 insert한다면
			if (k == 0) {
				newNode->next = head;   // 새노드가 리스트의 첫번째를 가리키도록 설정
				head = newNode;         //
				tail->next = head;      // tail->next는 항상 head를 가리키게 설정
			}
			// 제일 처음에 insert하는게 아니라면
			else {
				auto current = head;
				// 아래와 같이 조건을 준 이유
				// k가 size보다 클 경우를 처리
				// k가 size보다 클 경우 무한루프에 걸리기 때문
				for (int i = 0; i < k - 1 && current->next != head; i++) {
					current = current->next;
				}
				// current || new_Node || current->next
				newNode->next = current->next;
				current->next = newNode;

				// 새로운 노드가 마지막 노드가 되면서 tail 업데이트
				if (current == tail) {
					tail = newNode;
				}
			}
		}
		size++;
	}
	void print() {
		auto current = head;
		for (int i = 0; i < size; i++) {
			cout << current->value << " ";
			current = current->next;
		}
		cout << endl;
	}
};

int main() {
	CircularLinkedList<int> list;
	list.insert(0, 1);
	list.insert(1, 2);
	list.insert(2, 3);
	list.insert(0, 0);
	list.print();
}

 

연결된 양방향 순환 연결 리스트(circular doubly linked list)

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

template<typename T>
class ListNode {
public:
    T value;
    shared_ptr<ListNode<T>> next;
    ListNode<T>* prev;

    ListNode(T value, shared_ptr<ListNode<T>> next = nullptr, ListNode<T>* prev = nullptr)
        : value(value), next(move(next)), prev(prev) {}
};

template<typename T>
class CircularDoublyLinkedList {
public:
    shared_ptr<ListNode<T>> head = nullptr;
    ListNode<T>* tail = nullptr;
    int size = 0;

    CircularDoublyLinkedList() {}

    void insert(int k, T value) {
        if (size == 0) {
            head = make_shared<ListNode<T>>(value);
            tail = head.get();
            head->next = head; // Point to itself
            head->prev = tail; // Point to itself
        } else {
            if (k == 0) {
                auto newNode = make_shared<ListNode<T>>(value, head, tail);
                head->prev = newNode.get();
                tail->next = newNode;
                head = newNode;
            } else {
                auto current = head;
                for (int i = 0; i < k - 1 && current->next != head; i++) {
                    current = current->next;
                }
                auto newNode = make_shared<ListNode<T>>(value, current->next, current.get());
                current->next->prev = newNode.get();
                current->next = newNode;
                if (current.get() == tail) {
                    tail = newNode.get();
                }
            }
        }
        size++;
    }

    void print() {
        auto current = head;
        for (int i = 0; i < size; i++) {
            cout << current->value << " ";
            current = current->next;
        }
        cout << endl;
    }
};

int main() {
    CircularDoublyLinkedList<int> list;
    list.insert(0, 1);
    list.insert(1, 2);
    list.insert(2, 3);
    list.insert(0, 0);
    list.print(); // Should print: 0 1 2 3

    return 0;
}