设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next。val 是当前节点的值，next 是指向下一个节点的指针/引用。如果要使用双向链表，则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。

力扣（LeetCode）

首先我们有了一个类MyLinkedList,然后leetcode自己内置了一个单链表节点类：ListNode

前情提要

单链表节点类的介绍

在leetcode里，这个ListNode应该是这么实现的

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class ListNode
{
    //设置节点链接的下一个节点的位置和节点当前保存的值
    ListNode next;
    ListNode val;
public:
    //构造函数
    ListNode (){}
    //有参数的构造函数
    ListNode (int _data) 
    {
        val = _data;
    }
};

如此，一个简单的单链表类就实现了。

设计思路

我们要实现的功能有：

  • 获取节点位置的值
  • 头插
  • 尾插
  • 指定插
  • 删除

所以我们基本只需要在原有的基础上记录一下链表中已有元素的数量就可以了

代码实例

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

class MyLinkedList {
public:
    MyLinkedList() {
        //设置链表中链表的元素数量和头节点的值
        this->size = 0;
        this->head = new ListNode(0);
    }
    
    int get(int index) {
        //先将传入的索引值和已有元素的数量比较
        if (index < 0 || index >= size) {
            return -1;
        }
        ListNode *cur = head;
        //从头寻找，找到索引值所在的元素停下即可
        for (int i = 0; i <= index; i++) {
            cur = cur->next;
        }
        return cur->val;
    }
    
    //头插法，直接调用
    void addAtHead(int val) {
        addAtIndex(0, val);
    }
    
    //尾插法，直接调用
    void addAtTail(int val) {
        addAtIndex(size, val);
    }
    
    //指定插
    void addAtIndex(int index, int val) {
        //先比较一下
        if (index > size) {
            return;
        }
        //判断是否是头插
        index = max(0, index);
        //链表元素数+1
        size++;
        ListNode *pred = head;
        for (int i = 0; i < index; i++) {
            pred = pred->next;
        }
        //用传入的数据初始化一个新节点，再将其插入到指定索引到的位置
        ListNode *toAdd = new ListNode(val);
        toAdd->next = pred->next;
        pred->next = toAdd;
    }
    
    void deleteAtIndex(int index) {
        //判断一下范围
        if (index < 0 || index >= size) {
            return;
        }
        //失去了一个元素
        size--;
        ListNode *pred = head;
        //找到对应的位置后删除该元素
        for (int i = 0; i < index; i++) {
            pred = pred->next;
        }
        ListNode *p = pred->next;
        pred->next = pred->next->next;
        delete p;
        p = nullptr;
    }
private:
    int size;
    //使用力扣提供的类
    ListNode *head;
};