本文共 1393 字，大约阅读时间需要 4 分钟。

链表是一种用来存储一系列数据的数据结构，支持高效的增删之类操作。为了实现链表，可以选择单链表或者双链表。这里以单链表为例，每个节点需要包含两个属性：val（节点值）和next（指向下一个节点的指针，初始为空）。

链表类MyLinkedList实现了以下功能：

节点结构体定义

struct ListNode {int val;ListNode* next;ListNode(int value) : val(value), next(nullptr) {}};

初始化链表

MyLinkedList() {_dummyHead = new ListNode(0);_size = 0;}

获取第index个节点值

int get(int index) {int count = 0;ListNode* pNode = _dummyHead;while (pNode->next) {if (count == index) {return pNode->next->val;}pNode = pNode->next;++count;}return -1;}

在头部添加节点

void addAtHead(int val) {ListNode* newHead = new ListNode(val);_dummyHead->next = newHead;newHead->next = _dummyHead->next;_size++;}

在尾部添加节点

void addAtTail(int val) {ListNode* newTail = new ListNode(val);ListNode* pNode = _dummyHead;while (pNode->next) {pNode = pNode->next;}pNode->next = newTail;_size++;}

在指定位置添加节点

void addAtIndex(int index, int val) {if (index < 0) {addAtHead(val);return;}if (_size >= index) {insertBefore(index, val);} else {addAtTail(val);}}

删除指定位置的节点

void deleteAtIndex(int index) {if (index < 0 || index >= _size) {return;}ListNode* pNode = _dummyHead;for (int i = 0; i < index; ++i) {pNode = pNode->next;}if (pNode->next) {ListNode* nextNode = pNode->next;pNode->next = nextNode->next;delete nextNode;_size--;}}

功能说明

• get(index)：会返回第index个节点的值，如果索引无效返回-1。
• addAtHead(val)：在链表头部添加节点。
• addAtTail(val)：在链表尾部添加节点。
• addAtIndex(index, val)：在指定位置添加节点，支持链表末尾添加。
• deleteAtIndex(index)：删除指定位置的节点。

转载地址：http://nhpsz.baihongyu.com/