# Data structure - linear list / linked list

• The same problem can have different representation (storage) methods
• There is a common problem: the organization and management of ordered linear sequences

#### 1. what is a linear table?

Linear List: a linear structure consisting of ordered sequences of data elements of the same type

• The number of elements in a table is called the length of a linear table
• When a linear table has no elements, it is called an empty table
• The starting position of a table is called the header, and the ending position of a table is called the footer

#### 2. abstract data type description of linear table

• Type name: linear table (List)
• Data object set: a linear table is an ordered sequence of n (≥ 0) elements (a1, a2,..., an)
• Operation set: linear table L ∈ List, integer i represents position, element X ∈ ElementType
1. List MakeEmpty(): initializes an empty linear table L
2. ElementType FindKth(int K,List L): returns the corresponding element according to the bit order K
3. int Find(ElementType X,List L): find the first occurrence position of X in the linear table L
4. void Insert(ElementType X,int i,List L): inserts a new element X before bit sequence I
5. void Delete(int i,List L): deletes the elements of the location order I
6. int Length(List L): returns the length n of the linear table L
##### 2.1 implementation of sequential storage of linear tables

Use the continuous storage space of the array to store the elements of the linear table in sequence

```typedef struct LNode *List;

struct LNode
{
ElementType Data[MAXSIZE];
int Last;
};

struct LNode L;
List PtrL;
```

Accessing elements with subscript I: L.Data[i] or ptrl->data[i]
Length of linear table: L.Last+1 or ptrl->last+1

###### Implementation of main operations

1. initialization (create an empty sequence table)

```List MakeEmpty()
{
List PtrL;
PtrL = (List)malloc(sizeof(struct LNode));
PtrL->Last = -1;
return PtrL;
}
```

2. find

```int Find(ElementType X,List PtrL)
{
int i=0;
while(i<=PtrL->Last && PtrL->Data[i]!=X)
i++;
if(i > PtrL->Last) return -1; /*If not, return -1*/
else return i; /*The storage location is returned after finding*/
}
```

The average number of successful comparisons is (n+1)/2, and the average time performance is O(n)

3. insert (insert a new element with a value of X at the ith position)

```void Insert(ElementType X,int i,List PtrL)
{
int j;
if(PtrL->Last == MAXSIZE -1) /*The tablespace is full and cannot be inserted*/
{
printf("Table full");
return;
}

if(i<1 || i>PtrL->Last+2)	/*Check the legitimacy of the insertion position*/
{
printf("Illegal location");
return;
}

for(j=PtrL->Last;j>=i-1;j--)
PtrL->Data[j+1] = PtrL->Data[j]; /*Move ai~an backward in reverse order*/
PtrL->Data[i-1] = X;	/*New element insert*/
PtrL->Last++;			/*Last Still point to last element*/
return;
}
```

The average number of moves is n/2, and the average time performance is O(n)

4. delete (delete the element at position i of the table)

```void Delete(int i,List PtrL)
{
int j;
if(i<1 || i>PtrL->List+1)
{
printf("No no%d Elements",&i);
return;
}
for(j=i;j<=PtrL->Last;j++)
PtrL->Data[j-1] = PtrL->Data[j]; /*Move ai+1~an forward*/
PtrL->Last--;						 /*Last Still point to last element*/
return;
}
```
##### 2.2 chain storage implementation of linear table

Two logically adjacent elements are not required to be physically adjacent; The logical relationship between data elements is established through "chain". You do not need to move data elements to insert or delete, but only need to modify the "chain".

```typedef struct LNode *List;

struct LNode
{
ElementType Data;
List Next;
};

struct LNode L;
List PtrL;
```
###### Implementation of main operations

1. calculate meter length

```int Length(List PtrL)
{
List p = PtrL; /* p Point to the first node of the table */
int j=0;
while(p)
{
p = p->Next;
j++;			/*The current p points to the j-th node*/
}
return j;
}
```

Time performance is O(n)

2. find
(1) Find by sequence number: FindKth

```List FindKth(int K,List PtrL)
{
List p = PtrL;
int i=1;
while(p!=NULL && i<K)
{
p = p->Next;
i++;
}
if(i==K) return p; /*Find the kth and return the pointer*/
else return NULL; /*Otherwise, return null*/
}
```

(2) Find by value: find

```List Find(ElementType X,List PtrL)
{
List p=PtrL;
while(p!=NULL && p->Data != X)
p = p->Next;
return p;
}
```

Time performance is O(n)

3. insert (insert a new node with the value of X after the i-1 node)

```List Insert(ElementType X,int i,List PtrL)
{
List p,s;
if(i==1) /* Insert new node in header */
{
s=(List)malloc(sizeof(struct LNode)); /* Application and filling node */
s->Data = X;
s->Next = PtrL;
return s;	/* Return new header pointer */
}

p = FindKth(i-1,PtrL);	/* Find the i-1 node */
if(p==NULL)				/* The i-1 does not exist and cannot be inserted */
{
printf("parameter i error");
return NULL;
}
else
{
s = (List)malloc(sizeof(struct LNode)); /* Application and filling node */
s->Data = X;
s->Next = p->Next;		/* The new node is inserted after the i-1 node */
p->Next = s;
return PtrL;
}
}
```

4. delete (delete the node at the ith position of the linked list)

```List Delete(int i ,List PtrL)
{
List p,s;
if(i==1)					/* If you want to delete the first node */
{
s = PtrL;				/* s Point to the first node */
if(PtrL!=NULL) PtrL = PtrL->Next; /* Delete from linked list */
else return NULL;
free(s)		/* Release deleted nodes */
return PtrL;
}
}
```
##### 2.3 Generalized List

• Generalized table is a generalization of linear table
• For a linear table, n elements are basic single elements
• In a generalized table, these elements can be not only single elements but also another generalized table

```typedef struct GNode *GList;
struct GNode
{
int Tag;	/* Flag field: 0 indicates that the node is a single element, 1 indicates that the node is a generalized table */
union{		/* The sub table pointer field Sublist is multiplexed with the single element Data field Data, that is, the shared storage space */
ElementType Data;
GList SubList;
}URegion;
GList Next;		/* Point to subsequent nodes */
}
```