单链表

单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。

单链表的实现

#include "iostream"
typedef struct MyLinkedList{
    struct MyLinkedList *next=nullptr;
    int val{};
} MyLinkedList;


MyLinkedList* myLinkedListCreate() {
    auto *obj = (MyLinkedList*) malloc(sizeof(MyLinkedList) );
    obj -> next = nullptr;
    obj -> val = 0;
    return obj;
}

int ListLength(MyLinkedList *obj) { //?
    MyLinkedList *cur = obj -> next;
    int len = 0;
    while (cur != nullptr) {
        cur = cur -> next;
        len ++;
    }
    return len;
}

int myLinkedListGet(MyLinkedList* obj, int index) {
    int length = ListLength(obj);
    if (index < 0 || index >= length) {
        return -1;
    }
    MyLinkedList *cur = obj;
    for (int i = 0; i <= index; i ++) { //?
        cur = cur -> next;
    }
    return cur -> val;
}

void myLinkedListAddAtHead(MyLinkedList* obj, int val) {
    //myLinkedListAddAtIndex(obj, 0, val);
    auto *phead = (MyLinkedList*) malloc(sizeof(MyLinkedList) );
    phead -> next = obj -> next;
    obj -> next = phead;
    phead -> val = val;
}

void myLinkedListAddAtTail(MyLinkedList* obj, int val) {
    auto *ptail = (MyLinkedList*) malloc(sizeof(MyLinkedList) );
    MyLinkedList *cur = obj;
    while(true){
        if(cur->next == nullptr){
            break;
        }
        cur = cur -> next;
    }
    cur -> next = ptail;
    ptail -> next = nullptr;
    ptail -> val = val;
}

void myLinkedListAddAtIndex(MyLinkedList* obj, int index, int val) {
    int length = ListLength(obj);
    if (index <= 0) {
        myLinkedListAddAtHead(obj, val);
        /*    MyLinkedList *phead = (MyLinkedList*) malloc(sizeof(MyLinkedList) );
            phead -> next = obj -> next;
            obj -> next = phead;
            phead -> val = val;
        */
    }
    else if (index > length) {
        return;
    }
    else {
        auto *padd = (MyLinkedList*) malloc(sizeof(MyLinkedList) );
        MyLinkedList *cur = obj;
        for (int i = 0; i < index; i++) {
            cur = cur -> next;
        }
        padd -> next = cur -> next;
        cur -> next = padd;
        padd -> val =val;
    }
}

void myLinkedListDeleteAtIndex(MyLinkedList* obj, int index) {
    int length = ListLength(obj);
    if (index < 0 || index > length) {
        return ;
    }
    MyLinkedList *cur = obj;
    for (int i = 0; i < index; i++) {
        cur = cur -> next;
    }
    MyLinkedList *tmp = cur -> next;
    cur -> next = cur -> next -> next;
    free(tmp);
}

void myNodeFree(MyLinkedList *node) {
    while(node != nullptr){
        MyLinkedList *tmp = node;
        node = node -> next;
        free(tmp);
    }
}

void myLinkedListFree(MyLinkedList* obj) {
    myNodeFree(obj);
}

/* --------------test-------------- */
void print(MyLinkedList* obj){
    MyLinkedList *cur = obj -> next;
    while(cur != nullptr){
        std::cout << cur -> val << " ";
        cur = cur -> next;
    }
    std::cout << std::endl;
}
int main(){
    MyLinkedList *obj = myLinkedListCreate();
    myLinkedListAddAtTail(obj, 2);
    myLinkedListAddAtTail(obj, 3);
    myLinkedListAddAtTail(obj, 4);
    print(obj);
    myLinkedListAddAtIndex(obj, 1, 23);
    myLinkedListAddAtIndex(obj, -1, 33);
    print(obj);
    std::cout << myLinkedListGet(obj, 2) << std::endl;
    myLinkedListDeleteAtIndex(obj, 2);
    print(obj);
    myLinkedListFree(obj);
}