链表

链表（ linked list）就是一种典型的动态存储结构.其中的数据,分散为一系列称
作节点（ node） 的单位，节点之间通过指针相互索引和访问,为了引入新节点或删除原有节点，
只需在局部，调整少量相关节点之间的指针。

#include<iostream>
using namespace std;
class Node {
public:
    int data;
    Node* next;

---

构造函数

    Node(int _data) {
        data = _data;
        next = NULL;
    }
};

构成：数据 data
** 指针 next**

---

class LinkList {
private:
    Node* head;
public:
    LinkList() {
        head = NULL;
    }

---

插入

    void insert(Node *node, int index) {
        if (head == NULL) {
            head = node;
            return;
        }
        if (index == 0) {
            node->next = head;
            head = node;
            return;
        }
        Node *current_node = head;
        int count = 0;
        while (current_node->next != NULL && count < index - 1) {
            current_node = current_node->next;
            count++;
        }
        if (count == index - 1) {
            node->next = current_node->next;
            current_node->next = node;
        }
    }

思路：考虑链表为空的情况：直接将node作为head
若插入位置为0，即插入作为头结点。则只需将node的next指针指向head；
其他情况， 通过while循环找到node（index-1）
然后进行插入操作

输出

void output() {
    if (head == NULL) {
        return;
    }
    Node *current_node = head;
    while (current_node != NULL) {
        cout << current_node->data << " ";
        current_node = current_node->next;
    }
    cout << endl;
}

删除

    void delete_node(int index){
          if (head == NULL) {
            return;
        }
        Node *current_node = head;
        int count = 0;
        if(index==0){
            head=head->next;
        delete current_node;
            return;
        }
         while (current_node->next != NULL && count < index - 1) {
            current_node = current_node->next;
            count++;
        }
        if (count == index - 1&&current_node->next !=NULL) {
            Node *delete_node=current_node->next;
            current_node->next = delete_node->next;
            delete delete_node;
       }
    }
};

思路：考虑链表为空的情况：直接返回
若插入位置为0，即删除头结点。则只需将node的next指针指向head；
其他情况， 通过while循环找到node（index-1）
然后进行删除操作

---

int main() {

    LinkList linklist;
    for (int i = 1; i <= 10; i++) {
        Node *node = new Node(i);
        linklist.insert(node, i - 1);
    }

    linklist.output();
    linklist.delete_node(3);
    linklist.output();
    return 0;
}