# Data Structure (I) - 03 List
> PART (I) - 03
> Other parts in this series $\rightarrow$ [Data Structure - Syllabus ](/bU7575BKTwmwkvmJ5742xA)
> All the code in this part $\rightarrow$ [List](https://github.com/Benny0w0Liu/Data-Structure-Learning/tree/main/List)
# List as ADT
In computer science, a list or sequence is an abstract data type that represents a **finite** number of **ordered values (NO INDEX!)**, where the same value may occur more than once.
## constructor
Need a head.
## operations
* Set element in any position
* Appending elements
* Inserting elements
* Deleting elements
# Implementation(Using C)
## Link List
chain (鏈), also called a singly linked list (單一鏈結串列), is a linked list in which each node (節點) represents one element.
* Each node has exactly one link or pointer from one element to the next.
* The last node has a NULL (or 0) pointer

structure of a node

struct Node{
    int data;
    struct Node* next;
};


### Insert node

void Insert(struct Node** pointer_to_head,int pos,int x){
    struct Node* temp1 = (struct Node*)malloc(sizeof(struct Node));//new Node
    temp1->data = x;
    temp1->next = NULL;
    if(pos==0){//Insert to the head
    	temp1->next = *pointer_to_head;
    	*pointer_to_head = temp1;
    	return;
    }
    struct Node* temp2 = *pointer_to_head; 
    int i;
    for(i=0;i<pos-1;i++){//Go to the position we want
    	temp2 = temp2->next;
    }
    temp1->next = temp2->next;
    temp2->next = temp1;
}


### Delete node

### Reverse link
I think this concept is easy, so I will just show you the code.

void Reverse(struct Node** pointer_to_head){
    struct Node* temp = *pointer_to_head, *current = *pointer_to_head, *prev = NULL;
    while(temp != NULL){
	temp = current->next;//store the next node
        current->next = prev;//reverse the link
	    prev = current;//move to current node
	    current = temp;//move to next node
    }
    *pointer_to_head = prev;//set the head
} 

You can use the recursion method:

void recursionReverse(struct Node** pointer_to_head, struct Node* current_node){
    if(current_node->next==NULL){
    	*pointer_to_head = current_node;//1
    	return;
    } 
    recursionReverse(pointer_to_head, current_node->next);//go to next node
    struct Node* next_node= current_node->next;//2-1
    next_node->next=current_node;//2-2
    current_node->next=NULL;//2-3
} 


### Travel the list
#### Forward

void Print(struct Node* head){
    while(head!=NULL){//Travel the list
        printf("%d ", head->data);
    	head=head->next;
    }
    printf("\n");
}

#### Forward but using recursion

void recursionPrint(struct Node* head){
    if(head==NULL){
    	printf("\n");//end
    	return;
    } 
    printf("%d ",head->data);//print data
    recursionPrint(head->next);//go to next
}

#### reverse order using recursion

void recursionPrintReserveOrder(struct Node* head){
    if(head==NULL){
    	return;
    } 
    recursionPrintReserveOrder(head->next);//go to next first!
    printf("%d ",head->data);//then print data!
}

## Double Link List
In computer science, a doubly linked list is a linked data structure that consists of a set of sequentially linked records called nodes.
* Each node contains **3** fields: **2** link fields (references to the previous and to the next node in the sequence of nodes) and 1 data field.
* The beginning and ending nodes' previous and next links, respectively, point to null.

Basically it is same as previous one but the struture is:

struct Node{
	int data;
	struct Node* next;
	struct Node* prev;
};

When manipulating with node, please remeber the `prev`.

---

# Array v.s. List
> Acording to https://www.geeksforgeeks.org/what-is-the-difference-between-lists-and-arrays/

Aspect| Arrays| Lists|
|---|---|---|
Size|Arrays have a fixed size set during creation.|Lists are dynamic and can change in size during runtime.
Data Types|All elements in an array must be of the same data type.|Lists can accommodate elements of different data types.
|**Memory Allocation**| Memory for the entire array is allocated at once during initialization.|Lists **dynamically** allocate memory as elements are added or removed.
Access Time|Arrays provide constant-time access to elements through indexing.|Lists may have slightly variable access time due to dynamic resizing.
Flexibility|Arrays are less flexible as their size cannot be easily changed.|Lists are more flexible, allowing easy addition or removal of elements.