I Static linked list

1. What is a static linked list
a. Static linked list: allocate a whole piece of continuous memory space and place each node centrally. (similar to array)
b. The difference between a static linked list and a single linked list is that the static linked list does not store the address pointing to the next node, but the array subscript (cursor). Because the linked list data elements are stored in a whole continuous space, they can be accessed through the array subscript.
When the node is the last node in the linked list, the cursor value is set to - 1, which means that there are no other nodes behind.

II Insertion and deletion of linked list

1. Insertion of static linked list:
Premise:
In the dynamic linked list, the application and release of nodes are implemented by malloc() and free() functions of C language respectively;
In the static linked list:
The operation is an array. There is no problem of node application and release like a dynamic linked list, so we need to implement these two functions to insert and delete.

a. First, obtain the subscript with free:

Insert the code slice here:
int getCur(StaticLinkList tan)
{
	int i = tan[0].cur;
	if(tan[0].cur)
	{
   tan[0].cur = tan[i].cur;
    } 
	return i;
}

Before insertion: (find free subscript first)

After insertion: (assign the found free subscript, and then modify the cursor of the subscript to be inserted into the value to be inserted)

b. Insertion of static linked list:

Insert the code slice here:
int ListInsert(StaticLinkList tan,int i,ElemType e)//Insert new data before the ith element in the static linked list e
{
	int l,j,k;
 
	k = MAXSIZE -1;//The index of the last element of the array
	if(i < 1|| i > ListLength(L)+ 1)//ListLength is a function to calculate the length of the linked list
		return error;
 
	j = getCur(tan);
 
	if(j)
	{
		tan[j].data = e;
		for(l = 1;l <= i - 1;l++)
		{
			k = tan[k].cur;
		}
 
		tan[j].cur = tan[k].cur;
		tan[k].cur = j;
 
		return bingo;
	}
 
	return  error;
}

2. Delete static linked list:
Before deleting changes:
After deleting the change: (although the data is still there, the program has set it to - ignore)

c. Deletion of static linked list:

Insert the code slice here:
void recycleNode(StaticLinkList tan,int i)//Reclaim the idle node with subscript k to the standby linked list
{
	tan[i].cur = tan[0].cur ;
	tan[0].cur  = i;
}
int ListDelete(StaticLinkList tan,int i)//Delete the ith data element in the linked list
{
	int j,k;
	if(i < 1 || i > ListLength(L))return error;
 
	k = MAXSIZE - 1;
 
	for(j = 1;j <= i -1;j++)
	{
		k = tan[k].cur;//Gets the subscript of the element before the deleted element
 
	}
	j = tan[k].cur;//The subscript of the element to be deleted
	tan[k].cur = tan[j].cur;
 
	recycleNode(tan,j);
 
	return bingo;
}

Summarize the advantages and disadvantages of static linked list:

Advantages: during the insertion and deletion operations, only the cursor needs to be modified without moving elements, which improves the disadvantage that the insertion and deletion operations in the sequential storage structure require a large number of moving elements.

Disadvantages: 1) it loses the characteristics of random access of sequential storage structure. 2) The problem that it is difficult to determine the table length caused by continuous storage allocation (array) is not solved.

III Circular linked list

Circular Linked List: a linked list connected head to tail. Its feature is that the pointer field of the last node points to the head node of the linked list, and the whole linked list is linked into a ring through the pointer field.
Since there is no NULL pointer in the single loop linked list, when traversing the linked list, the loop termination condition is not to judge whether the pointer is empty like the single link list, but whether it is equal to a specific pointer, because the basic operation of the single loop linked list is the same or similar to the previous single link list

IV Bidirectional linked list

If you start from any node to access all nodes in the linked list, it is very appropriate to use the circular linked list. However, if you need to frequently access the direct precursor of a node, it can also be realized by using the storage of a single linked list, but finding the precursor node needs to be traversed by the linked list, which is inefficient. At this time, we use the two-way linked list.
Bidirectional linked list: refers to the two pointer fields set up in each node of the linked list: one pointing to the precursor and one pointing to the successor; This forms two chains in different directions.

Here is a two-way circular linked list:
//The basic program is similar to the previous program
#include<stdio.h>
#include<stdlib.h>

#define OK 1
#define ERROR 0;

typedef char ElemType;
typedef int Status;
typedef struct DualNode
{
    ElemType data;
    struct DualNode* prior;
    struct DualNode* next;
}DualNode, * DuLinkList;

Status InitList(DuLinkList* L)
{
    DualNode* p, * q;
    int i;

    *L = (DuLinkList)malloc(sizeof(DualNode));

    if (!(*L))
    {
        return ERROR;
    }

    (*L)->next = (*L)->prior = NULL;
    p = (*L);

    for (i = 0; i < 26; i++)
    {
        q = (DualNode*)malloc(sizeof(DualNode));
        if (!q)
        {
            return ERROR;
        }

        q->data = 'A' + i;
        q->prior = p;
        q->next = p->next;
        p->next = q;
        p = q;
    }

    p->next = (*L)->next;
    (*L)->next->prior = p;

    return OK;
}

void caser(DuLinkList* L, int i)
{
    if (i > 0)
    {
        do
        {
            (*L) = (*L)->next;
        } while (--i);

    }
    if (i < 0)
    {
        i = i - 1;
        (*L) = (*L)->next;

        do
        {
            (*L) = (*L)->prior;
        } while (++i);
    }

}

int main()
{
    DuLinkList L;
    int i, n;

    InitList(&L);
    printf("Please enter an integer:\n");
    scanf_s("%d", &n);
    printf("\n");

    caser(&L, n);

    for (i = 0; i < 26; i++)
    {
        L = L->next;
        printf("%c", L->data);
    }

    printf("\n");

    return 0;
}