美文网首页
单链表_双向链表

单链表_双向链表

作者: MagicalGuy | 来源:发表于2018-10-07 14:28 被阅读0次

单链表：

template<class T>
class OLinkList {
public:
    typedef struct _LIST_NODE {
        T nData;
        _LIST_NODE* pListNext;
    }LIST_NODE;
    OLinkList();
    ~OLinkList();
    void push_fornt(T nEle);//头部插入元素
    void push_back(T nEle);//尾部插入元素
    void pop_front();//头部删除元素
    void pop_back();//尾部删除元素
    void insert(int pos, T nEle);//在pos位置插入元素nEle
    void erase(int pos, T* pEle=0);//删除pos位置的元素
    void remove(T nEle);//删除元素nEle
    void setData(int pos, T nEle);//将pos位置的元素改为nEle
    int find(T nEle);//查找元素nEle
    bool empty();//判断是不是为空链表
    bool clear();//清空链表
    int size();//返回当前元素个数
    void print();//遍历打印链表元素
private:
    LIST_NODE* pHeader;//头指针
    int nCount;   //当前个数
};


template<class T>
OLinkList<T>::OLinkList():pHeader(NULL),nCount(0) {}
template<class T>
OLinkList<T>::~OLinkList() { clear(); }
//头部插入元素
template<class T>
void OLinkList<T>::push_fornt(T nEle) {
    //如果为空
    if(empty()){
        pHeader = new LIST_NODE{};
        pHeader->nData = nEle;
        nCount++;
        return;
    }
    LIST_NODE* pTemp = new LIST_NODE{};
    pTemp->nData = nEle;
    pTemp->pListNext = pHeader;
    pHeader = pTemp;
    nCount++;
}
//尾部插入元素
template<class T>
void OLinkList<T>::push_back(T nEle) {
    if (empty()) { push_fornt(nEle); return; }
    LIST_NODE* pTemp = pHeader;
    while (pTemp->pListNext) {
        pTemp = pTemp->pListNext;
    }
    LIST_NODE* pNew = new LIST_NODE{};
    pNew->nData = nEle;
    pTemp->pListNext = pNew;
    nCount++;
}
//头部删除元素
template<class T>
void OLinkList<T>::pop_front() {
    //链表为空
    if (empty()) { 
        printf("删除失败\n");
        return; 
    }
    //链表只有一个元素
    if (nCount==1) {
        delete pHeader;
        pHeader = nullptr;
        nCount--;
        return;
    }
    //先保存第二个元素
    LIST_NODE* pTemp = pHeader->pListNext;
    delete pHeader;
    pHeader = pTemp;
    nCount--;
}
//尾部删除元素
template<class T>
void OLinkList<T>::pop_back() {
    //如果链表为空
    if (empty()) {
        printf("删除失败\n");
        return;
    }
    //如果只有一个元素
    if (nCount==1) {
        delete pHeader;
        pHeader = nullptr;
        nCount--;
        return;
    }
    LIST_NODE* pTemp = pHeader;
    //找到倒数第二个节点
    for (int i = 0; i < nCount-2;i++) {
        pTemp = pTemp->pListNext;
    }
    delete pTemp->pListNext;
    pTemp->pListNext = nullptr;
    nCount--;
}
//在pos位置插入元素nEle
template<class T>
void OLinkList<T>::insert(int pos, T nEle) {
    //插入位置非法
    if (pos<0||pos>nCount) {
        printf("插入位置错误");
        return;
    }
    //空链表
    if (empty()) {
        push_fornt(nEle);
    }
    //头部插入
    if (pos == 0) { push_fornt(nEle); }
    //先找到前一个元素节点
    LIST_NODE* pTemp = pHeader;
    for (int i = 0; i < pos - 1;i++) {
        pTemp = pTemp->pListNext;
    }
    LIST_NODE* pNew = new LIST_NODE{};
    pNew->nData = nEle;
    pNew->pListNext = pTemp->pListNext;
    pTemp->pListNext = pNew;
    nCount++;
}
//删除pos位置的元素
template<class T>
void OLinkList<T>::erase(int pos, T* pEle) {
    //删除位置非法
    if (pos<0||pos>=nCount) {
        printf("删除位置错误");
        return;
    }
    //链表为空
    if (empty()) {
        printf("链表为空删除错误");
        return;
    }
    //头部删除
    if(pos==0){
        pop_front();
    }
    //其他情况
    //先找到删除位置的前一个链表节点
    LIST_NODE* pTemp = pHeader;
    for (int i = 0; i < pos - 1;i++) {
        pTemp = pTemp->pListNext;
    }
    if (pEle) {
        *pEle = pTemp->pListNext->nData;
    }
    LIST_NODE* pTemp2 = pTemp->pListNext->pListNext;
    delete pTemp->pListNext;
    pTemp->pListNext = pTemp2;
    nCount--;
}
//删除元素nEle
template<class T>
void OLinkList<T>::remove(T nEle) {
    //链表为空
    if (empty()) {
        printf("链表为空删除失败");
        return;
    }
    //找到
    if (find(nEle)) {
        erase(find(nEle));
    }
}
//将pos位置的元素改为nEle
template<class T>
void OLinkList<T>::setData(int pos, T nEle) {
    if (pos < 0||pos>=nCount) {
        printf("修改位置错误");
        return;
    }
    if (empty()) {
        printf("链表为空修改失败");
        return;
    }
    LIST_NODE* pTemp = pHeader;
    for (int i = 0; i < pos;i++) {
        pTemp = pTemp->pListNext;
    }
    pTemp->nData = nEle;
}
//查找元素nEle
template<class T>
int OLinkList<T>::find(T nEle) {
    if (empty()) {
        printf("链表为空查找元素失败");
        return -1;
    }
    LIST_NODE* pTemp = pHeader;
    for (int i = 0; i < nCount;i++) {
        
        if (pTemp->nData==nEle) {
            return i;
        }
        pTemp = pTemp->pListNext;
    }
    return -1;
}
//判断是不是为空链表
template<class T>
bool OLinkList<T>::empty() {
    if (nCount==0||pHeader==nullptr) {
        return true;
    }
    return false;
}
//清空链表
template<class T>
bool OLinkList<T>::clear() {
    if (empty()) {
        return false;
    }
    LIST_NODE* pTemp = pHeader;
    
    while (pTemp->pListNext) {
        pHeader = pTemp->pListNext;
        delete pTemp;
        pTemp = pHeader;
    }
    //删除最后一个节点
    //delete pTemp;
    delete pHeader;
    pTemp = nullptr;
    nCount = 0;
    return true;
}
//返回当前元素个数
template<class T>
int OLinkList<T>::size() {
    return nCount;
}
//遍历打印链表元素
template<class T>
void OLinkList<T>::print() {
    if(empty()){
        printf("链表为空不用清空！");
        return;
    }
    LIST_NODE* pTemp = pHeader;
    
    while (pTemp->pListNext) {
        cout << pTemp->nData << " ";
        pTemp = pTemp->pListNext;
    }
    cout << pTemp->nData;
    cout << endl;
}
int main() {
    OLinkList<int> linkList;
    linkList.push_back(1);
    linkList.push_back(2);
    linkList.push_back(3);
    linkList.print();
    linkList.push_fornt(4);
    linkList.print();
    linkList.insert(2,5);
    linkList.print();
    int data;
    linkList.erase(1,&data);
    linkList.print();
    linkList.push_back(6);
    linkList.push_back(7);
    linkList.push_back(8);
    linkList.print();
    linkList.pop_back();
    linkList.print();
    linkList.pop_front();
    linkList.print();
    linkList.setData(2,9);
    linkList.print();
    printf("%d\n", linkList.size());
    linkList.clear();
    printf("%d\n", linkList.size());
    system("pause");
    return 0;
}

