Linked List in C

Doubly Linked List

  1 #include<stdio.h>
  2 #include<stdlib.h>
  3 
  4 typedef struct node{
  5     int val;
  6     struct node *prev, *next;
  7 }node;
  8 
  9 node *head = NULL;
 10 
 11 node* insert_after(node *n, int val){
 12     // insert_after next to current node
 13     node *newnode = (node*)malloc(sizeof(node));
 14     newnode->val = val;
 15     newnode->next = NULL;
 16     newnode->prev = NULL;
 17     if(n == NULL){
 18         n = newnode;
 19     }else{
 20         newnode->next = n->next;
 21         newnode->prev = n;
 22 
 23         if(n->next != NULL) n->next->prev = newnode;
 24         n->next = newnode;
 25     }
 26     return n;
 27 }
 28 
 29 node* insert_before(node *n, int val){
 30     if(n == NULL){
 31         n = insert_after(n, val);
 32     }else{
 33         node *prev = n->prev;
 34         if(prev == NULL){
 35             // insert at head return new head
 36             prev = insert_after(prev, val);
 37             prev->next = n;
 38             n->prev = prev;
 39             n = prev;
 40         }else{
 41             prev = insert_after(prev, val);
 42         }
 43         
 44     }
 45     return n;
 46 }
 47 
 48 node* remove(node *n){
 49     node *removenode = n;
 50     node *returnnode = NULL;
 51     if(n->prev != NULL){
 52         n->prev->next = n->next;
 53         returnnode = n->prev;
 54     }
 55     if(n->next != NULL){
 56         n->next->prev = n->prev;
 57         returnnode = n->next;
 58     }
 59     free(removenode);
 60     return returnnode;
 61 }
 62 
 63 void print_list(node *head){
 64     printf("List : ");
 65     if(head == NULL){
 66         printf("--EMPTY--");
 67     }
 68     while(head != NULL){
 69         printf("%d ", head->val);
 70         head = head->next;
 71     }
 72 
 73     printf("\n");
 74 }
 75 
 76 int main(){
 77     head = insert_after(head, 1);
 78     print_list(head);
 79     head = insert_after(head, 2);
 80     print_list(head);
 81     head = insert_after(head, 3);
 82     print_list(head);
 83     head = insert_before(head, 4);
 84     print_list(head);
 85     head = insert_before(head, 5);
 86     print_list(head);
 87 
 88     node *temp = head->next->next;
 89     temp = insert_after(temp, 6);
 90     print_list(head);
 91 
 92     head = remove(head);
 93     print_list(head);
 94     head = remove(head);
 95     print_list(head);
 96     head = remove(head);
 97     print_list(head);
 98 
 99     temp = head->next;
100     temp = remove(temp);
101     print_list(head);
102 
103     temp = head->next;
104     temp = remove(temp);
105     print_list(head);
106 
107 
108     head = remove(head);
109     print_list(head);
110 }

Singly Linked List

• เอามาจาก wiki.acioi.in.th

 1  #include<stdio.h>
 2  #include<stdlib.h>
 3  
 4  struct Node {
 5  	int val;
 6  	Node* next;
 7  };
 8  
 9  Node* new_node(int val) {
10  	Node* node = (Node*)malloc(sizeof(Node));
11  	node->val = val;
12  	node->next = NULL;
13  	return node;
14  }
15  
16  // ถ้าไม่เจอจะ return โหนดสุดท้าย
17  Node* find_parent(Node* node, int val) {
18  	if(node == NULL)return NULL;
19  	if(node->next == NULL)return node;
20  	if(node->next->val == val)return node;
21  	return find_parent(node->next, val);
22  }
23  
24  Node* find(Node* node, int val) {
25  	if(node == NULL)return NULL;
26  	if(node->val == val)return node;
27  	return find(node->next, val);
28  }
29  
30  void insert(Node* root, int val) {
31  	Node* node = new_node(val);
32  	node->next = root->next;
33  	root->next = node;
34  }
35  
36  void insert_before(Node* root, int p_val, int val) {
37  	Node* parent = find_parent(root, p_val);
38  	if(parent == NULL)return;
39  	insert(parent, val);
40  }
41  
42  void delete_node(Node* node, int val) {
43  	Node* parent = find_parent(node, val);
44  	if(parent == NULL)return;
45  	if(parent->next == NULL)return;
46  	Node* tmp = parent->next;
47  	parent->next = parent->next->next;
48  	free(tmp);
49  }
50  
51  void print_recursive(Node* node) {
52  	if(node == NULL)return;
53  	printf("%d ", node->val);
54  	print_recursive(node->next);
55  }
56  
57  void print_for(Node* node) {
58  	for( ; node != NULL; node = node->next)
59  	printf("%d ", node->val);
60  }
61  
62  int main(int argc, char *argv[])
63  {
64  	Node* root = new_node(0);
65  
66  	for(int i = 1; i <= 10; i++) {
67  		insert(root, i);
68  		print_recursive(root->next);
69  		printf("\n");
70  	}
71  	printf("\n");
72  
73  	for(int i = 1; i <= 10; i += 4) {
74  		delete_node(root, i);
75  		print_for(root->next);
76  		printf("\n");
77  	}
78  	printf("\n");
79  
80  	for(int i = 1; i <= 10; i += 3) {
81  		insert_before(root, i, i * 2);
82  		print_for(root->next);
83  		printf("\n");
84  	}
85  	printf("\n");
86  
87  getchar();
88  
89  return 0;
90  }