指针变量

• 创建指针变量：int* p;
• 间接取值：cout << *p;
• 注意：创建指针变量时的*和创建完指针变量间接取值时的*是完全不同的概念。

图解指针

创建 a、b 变量，并在内存中分配空间。

创建指向指针变量 p1、p2 并在内存中分配空间。

将 p1 指向 a，即指针变量 p1 中保存 普通变量 a 的地址。

指针访问数组

链表数据结构

链表相较于数组，可以充分利用内存中分散的空间，但是每个节点都至少需要一个指针，我们可以用 class 封装一个动态链表。

双向链表结点

template<class T>
struct ListNode {
    T data;
    ListNode* next;
    ListNode* prior;
};

一个数据域，一个向后指针域，一个向前指针域。

链表类

• 私有数据和方法：

• 首先通过 typedef 起别名，Node 即 ListNode<T>，PNode 即 ListNode<T> *。

• head 为链表头指针，tail 为链表尾指针。初始化时头指针和尾指针互连。

• cnt 为链表中结点数量，头尾结点不包括在内。

• PNode get_addr(int k) 是获取第 k 个结点的地址，该方法会被其它几个共有方法调用，但是我们又不希望该接口公开，就设置为私有方法。

#include <iostream>
using namespace std;

template<class T>
struct ListNode {
    T data;
    ListNode* next;
    ListNode* prior;
};

template<class T>
class MyList {
private:
    typedef ListNode<T> Node, * PNode;
    PNode head, tail;
    int cnt = 0;
    PNode get_addr(int k) {
        if (k > size() || k <= 0) return NULL;
        PNode p = head->next;
        while (k > 1) {
            p = p->next;
            k--;
        }
        return p;
    }

public:
    MyList() {
        head = new Node;
        tail = new Node;
        head->next = tail;
        tail->prior = head;
    }

    void push_back(T x) {
        cnt++;
        PNode s = new Node;
        PNode p = tail->prior;
        s->data = x;
        s->next = tail;
        p->next = s;
        tail->prior = s;
        s->prior = p;
    }

    void push_front(T x) {
        cnt++;
        PNode s = new Node;
        PNode q = head->next;
        s->data = x;
        s->next = q;
        head->next = s;
        q->prior = s;
        s->prior = head;
    }

    int size() {
        return cnt;
    }

    int get(int k) {
        return get_addr(k)->data;
    }

    void insert(int k, T x) {
        cnt++;
        PNode s = new Node;
        s->data = x;
        PNode q = get_addr(k);
        PNode p = q->prior;
        s->next = q;        p->next = s;
        q->prior = s;        s->prior = p;
    }

    void del(int k) {
        PNode s = get_addr(k);
        PNode p = s->prior, q = s->next;
        p->next = q;
        q->prior = p;
        delete s;
        cnt--;
    }

    void traverse() {
        PNode p = head->next;
        while (p != tail) {
            cout << p->data << " ";
            p = p->next;
        }
        cout << endl;
    }

};

int main() {

    MyList<int> lst;

    for(int i = 1; i <= 10; i++) 
        lst.push_back(i);

    lst.push_front(888);

    lst.traverse();

    return 0;
}