双链表代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>

using namespace std;

template <typename E>

class MyLinkedList {
	struct Node {
		E val;
		Node* next;
		Node* prev;

		Node(E value) : val(value), next(nullptr), prev(nullptr) {};
	};

	Node* head;
	Node* tail;
	int size;

public:
	MyLinkedList() {
		head = new Node(E());//使用E()的原因是因为确保输入可以正确初始化
		tail = new Node(E());

		head->next = tail;
		tail->prev = head;

		size = 0;
	}

	~MyLinkedList() {
		while (size > 0) {
			removeFirst();
		}
		delete head;
		delete tail;
	}

	// 功能区

	void addLast(E value) {
		Node* x = new Node(value);
		Node* temp = tail->prev;

		x->next = tail;
		x->prev = temp;

		temp->next = x;
		tail->prev = x;
		// temp <-> x <-> tail

		size++;
	}

	void addFirst(E value) {
		Node* x = new Node(value);
		Node* temp = head->next;

		x->next = temp;
		x->prev = head;

		temp->prev = x;
		head->next = x;

		// head <-> x <-> temp
		size++;
	}

	void add(int index, E element) {
		checkPositionIndex(index);
		if (index == size) {
			addLast(element);
			return;
		}

		Node* p = getNode(index);
		Node* temp = p->prev;

		Node* x = new Node(element);

		x->prev = temp;
		x->next = p;

		p->prev = x;
		temp->next = x;
		// temp <-> x <-> p

		size++;
	}

	E removeFirst() {
		if (size < 1) {
			throw out_of_range("No elements to remove");
		}

		Node* x = head->next;
		Node* temp = x->next;
		// head <-> x <-> temp
		head->next = temp;
		temp->prev = head;

		E val = x->val;
		delete x;

		size--;
		return val;
	}

	E removeLast() {
		if (size < 1) {
			throw out_of_range("No elements to remove");
		}

		Node* x = tail->prev;
		Node* temp = x->prev;
		// temp <-> x <-> tail
		tail->prev = temp;
		temp->next = tail;

		E val = x->val;
		delete x;

		size--;
		return val;
	}

	E remove(int index) {
		checkElementIndex(index);

		Node* x = getNode(index);
		Node* prev = x->prev;
		Node* next = x->next;
		// prev <-> x <-> next
		next->prev = prev;
		prev->next = next;

		E val = x->val;
		x->prev = nullptr;
		x->next = nullptr;
		delete x;
		// prev <-> next

		size--;
		return val;
	}

	E get(int index) {
		checkElementIndex(index);
		Node* p = getNode(index);

		return p->val;
	}

	E getFirst() {
		if (size < 1) {
			throw out_of_range("No elements in the list");
		}

		return head->next->val;
	}

	E getLast() {
		if (size < 1) {
			throw out_of_range("No elements in the list");
		}

		return tail->prev->val;
	}

	E set(int index, E val) {
		checkElementIndex(index);

		Node* p = getNode(index);

		E oldval = p->val;
		p->val = val;

		return oldval;
	}

	int getSize() const{
		return size;
	}

	bool isEmpty() const {
		return size == 0;
	}

	void display() {
		cout << "size = " << size << endl;
		for (Node* p = head->next; p != tail; p = p->next) {
			cout << p->val << " <-> ";
		}
		cout << "nullptr" << endl;
		cout << endl;
	}

private:
	Node* getNode(int index) {
		checkElementIndex(index);
	
		Node* p;

		if (index <= size / 2) {
			p = head->next;
			for (int i = 0; i < index; i++) p = p->next;
		}
		else {
			p = tail->prev;
			for (int i = 0; i < size - 1 - index; i++) p = p->prev;//注意-1是因为0-base
		}
		return p;
	}

	bool isElementIndex(int index) const{
		return index >= 0 && index < size;//不知道为什么
	}

	bool isPositionIndex(int index) const{
		return index >= 0 && index <= size;
	}

	// 检查 index 索引位置是否可以存在元素
	void checkElementIndex(int index) const {
		if (!isElementIndex(index))
			throw out_of_range("Index: " + to_string(index) + ", Size: " + to_string(size));
	}

	// 检查 index 索引位置是否可以添加元素
	void checkPositionIndex(int index) const {
		if (!isPositionIndex(index))
			throw out_of_range("Index: " + to_string(index) + ", Size: " + to_string(size));
	}

};

int main() {
	MyLinkedList<int> list;
	list.addLast(1);
	list.addLast(2);
	list.addLast(3);
	list.addFirst(0);
	list.add(2, 100);

	list.display();
	// size = 5
	// 0 <-> 1 <-> 100 <-> 2 <-> 3 <-> null

}

参考网站
链表代码实现