Difference between revisions of "Linked List in C"

From Ta Wiki
Jump to navigation Jump to search
(Created page with "== Doubly Linked List == <syntaxhighlight lang="c++" line='line'> #include<stdio.h> #include<stdlib.h> typedef struct node{ int val; struct node *prev, *next; }node;...")
 
 
(One intermediate revision by the same user not shown)
Line 111: Line 111:
 
     print_list(head);
 
     print_list(head);
 
}
 
}
−
</syntaxhighlight>
 
−
 
−
== Singly Linked List ==
 
−
<syntaxhighlight lang="c++" line='line'>
 
−
#include<stdio.h>
 
−
#include<stdlib.h>
 
−
 
−
struct Node {
 
−
int val;
 
−
Node* next;
 
−
};
 
−
 
−
Node* new_node(int val) {
 
−
Node* node = (Node*)malloc(sizeof(Node));
 
−
node->val = val;
 
−
node->next = NULL;
 
−
return node;
 
−
}
 
−
 
−
// ถ้าไม่เจอจะ return โหนดสุดท้าย
 
−
Node* find_parent(Node* node, int val) {
 
−
if(node == NULL)return NULL;
 
−
if(node->next == NULL)return node;
 
−
if(node->next->val == val)return node;
 
−
return find_parent(node->next, val);
 
−
}
 
−
 
−
Node* find(Node* node, int val) {
 
−
if(node == NULL)return NULL;
 
−
if(node->val == val)return node;
 
−
return find(node->next, val);
 
−
}
 
−
 
−
void insert(Node* root, int val) {
 
−
Node* node = new_node(val);
 
−
node->next = root->next;
 
−
root->next = node;
 
−
}
 
−
 
−
void insert_before(Node* root, int p_val, int val) {
 
−
Node* parent = find_parent(root, p_val);
 
−
if(parent == NULL)return;
 
−
insert(parent, val);
 
−
}
 
−
 
−
void delete_node(Node* node, int val) {
 
−
Node* parent = find_parent(node, val);
 
−
if(parent == NULL)return;
 
−
if(parent->next == NULL)return;
 
−
Node* tmp = parent->next;
 
−
parent->next = parent->next->next;
 
−
free(tmp);
 
−
}
 
−
 
−
void print_recursive(Node* node) {
 
−
if(node == NULL)return;
 
−
printf("%d ", node->val);
 
−
print_recursive(node->next);
 
−
}
 
−
 
−
void print_for(Node* node) {
 
−
for( ; node != NULL; node = node->next)
 
−
printf("%d ", node->val);
 
−
}
 
−
 
−
int main(int argc, char *argv[])
 
−
{
 
−
Node* root = new_node(0);
 
−
 
−
for(int i = 1; i <= 10; i++) {
 
−
insert(root, i);
 
−
print_recursive(root->next);
 
−
printf("\n");
 
−
}
 
−
printf("\n");
 
−
 
−
for(int i = 1; i <= 10; i += 4) {
 
−
delete_node(root, i);
 
−
print_for(root->next);
 
−
printf("\n");
 
−
}
 
−
printf("\n");
 
−
 
−
for(int i = 1; i <= 10; i += 3) {
 
−
insert_before(root, i, i * 2);
 
−
print_for(root->next);
 
−
printf("\n");
 
−
}
 
−
printf("\n");
 
−
 
−
getchar();
 
−
 
−
return 0;
 
−
}
 
 
</syntaxhighlight>
 
</syntaxhighlight>

Latest revision as of 00:24, 8 March 2019

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 }
Retrieved from "https://wiki.ta.in.th/index.php?title=Linked_List_in_C&oldid=116"