链表的C++实现

  有的时候,处于内存中的数据并不是连续的。那么这时候,我们就需要在数据结构中添加一个属性,这个属性会记录下面一个数据的地址。有了这个地址之后,所有的数据就像一条链子一样串起来了,那么这个地址属性就起到了穿线连结的作用。

链表有:单链表,双链表,单循环链表,双循环链表。

理解单链表,其他几种也就大同小异。

    相比较普通的线性结构,链表结构的优势是什么呢?我们可以总结一下:
    (1)单个节点创建非常方便,普通的线性内存通常在创建的时候就需要设定数据的大小
    (2)节点的删除非常方便,不需要像线性结构那样移动剩下的数据
    (3)节点的访问方便,可以通过循环或者递归的方法访问到任意数据,但是平均的访问效率低于线性表

    那么在实际应用中,链表是怎么设计的呢?我们可以以int数据类型作为基础,设计一个简单的int链表:

#include <iostream>
#include <cstdlib>

 using namespace std;

struct list_node{
    int data;
    list_node *next;

};

class list{
public:
    list():head(NULL){};
    ~list();
    void print();
    void insert(int value);
/*you had better insert from the front list,that costs O(1),
*here i just insert into the taile, costing O(n)
*/
    void insert_back(int pos, int value);//inisert a node with value equals to value after the node with value equals to pos
    void delete_back(int pos);//delete the node after the node with value equals to pos
protected:
    list_node* find(int pos); //find the node with the value equals to pos

private:
    list_node* head; //point to the first node

};


list::~list()
{

}

list_node* list::find(int pos)
{
    if(NULL==head)
        return NULL;
    list_node* tmp=head;
    while((NULL!=tmp)&&(tmp->data!=pos))
        tmp=tmp->next;
    return tmp;

}

void list::insert(int value)
{
    if(head==NULL)
    {
        head = new list_node();
        head->data=value;
        head->next=NULL;

    }
    else
    {
        list_node *tmp= head;
        while(tmp->next!=NULL)
            tmp=tmp->next;
        list_node *node = new list_node();
        node->data=value;
        node->next=NULL;
        tmp->next=node;
    }
}

void list::insert_back(int pos, int value)
{
    list_node *tmp = find(pos);
    if(NULL==tmp)
        return;
    else
    {
        list_node *node = new list_node();
        node->data=value;
        node->next=tmp->next;
        tmp->next=node;
    }

}

void list::delete_back(int pos)
{
    list_node *tmp = find(pos);
    if(NULL==tmp)
    {
        cout<<"the value of pos isnot exist"<<endl;
        return;
    }
    else
    {
        if(tmp->next==NULL)
        {
            cout<<"pos is the last node"<<endl;
            return;
        }
        else
        {
            tmp->next=tmp->next->next;
        }
    }
}

void list::print()
{
    list_node *tmp = head;
    while(tmp!=NULL)
    {
        cout<<tmp->data<<" ";
        tmp=tmp->next;
    }
    cout<<endl;
}

int main()
{
    list myList;
    for(int i=1;i<10;++i)
    {
        myList.insert(i);
    }
    myList.print();
    myList.insert(11);
    myList.print();
    myList.insert_back(5, 555);
    myList.print();
    myList.delete_back(6);
    myList.print();
}

运行结果:

链表的C++实现

链表的C++实现,布布扣,bubuko.com

链表的C++实现

上一篇:robot framework接口测试之一-完整的测试用例


下一篇:attention - 5 - GCNet: Non-local Networks Meet Squeeze-Excitation Networks and Beyond - 1 - 论文学习