[DATA STRUCTURE] 04. 이중 연결 리스트(Doubly Linked List)

아래의 코드는 C++로 구현된 이중 연결 리스트다.

C++ STL의 이터레이터를 흉내 내서 구현했으며 단방향 연결 리스트와는 다르게, 이전노드에 대한 접근이 자유롭다.

 

#pragma once

template <typename T>
struct Node {

	T data;
	Node* prev;
	Node* next;
};

template <class T>
class list {
private:

	Node<T>* header;
	Node<T>* trailer;
	int nSize;

public:

	class iterator { //STL의 이터레이터와 같은 역할
	private:

		Node<T>* nodePtr;

	public:

		iterator() : nodePtr(nullptr) {}
		iterator(Node<T>* p) : nodePtr(p) {}

		T& operator*() { //현 이터레이터의 위치에서 노드 데이터를 참조
			
			return nodePtr->data; 
		}

		iterator& operator++() { //전위 연산자(++) 후위X

			nodePtr = nodePtr->next;
			return *this;
		}

		iterator& operator--() { //전위 연산자(--) 후위X

			nodePtr = nodePtr->prev;
			return *this;
		}

		bool operator==(const iterator& it) const {

			return nodePtr == it.nodePtr;
		}

		bool operator!=(const iterator& it) const {

			return nodePtr != it.nodePtr;
		}

		friend class list;
	};

public:

	list() {

		nSize = 0;
		header = new Node<T>{ T(), nullptr, nullptr };
		trailer = new Node<T>{ T(), nullptr, nullptr };
		header->next = trailer;
		trailer->prev = header;
	}

	~list() {

		while (!empty()) {
		
			pop_front();
		}

		delete header;
		delete trailer;
	}

	iterator begin() const { //노드의 머리 부분을 반환

		return iterator(header->next);
	}

	iterator end() const { //노드의 꼬리 부분을 반환

		return iterator(trailer);
	}

	void insert(const iterator& pos, const T& val) { //현 이터레이터의 위치에 노드를 생성

		Node<T>* nodeCurr = pos.nodePtr;
		Node<T>* newNode = new Node<T>{ val, nodeCurr->prev, nodeCurr };
		
		newNode->prev->next = newNode;
		newNode->next->prev = newNode;
		
		nSize++;
	}

	void push_front(const T& val) {

		insert(begin(), val);
	}

	void push_back(const T& val) {

		insert(end(), val);
	}

	void erase(const iterator& pos) { //현 이터레이터의 위치에 있는 노드를 삭제

		Node<T>* nodeCurr = pos.nodePtr;
		
		nodeCurr->prev->next = nodeCurr->next;
		nodeCurr->next->prev = nodeCurr->prev;
		
		delete nodeCurr;

		nSize--;
	}

	void pop_front() {

		if (!empty()) {
		
			erase(begin());
		}
	}

	void pop_back() {

		if (!empty()) {
		
			erase(--end());
		}
	}

	iterator find(const T& val) { //입력된 값을 기반으로 저장된 노드의 위치를 반환

		Node<T>* nodeCurr = header->next;

		while (nodeCurr->data != val && nodeCurr != trailer) {
		
			nodeCurr = nodeCurr->next;
		}

		return iterator(nodeCurr);
	}

	bool empty() const { //포인터의 nullptr 확인이 아닌 nSize의 값으로 리스트의 상태를 판단

		return nSize == 0;
	}

	int size() const { //리스트에 저장된 노드의 개수를 반환

		return nSize;
	}
};

 

 

 

주요 특징

 

1. 노드로 구성 : 이중 연결 리스트는 노드(Node)라고 불리는 요소로 구성된다.

(각 노드는 데이터 필드와(data filed) 이전 포인터(previous pointer)와 다음 포인터(next pointer)를 가진다.)

 

2. 양방향 접근 : 각 노드가 이전 노드와 다음 노드를 가리키는 포인터를 가지고 있으므로 데이터를 양쪽에서 접근할 수 있다.

 

3. 동적 크기 : 노드를 동적으로 추가 또는 제거할 수 있으므로 크기가 미리 정해지지 않는다.

 

4. 삽입과 삭제 : 새 노드를 삽입하면 이전 노드와 다음 노드의 링크를 조정하고

삭제한다면 해당 노드의 이전 노드와 다음 노드의 링크를 조정한다.

 

5. 메모리 효율 : 노드가 필요할 때만 생성하고 필요 없어지면 메모리에서 해제할 수 있다.

 

 

장점

 

1. 양방향 순회 : 이중 연결 리스트는 양방향 순회가 가능하다.

어떤 방향에서도 순회할 수 있으므로, 뒤에서부터도 노드에 쉽게 접근할 수 있다.

 

2. 뒤로 가기가 쉬움 : 단일 연결 리스트와 비교했을 때, 뒤로 가는 연산이 쉽다.

이전 노드에 대한 참조가 있으므로 뒤로 이동할 수 있다.

 

3. 중간 노드 삭제 효율성 : 특정 노드를 삭제할 때, 해당 노드의 이전 및 다음 노드를 직접 조작할 수 있으므로

삭제 작업이 효율적이며 이 작업은 일반적으로 O(1)의 시간 복잡도를 가진다.

 

 

단점

 

1. 메모리 사용 : 각 노드가 이전 및 다음 노드에 대한 포인터를 가지고 있기에 메모리 사용이 더 많을 수 있으며

이에 따라 메모리 오버헤드가 발생할 수 있다.

 

2. 복잡성 : 이중 연결 리스트는 구현 및 관리가 단일 연결 리스트에 비해 더 복잡하다.

 

3. 접근 시간 : 특정 인덱스 위치의 요소를 찾는 데 O(n)의 시간 복잡도를 가지며 랜덤 액세스가 느리다.