数据结构之线性表（下）

单链表

单链表：通过指针连接的线性表

没有指针的语言如果表示链表？
答案是静态链表，静态链表用数组表示，使用元素的物理位序来替代地址

C++
Node

class Node {
public:
    int data;
    Node *next;
};

LinkedList

class LinkedList{
    Node *linkedList;
    int length;
public:
    LinkedList();
    ~LinkedList();
    bool listEmpty();
    int listLength();
    void clearList();
    void listInsertHead(int data);
    void listInsertTail(int data);
    void listInsert(int index,int data);
    void listDelete(int index);
    Node *getElem(int index);
    int locateElem(int data);
    Node* priorElem(Node *node);
    Node* nextElem(Node *node);
    void ListTraverse();
};


LinkedList::LinkedList(){
    linkedList = new Node();
    linkedList->data = 0;
    linkedList->next = nullptr;
    length = 0;
}

LinkedList::~LinkedList(){
    clearList();
    delete linkedList;
    linkedList = nullptr;
}

bool LinkedList::listEmpty(){
    return length == 0;
}

int LinkedList::listLength(){
    return length;
}

void LinkedList::clearList(){
    Node *currentNode = linkedList->next;
    while (currentNode) {
        Node *currentNextNode = currentNode->next;
        delete currentNode;
        currentNode = currentNextNode;
    }
    linkedList->next = nullptr;
    length = 0;
}

void LinkedList::listInsertHead(int data){
    Node *temp = new Node;
    temp->data = data;
    temp->next = linkedList->next;
    linkedList->next = temp;
    length++;
}

void LinkedList::listInsertTail(int data){
    Node *temp = new Node;
    temp->data = data;
    temp->next = nullptr;
    Node *tailNode = linkedList;
    while (tailNode->next) {
        tailNode = tailNode->next;
    }
    tailNode->next = temp;
    length++;
}

void LinkedList::listInsert(int index, int data){
    Node *temp = new Node;
    temp->data = data;
    Node *indexPreNode = linkedList;
    for (int k = 0; k < index; k++) {
        indexPreNode = indexPreNode->next;
    }
    temp->next = indexPreNode->next;
    indexPreNode->next = temp;
    length++;
}

void LinkedList::listDelete(int index){
    Node *indexPreNode = linkedList;
    for (int k = 0; k < index; k++) {
        indexPreNode = indexPreNode->next;
    }
    Node *waitDeleteNode = indexPreNode->next;
    indexPreNode->next = waitDeleteNode->next;
    delete waitDeleteNode;
    waitDeleteNode = nullptr;
    length--;
}

Node *LinkedList::getElem(int index){
    Node *indexNode = linkedList->next;
    for (int k = 0; k < index; k++) {
        indexNode = indexNode->next;
    }
    return indexNode;
}

int LinkedList::locateElem(int data){
    Node *currentNode = linkedList->next;
    for (int i = 0; i<length; i++) {
        if (currentNode->data == data) {
            return i;
        }else{
            currentNode = currentNode->next;
        }
    }
    return -1;
}

Node* LinkedList::priorElem(Node *node){
    Node *preNode = linkedList->next;
    for (int i = 0; i<length; i++) {
        if (preNode->next->data == node->data) {
            return preNode;
        }else{
            preNode = preNode->next;
        }
    }
    return nullptr;
}

Node* LinkedList::nextElem(Node *node){
    Node *currentNode = linkedList->next;
    for (int i = 0; i<length; i++) {
        if (currentNode->data == node->data) {
            return currentNode->next;
        }else{
            currentNode = currentNode->next;
        }
    }
    return nullptr;
}

void LinkedList::ListTraverse(){
    Node *currentNode = linkedList->next;
    while (currentNode) {
        std::cout<<currentNode->data<<std::endl;
        currentNode = currentNode->next;
    }
}