---
tags: codebook
---

<!-- {%hackmd theme-dark %} -->

# linked list

## 10/25/2021

#include<iostream>
#include<algorithm>
using namespace std;
template<typename T>
struct linked_list {
//member variables
	size_t container_size;
	size_t size() const {return container_size;}

//struct node
	struct node {
		T val;
		node *prev, *next;
		node(const T& x, node* ptr = nullptr):
			val(x), prev(ptr), next(nullptr) {}
	} *start, *period;

//struct iterator
	struct iterator {
		node* data;
		iterator(node* ptr = nullptr): data(ptr) {}
		iterator operator++() {
			return data = data->next;
		}
		iterator operator--() {
			return data = data->prev;
		}
		bool operator==(const iterator b) const {
			return data == b.data;
		}
		operator bool() const {
			return data != nullptr;
		}
		T& operator*() {
			return data->val;
		}
		T operator*() const {
			return data->val;
		}
	};
	iterator begin() {return iterator(start);}
	iterator end() {return iterator(period);}

//functions
	iterator insert(const T& x, iterator ptr) {
		container_size++;
		if (container_size == 1) {
			start = new node(x);
			start->next = period;
			period->prev = start;
			return iterator(start);
		}
		node* tmp = new node(x, ptr.data->prev);
		if (tmp->prev)
			tmp->prev->next = tmp;
		tmp->next = ptr.data;
		ptr.data->prev = tmp;
		return iterator(tmp);
	}

	iterator push_front(const T& x) {
		container_size++;
		node* tmp = start;
		start = new node(x);
		start->next = tmp;
		tmp->prev = start;
		return iterator(start);
	}

	iterator push_back(const T& x) {
		container_size++;
		if (container_size == 1) {
			start = new node(x);
			start->next = period;
			period->prev = start;
			return iterator(period);
		}
		node* tmp = period->prev;
		tmp->next = new node(x, tmp);
		tmp = tmp->next, tmp->next = period;
		period->prev = tmp;
		return iterator(period);
	}

	iterator pop_front() {
		if (container_size <= 0)
			return iterator(nullptr);
		container_size--;
		node* tmp = start;
		start = start->next;
		start->prev = nullptr;
		delete tmp;
		return iterator(start);
	}

	iterator pop_back() {
		if (container_size <= 0)
			return iterator(nullptr);
		container_size--;
		node* tmp = period->prev;
		if (tmp && tmp->prev)
			tmp->prev->next = period;
		delete tmp;
		return iterator(period);
	}

//constructor
	linked_list(): container_size(0), start(new node(~0u)), period(start) {}
};

int main() {
	linked_list<int> list;
	for (auto i : {1, 2, 3, 4, 5, 6, 7, 8, 9, 10})
		list.insert(i, list.end());
	for (auto i = list.begin(); i != list.end(); ++i)
		cout << *i << ' ';
	cout << endl;
	return 0;
}

## old version

struct linked_list {
    struct node {
        int val;
        node *next;
        node(const int& x): val(x) { next = nullptr; }
    } *root, *end;
    void push_front(const int& x) {
        node* tmp = root;
        root = new node(x);
        root->next = tmp;
    }
    void push_back(const int& x) {
        if (!root)
            root = end = new node(x);
        else
            end->next = new node(x), end = end->next;
    }
    void print_all() {
        node* cur = root;
        while (cur)
            cout << cur->val << ' ', cur = cur->next;
    }
    linked_list(): root(nullptr), end(nullptr) {}
};