数据结构与算法之-----链表（List)

前言

写在前面的话：数据结构与算法。

1. 对于初识数据结构的小伙伴们，鉴于后面的数据结构的构建会使用到同tag前面的内容，包括具体数据结构的应用，所使用到的数据结构，也是自己构建的，未使用系统的库文件，因此，建议这类小伙伴们按顺序进行学习；

2. 对于想查询有关资料的小伙伴们，可以选择性地浏览。希望大家都能有所收获～

向量与链表的区别

本章的主要内容：链表。

上一篇文章笔者分享了数据结构中最为基础的结构-----向量（顺序表），它的特点是，数据存储在内存的一块连续区域中，如果该区域末端的内存区域已被占用，再使用扩容操作就可能会导致意外结果。

再比如说，如果一个业务逻辑中，插入和删除操作比较频繁，使用向量结构的话，会使得效率变低，综合多种因素考虑，我们产生了一种新的数据结构-----链表：

向量与链表的基本区别：

• 向量：数据存储在内存的一块连续区域中；

• 链表：数据存储在内存的非连续区域中；

如上所言，插入和删除操作比较频繁，则选择链表，而如果查询操作更为频繁，则应采用向量结构存储。

构建链表

下面，我们来看链表的一些基本运算。我们先来看链表结点模版类，在该类中，定义了链表结点的一些基本操作：

/*
 *
 * 作者：易果啥笔
 * 时间：2021.8.19
 * 内容：链表结点模版类
 *
 *
 */
#ifndef LINKLIST_LISTNODE_H
#define LINKLIST_LISTNODE_H

typedef int Rank ; //秩

template <typename T> struct ListNode { //链表结点模版类----双向链表
    //成员
    T data ; ListNode<T>* pred ; ListNode<T>* succ ; //数据，前驱，后继
    //构造函数
    ListNode() {} ; //针对header和trailer的构造
    ListNode( T e , ListNode<T>* p = NULL , ListNode<T>* s = NULL) : data(e),pred(p),succ(s) {} //参数初始化列表
    //操作接口
    ListNode<T>* insertAsPred(T const& e) ; //紧靠当前结点之前插入新结点
    ListNode<T>* insertAsSucc(T const& e) ; //紧靠当前结点之后插入新结点
};

/*
 *
 * 作者：易果啥笔
 * 时间：2021.8.18
 * 内容：链表结点模版类的实现
 *
 *
 */

template <typename T> ListNode<T>* ListNode<T>::insertAsPred(const T &e) {
    ListNode<T>* x = new ListNode(e,pred, this); //创建新结点
    pred->succ = x ;
    pred = x ;
    return x; //返回新结点的位置
}

template <typename T> ListNode<T>* ListNode<T>::insertAsSucc(const T &e) {
    ListNode<T>* x = new ListNode(e,this,succ); //创建新结点
    succ->pred = x ;
    succ = x;
    return x;
}

#endif //LINKLIST_LISTNODE_H

接着，我们定义链表模版类，用于定义结点与结点之间的结构关系：

/*
 *
 * 作者：易果啥笔
 * 时间：2021.8.19
 * 内容：链表模版类
 *
 *
 */

#ifndef LINKLIST_LINKLIST_H
#define LINKLIST_LINKLIST_H
#include <cstdlib>
#include "ListNode.h"

