基于链表的算法分析之增删查改

　　在链表描述中，集合中的元素都放在链表的节点中进行描述。链表中的节点不是一个数组元素，因此不能通过公式来映射定位某个元素。取而代之的是，每个节点中都包含了下一个节点的位置信息，链表的表头包含了第一个节点的位置信息。
　　为了在集合中找到第k个元素，就必须从表头开始，遍历第1个到第k个节点。它的时间复杂度是O(k)，平均时间复杂度为O(length)。
　　为了在集合中删除第k个元素，就要先找到第k-1和第k个节点，使第k-1个节点的下一个节点位置信息指向第k+1个节点，然后释放第k个节点所占的空间。它的时间复杂度是O(k)，平均时间复杂度为O(length)。
　　插入和删除的过程很相似，首先要创建一个新的节点，然后找到第k-1个节点，在该节点的后面插入新的节点，并把第k-1个节点、新的节点的下一个节点位置信息进行适当设置。它的时间复杂度是O(k)，平均时间复杂度为O(length)。
　　采用数组描述方法的集合仅需要能够保存所有元素的空间以及保存集合最大尺寸所需要的空间。链表描述需要除集合元素本身的空间意外，还需要额外的空间，用例保存链接节点指向下一个节点位置的指针。但一般情况下，链表描述要比数值描述的空间利用率高得多。
　　虽然数组描述、链表描述插入和删除操作的平均时间复杂度均为O(length)，但由于移动元素的操作比遍历元素的操作的开销要大得多，所以采用链表描述所实现的插入和删除操作要比数组描述执行得更快。而采用数组描述可以在常数时间内访问第k个元素，而在链表中，这种操作所需要的时间是O(k)。

根据以上算法写出此算法的检索、插入和删除指定位置元素的操作的函数。（只写出一个思路也可以）

其实刚开始学习变成，都是一种无从下手的感觉。多练练就好多了。这里
手写了一个大概原型，实现了push_item_front，其它的你自己来实现吧，写完之后自己写一些测试用例测试一下。不是很难的。

template <typename T>
class ListT
{
public:
        typedef struct _ITEM
        {   
                T data;
                struct _ITEM *next;
        } Item;

public:
        ItemListT() : n(0), m_head(NULL), m_tail(NULL)
        {   
        }   

        ~ItemListT()
        {   
                clear();
        }   

        // push item at front, ++n, return 0 for success, -1 for failed
        int push_item_front(T &t) 
        {   
                Item *it = new Item;
                if(NULL == it) // new failed
                {   
                        return -1; 
                }   

                if((NULL == m_head) && (NULL == m_tail))
                {   
                        m_head = m_tail = it;
                }
                else
                {
                        it->next = m_head;
                        m_head = it;
                }
                                ++n;
        }

        // push item at back, ++n, return 0 for success, -1 for failed
        int push_item_back(T &t);
        // pop item from front, ++n
        T pop_item_front();
        // pop item from back, ++n
        T pop_item_back();

        // add item at k pos, ++n, return 0 for success, -1 for failed
        int add_item_k(T &t, int k);
        // delete item at k pos, --n, return 0 for success, -1 for failed
        int del_item_k(int k);
        // get item at k pos, return 0 for success, -1 for failed
        int get_item_k(T &t, int k);
        // modify item at k pos, return 0 for success, -1 for failed
        int mod_item_k(T &t, int k);

        // clear all items
        void clear();
        // is empty, return true for empty, false for not empty
        bool is_empty();

protected:
        // head, tail
        Item *m_head;
        Item *m_tail;

        // number
        int n;
};