用C/C++实现LinkedList

//
// Created by issuser on 2021/8/30.
//

#include <string.h>
#include <assert.h>
#include <android/log.h>

template <class E>
struct Node{
    Node<E>* next;
    Node<E>* prev;
    E value;
public:
    Node<E>(E value,Node<E>* prev,Node<E>* next){
        this->value=value;
        this->next=next;
        this->prev=prev;

    }
};

template <class E>
class LinkedList{
    Node<E>* head=NULL;
    Node<E>* last=NULL;
    int size;


public:
    void push(E e);

    ~LinkedList();

    Node<E>* node(int index);

    E getValue(int index);

    void insert(int index,E value);

    E remove(int index);

    E getLast();

    E removeLast();

    void printLog();



};

template<class E>
void LinkedList<E>::push(E e) {
    Node<E>* newNode=new Node<E>(e,NULL,NULL);
    if(head!=NULL){
        newNode->prev=last;
        last->next=newNode;
        last=newNode;
    }else{
        head=newNode;
        last=newNode;
    }


    size++;
}

template<class E>
Node<E> *LinkedList<E>::node(int index) {
    assert(index>=0&&index<size);

    if(index<=size/2){
        Node<E>* node1=head;
        for(int i=0;i<index;i++){
            node1=node1->next;
        }
        return node1;
    } else{

        Node<E>* node1=last;

        for(int i=size-1;i>index;i--){
            node1=node1->prev;
        }
        return node1;

    }


}

template<class E>
E LinkedList<E>::getValue(int index) {
    Node<E>* node1=node(index);
    return node1->value;
}

template<class E>
void LinkedList<E>::insert(int index,E value) {
    Node<E>* newNode=new Node<E>(value,NULL,NULL);
    if(index=0){
        newNode->next=head;
        head->prev=newNode;
        head=newNode;

    } else{
        Node<E>* pre=node(index-1);

        Node<E>*next=node(index);

        pre->next=newNode;
        newNode->prev=pre;

        newNode->next=next;
        next->prev=newNode;

    }

    size++;

}

template<class E>
E LinkedList<E>::remove(int index) {
    assert(index>=0&&index<size);

    if(size==1){
        E value=head->value;
        delete head;
        delete last;
        head=NULL;
        last=NULL;
        size--;
        return value;
    }


    if(index==0){
        Node<E>* deleteNode=head;
        E value=deleteNode->value;
        head=head->next;

        head->prev=NULL;
        deleteNode->next=NULL;


        delete deleteNode;
        size--;
        return value;
    }

    if(index==size-1){
        Node<E>* deletenOde=node(size-1);
        E value=deletenOde->value;

        last=deletenOde->prev;

        last->next=NULL;
        deletenOde->prev=NULL;
        delete  deletenOde;
        size--;
        return value;

    }

    Node<E>* deletNode=node(index);

    Node<E>* prev=deletNode->prev;
    Node<E>* next=deletNode->next;

    prev->next=next;
    next->prev=prev;


    E value=deletNode->value;

    delete  deletNode;
    size--;

    return value;
}

template<class E>
E LinkedList<E>::getLast() {
    return last->value;
}

template<class E>
E LinkedList<E>::removeLast() {
    return remove(size--);
}

template<class E>
void LinkedList<E>::printLog() {
    Node<E>* node1=head;
    for(int i=0;i<size;i++){
        __android_log_print(ANDROID_LOG_ERROR,"LIST","index=%d,value=%d",i,node1->value);
        node1=node1->next;

    }

}

LinkedList 使用双向链表 相较于单向链表，在性能上更出色，主要体现在两个地方

push 方法。双向链表由于有一个尾节点指针，每次只要在尾节点中添入即可。因此它的时间是O1 常量级。
单向链表则每次来从头节点移动到尾节点，因此时间是On

get方法。双向链表 可以根据index更靠近首节点还是尾节点 来选择从首节点向下遍历还是尾节点向上遍历。因此它的时间平均是单节点的一半。