简介

特点：

1、 用一组地址任意的存储单元 存储数据元素。存储单元地址 可连续，也可不连续。

为了形成逻辑线性结构，每一个结点 除了保存需要存储的数据外，还需要保存逻辑上相邻的下一个结点的地址。

2、链表由n个类型相同的结点通过指针链接形成线性结构。结点由数据域和指针域组成。

数据域用于存储结点代表的数据，指针域存储结点的后继结点地址。

3、

链表不支持随机访问。有n个结点的线性表，访问某个结点的平均时间复杂度为O(n/2)，最坏为O(n) 。而数组支持随机访问，他的访问时间复杂度为O(1)

         

 

优点：插入和删除操作无需移动元素，只需修改结点的指针域。这点恰巧是顺序表(如ArrayList和数组)的缺点。

缺点：访问元素时，不支持随机访问。访问第n个数据元素，必须先得到第n-1个元素的地址，

因此访问任何一个结点必须从头结点开始向后迭代寻找，直到找到这个目标结点为止。 

 

 

结点：由数据域和指针域构成。数据域用来存储数据元素，而指针域用来保存逻辑上相邻的下一个结点的地址。

头结点：也叫哑结点（dummy node）。为了方便，一般情况下，我们都在链表的第一个逻辑位置上使用一个头结点。它的数据域不保存数据，而指针域保存表的第一个结点的地址，他相当于一个标记结点。

 

带头结点的单链表的示意图

 

 

 如下是一个保存 char类型，数据元素依次为 【'A' , 'B' , 'C'】的，带头结点的链表的结构图。

 

 

链表的主要操作

• 追加结点（尾插法和头插法追加）
• 插入结点（在指定的索引位置插入一个结点）
• 删除结点（删除一个指定索引的结点）
• 访问结点（get/set）
• 遍历结点

 代码实现

 

 初始状态

使用成员字段headNode 代表头结点（ListNode结构体对象），初始状态指针域为NULL。

使用成员字段pLastNode保存链表的最后一个结点地址，这样在执行append操作时，就不必循环了。

使用成员字段size保存链表实时长度。

 

在执行clear操作后，链表会恢复到这个状态。

 

#include
     
      #include
      
       #include
       
           using namespace std;struct ListNode{    int element;    ListNode* next;        ListNode(int e=0,ListNode* nxt=0):element(e),next(nxt)    {    }    };class LinkeList{private:    ListNode  headNode;      //头结点    ListNode* pLastNode;     //保存最后一个结点的地址    int size;                //表实际长度    public:    LinkeList():headNode(0,0),pLastNode(0),size(0)    {        pLastNode = &headNode;    }        ~LinkeList()    {        //析构函数：释放所有的数据结点        clear();    }    /*    * 功能:删除索引为index 的结点      * 时间复杂度O(n)    */    bool remove(int index)    {        ListNode *p = &headNode;        ListNode *p_delete;        int i=0;                if(index <0) return false;                //循环用于获取 待删除结点的前一个结点的指针 。        //用 i
        
         next;            i++;        }                //退出循环后，合法情况下，p为待删除结点的前一个结点的指针        //因此p 和 p->next 都不能为空 ，否则就是因为参数index不合法        if(p==0 || p->next==0)            return false;                            p_delete = p->next;            if(p_delete->next==0)            pLastNode = p;   //如果删除的是最后一个结点，则更新pLastNode        p->next = p_delete->next;        delete p_delete;        size --;                        return true;    }            /*    * 功能:将新元素e包装为结点，插入到索引为index 的地方。    * 时间复杂度O(n)    */        bool insert(int index , int e)    {        ListNode *p = &headNode;        ListNode *p_new;        int i=0;                if(index <0) return false;                //循环用于获取 待插结点的前一个结点的指针        //用 i
         
          next;            i++;        }                //退出循环后，合法情况下，p为待插结点的前一个结点的指针        //因此p 不能为空 ，否则就是因为参数index不合法，index过大 。        //但是p->next可以为空，如果是空，则相当于末尾追加append 。如果不为空，则是在中间位置插入。        if(p==0) return false;                p_new = new ListNode(e,p->next);          if(p->next == 0)            pLastNode = p_new;   //更新pLastNode        p->next = p_new;                size++;                        return true;    }                /*    * 功能:在链表末尾追加一个元素。    */    void append(int e)    {        ListNode*new_node = new ListNode(e,0);  //构造新结点                pLastNode->next = new_node;        pLastNode = new_node;            size++;    }        int length()const    {        return size;    }        int indexOf(int e)const    {        ListNode *p = headNode.next;                for(int i=0;p!=0;++i,p=p->next){            if(p->element == e) return i;        }        return -1;   // not found    }             bool isEmpty()const    {        return size == 0;    }            /*    * 功能：删除所有的数据结点，清空表    */    void clear()    {        ListNode*p = headNode.next;            ListNode* t;        while(p!=0){            t = p;            p = p->next;            delete t;        }        //回归初始状态        headNode.next= 0;        pLastNode = &headNode;        size = 0;    }        void show()const    {        ListNode*p = headNode.next;                cout<<"[";        while(p!=0){            if(p!=headNode.next)                cout<<',';            cout<
          
           element; p=p->next; } cout<<"]"; } int operator[](size_t index)const { ListNode*p = headNode.next; int i=0; if( index <0 || index >= size ) throw std::out_of_range(0); while(p!=0 && i
           
            next; i++; } return p->element; } int& operator[](size_t index) { ListNode*p = headNode.next; int i=0; if( index <0 || index >= size ) throw std::out_of_range(0); while(p!=0 && i
            
             next; i++; } return p->element; } };int main(){ LinkeList list; list.append(1); list.append(2); list.append(6); list.insert(2,3); list.insert(3,4); list.insert(4,5); list.insert(5,5); cout<<"len = "<
             
              <
             
            
           
          
         
        
       
      
     

 

获取指定索引处的元素

 链表不支持随机访问。因此时间复杂度为O(n)。这是单链表不可避免的缺点。 

 

int& operator[](size_t index){        ListNode*p = headNode.next;        int i=0;                if( index <0 || index >= size  )   //索引越界            throw std::out_of_range(0);                while(p!=0 && i
     
      next;            i++;                }        return p->element;}
     

 

 

