【Data structure】Static linked list

Hits: 0

[]Static linked list of [data structures]

static [linked list]

Linked list implemented as an array

advantage

Add and delete operations without moving a lot of elements

shortcoming

no random access

You can only search backwards from the head node

capacity is fixed

c code implementation

Get the index of the last node and get the position of the first free node

//Get the last node coordinates 
int  getLastNode (StaticList list )
 {
     for ( int i= 0 ; i< 100 ; i++)
    {
        if(list[i].next==-1)
        {
            return i;
        }
    }
}

//Get the first unused free area 
int  getLastIndex (StaticList list )
 {
     if (state)
    {
        state=false;
        size=100;
        for(int i=0; i<100; i++)
        {
            if(list[i].next==-2)
            {
                size=i;
                break;
            }
        }
    }
    return size;
}

Initialize static linked list

next=-2 is just to make a mark, indicating that the space is not occupied

//Initialize a static linked list 
void  initList (StaticList * list )
 {
    (* list )[ 0 ]=createStart();
     int i= 1 ;
     //The empty nodes are marked here, indicating that these nodes have not been used 
    for (i; i< 100 ; i++)
    {
        (*list)[i].next=-2;
    }
}

add a node at the end

//Add data at the end 
void  addLast (StaticList * list ,Node * node)
 {
     int insertIndex=getLastIndex(* list );
     if (insertIndex== 100 )
    {
        //list is full 
        return ;
    }
    else
    {
        (*list)[insertIndex]=*node;

    }
    (*list)[insertIndex]=*node;
    (*list)[insertIndex].next=-1;
    (*list)[getLastNode(*list)].next=insertIndex;
    state=true;
}

add a node after a coordinate

//Add a node after a coordinate 
void  addAfterIndex (StaticList * list , int index,Node *node)
 {
     int insertIndex=getLastIndex(* list );
     if (index< 0 ||index> 98 )
    {
        return;
    }
    if(insertIndex==100)
    {
        //list is full 
        return ;
    }
    else
    {
        (*list)[insertIndex]=*node;
    }
    (*list)[insertIndex].next=(*list)[index].next;
    (*list)[index].next=insertIndex;
    state=true;
}

[traverse]

// Traverse 
void  forEach (StaticList list ) {
    Node node=list[0];
    do{
        node=list[node.next];
        printf("%d\n",node.data);
    }while(node.next!=-1);
}

total code

# include  <stdio.h>
 # include  <stdlib.h>
 # include  <stdbool.h>
 # define MaxSize 100 
bool state= true ;
 int size;
 typedef  struct 
{ 
    int data;    //Stored data 
    int next;   //Next subscript of a node
} StaticList[MaxSize],Node;
//Create a head node 
Node createStart ()
 {
    Node start;
    start.next=-1;
    return start;
}
//Initialize a static linked list 
void  initList (StaticList * list )
 {
    (* list )[ 0 ]=createStart();
     int i= 1 ;
     //The empty nodes are marked here, indicating that these nodes have not been used 
    for (i; i< 100 ; i++)
    {
        (*list)[i].next=-2;
    }
}

//Get the last node coordinates 
int  getLastNode (StaticList list )
 {
     for ( int i= 0 ; i< 100 ; i++)
    {
        if(list[i].next==-1)
        {
            return i;
        }
    }
}

//Get the first unused free area 
int  getLastIndex (StaticList list )
 {
     if (state)
    {
        state=false;
        size=100;
        for(int i=0; i<100; i++)
        {
            if(list[i].next==-2)
            {
                size=i;
                break;
            }
        }
    }
    return size;
}

//Add data at the end 
void  addLast (StaticList * list ,Node * node)
 {
     int insertIndex=getLastIndex(* list );
     if (insertIndex== 100 )
    {
        //list is full 
        return ;
    }
    else
    {
        (*list)[insertIndex]=*node;

    }
    (*list)[insertIndex]=*node;
    (*list)[insertIndex].next=-1;
    (*list)[getLastNode(*list)].next=insertIndex;
    state=true;
}

// Traverse 
void  forEach (StaticList list ) {
    Node node=list[0];
    do{
        node=list[node.next];
        printf("%d\n",node.data);
    }while(node.next!=-1);
}

//Add a node after a coordinate 
void  addAfterIndex (StaticList * list , int index,Node *node)
 {
     int insertIndex=getLastIndex(* list );
     if (index< 0 ||index> 98 )
    {
        return;
    }
    if(insertIndex==100)
    {
        //list is full 
        return ;
    }
    else
    {
        (*list)[insertIndex]=*node;
    }
    (*list)[insertIndex].next=(*list)[index].next;
    (*list)[index].next=insertIndex;
    state=true;
}

void  main ()
 {

    //At this point a StaticList is a static list 
    StaticList list ;
    initList(&list);
    Node a;
    a.data=1;
    addLast(&list,&a);
    a.data=2;
    addLast(&list,&a);
    a.data=3;
    addAfterIndex(&list,1,&a);
    forEach(list);

}

You may also like...

Leave a Reply

Your email address will not be published.