1. vector

코드

#pragma once

#include <iostream>

template <typename T>
class Vector
{
public:
	Vector(size_t maxSize = 10)
		: mSize(0), mMaxSize(0)
	{
		reserve(maxSize);
	}

	~Vector()
	{
		delete[] mData;
	}

	void reserve(size_t size) noexcept;
	void resize(size_t size);
	void pushBack(const T& value);
	void pushBack(T&& value);
	void popBack();
	void print() const;
	void clear() { mSize = 0; }
	size_t size() const { return mSize; }

	T& operator[](size_t location);

private:
	T* mData;
	size_t mSize;
	size_t mMaxSize;
};

template <typename T>
inline void Vector<T>::reserve(size_t size) noexcept
{
	if (size <= mMaxSize)
	{
		return;
	}

	T* tmp = new T[size];
	for (size_t i = 0; i < mSize; ++i)
	{
		tmp[i] = mData[i];
	}

	delete[] mData;
	mData = tmp;
	tmp = nullptr;
	mMaxSize = size;
}

template<typename T>
inline void Vector<T>::resize(size_t size)
{
	if (mMaxSize <= size)
	{
		reserve(size);
	}
	mSize = size;
}

template<typename T>
inline void Vector<T>::pushBack(const T& value)
{
	if (mSize == mMaxSize)
	{
		reserve(2 * mMaxSize);
	}

	mData[mSize] = value;
	++mSize;
}

template<typename T>
inline void Vector<T>::pushBack(T&& value)
{
	if (mSize == mMaxSize)
	{
		reserve(2 * mMaxSize);
	}

	mData[mSize] = std::move(value);
	++mSize;
}

template<typename T>
inline void Vector<T>::popBack()
{
	if (mSize == 0)
	{
		return;
	}
	--mSize;
}

template<typename T>
inline void Vector<T>::print() const
{
	for (size_t i = 0; i < mSize; ++i)
	{
		std::cout << mData[i] << " ";
	}
	std::cout << "\n";
}

template<typename T>
inline T& Vector<T>::operator[](size_t location)
{
	return mData[location];
}

사용

#include "vector.h"

int main()
{
    std::cout << "Hello Vector!\n";
    Vector<int> vec1;
    vec1.pushBack(1);
    vec1.pushBack(5);
    vec1.pushBack(3);
    vec1.pushBack(2);
    vec1.print();

    for (size_t i = 0; i < vec1.size(); ++i)
    {
        std::cout << vec1[i] << " ";
    }
    std::cout << "\n";

    return 0;
}

#include <iostream>

#include "list.h"
#include "vector.h"

int main()
{
    DoublyLinkedList<int> dll;
    dll.push_front(1);
    dll.push_front(2);
    dll.push_front(3);

    dll.insert(0, 100);
    dll.insert(4, 200);
    dll.print();
    std::cout << dll.size() << std::endl;

    dll.erase(0);
    dll.print();

    dll.erase(2);
    dll.print();

    for (size_t i = 0; i < dll.size(); ++i)
    {
        std::cout << dll[i] << " ";
    }
    std::cout << "\n";

    return 0;
}

2. doubly linked list

코드

#pragma once

#include <exception>
#include <iostream>

template<typename T>
struct Node
{
	T data;
	Node* prev;
	Node* next;

	Node(const T& data)
		: data(data)
		, prev(nullptr)
		, next(nullptr)
	{}

	Node()
		: data(T())
		, prev(nullptr)
		, next(nullptr)
	{}
};

template<typename T>
class DoublyLinkedList
{
public:
	DoublyLinkedList()
		: mHead(new Node<T>())
		, mTail(new Node<T>())
	{
		mHead->next = mTail;
		mTail->prev = mHead;
	}

	~DoublyLinkedList()
	{
		Node<T>* node = mHead;
		Node<T>* tmp;
		while (node->next != nullptr)
		{
			tmp = node;
			node = node->next;
			delete tmp;
		}
		delete mTail;
	}

	T& operator [](size_t location);

	size_t size() const { return mSize; }
	void push_front(const T& value);
	void push_back(const T& value);
	void insert(size_t location, const T& value);
	void erase(size_t location);
	void print() const;

private:
	Node<T>* mHead;
	Node<T>* mTail;
	size_t mSize{ 0 };
};

template<typename T>
inline T& DoublyLinkedList<T>::operator[](size_t location)
{
	if (location < 0 || location >= mSize)
	{
		throw std::runtime_error("Invalid location");
	}

	Node<T>* node;
	if (location > mSize / 2)
	{
		node = mTail;
		for (size_t i = mSize; i > location; --i)
		{
			node = node->prev;
		}
	}
	else
	{
		node = mHead;
		for (size_t i = 0; i <= location; ++i)
		{
			node = node->next;
		}
	}

	return node->data;
}

template<typename T>
inline void DoublyLinkedList<T>::push_front(const T& value)
{
	insert(0, value);
}

template<typename T>
inline void DoublyLinkedList<T>::push_back(const T& value)
{
	insert(mSize - 1, value);
}

template<typename T>
inline void DoublyLinkedList<T>::insert(size_t location, const T& value)
{
	if (location < 0 || location > mSize)
	{
		return;
	}
	
	Node<T>* newNode = new Node<T>(value);
	Node<T>* prevNode;
	if (location > mSize / 2)
	{
		prevNode = mTail->prev;
		for (size_t i = mSize; i > location; --i)
		{
			prevNode = prevNode->prev;
		}
	}
	else
	{
		prevNode = mHead;
		for (size_t i = 0; i < location; ++i)
		{
			prevNode = prevNode->next;
		}
	}

	newNode->prev = prevNode;
	newNode->next = prevNode->next;
	newNode->prev->next = newNode;
	newNode->next->prev = newNode;
	++mSize;
}

template<typename T>
inline void DoublyLinkedList<T>::erase(size_t location)
{
	if (location < 0 || location >= mSize)
	{
		return;
	}

	Node<T>* nodeToDelete;
	if (location > mSize / 2)
	{
		nodeToDelete = mTail;
		for (size_t i = mSize; i > location; --i)
		{
			nodeToDelete = nodeToDelete->prev;
		}
	}
	else
	{
		nodeToDelete = mHead;
		for (size_t i = 0; i <= location; ++i)
		{
			nodeToDelete = nodeToDelete->next;
		}
	}

	nodeToDelete->prev->next = nodeToDelete->next;
	nodeToDelete->next->prev = nodeToDelete->prev;
	delete nodeToDelete;
	--mSize;
}

template<typename T>
inline void DoublyLinkedList<T>::print() const
{
	Node<T>* node = mHead->next;
	while (node != mTail)
	{
		std::cout << node->data << " ";
		node = node->next;
	}
	std::cout << "\n";
}

사용

#include "list.h"

int main()
{
    DoublyLinkedList<int> dll;
    dll.push_front(1);
    dll.push_front(2);
    dll.push_front(3);

    dll.insert(0, 100);
    dll.insert(4, 200);
    dll.print();
    std::cout << dll.size() << std::endl;

    dll.erase(0);
    dll.print();

    dll.erase(2);
    dll.print();

    for (size_t i = 0; i < dll.size(); ++i)
    {
        std::cout << dll[i] << " ";
    }
    std::cout << "\n";

    return 0;
}