基础数据结构 -链表

链表描述:

内存中内部的存储方式,通常情况下可以认为是多个节点存储一串的的结构

  链表存储结构

            数据域 Data field

            指针域 pointer field   

强调: 指针域 一般指向下一个节点的地址 , 或者也可以认为是下一个节点的的引用(引用可以指向任意的对象)

指针域实现→ c 内存中的地址 ,地址唯一标记节点的位置

                    存的是数组下标 →  存储的是相对的地址的概念 

                    下一个节点,也有存储引用

完结: 只要相关结构中增加了一项指针域,结构就可以串成链表的结构

链表特点:

 至少必须包含两个部分: 数据和指针域

 链表的每个节点,通过指针域的值,形成了一个线性结构

 ps 由于是通过指针区串联成的一串,所以只允许从前向后依次访问节点. 不允许用下标.

  (访问速度)也就成了o(n ) 

 —也正是链表是一种松散的结构,由于指针域存储的是下一个引用,也就是说我只要改变了指针的指向. 就可以完成动态的插入或修改(我可以吧插入地址,修改成修改前的下一个内存地址)

 插入和修改删除都是o(1)的

 并不适合快速查找.

链表的实现

指针版

  struct linkListNode{
       linkListNode(int data):data(data),next(NULL){};
       int data;
       linkListNode *next;
    };
    
    void  impleLinkList_bystruct(){
       void  Data_struct::impleLinkList_bystruct(){
       linkListNode *head=NULL;
       head=new linkListNode(1);
       head->next =new linkListNode(2);
       head->next->next = linkListNode(3);
       head->next->next->next =new  linkListNode(4);

       LinkListNode  *p=head;
       while (p!=NULL) {
           cout << p->next << e
        }
       cout << endl;
     }

数组下标实现链表

//add 函数的作用地址index 节点后 添加一个地址为p的节点,并在让p节点中存储val

int next[10];
    int data[10];
    void  LinkListadd(int ind ,int p,int val){
       next[ind]=p;
       data[p]=val;
       return ;
   }
    
    void  impleLinkList_byarr(){
         int  head =3 ;
          data[3]=0;
        //头节点是3
        //3节点后添加5节点,存的是1
        LinkListadd(3,5,1);
        //五节点添加2节点,存的是2
        LinkListadd(5,2,2);
        //2节点添加的是7节点 ,存的是3
        LinkListadd(2,7,3);
        // 第二个是下一个节点 ,最后一个是值
        LinkListadd(7,9,100);
        //构造了链表
        
        int p =head;
        while(p=!0){
            cout << "->" <<data[p] << endl;
            p =next[p];
        }
        return 0;
     }