双向链表：

class DouLinkList {
public:
    typedef struct _LIST_NODE {
        int nData;
        _LIST_NODE* pListNext;
        _LIST_NODE* pListPrior;
    }LIST_NODE;
    DouLinkList();
    ~DouLinkList();
    void push_fornt(int nEle);//头部插入元素
    void push_back(int nEle);//尾部插入元素
    void pop_front();//头部删除元素
    void pop_back();//尾部删除元素
    void insert(int pos, int nEle);//在pos位置插入元素nEle
    void erase(int pos, int* pEle = 0);//删除pos位置的元素
    void remove(int nEle);//删除元素nEle
    void setData(int pos, int nEle);//将pos位置的元素改为nEle
    int find(int nEle);//查找元素nEle
    bool empty();//判断是不是为空链表
    bool clear();//清空链表
    int size();//返回当前元素个数
    void print();//遍历打印链表元素
private:
    LIST_NODE* pHeader;//头指针
    LIST_NODE* pTail;//尾指针
    int nCount;   //当前个数
};


DouLinkList::DouLinkList() :pHeader(NULL), nCount(0) {}
DouLinkList::~DouLinkList() { clear(); }
//头部插入元素
void DouLinkList::push_fornt(int nEle) {
    //如果为空
    if (empty()) {
        pHeader = new LIST_NODE{};
        pHeader->nData = nEle;
        //头尾相同
        pTail = pHeader;
        nCount++;
        return;
    }
    LIST_NODE* pTemp = new LIST_NODE{};
    pTemp->nData = nEle;
    pTemp->pListNext = pHeader;
    //添加前驱指针
    pHeader->pListPrior = pTemp;
    pHeader = pTemp;
    nCount++;
}
//尾部插入元素
void DouLinkList::push_back(int nEle) {
    if (empty()) { push_fornt(nEle); return; }
    LIST_NODE* pTemp = pHeader;
    while (pTemp->pListNext) {
        pTemp = pTemp->pListNext;
    }
    LIST_NODE* pNew = new LIST_NODE{};
    pNew->nData = nEle;
    //添加新节点的前驱
    pNew->pListPrior = pTemp;
    //添加尾节点
    pTail = pNew;
    pTemp->pListNext = pNew;
    nCount++;
}
//头部删除元素
void DouLinkList::pop_front() {
    //链表为空
    if (empty()) {
        printf("删除失败\n");
        return;
    }
    //链表只有一个元素
    if (nCount == 1) {
        delete pHeader;
        pHeader = nullptr;
        delete pTail;
        pTail = nullptr;
        nCount--;
        return;
    }
    //先保存第二个元素
    LIST_NODE* pTemp = pHeader->pListNext;
    delete pHeader;
    pHeader = pTemp;
    pHeader->pListPrior = nullptr;
    nCount--;
}
//尾部删除元素
void DouLinkList::pop_back() {
    //如果链表为空
    if (empty()) {
        printf("删除失败\n");
        return;
    }
    //如果只有一个元素
    if (nCount == 1) {
        delete pHeader;
        pHeader = nullptr;
        nCount--;
        if (empty()) { pTail = nullptr; }
        return;
    }
    LIST_NODE* pTemp = pHeader;
    //找到倒数第二个节点
    for (int i = 0; i < nCount - 2; i++) {
        pTemp = pTemp->pListNext;
    }
    delete pTemp->pListNext;
    pTemp->pListNext = nullptr;
    //尾部指针
    pTail = pTemp;
    nCount--;
    if (empty()) { pTail = nullptr; }
}
//在pos位置插入元素nEle
void DouLinkList::insert(int pos, int nEle) {
    //插入位置非法
    if (pos<0 || pos>nCount) {
        printf("插入位置错误");
        return;
    }
    //空链表
    if (empty()) {
        push_fornt(nEle);
    }
    //头部插入
    if (pos == 0) { push_fornt(nEle); }
    //先找到前一个元素节点
    LIST_NODE* pTemp = pHeader;
    for (int i = 0; i < pos - 1; i++) {
        pTemp = pTemp->pListNext;
    }
    //新节点
    LIST_NODE* pNew = new LIST_NODE{};
    pNew->nData = nEle;
    //新节点的前驱
    pNew->pListPrior = pTemp;
    //新节点的后继 =  前一个节点的下一个
    pNew->pListNext = pTemp->pListNext;
    //前一节点的后一个的前驱
    pTemp->pListNext->pListPrior = pNew;
    //前一个节点的下一个 = 新的
    pTemp->pListNext = pNew;
    nCount++;
}
//删除pos位置的元素
void DouLinkList::erase(int pos, int* pEle) {
    //删除位置非法
    if (pos < 0 || pos >= nCount) {
        printf("删除位置错误");
        return;
    }
    //链表为空
    if (empty()) {
        printf("链表为空删除错误");
        return;
    }
    //头部删除
    if (pos == 0) {
        pop_front();
    }
    //其他情况
    //先找到删除位置的前一个链表节点
    LIST_NODE* pTemp = pHeader;
    for (int i = 0; i < pos - 1; i++) {
        pTemp = pTemp->pListNext;
    }
    if (pEle) {
        *pEle = pTemp->pListNext->nData;
    }
    LIST_NODE* pTemp2 = pTemp->pListNext->pListNext;
    delete pTemp->pListNext;
    //前驱
    pTemp2->pListPrior = pTemp;
    //前一个的后继
    pTemp->pListNext = pTemp2;
    nCount--;
}
//删除元素nEle
void DouLinkList::remove(int nEle) {
    //链表为空
    if (empty()) {
        printf("链表为空删除失败");
        return;
    }
    //找到
    if (find(nEle)) {
        erase(find(nEle));
    }
}
//将pos位置的元素改为nEle
void DouLinkList::setData(int pos, int nEle) {
    if (pos < 0 || pos >= nCount) {
        printf("修改位置错误");
        return;
    }
    if (empty()) {
        printf("链表为空修改失败");
        return;
    }
    LIST_NODE* pTemp = pHeader;
    for (int i = 0; i < pos; i++) {
        pTemp = pTemp->pListNext;
    }
    pTemp->nData = nEle;
}
//查找元素nEle
int DouLinkList::find(int nEle) {
    if (empty()) {
        printf("链表为空查找元素失败");
        return -1;
    }
    LIST_NODE* pTemp = pHeader;
    for (int i = 0; i < nCount; i++) {
        if (pTemp->nData == nEle) {
            return i;
        }
        pTemp = pTemp->pListNext;
    }
    return -1;
}
//判断是不是为空链表
bool DouLinkList::empty() {
    if (nCount == 0 || pHeader == nullptr) {
        return true;
    }
    return false;
}
//清空链表
bool DouLinkList::clear() {
    if (empty()) {
        return false;
    }
    LIST_NODE* pTemp = pHeader;
    while (pTemp->pListNext) {
        pHeader = pTemp->pListNext;
        delete pTemp;
        pTemp = pHeader;
    }
    //删除最后一个节点
    delete pTemp;
    //delete pHeader;
    pTemp = nullptr;
    //尾指针
    pTail = nullptr;
    nCount = 0;
    return true;
}
//返回当前元素个数
int DouLinkList::size() {
    return nCount;
}
//遍历打印链表元素
void DouLinkList::print() {
    if (empty()) {
        printf("链表为空不用清空！");
        return;
    }
    LIST_NODE* pTemp = pHeader;
    while (pTemp->pListNext) {
        cout << pTemp->nData << " ";
        pTemp = pTemp->pListNext;
    }
    cout << pTemp->nData;
    cout << endl;
}
int main() {
        DouLinkList linkList;
        linkList.push_back(1);
        linkList.push_back(2);
        linkList.push_back(3);
        linkList.print();
        linkList.push_fornt(4);
        linkList.print();
        linkList.insert(2, 5);
        linkList.print();
        int data;
        linkList.erase(1, &data);
        linkList.print();
        linkList.push_back(6);
        linkList.push_back(7);
        linkList.push_back(8);
        linkList.print();
        linkList.pop_back();
        linkList.print();
        linkList.pop_front();
        linkList.print();
        linkList.setData(2, 9);
        linkList.print();
        printf("%d\n", linkList.size());
        linkList.clear();
        printf("%d\n", linkList.size());
    system("pause");
    return 0;
}

