# Data structure - linear list - linked storage structure, static linked list (Java, C language)

## 1, Lack of sequential storage structure

Although the sequential storage structure has its advantages, it also has a great defect. Its insertion and deletion need to move a large number of elements, resulting in the problem of algorithm efficiency. At present, there are few operations on the stored data, so we can't feel it. However, when the number of operations reaches a certain degree, The deficiency of the algorithm written in sequential storage structure is reflected.

## 2, Chain storage structure

The above sequential storage structure is insufficient. Therefore, we need a chain storage structure to solve this problem
We use an example to understand the difference between chain storage structure and sequential storage structure

Example 1
Suppose there are two zoos now. In order to make it easier for tourists to see all animals and find them, zoo A places each animal on one line, and there are the previous animal and the next animal before and after each animal; B the zoo places each animal in the most suitable position and scattered around the zoo. In order to facilitate tourists, A sign will be placed in the viewing area of each animal to recommend tourists to the next place so that tourists can see all animals. Now, the zoo wants to add A new animal. Zoo A wants to put it in the middle, but there is no position. It must move the animals in the second half back to A position; Zoo B only needs to change A sign, point the sign of the previous animal to the new animal, and then point to the next animal. Will the workload be much smaller.

Therefore, we can see that A zoo is A sequential storage structure. Its storage units are continuous. Insertion and deletion operations need to move A large number of elements, while the chain storage structure does not. Its storage space is arbitrary. It only needs to add A pointer to store the next element to each element. In this way, The later storage location does not need to be changed. This greatly reduces the execution time of the algorithm, but also increases the size of data storage. Therefore, it can be said that it sacrifices space for time.

## 3, Chain storage structure code (C language)

C language provides a good tool, which is pointer. We can store the location of the next data storage through pointer. Each data + pointer is called a node, the stored data is called a data field, and the place where the pointer is stored is called a pointer field.

Here, you need to distinguish between the header pointer and the header node:

• The head pointer refers to the pointer to the first node pointed by the linked list. If the linked list has a head node, it refers to the pointer to the head node;
• The head pointer has the function of marking, so it is often preceded by the name of the linked list
• Whether the linked list is empty or not, the header pointer is not empty. The header pointer is a necessary element of the linked list

• The head node is set up for the unity and convenience of operation. If it is placed before the node of the first element, its data field is generally meaningless (it can also store the length of the linked list)
• With the head node, the operation of inserting and deleting the first node before the first element node is unified with other nodes
• The head node is not necessarily a necessary element of the linked list

Generally speaking, the head node is set up for easy operation, and it is OK not to use it.

Compared with the sequential storage structure, the linked list also has its disadvantages. For example, the query operation must start from the first node and point to the latter element until it is found. The time complexity is n. compared with the 1 of the sequential storage structure, it is indeed troublesome, but the insertion and deletion of the linked list will reflect its advantages over the sequential storage structure.
The figure above should clearly explain the insertion operation, that is, changing the position pointed by the pointer. Delete is the same operation, that is, point the pointer field of the previous node of the node to be deleted to the next node of the deleted node.
The following is the code (this code is the routine code in the big talk data structure, which I think has been written very clearly)

Looking at this code, I suggest reviewing the knowledge about structure and structure pointer first, because I've seen this code for a long time

