双向链表C++实现

双向链表实现，通过C++实现

#ifndef LinkList_hpp

#define LinkList_hpp

typedef struct Node{

    int data;

    Node* next;

    Node* pre;

}Node;

class LinkList{

private:

    Node *head;

    Node *tail;

    int length;

public:

    LinkList();

    //分配内存，构建节点

    Node* makeNode();

    //添加节点到链表尾

    bool push(int data);

    //弹出链表最后一个节点，并返回值

    int pop();

    //通过index来查找链表中的元素

    int objectAt(int index);

    //插入元素到指定位置的前方

    bool insert(int index,int data);

    //打印链表的所有元素

    void display();

};

#endif /* LinkList_hpp */

#include "LinkList.hpp"

#include <iostream>

#include <mm_malloc.h>

using namespace std;

LinkList::LinkList(){

    head = makeNode();

    tail = head;

    length = 0;

}

Node * LinkList::makeNode(){

    Node* node = (Node*)malloc(sizeof(Node));

    return node;

}

bool LinkList::push(int data){

    Node *node = makeNode();

    if(!node){

        return false;

    }

    node->data = data;

    node->pre = tail;

    tail->next = node;

    tail = node;

    length ++;

    return true;

}

int LinkList::pop(){

    int data = 0;

    Node* node = head->next;

    while (node->next) {

        node = node->next;

    }

    data = node->data;

    tail = node->pre;

    tail->next = node->next;

    length--;

    free(node);

    node = NULL;

    return data;

}

int LinkList::objectAt(int index){

    if(index<1 || index > length){

        return 0;

    }

    int data = 0;

    Node* q = head;

    for(int i=0; i < index;i++){

        q = q->next;

    }

    data = q->data;

    return data;

}

bool LinkList::insert(int index, int data){

    if(index<1 || index> length){

        return false;

    }

    Node *p = makeNode();

    p->data = data;

    Node *q = head;

    for(int i=0; i < index; i++){

        q = q->next;

    }

    p->pre = q->pre;

    p->next = q;

    q->pre->next = p;

    q->pre = p;

    length ++;

    return true;

}

void LinkList::display(){

    Node *n = head->next;

    cout<<"data:";

    while (n) {

        cout<<n->data<<" ";

        n = n->next;

    }

    cout << endl;

}

巴特西

双向链表C++实现

最新文章

热门文章