单向链表(C++)

Node节点定义：

class IntSLLNode {
public:
    IntSLLNode() {
        next = 0;
    }

    IntSLLNode(int val, IntSLLNode *in = 0) {
        info = val;
        next = in;
    }

    int info;
    IntSLLNode *next;
};

这里有个地方，带参数的构造函数中的第二个参数是个小细节，在后面管理链表的InSLList类中，addToHead里面，通过这个参数来连接节点，从而使每次new出来的节点都是头节点。

接下来就是构造用来管理链表的管理类，增加头结点，增加尾节点等等功能,这里我们起名为IntSLList，刚才提到过：

#include "IntSLLNode.h"

class IntSLList {
public:
    IntSLList() {
        head = tail = 0;
    }

    ~IntSLList();
    int isEmpty() {
        return head == 0;
    }

    void addToHead(int);
    void addToTail(int);
    int deleteFromHead();
    int deleteFromTail();
    void deleteNode(int);

    bool isInList(int) const;

private:
    IntSLLNode *head, *tail;
};

接下来实现这个类中的每个函数的功能
1、addToHead(int):

void IntSLList::addToHead(int val) {
    head = new IntSLLNode(val, head);
    if (tail == 0) {
        tail = head;
    }
}

这个函数很简单，主要就是构建头节点和判断头节点是否相同，如果相同就是指向同一个节点。其中head每次都是最新的头节点，这个地方刚才上面有所提到，不再描述。接下来我们来看addToTail这个函数
2、addToTail(int)：

void IntSLList::addToTail(int val) {
    if (tail != 0) {
        tail->next = new IntSLLNode(val);
        tail = tail->next;
    } else
        head = tail = new IntSLLNode(val);
}

这个函数也很简单，主要就是两个思路，第一个判断当前链表里面有没有节点，如果有直接创建一个新的，并赋值给tail->next，然后再讲next赋值给tail更新一下节点就好了。如果当前链表里面没有节点，那就让head和tail同时指向新节点即可。

以上就是添加节点的两个函数，下面来看看删除节点的三个函数：
1、deleteFromHead():

int IntSLList::deleteFromHead() {
    int val = head->info;
    IntSLLNode* temp = head;
    if (head == tail) {
        head = tail = 0;
    } else
        head = head->next;

    delete temp;
    return val;
}

函数返回值为Int，代表着你删除头节点存储的val值是多少，这么设计主要是为了当节点要删除时，但是一时间还有用，就将val返回用来处理外部逻辑，然后进入函数中之后，用一个临时int变量把要删除的head存储的值存储起来用来返回，再用一个临时指针保存当前头结点，其次判断当前头结点和尾节点是否相同，如果相同，先将这两个指针指向null，然后删除，如果不相等，先将当前头结点的下个结点赋值给当前头指针，让这个结点成为新的节点，然后再把保存的节点删除，然后被删除头结点的值。
删除完了头结点我们来看一下删除尾节点，删除尾节点代码稍微多一些。
2、deleteFromTail():

int IntSLList::deleteFromTail() {
    int val = tail->info;
    if (head == tail) {
       delete head;
       head = tail = 0;
    } else {
        IntSLLNode *temp;
        for (temp = head; temp->next != tail; temp = temp->next);
        delete tail;
        tail = temp;
        tail->next = 0;
    }

    return val;
}

跟删除头结点一样，先用一个int的临时变量保存要删除尾节点存储的值，用于返回，接下来判断头指针和尾指针是不是指向同一个节点，如果是的话，将tail节点删除，然后将两个指针都指向null，如果不是，声明一个临时节点指针，然后for循环查找尾节点的前一个节点并让临时节点指针指向这个节点，删除tail尾几点，然后并重新更新tail，让tail=tmp，更新完之后，让这个新尾尾节点的next指向null。
下面我们来看看最后一个删除函数
3、deleteNode(int)：

void IntSLList::deleteNode(int val) {
    if (head != 0) {
        if (head == tail) {
            delete head;
            head = tail = 0;
        } else if(val == head->info) {
            IntSLLNode *temp = head;
            head = head->next;
            delete temp;
        } else {
            IntSLLNode *pred, *tmp;
            for (pred = head, tmp = head->next; tmp != 0 && !(tmp->info == val);pred=pred->next, tmp=tmp->next);
            if (tmp != 0) {
                pred->next = tmp->next;
                if (tmp == tail) {
                    tail = pred;
                }
                delete tmp;
            }
        }

    }
}

先判断当前链表里面是否有节点，如果没有就不做任何处理，如果有，有三种情况需要处理，第一种是不是只有一个节点，如果是的话，删除节点，然后将head和tail指针指向null，第二种情况，要删除的节点刚好是头结点，方法跟以前一样，用一根临时节点指针保存当前头结点，然后将head指针指向下一个节点，然后删除刚才保存的节点，这样就删除掉了，第三种情况，如果要删除节点不符合上述两种情况，就代表删除链表其中某个一个节点，我们用两个节点指针来操作，一个是pred，一个是tmp，为什么要声明两个节点指针，我们一会再讨论，第一个思路，用tmp找出要删除节点的位置，当找到了之后并且节点指针指向的不是null，现在将上一个节点的next更新到tmp的next，用来断开删除的节点，然后判断是否等于尾节点，如果是，这个时候pred就起到作用了，更新tail尾节点指针，然后将tmp指向的节点删除，如果不是，直接删除tmp节点。
根据上述分析，链表的增删的管理类就完成了，改和查，相对简单，这里就不描述了，感兴趣的可以自己研究一下