template <typename T> class List {
    private:

        int _size ; ListNode<T>* header ; ListNode<T>* trailer ; //规模，头哨兵，尾哨兵

    protected:

        void init() ; //链表创建时的初始化
        int clear() ; //清除所有结点
        void swap(T& x,T& y){T temp = x ; x = y ; y = temp ; } //用于双向链表的倒置
        void copyNodes(ListNode <T>* p , int n) ; //复制链表中自位置p起的n项
        void merge(ListNode <T>* & , int , List<T>& , ListNode<T>* , int) ; //有序链表区间归并
        void mergeSort(ListNode <T>* & p , int n) ; //对从p开始的连续的n个结点归并排序
        void insertionSort(ListNode <T>*,int); //对从p开始的连续的n个结点插入排序
        void selectionSort(ListNode <T>*,int); //对从p开始的连续的n个结点选择排序

    public:

        //构造函数
        List(){ init();} ; //默认构造函数

        //析构函数
        ~List() ; //释放（包含头，尾哨兵在内的）所有结点

        //只读访问接口
        Rank size() const {return _size;} ; //规模

        bool empty() const {return _size<=0;} ; //判空

        T& operator[](int r) const ; //重载，支持循秩访问

        ListNode<T>* first() const {return header->succ ;} ; //首结点位置

        ListNode<T>* last() const {return trailer->pred ;} ; //末结点位置

        bool valid(ListNode<T>* p) //判断位置p是否对外合法
        {return p && (trailer != p) && (header != p) ;} ; //将头尾结点等同于NULL

        int disordered() const ; //判断链表是否已经排序

        ListNode<T>* find(T const& e) const  {return find(e,_size,trailer); }//无序链表查找

        ListNode<T>* find(T const& e,int n,ListNode<T>* p) const ; //无序区间查找

        ListNode<T>* search(T const& e) const {return search(e,_size,trailer); } ; //有序链表查找

        ListNode<T>* search(T const& e,int n,ListNode<T>* p) const ; //有序区间查找

        ListNode<T>* selectMax(ListNode<T>* p,int n) ;

        ListNode<T>* selectMax(){return selectMax(header->succ,_size) ;} ;//返回整体最大者

        //可写访问接口
        ListNode<T>* insertAsFirst(T const& e) ; //将e当作首结点插入

        ListNode<T>* insertAsLast(T const& e) ; //将e当作末结点插入

        ListNode<T>* insertAsBefore(ListNode<T>*,T const& e) ; //将e当作p的前驱插入

        ListNode<T>* insertAsAfter(ListNode<T>*,T const& e) ; //将e当作p的后继插入

        T remove(ListNode<T>* p); //删除合法位置p处的结点，返回被删除结点的数据项

        void merge(List<T>& L){merge(first(),_size,L,L.first(),L._size);}//全链表归并

        void sort(ListNode<T>* p,int n); //链表区间排序

        void sort(){sort(first(),_size);}; //链表整体排序

        int deduplicate(); //无序去重

        int uniquify(); //有序去重

        void reverse(); //前后倒置

        //遍历
        void traverse(void (*) (T&));

};

/*
 *
 * 作者：易果啥笔
 * 时间：2021.8.18
 * 内容：链表模版类的实现
 *
 *
 */

/*
 * protected方法
 */

template <typename T> void List<T>::init() { //链表初始化，在创建链表对象是统一调用
    header = new ListNode<T>;
    trailer = new ListNode<T>;
    header->succ = trailer;
    header->pred = NULL;
    trailer->pred = header;
    trailer->succ = NULL;
    _size = 0;

}

template <typename T> int List<T>::clear() {
    int oldSize = _size ;
    while(0 < _size) remove(header->succ);
    return oldSize ; //返回原来的总结点数
}

template<typename T> void List<T>::copyNodes(ListNode <T>* p, int n){
    init();
    while(n--){
        insertAsLast(p->data) ; p = p->succ ;
    }
}


template <typename T> void List<T>::insertionSort(ListNode<T> * p, int n) {
    for(int r = 0 ; r < n ; r++){
        insertAsAfter(search(p->data,r,p),p->data) ; //查找适当的位置并插入
        p = p->succ ; remove(p->pred); //转向下一结点
    }
}


template <typename T> ListNode<T>* List<T>::selectMax(ListNode<T>* p,int n) {
    ListNode<T>* max = p ;
    for(ListNode<T>* cur = p ; 1 < n ; n--){
        if((cur = cur->succ)->data >= max->data)
            max = cur ;
    }
    return max ; //返回最大结点位置
}

