[자료구조] 링크드리스트 (Linked list)

링크드리스트 (Linked list) 란?

• 연결 리스트는 각 노드가 데이터와 다음 노드의 주소를 포함하여 순차적으로 연결된 자료구조
• 동적으로 크기를 조절할 수 있다.

단일 연결 리스트(Singly Linked List)

양방향 연결 리스트(Doubly Linked List)

기존적으로는 현재의 노드가 다음 노드만을 참조하는 단일 연결 리스트(Singly Linked List) 부터 
이전 노드와 다음 노드 모두를 참조하는 양방향 연결 리스트(Doubly Linked List) 등으로 다양하게 확장이 이루어질 수 있다.

장단점

장점

• 동적으로 크기를 조절할 수 있다.
• 배열과 달리 삽입 삭제의 용이하다.

단점

• 임의적으로 특정 데이터의 접근이 불가능하다.
• 추가적인 메모리 비용이 든다.

 

단일 연결 리스트(Singly Linked List)

장점:

• 각 노드가 다음 노드만을 참조는 next만 가지고 있기때문에 양뱡향에 비해 메모리사용량이 줄어든다.
• 노드 삽입과 삭제가 비교적 단순하고 코드가 간결하다.

단점:

• next만 가지고있기 때문에 각 노드에서 다음 노드로만 이동이가능하고 이전노드로는 이동이 불가능하다.

 

양방향 연결 리스트(Doubly Linked List)

장점:

• prev 포인터가 있어, 리스트의 어느 위치에서든 앞뒤로 쉽게 이동할 수 있다.
• 양쪽 방향으로 순회가 필요한 경우 적합하다.

단점:

• next와 prev 포인터를 모두 유지해야 하므로, 단일 연결 리스트에 비해 메모리 사용량이 증가한다.
• 삽입과 삭제 시 next와 prev를 모두 업데이트해야 하므로, 코드가 더 복잡하다.

구현

#include <list> 사용

#include <iostream>
#include <list>

using namespace std;

int main() {
	list<int> myList;
	myList.push_back(1);
    myList.push_back(2);
    myList.push_back(3);
    myList.push_back(4);
    myList.push_back(5);

	// push_back
	myList.push_back(6);
		
	// pop_front
	myList.pop_front();
		
	// front & back
	cout << "Front: " << myList.front() << ", Back: " << myList.back() << "\n"; // output : Front: 2, Back: 6
		
	// reverse
	myList.reverse();
		
	// 출력
	for (auto value : myList) {
		cout << value << " "; // output : 6 5 4 3 2
	}
		
	return 0;
}

 

Doubly Linked List 구현

#ifndef DOUBLYLINKEDLIST_HPP_
#define DOUBLYLINKEDLIST_HPP_

#include <iostream>
#include <vector>

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

	Node(int value) : data(value), next(nullptr), prev(nullptr) {}
	~Node() {}
};

class DoublyLinkedList
{
private:
	Node *head;
	Node *tail;
public:
	DoublyLinkedList() : head(nullptr), tail(nullptr) {}
	~DoublyLinkedList() {}

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

	void push_front(int value) {
		Node *newNode = new Node(value);
		if (head == nullptr) {
			head = tail = newNode;
		}
		else {
			newNode->next = head;
			head->prev = newNode;
			head = newNode;
		}
	}

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

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

	int front() {
		return head->data;
	}

	int back() {
		return tail->data;
	}

	void reverse() {
		Node* current = head;
		Node* temp = nullptr;

		tail = head;

		while (current != nullptr) {
			temp = current->prev;
			current->prev = current->next;
			current->next = temp;
			current = current->prev;
		}

		if (temp != nullptr) {
			head = temp->prev;
		}
	}
};

#endif