[자료구조] doubly linked list

오류가 있을 수 있습니다. 멀티스레드 환경이 고려되지 않았습니다. 템플릿을 사용하지 않았고 int형 데이터만 저장합니다. 표준 라이브러리(std::list)의 멤버 함수를 일부 참고했습니다.

 

DDL.h

#pragma once

class DDL
{	
private:
	struct Node
	{
		int data;
		Node* prev;
		Node* next;

	public:
		Node(int data)
			:data(data)
		{
			prev = nullptr;
			next = nullptr;
		}
	};

private:
	int _size = 0;
	Node* _head = nullptr;
	Node* _tail = nullptr;
	
public:
	DDL() = default;
	~DDL();

	void push_front(int data);
	void push_back(int data);
	bool push_after(int pos, int data);
	bool push_before(int pos, int data);
	void pop_back();
	void pop_front();
	int back() const;
	int front() const;
	void erase(int pos);
	int  size() const;
	void print_all();
};

 

DDL.ccp

#include "DDL.h"
#include <iostream>

void DDL::push_front(int data)
{
	Node* new_node = new Node(data);
	if (0 == _size)
	{
		_head = _tail = new_node;
	}
	else 
	{
		_head->prev = new_node;
		new_node->next = _head;
		_head = new_node;		
	}
	++_size;
}

void DDL::push_back(int data)
{
	Node* new_node = new Node(data);
	if (0 == _size)
	{
		_head = _tail = new_node;
	}
	else
	{
		Node* last = _head;
		while (last->next != nullptr)
			last = last->next;

		last->next = new_node;
		new_node->prev = last;
		_tail = new_node;
	}
	++_size;
}

bool DDL::push_after(int pos, int data)
{
	if (pos < 0) return false;
	else if (pos >= _size - 1)
		push_back(data);
	else
	{
		int count = 0;
		Node* find = _head;
		while (count++ != pos)
		{
			find = find->next;
		}
		// find <-> find_next
		// find <-> new_node <-> find_next
		Node* new_node = new Node(data);
		new_node->next = find->next;
		new_node->prev = find;
		find->next->prev = new_node;
		find->next = new_node;
	}
	++_size;
	return true;
}

bool DDL::push_before(int pos, int data)
{
	if (pos > _size - 1) return false;
	else if (pos <= 0)
		push_front(data);
	else
	{
		Node* new_node = new Node(data);
		Node* find = _head;
		int count = 0;
		while (count++ != pos)
			find = find->next;

		// find_prev <-> find
		// find_prev <-> new <-> find
		new_node->next = find;
		new_node->prev = find->prev;
		find->prev->next = new_node;
		find->prev = new_node;
	}

	++_size;
	return true;
}

void DDL::pop_back()
{
	if (0 == _size) return;
	else if (1 == _size)
	{
		delete _head;
		_head = nullptr;
		_tail = nullptr;
	}
	else
	{
		Node* last = _tail;
		_tail->prev->next = nullptr;
		_tail = _tail->prev;
		delete last;
	}
	--_size;
}

void DDL::pop_front()
{
	if (0 == _size) return;
	else if (1 == _size)
	{
		delete _head;
		_head = nullptr;
		_tail = nullptr;
	}
	else
	{
		Node* top = _head;
		_head->next->prev = nullptr;
		_head = _head->next;
		delete top;
	}
	--_size;
}

int DDL::back() const
{
	return _tail->data;
}

int DDL::front() const
{
	return _head->data;
}

void DDL::erase(int pos)
{
	if (pos < 0 || pos > _size - 1 || 0 == _size) return;
	else if (1 == _size)
	{
		delete _head;
		_tail = nullptr;
		_head = nullptr;
	}
	else
	{
		int count = 0;
		Node* find = _head;
		while (count++ != pos)
			find = find->next;

		// find_prev <-> find <-> find_next
		// nullptr <-> find <-> find_next;
		// find_prev <-> find <-> nullptr
		if (_head == find)
		{
			find->next->prev = nullptr;
			_head = find->next;
			delete find;
		}
		else if (_tail == find)
		{
			find->prev->next = nullptr;
			_tail = find->prev;
			delete find;
		}
		else
		{
			find->prev->next = find->next;
			find->next->prev = find->prev;
			delete find;
		}
	}
	--_size;
}

int DDL::size() const
{
	return _size;
}

void DDL::print_all()
{
	if (0 == _size) return;
	Node* node = _head;
	while (node != nullptr)
	{
		std::cout << node->data << " ";
		node = node->next;
	}
}

DDL::~DDL()
{
	if (1 == _size)
		delete _head;
	else if (_size > 1)
	{
		while (_size--)
		{
			Node* node = _tail;
			_tail = _tail->prev;
			delete node;
		}
	}
}

 

test

#include "DDL.h"
#include <cstdio>
int main()
{
	DDL ddl;
	ddl.push_front(3);
	ddl.push_front(4);
	ddl.push_front(1);
	ddl.push_back(5);
	ddl.push_back(7);
	//ddl.print_all(); // 1 4 3 5 7

	ddl.push_after(0, 8);
	//ddl.print_all(); // 1 8 4 3 5 7
	ddl.push_before(3, 9);
	//ddl.print_all(); // 1 8 4 9 3 5 7

	ddl.erase(2);
	//ddl.print_all(); // 1 8 9 3 5 7

	ddl.pop_back();
	ddl.pop_back();
	//ddl.print_all(); // 1 8 9 3

	ddl.pop_front();
	//ddl.print_all(); // 8 9 3

	ddl.push_after(1, 10);
	//ddl.print_all(); // 8 9 10 3

	ddl.push_before(3, 4);
	//ddl.print_all(); // 8 9 10 4 3

	ddl.erase(2);
	//ddl.print_all(); // 8 9 4 3

	//printf("%d\n", ddl.front()); // 8
	//printf("%d\n", ddl.back()); // 3

	ddl.erase(0);
	//ddl.print_all(); // 9 4 3

	ddl.erase(2);
	//ddl.print_all(); // 9 4

	printf("%d\n", ddl.size()); // 2
}