你可以选择使用单链表或者双链表，设计并实现自己的链表。

单链表中的节点应该具备两个属性：val 和 next 。val 是当前节点的值，next 是指向下一个节点的指针/引用。

如果是双向链表，则还需要属性 prev 以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。

实现 MyLinkedList 类：

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/design-linked-list

这道题目设计链表的五个接口：

• 获取链表第index个节点的数值
• 在链表的最前面插入一个节点
• 在链表的最后面插入一个节点
• 在链表第index个节点前面插入一个节点
• 删除链表的第index个节点

下面采用的设置一个虚拟头结点，代码如下：

class MyLinkedList {
public:struct LinkedNode{int val;LinkedNode* next;LinkedNode(int val):val(val),next(nullptr){}};//将虚拟头节点作为头节点(生成头节点)MyLinkedList(){dummpyNode = new LinkedNode(0);size = 0;}//这点要把虚拟节点算进去，所以size-1int get(int index) {if(index > (size - 1) || index < 0){return -1;}LinkedNode* cur = dummpyNode->next;while(index--){cur = cur->next;}return cur->val;}void addAtHead(int val) {LinkedNode* newNode = new LinkedNode(val);newNode->next = dummpyNode->next;dummpyNode->next = newNode;size++;}void addAtTail(int val) {LinkedNode* newNode = new LinkedNode(val);LinkedNode* cur = dummpyNode;while(cur->next != NULL){cur = cur->next;}cur->next = newNode;size++;}//添加头尾有特殊的函数实现功能，这点不需要实现所以是//index > sizevoid addAtIndex(int index, int val) {if(index > size || index < 0){return;}LinkedNode* newNode = new LinkedNode(val);LinkedNode* cur = dummpyNode;while(index--){cur = cur->next;}newNode->next = cur->next;cur->next = newNode;size++;}//这点有>=是因为删除不涉及头尾void deleteAtIndex(int index) {if(index >= size || index < 0){return;}LinkedNode *cur = dummpyNode;while(index--){cur = cur->next;}LinkedNode* tmp = cur->next;cur->next = cur->next->next;delete tmp;size--;}private:LinkedNode *dummpyNode; //虚拟头节点int size;   //链表大小
};/*** Your MyLinkedList object will be instantiated and called as such:* MyLinkedList* obj = new MyLinkedList();* int param_1 = obj->get(index);* obj->addAtHead(val);* obj->addAtTail(val);* obj->addAtIndex(index,val);* obj->deleteAtIndex(index);*/