单链表_双向链表

单链表：

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;
}

最后编辑于：2018.10.11 14:13:17

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 216,544评论 6赞 501
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 92,430评论 3赞 392
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 162,764评论 0赞 353
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 58,193评论 1赞 292
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 67,216评论 6赞 388
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 51,182评论 1赞 299
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 40,063评论 3赞 418
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 38,917评论 0赞 274
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 45,329评论 1赞 310
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 37,543评论 2赞 332
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 39,722评论 1赞 348
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 35,425评论 5赞 343
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 41,019评论 3赞 326
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 31,671评论 0赞 22
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 32,825评论 1赞 269
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 47,729评论 2赞 368
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 44,614评论 2赞 353

单链表_双向链表

推荐阅读更多精彩内容