```#include "stdio.h"
#include "string.h"
#include "ctype.h"
#include "stdlib.h"

#include "math.h"
#include "time.h"

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

#define MAXSIZE 20 / * initial allocation of storage space*/

typedef int Status;/* Status Is the type of function whose value is the result status code of the function, such as OK */
typedef int ElemType;/* ElemType The type depends on the actual situation. It is assumed to be int */

Status visit(ElemType c)
{
printf("%d ",c);
return OK;
}

typedef struct Node
{
ElemType data;
struct Node *next;
}Node;

/* Initialize linked linear list */
{
if(!(*L)) /* Storage allocation failed */
return ERROR;
(*L)->next=NULL; /* Pointer field is null */

return OK;
}

/* Initial condition: linked linear list L already exists. Operation result: if l is an empty table, it returns TRUE; otherwise, it returns FALSE */
{
if(L->next)
return FALSE;
else
return TRUE;
}

/* Initial condition: linked linear list L already exists. Operation result: reset l to empty table */
{
p=(*L)->next;           /*  p Point to the first node */
while(p)                /*  It's not at the end of the watch */
{
q=p->next;
free(p);
p=q;
}
(*L)->next=NULL;        /* The header node pointer field is null */
return OK;
}

/* Initial condition: linked linear list L already exists. Operation result: returns the number of data elements in L */
{
int i=0;
LinkList p=L->next; /* p Point to the first node */
while(p)
{
i++;
p=p->next;
}
return i;
}

/* Initial condition: linked linear table l already exists, 1 ≤ i ≤ ListLength(L) */
/* Operation result: use e to return the value of the ith data element in L */
{
int j;
LinkList p;		/* Declare a node p */
p = L->next;		/* Let p point to the first node of the linked list L */
j = 1;		/*  j For counter */
while (p && j<i)  /* p When it is not empty or the counter j is not equal to i, the loop continues */
{
p = p->next;  /* Let p point to the next node */
++j;
}
if ( !p || j>i )
return ERROR;  /*  The ith element does not exist */
*e = p->data;   /*  Take the data of the i th element */
return OK;
}

/* Operation result: returns the bit order of the first data element in L that satisfies the relationship with e. */
/* If such a data element does not exist, the return value is 0 */
{
int i=0;
while(p)
{
i++;
if(p->data==e) /* Find such a data element */
return i;
p=p->next;
}

return 0;
}

/* Initial condition: linked linear table l already exists, 1 ≤ i ≤ ListLength(L), */
/* Operation result: insert a new data element e before the ith position in L, and add 1 to the length of L */
{
int j;
p = *L;
j = 1;
while (p && j < i)     /* Find the ith node */
{
p = p->next;
++j;
}
if (!p || j > i)
return ERROR;   /* The ith element does not exist */
s = (LinkList)malloc(sizeof(Node));  /*  Generate a new node (C language standard function) */
s->data = e;
s->next = p->next;      /* Assign the successor node of p to the successor node of s  */
p->next = s;          /* Assign s to the successor of p */
return OK;
}

/* Initial condition: linked linear table l already exists, 1 ≤ i ≤ ListLength(L) */
/* Operation result: delete the ith data element of L and return its value with e. the length of L is reduced by 1 */
{
int j;
p = *L;
j = 1;
while (p->next && j < i)	/* Traverse to find the ith element */
{
p = p->next;
++j;
}
if (!(p->next) || j > i)
return ERROR;           /* The ith element does not exist */
q = p->next;
p->next = q->next;			/* Assign the successor of q to the successor of p */
*e = q->data;               /* Give the data in the q node to e */
free(q);                    /* Let the system reclaim this node to free up memory */
return OK;
}

/* Operation result: output to each data element of L in turn */
{
while(p)
{
visit(p->data);
p=p->next;
}
printf("\n");
return OK;
}

/*  Randomly generate the values of n elements and establish a single chain linear table L with header node (header interpolation) */
{
int i;
srand(time(0));                         /* Initialize random number seed */
(*L)->next = NULL;                      /*  First establish a single linked list of leading nodes */
for (i=0; i<n; i++)
{
p = (LinkList)malloc(sizeof(Node)); /*  Generate new node */
p->data = rand()%100+1;             /*  Randomly generate numbers within 100 */
p->next = (*L)->next;
(*L)->next = p;						/*  Insert into header */
}
}

/*  Randomly generate the values of n elements, and establish a single chain linear table L with header node (tail interpolation method) */
{
int i;
srand(time(0));                      /* Initialize random number seed */
*L = (LinkList)malloc(sizeof(Node)); /* L For the entire linear table */
r=*L;                                /* r Is the node pointing to the tail */
for (i=0; i<n; i++)
{
p = (Node *)malloc(sizeof(Node)); /*  Generate new node */
p->data = rand()%100+1;           /*  Randomly generate numbers within 100 */
r->next=p;                        /* Point the pointer of the end node at the end of the table to the new node */
r = p;                            /* Define the current new node as the footer terminal node */
}
r->next = NULL;                       /* Indicates the end of the current linked list */
}

int main()
{
ElemType e;
Status i;
int j,k;
i=InitList(&L);
printf("initialization L After: ListLength(L)=%d\n",ListLength(L));
for(j=1;j<=5;j++)
i=ListInsert(&L,1,j);
printf("stay L Insert the header of 1 in turn～5 After: L.data=");
ListTraverse(L);

printf("ListLength(L)=%d \n",ListLength(L));
i=ListEmpty(L);
printf("L Empty: i=%d(1:Is 0:no)\n",i);

i=ClearList(&L);
printf("empty L After: ListLength(L)=%d\n",ListLength(L));
i=ListEmpty(L);
printf("L Empty: i=%d(1:Is 0:no)\n",i);

for(j=1;j<=10;j++)
ListInsert(&L,j,j);
printf("stay L Insert 1 at the end of the table～10 After: L.data=");
ListTraverse(L);

printf("ListLength(L)=%d \n",ListLength(L));

ListInsert(&L,1,0);
printf("stay L After the header of is inserted into 0: L.data=");
ListTraverse(L);
printf("ListLength(L)=%d \n",ListLength(L));

GetElem(L,5,&e);
printf("The value of the fifth element is:%d\n",e);
for(j=3;j<=4;j++)
{
k=LocateElem(L,j);
if(k)
printf("The first%d The values of the elements are%d\n",k,j);
else
printf("No value is%d Element of\n",j);
}

k=ListLength(L); /* k Table length */
for(j=k+1;j>=k;j--)
{
i=ListDelete(&L,j,&e); /* Delete the j-th data */
if(i==ERROR)
printf("Delete paragraph%d Data failed\n",j);
else
printf("Delete paragraph%d The element values of are:%d\n",j,e);
}
printf("Sequential output L Elements:");
ListTraverse(L);

j=5;
ListDelete(&L,j,&e); /* Delete the 5th data */
printf("Delete paragraph%d The element values of are:%d\n",j,e);

printf("Sequential output L Elements:");
ListTraverse(L);

i=ClearList(&L);
printf("\n empty L After: ListLength(L)=%d\n",ListLength(L));
printf("Overall creation L Element of(Head insertion): ");
ListTraverse(L);

i=ClearList(&L);
printf("\n delete L After: ListLength(L)=%d\n",ListLength(L));
CreateListTail(&L,20);
printf("Overall creation L Element of(Tail interpolation): ");
ListTraverse(L);

return 0;
}
```