template <typename T> void List<T>::selectionSort(ListNode<T>* p, int n) {
    ListNode<T>* head = p->pred ;
    ListNode<T>* tail = p ;
    for(int i = 0 ; i < n ; i++) tail = tail->succ ;
    while(1 < n) {
        ListNode<T>* max = selectMax(head->succ,n) ;
        insertAsBefore(tail,remove(max));
        tail = tail->pred ; n-- ;
    }
}


template <typename T> void List<T>::merge(ListNode<T> *& p, int n, List<T> & L, ListNode<T> * q, int m) {
    ListNode<T>* pp = p->pred ;
    while(0 < m)
        if((0 < n) && (p->data <= q->data)){
            if(q == (p = p->succ)) break ; n-- ;
        }
        else{
            insertAsBefore(p,L.remove((q = q->succ)->pred)) ; m-- ;
        }
    p = pp->succ ;

}

template <typename T> void List<T>::mergeSort(ListNode<T> *&p, int n) {
    if(n < 2) return ;
    int m = n >> 1;
    ListNode<T>* q = p ;
    for(int i = 0 ; i < m ; i++) q = q->succ ;
    mergeSort(p,m) ;
    mergeSort(q,n-m );
    merge(p,m,*this,q,n-m); //归并
}

/*
 * public方法
 */

template <typename T> List<T>::~List(){
    clear() ; delete header ; delete trailer ;
}


template <typename T> ListNode<T>* List<T>::find(T const& e,int n,ListNode<T>* p) const {
    while(0 < n--)
        if(e == (p = p->pred)->data) return p; //逐个比对，直至命中或范围越界
    return NULL; //失败时，返回NULL
}

template <typename T> ListNode<T>* List<T>::search(T const& e,int n,ListNode<T>* p) const {
    while(0 <= n--) //在结点p的n个前驱结点中查找，找到不大于e的最后者
        if(((p = p->pred)->data) <= e) break;
    return p; //返回终止的位置

}

template <typename T> ListNode<T>* List<T>::insertAsFirst(T const& e){
    _size++ ; return header->insertAsSucc(e); //e当作首结点插入
}
template <typename T> ListNode<T>* List<T>::insertAsLast(T const& e){
    _size++ ; return trailer->insertAsPred(e); //e当作尾结点插入
}
template <typename T> ListNode<T>* List<T>::insertAsBefore(ListNode<T>* p , T const& e){
    _size++ ; return p->insertAsPred(e); //e当作p的前驱结点插入
}
template <typename T> ListNode<T>* List<T>::insertAsAfter(ListNode<T>* p , T const& e){
    _size++ ; return p->insertAsSucc(e); //e当作p的后继结点插入
}

template <typename T> T List<T>::remove(ListNode<T>* p){
    T e = p->data;
    p->pred->succ = p->succ;
    p->succ->pred = p->pred;
    delete p ; _size-- ;
    return e ; //返回备份的数据项
}


template <typename T> int List<T>::deduplicate(){
    if(_size < 2) return 0;
    int oldSize = _size ;
    ListNode<T>* p = header ; Rank r = 0 ;
    while(trailer != (p = p->succ)){
        ListNode<T>* q = find(p->data,r,p);
        q ? remove(q) : r++ ;
    }
    return oldSize - _size ; //返回被删除总数
}

template <typename T> int List<T>::uniquify(){
    if(_size < 2) return 0;
    int oldSize = _size;
    ListNode<T>* p ; ListNode<T>* q ;
    for(p = header,q = p->succ ; trailer != q ; p = q , q = q->succ) //从自左向右扫描
        if(p->data == q->data){remove(q) ; q = p ;}
    return oldSize - _size ; //返回被删除总数
}


template <typename T> void List<T>::traverse(void (*visit) (T&)){
    for(ListNode<T>* p = header->succ ; p != trailer ; p = p->succ)
        visit(p->data);
}

