单链表的优化（十三）

        我们在之前实现了单链表，那么我们如何遍历单链表中的每一个数据元素呢？肯定直接一个 for 循环就可以搞定啊，我们来看看当前基于我们实现的单链表遍历的方法，main.cpp 如下

#include <iostream> #include "LinkList.h" using namespace std; using namespace DTLib; int main() {     LinkList<int> list;     for(int i=0; i<5; i++)      // O(1)     {         list.insert(0, i);     }     for(int i=0; i<list.length(); i++) // O(n)     {         cout << list.get(i) << endl;     }     return 0; }

        我们来看看输出结果，看看是不是遍历呢

        结果是正确的，我们来分析下上面的测试代码的效率。第一个 for 循环，因为每次都是在 0 位置处插入数据元素，因此它的时间复杂度是 O(1)；而第二个 for 循环，因为它要全部循环一遍，因此它的时间复杂度为 O(n)。我们就奇怪了，明明同样是两个 for 循环，效率竟然不相同。不能以线性的时间复杂度完成单链表的遍历，那么此时新的需求就产生了：为单链表提供新的方法，在线性时间内完成遍历。

        下来说说设计思路，利用游标的思想：

        1、在单链表的内部定义一个游标（Node* m_current）；

        2、遍历开始前将游标指向位置为 0 的数据元素；

        3、获取游标指向的数据元素；

        4、通过结点中的 next 指针移动游标。

        提供一组遍历相关的函数，以线性的时间复杂度完成遍历链表，如下

        遍历函数原型设计如下：

        bool move(int i, int step = 1);

        bool end();

        T current();

        bool next();

        下来我们来看看优化后的 LinkList.h 是怎样的，如下

LinkList.h 源码

#ifndef LINKLIST_H #define LINKLIST_H #include "List.h" #include "Exception.h" namespace DTLib { template < typename T > class LinkList : public List<T> { protected:     struct Node : public Object     {         T value;         Node* next;     };     mutable struct : public Object     {         char reserved[sizeof(T)];         Node* next;     } m_header;     int m_length;     int m_step;     Node* m_current;     Node* position(int i) const     {         Node* ret = reinterpret_cast<Node*>(&m_header);         for(int p=0; p<i; p++)         {             ret = ret->next;         }         return ret;     } public:     LinkList()     {         m_header.next = NULL;         m_length = 0;         m_step = 1;         m_current = NULL;     }     bool insert(const T& e)     {         return insert(m_length, e);     }     bool insert(int i, const T& e)     {         bool ret = ((0 <= i) && (i <= m_length));         if( ret )         {             Node* node = new Node();             if( node != NULL )             {                 Node* current = position(i);                 node->value = e;                 node->next = current->next;                 current->next = node;                 m_length++;             }             else             {                 THROW_EXCEPTION(NoEnoughMemoryException, "No memory to insert new element ...");             }         }     }     bool remove(int i)     {         bool ret = ((0 <= i) && (i < m_length));         if( ret )         {             Node* current = position(i);             Node* toDel = current->next;             current->next = toDel->next;             delete toDel;             m_length--;         }         return ret;     }     bool set(int i, const T& e)     {         bool ret = ((0 <= i) && (i < m_length));         if( ret )         {             position(i)->next->value = e;         }         return ret;     }     T get(int i) const     {         T ret;         if( get(i, ret) )         {             return ret;         }         else         {             THROW_EXCEPTION(IndexOutOfBoundsException, "Invaild parameter i to get element ...");         }     }     bool get(int i, T& e) const     {         bool ret = ((0 <= i) && (i < m_length));         if( ret )         {             e = position(i)->next->value;         }         return ret;     }     int find(const T& e) const     {         int ret = -1;         int i = 0;         Node* node = m_header.next;         while( node )         {             if( node->value == e )             {                 ret = i;                 break;             }             else             {                 node = node->next;                 i++;             }         }         return ret;     }     int length() const     {         return m_length;     }     void clear()     {         while( m_header.next )         {             Node* toDel = m_header.next;             m_header.next = toDel->next;             delete toDel;         }         m_length = 0;     }     bool move(int i, int step = 1)     {         bool ret = (0 <= i) && (i < m_length) && (step > 0);         if( ret )         {             m_current = position(i)->next;             m_step = step;         }         return ret;     }     bool end()     {         return (m_current == NULL);     }     T current()     {         if( !end() )         {             return m_current->value;         }         else         {             THROW_EXCEPTION(INvalidOPerationException, "No value at current position ...");         }     }     bool next()     {         int i = 0;         while( (i < m_step) && !end() )         {             m_current = m_current->next;             i++;         }         return (i == m_step);     }     ~LinkList()     {         clear();     } }; } #endif // LINKLIST_H

main.cpp 源码

#include <iostream> #include "LinkList.h" using namespace std; using namespace DTLib; int main() {     LinkList<int> list;     for(int i=0; i<5; i++)      // O(1)     {         list.insert(0, i);     }     for(list.move(0); !list.end(); list.next()) // O(1)     {         cout << list.current() << endl;     }     return 0; }

        我们来看看编译结果

        我们看到结果还是正确的，证明我们上面代码的编写是没有错误的。我们再来分析下，它每次移动，移动后 current 指针就停在那块，等到下次移动的时候还是从这块开始移动。也就是说，每次遍历的时候，它只需要遍历一次就可以输出结果了，这样的话它遍历的时间复杂度就为 O(1) 了。我们再来将 new 和 delete 操作封装下，方便后面的使用，具体封装如下

virtual Node* create()     {     return new Node(); } virtual void destroy (Node* pn) {     delete pn; }

        然后将下面的 new 和 delete 操作全部换成 create 和 destory 函数。我们来试下将 main.cpp 测试代码中移动的 step 改为 2，那么它便输出的是偶数了。我们来看看结果

        确实是输出的只有偶数。那么我们移动的 step 为 10 呢？那它就应该只输出 4 了，我们再来看看结果

        现在我们的 LinkList 类已经近乎完美了，优化后的效率遍历的时候极大的提高了。通过今天对 LinkList 优化的学习，总结如下：1、单链表的遍历需要在线性时间内完成；2、在单链表内部定义游标变量，通过游标变量提高效率；3、遍历相关的成员函数是相互依赖，相互配合的关系；4、封装结点的申请和删除操作更有利于增强扩展性。