## 4, Chained storage structure of linear list (Java)

Because Java does not have the concept of pointer variable or structure, we will use class to replace the structure, and the pointer address is actually the object name. We can define a node class to store the next node.

Then the idea is: we define a Node class Node as a Node. The Node class has a data field and a pointer field. The pointer field is implemented by Node next. This pointer is actually a class. Define the linked list class, which contains the head pointer and tail pointer, as well as the operations on the linked list. It generizes the linked list and can store any object.

The following code is written by myself. There may be some shortcomings and the encapsulation is not very good. As for the operation of deletion and insertion, it is actually the same as C language. You can see the above.

```package date;

private Node rear;//Tail pointer of linked list
private int size=0;
private class Node{//Node class
E data;//Data domain
Node next;//Pointer field
public Node(){
this.data=null;
this.next=null;
}
public Node(E e){
this.data=e;
this.next=null;
}
public Node(E e,Node next){
this.data=e;
this.next=next;
}
}
public LinkedList() {//The tail pointer is null, and the head pointer points to the tail pointer to create a linked list
this.rear=null;
}
public void add(int index, E e) {
if(index<0 || index>size){
throw new IllegalArgumentException("Angle mark out of bounds");
}
Node n = new Node(e);
if(size==0){
rear = n;
}else if(index == size){   //Tail interpolation
rear.next = n;
rear = n;
}else{      //Intermediate insertion
for (int i = 0; i < index; i++) {
p = p.next;
}
n.next = p.next;
p.next = n;
}
this.size++;
}
public E remove(int index) {
if(size==0){
throw new IllegalArgumentException("Empty table");
}
if(index<0 || index>=size){
throw new IllegalArgumentException("Angle mark out of bounds");
}
E res = null;
if(size == 1){//When there is only one data
}else if(index == 0){
res = del.data;
del.next = null;
del = null;
}else if(index == size-1){
while(true){
if(p.next != rear){
p = p.next;
}else{
break;
}
}
res = p.next.data;
p.next = null;
rear = p;
}else{
for (int i = 0; i < index; i++) {
p = p.next;
}
Node del = p.next;
res = del.data;
p.next = del.next;
del.next = null;
del = null;
}
size--;
return res;
}
public E get(int index) {
if(size==0){
throw new IllegalArgumentException("Empty table");
}
if(index<0 || index>size){
throw new IllegalArgumentException("Angle mark out of bounds");
}
if(index == 0){
}else if(index == size-1){
return rear.data;
}else{
for (int i = 0; i <= index; i++) {
p = p.next;
}
return p.data;
}
}
public static void main(String[] args) {
for(int i=0;i<5;i++)
{
}
System.out.println("List length:"+s.size);
System.out.println("2nd data:"+s.get(2));
System.out.println("Delete the second data");
s.remove(2);
for(int i=0;i<s.size;i++)
{
System.out.println("output"+s.get(i));
}
}

}

```

1. Why do you need a static linked list: C language can well operate the data in memory through the pointer, and Java also realizes the function of the pointer through the object reference mechanism, but the early languages such as Basic can not realize this function, so how to realize the linked list? That is to use arrays to describe linked lists.
2. How to realize the static linked list: we know that each node needs a pointer field and data field. In C language, we also use the structure to realize the pointer field, but at this time, we do not use the structure pointer to realize it, and define an int variable as a cursor. We use the array as a linked list to store these structures, and the cursor is the subscript pointing to the position where the next structure is stored in the array. In this way, we can realize the linked list without using pointer variables.

Although the static linked list implements the linked list and solves the element movement problem of the sequential storage structure. It only needs to modify the cursor, it loses the random access characteristics of the linked storage structure because it uses an array for description. Therefore, the use of static linked list is not widely used in C language and Java, and it is not recommended.

So there is no code here. You can try. It will be easier to understand if you describe it with an array.