template <typename T> void List<T>::sort(ListNode<T>* p,int n) { //链表区间排序
    switch (random() % 3)
    {
        case 1:
            insertionSort(p,n) ; break; //插入排序
        case 2:
            selectionSort(p,n) ; break; //选择排序
        default:
            mergeSort(p,n) ; break; //归并排序

    }
}

template <typename T> T& List<T>::operator[] (int r) const {
    ListNode<T>* p = first() ;
    while(0 < r--) p = p->succ ;
    return p->data ;
}

template<typename T> int List<T>::disordered() const {
    int count = 0 ;
    for(ListNode<T>* p = header->succ ; p->succ != trailer ; p = p->succ){
        if(p->data > p->succ->data)
            count++;
    }
    return count ; //返回逆序的个数
}

template<typename T> void List<T>::reverse() {
    ListNode<T>* begin  = header;
    ListNode<T>* end = trailer;
    while( ( begin != end ) && ( end->succ != begin ) ){
        swap(begin->data,end->data);
        begin = begin->succ;
        end = end->pred;
    }
}


#endif //LINKLIST_LIST_H

代码比较长，

• 如果是查阅有关资料，可以选择性的浏览；

• 如果是学习数据结构，笔者建议尽量全部理解并且自己能够动手写一个“微型版”的链表，这对数据结构的学习非常有帮助。

下面是链表的有关使用：

/*
 *
 * 作者：易果啥笔
 * 时间：2021.8.19
 * 内容：链表的使用
 *
 *
 */

#include <iostream>
#include "List.h"
#include <ctime>

using namespace std;

template <typename T> void print(T& e){
    cout<<e<<"\t";
}

int main(){
    clock_t start[10],finish[10];

    List<int> list; //建立链表

    //测试插入耗时
    start[0] = clock();
    list.insertAsFirst(1);
    finish[0] = clock();
    cout<<"插入耗时："<<(double)(finish[0] - start[0])/CLOCKS_PER_SEC<<'s'<<endl;

    list.insertAsFirst(2);
    list.insertAsFirst(3);
    list.insertAsFirst(4);
    list.insertAsFirst(5);
    list.insertAsFirst(6);
    list.insertAsFirst(7);
    list.insertAsFirst(8);
    list.insertAsFirst(9);
    list.insertAsFirst(10);
    list.insertAsFirst(11);

    cout<<"第一个结点的地址为："<<list.first()<<endl; //返回一个地址

    //测试无序查找耗时
    start[1] = clock();
    cout<<"数据'4'的地址为："<<list.find(4)<<endl;
    finish[1] = clock();
    cout<<"无序查找耗时："<<(double)(finish[1] - start[1])/CLOCKS_PER_SEC<<'s'<<endl;


    list.insertAsBefore(list.find(4),100);
    list.insertAsAfter(list.find(100),678);
    list.remove(list.find(678));
    list.traverse(print);
    cout<<"\n";

    //测试排序耗时
    start[2] = clock();
    list.sort();
    finish[2] = clock();
    cout<<"排序耗时："<<(double)(finish[2] - start[2])/CLOCKS_PER_SEC<<'s'<<endl;

    list.traverse(print);
    cout<<"\n";

    //测试有序查找耗时
    start[3] = clock();
    list.search(100);
    finish[3] = clock();
    cout<<"有序查找耗时："<<(double)(finish[3] - start[3])/CLOCKS_PER_SEC<<'s'<<endl;

    //cout<<list.search(3,11,list.find(100)) <<endl;

    list.insertAsAfter(list.search(3),333);
    list.traverse(print);
    cout<<endl;
    //测试双向链表的倒置耗时
    start[4] = clock();
    list.reverse();
    finish[4] = clock();
    cout<<"倒置耗时："<<(double)(finish[4] - start[4])/CLOCKS_PER_SEC<<'s'<<endl;

    list.traverse(print);
    cout<<endl;

    list.sort();
    list.reverse();

    cout<<list.disordered()<<"\t"<<list.size()<<endl;
    return 0;

}

好了，链表的有关知识就介绍到这了，如果有什么错误之处，欢迎在评论区指出。