链表

单向链表

• 包含，创建，析构，指定位置插入，指定位置删除，反向链表，打印

struct Node{
    int data;
    Node *next;
    Node(int d):data(d){}
};
class LinkList {
private:
    Node *head;
    int length;
public:
    // 创建空链表
    LinkList(){
        head = NULL;
        length = 0;
    }
    // 析构
    ~LinkList(){
        Node *temp;
        for (int i = 0; i < length; i++){
            temp = head;
            head = head->next;
            delete temp;
        }
    }
    // 在第pos个元素后插入data
    void Insert(int data,int pos){      
        if (pos<0 || pos>length){
            cout << "illegal position!" << endl;
            return;
        }
        int index = 1;
        Node *node = new Node(data);
        Node *temp = head;
        if (pos == 0){
            node->next = temp;
            head = node;
            length++;
            return;
        }
        while (index < pos){
            temp = temp->next;
            index++;
        }
        node->next = temp->next;
        temp->next = node;
        length++;
        return;
    }
    // 删除第pos个元素
    void Delete(int pos){
        if (pos<0 || pos>length){
            cout << "illegal position!" << endl;
            return;
        }
        if (pos == 1){
            Node *p = head;
            head = head->next;
            length--;
            delete p;
            return;
        }
        int index = 2;
        Node *temp = head;
        while (index < pos){
            temp = temp->next;
            index++;
        }
        Node *p = temp->next;
        temp->next = temp->next->next;
        delete p;
        length--;
        return;
    }
    // 反向链表
    void Reverse(){
        if (length<2)
            return;
        Node *curNode = head;
        Node *nextNode = head->next;
        Node *temp;
        while (nextNode != NULL){
            temp = nextNode->next;
            nextNode->next = curNode;
            curNode = nextNode;
            nextNode = temp;        
        }
        head->next = NULL;
        head = curNode;
    }
    // 查找节点位置，返回第一个匹配的位置，查找不到时返回-1
    int Find(int data){
        Node *temp = head;
        int index = 1;
        while (temp != NULL){
            if (temp->data == data)
                return index;
            temp = temp->next;
            index++;
        }
        return -1;      
    }
    // 打印链表
    void Print(){
        if (head == NULL){
            cout << "empty LinkList!" << endl;
            return;
        }
        Node *temp = head;
        while (temp != NULL){
            cout << temp->data << " ";
            temp = temp->next;
        }
        cout <<endl;
    }
};

双向链表

• 包含，创建，析构，指定位置后插入，指定位置删除，打印

struct DulNode{
    int data;
    DulNode *prior;
    DulNode *next;
    DulNode(int d) :data(d), prior(NULL), next(NULL){}
};
class DulLinkList{
private:
    DulNode *head;
    int length;
public:
    DulLinkList(){
        head = NULL;
        length = 0;
    }
    ~DulLinkList(){
        DulNode *temp;
        for (int i = 0; i < length; i++){
            temp = head;
            head = head->next;
            delete temp;
        }
    }
    void Insert(int data, int pos){
        if (pos < 0 || pos>length){
            cout << "illegal position" << endl;
        }
        DulNode *node = new DulNode(data);
        DulNode *temp = head;
        if (pos == 0){
            head = node;
            length++;
            return;
        }
        int index = 1;
        if (index < pos){
            temp = temp->next;
            index++;
        }
        node->prior = temp;
        node->next = temp->next;
        if (temp->next != NULL)
            temp->next->prior = node;
        temp->next = node;
        length++;
    }
    void Delete(int pos){
        if (pos < 0||pos>length){
            cout << "illegal position" << endl;
            return;
        }
        DulNode *temp = head;
        if (pos == 1){
            head = head->next;
            if (head != NULL)
                head->prior = NULL;
            delete temp;
            length--;
            return;
        }
        int index = 2;
        while (index < pos){
            temp = temp->next;
            index++;
        }
        DulNode *p = temp->next;
        temp->next = temp->next->next;
        if (p->next != NULL)
            p->next->prior = temp;
        length--;
        delete p;

    }
    int Find(int data) {
        DulNode *temp = head;
        int index = 1;
        while (temp != NULL){
            if (temp->data == data)
                return index;
            temp = temp->next;
            index++;
        }
        return -1;
    }
    void Print() {
        if (length == 0){
            cout << "empty DulLinkList!" << endl;
            return;
        }
        DulNode *temp = head;
        while (temp != NULL){
            cout << temp->data << " ";
            temp = temp->next;
        }
        cout << endl;
    }

};