相关文章

  • 双向链表&双向循环链表

    链表分为：单链表、单向循环链表、双向链表、双向循环链表本节主要说明：双向链表、双向循环链表 定义结点 一、双向链表...

  • 线性表--链式存储结构--双向链表

    双向链表 一、双向链表结构 双向链表结点结构 既然单链表可以有循环链表，那么双向链表当然也可以有。 由于这是双向链...

  • 双向链表

    双向链表的结构 既然单链表有循环链表，双向链表当然也有双向循环链表，如下图： 问： 双向链表中某个节点p的后继节点...

  • 五、双向链表

    双向链表 此前介绍的链表，也叫做单向链表使用双向链表可以提升链表的综合性能 修改之前的单链表的源码： 双向链表 –...

  • 6.双向链表

    双向链表结构： 既然单链表可以有循环链表，那么双向链表当然也可以有: 双向链表的插入操作： s->next = p...

  • 数据结构与算法之数组与链表

    线性表包括数组，链表（单链表，双向链表，循环链表，双向循环链表，静态链表），栈（顺序栈，链式栈），队列（普通队列，...

  • 链表

    链表 缺点：查找复杂有点：定点删除／插入元素 单链表 双向链表 循环链表 双向循环链表 数组与链表的区别 数据存储...

  • 数据结构与算法之栈与队列

    线性表包括数组，链表（单链表，双向链表，循环链表，双向循环链表，静态链表），栈（顺序栈，链式栈），队列（普通队列，...

  • Java 双向链表的增删改查

    双向链表 简介 双向链表是基于单链表的基础上，每个节点中添加了一个指向上一个节点的指针。相对单链表而言，双向链表中...

  • 数据结构与算法学习-双向链表

    双向链表 在上一篇单链表中已经提到了双向链表，其实单链表实现时候，双向链表相对容易多了，只不过对每个节点多了一个前...

网友评论

      本文标题：单链表_双向链表

      本文链接：https://www.haomeiwen.com/subject/vuukaftx.html

      延伸阅读

      深度阅读

      • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

      栏目导航

      热点阅读

      关于我们|服务条款|联系我们|单链表_双向链表|投稿指南|网站地图|RSS订阅|排版工具|手机版

      提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

      Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

      备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

      本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

      所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！