插入元素

插入元素前，需要先获取待插入位置的前一个结点的地址。在插入时，先连接后结点，在连接前结点，这样就避免使用临时变量了。

在已知待插入位置的前一个结点的地址情况下，时间复杂度为O（1）

 

删除元素 

删除元素前，需要先获取待删除位置的前一个结点的地址。

在已知待删除位置的前一个结点的地址情况下，时间复杂度为O（1）

 

 

小提示

1、从理论上说，链表的优点就是因为他插入和删除等更改元素位置的操作很高效，时间复杂度为O（1） ，但实际上，由于我们在使用线性表时，是基于索引的，我们总是用索引标识一个结点，而不是他的地址，因此这就削弱了链表的优势。例如为了删除索引为n的结点，我们必须从头结点开始循环，找到索引为n-1的结点的地址，然后才能执行删除操作。所以从这方面看，实际操作时时间复杂度依然是O（n）。但是，修改指针比移动大量结点元素快多了，所以通常这也不是太大的问题。

 

 

2、链表是不支持随机访问的，因此，对于链表，如果我们想对所有的结点执行某种操作，不应该使用传统的 for 循环，而应该使用迭代器，因为迭代器只需完成一次性循环，避免反复循环。下面是一Java集合框架中的LinkedList做测试，可以明显感受二者的差距，使用迭代器遍历比使用for循环快近10倍。

 

public class DataStructure{    public static void main(String[] args)    {        LinkedList
      
        list = new LinkedList
       
        ();                for(int i=0;i<100000;++i)        {            list.add(i);        }                useIterator(list);        //useForLoop(list);            }            //耗时:4950ms    public static void useForLoop(LinkedList
        
          list)    {        long s = System.currentTimeMillis();                for (int i = 0; i < list.size(); i++)        {            System.out.println(list.get(i));         }        long e = System.currentTimeMillis();                System.out.println("耗时:"+(e-s) + "ms");            }        //耗时:546ms    public static void useIterator(LinkedList
         
           list)    {                long s = System.currentTimeMillis();                for(Integer i:list)        {            System.out.println(i);        }        long e = System.currentTimeMillis();                        System.out.println("耗时:"+(e-s) + "ms");    }}
         
        
       
      

 

 

练习

1、实现单链表的选择排序

2、实现单链表的头插法添加数据

3、实现反转单链表（空间复杂度为O（1））

 

/*代码省去了前面已经实现的部分*/class LinkeList{//...public://...         //选择排序     void selectSort()    {        ListNode *aim = headNode.next;          ListNode *min;        ListNode *p;        int t;                if(aim==0) return;   //空表无需排序                 while(aim->next!=0)        {            min = aim;      //假设当前比较对象结点aim是最小的             p = aim->next;            while(p!=0)            {                if(min->element  >  p->element){                    min = p;                }                p = p->next;                }            if(min != aim)  //最小元素易主了             {                t = min->element;                min->element = aim->element;                aim->element = t;                    }                        aim = aim->next;            }        }            //头插法添加数据 :将数据添加为链表的第一个结点中     void addFirst(int e)    {        ListNode*new_node = new ListNode(e,headNode.next);  //构造新结点         headNode.next = new_node;        size++;    }        //反转单链表     void revserse()    {        ListNode* pre=0;        ListNode* cur = headNode.next;        ListNode* nxt = cur->next;                if(size < 1) return ;                while(nxt!=0)        {            cur->next = pre;            pre = cur;            cur = nxt;                        nxt = nxt->next;                    }                cur->next = pre;        headNode.next = cur;               }     };