【数据结构】链表

文章目录

• • 链表的概念及结构
  • 链表的分类
  • 常用的两种链表
  • • 无头单项非循环链表
    • • 代码实现
    • 带头双向循环链表
    • • 代码实现
  • 顺序表和链表的区别

链表的概念及结构

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的

链表的分类

链表可以按三种方式分类

• 单项或者双向

• 带头或者不带头

• 循环或者不循环

这三种分类方式可以组合，也就是说，一共有8种不同的链表

---

常用的两种链表

无头单项非循环链表

结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等

---

代码实现

#ifndef CLION_SLIST_HPP
#define CLION_SLIST_HPP

#include 
namespace ns_SList{

    //节点类
    template<class T>
    class SListNode{
    public:
        T data;
        SListNode* next;
    };

    template<class T>
    class SList{
    private:
        typedef SListNode<T> Node;
        typedef SListNode<T>* PNode;
        PNode pHead;
    public:
        SList():pHead(nullptr)
        {}

    private:
        //获取新节点
        PNode BuySListNode(const T& val){
            PNode newNode = new Node;
            if(newNode == nullptr){
                std::cout<<"BuyNode Error"<<std::endl;
            }
            newNode->data = val;
            newNode->next = nullptr;
            return newNode;
        }
    public:
        //打印单链表
        void SListPrint(){
            PNode cur = pHead;
            while(cur != nullptr){
                std::cout<<cur->data<<"->";
                cur = cur->next;
            }
            std::cout<< "nullptr" <<std::endl;
        }

        //尾插
        void push_back(const T& val){
            PNode newNode = BuySListNode(val);
            if(pHead == nullptr){
                pHead = newNode;
            }
            else{
                //接收头指针
                PNode tail = pHead;
                //找到尾
                while(tail->next != nullptr){
                    tail = tail->next;
                }
                //最后一个节点的next指向newNode
                tail->next = newNode;
            }
        }

        //头插
        void push_front(const T& val){
            PNode newNode = BuySListNode(val);
            //新节点的next指向pHead
            //pHead里存的是第一个节点的地址
            newNode->next = pHead;
            //更新pHead
            pHead = newNode;
        }


        //尾删
        void pop_back(){
            //分三种情况
            //1. 链表空，不做任何处理，直接return
            //2. 链表只有一个节点，直接释放该节点，然后把头节点置空
            //3. 链表有多个节点，找到最后一个节点的前一个节点，释放最后一个节点，然后把前一个节点的next置空
            if(pHead == nullptr){
                return;
            }
            else if(pHead->next == nullptr){
                delete pHead;
                pHead = nullptr;
            }
            else{
                PNode tail = pHead->next;
                PNode prev = pHead;
                while(tail->next != nullptr){
                    prev = tail;
                    tail = tail->next;
                }
                delete tail;
                tail = nullptr; //非必要
                prev->next = nullptr;
            }
        }

        //头删
        void pop_front(){
            if(pHead == nullptr){
                return;
            }
            else{
                //记录第一个节点的地址
                PNode oldHead = pHead;
                //头指针指向第一个节点的下一个节点
                pHead = oldHead->next;
                //释放第一个节点的空间
                delete oldHead;
                oldHead = nullptr;
            }
        }

        // 单链表在pos位置之后插入x
        void insertAfter(PNode pos,const T& val){
            assert(pos);
            PNode newNode = BuySListNode(val);
            //先让新节点的next指向pos的next，保证pos后面的节点不会丢失
            newNode->next = pos->next;
            //然后让pos->next指向新节点
            pos->next = newNode;
        }


        // 单链表删除pos位置之后的值
        void eraseAfter(PNode pos){
            assert(pos);

            if(pHead == nullptr){
                return;
            }

            //让pos的next，指向pos位置之后的之后的节点
            PNode nextNode = pos->next;
            pos->next = nextNode->next;

            //释放pos位置之后的空间
            delete nextNode;
            nextNode = nullptr;
        }

        //查找val值
        PNode find(const T& val){
            PNode cur = pHead;
            while(cur != nullptr){
                if(cur->data == val){
                    return cur;
                }
                cur = cur->next;
            }
            return nullptr;
        }

        ~SList(){
            delete pHead;
            pHead = nullptr;
        }
    };
}

#endif //CLION_SLIST_HPP

带头双向循环链表

结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了.

---

代码实现

#ifndef CLION_DLIST_HPP
#define CLION_DLIST_HPP
#include 
namespace ns_DList{

    //节点类
    template <class T>
    class ListNode{
    public:
        ListNode* prev;
        ListNode* next;
        T val;
    public:
        ListNode(const T& val = T())
        :prev(nullptr)
        ,next(nullptr)
        ,val(val)
        {}
    };


    //链表类
    template <class T>
    class List{
    private:
        typedef ListNode<T> Node;
        typedef ListNode<T>* pNode;
        pNode pHead;
    public:
        List()
        :pHead(BuyListNode())
        {
            pHead->next = pHead;
            pHead->prev = pHead;
        }


    public:
        pNode BuyListNode(const T& val = T()){
            pNode newNode = new Node(val);
            return newNode;
        }

        void printList(){
            pNode cur = pHead->next;

            while(cur != pHead){
                std::cout<< cur->val << "->" ;
                cur = cur->next;
            }
            std::cout<<"nullptr"<<std::endl;
        }


        void insert(pNode pos, const T& val){
            pNode newNode = BuyListNode(val);

            pNode prev = pos->prev;

            prev->next = newNode;
            newNode->prev = prev;

            newNode->next = pos;
            pos->prev = newNode;

        }

        void push_back(const T& val){
            insert(pHead,val);
        }

        void push_front(const T& val){
            insert(pHead->next,val);
        }

        void pop_back(){
            erase(pHead->prev);
        }
        void pop_front(){
            erase(pHead->next);
        }

        void erase(pNode pos){
            assert(pHead);
            assert(pHead->next != pHead);
            pNode prev = pos->prev;
            pNode next = pos->next;
            delete pos;
            prev->next = next;
            next->prev = prev;
        }

        pNode find(const T& val){
            assert(pHead);

            pNode cur = pHead->next;
            while(cur != pHead){
                if(cur->val == val){
                    return cur;
                }
                cur = cur->next;
            }
            return nullptr;
        }

        int size(){
            int sz = 0;
            pNode cur = pHead->next;
            while(cur != pHead){
                sz++;
                cur = cur->next;
            }
            return sz;
        }

        ~List(){
            int sz = size();
            for(int i = 0; i < sz, i++){
                erase(pHead->next);
            }
            delete pHead;
            pHead = nullptr;
        }
    };
}

#endif //CLION_DLIST_HPP

顺序表和链表的区别

不同点	顺序表	链表
存储空间上	物理上一定连续	逻辑上连续，但物理上不一定连续
随机访问	支持O(1)	不支持O(N)
任意位置插入或删除元素	可能需要搬移元素，效率低O(N)	只需修改指针指向
插入	动态顺序表，空间不够时需要扩容	没有容量的概念
应用场景	元素高效存储+频繁访问	任意位置插入和删除频繁
缓存利用率	高	低