Advertisement
AshTurner67

Doubly LL implementation

Oct 22nd, 2024 (edited)
109
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 5.04 KB | Source Code | 0 0
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #define HEAD list->head
  4. #define TAIL list->tail
  5. #define CURR list->curr
  6. #define SIZE list->size
  7.  
  8.  
  9. // DONE
  10. typedef struct Node
  11. {
  12.     int data;
  13.     // add *next and *prev here
  14.     struct Node* next;
  15.     struct Node* prev;
  16. } Node; // DONE
  17.  
  18.  
  19. // DONE
  20. typedef struct LinkedList
  21. {
  22.     // add Node* head, tail, current_position and other necessary fields here
  23.     Node* head;
  24.     Node* tail;
  25.     Node* curr;
  26.     int size;
  27.    
  28. } LinkedList;
  29.  
  30.  
  31. // DONE
  32. void init_linkedlist(LinkedList *list)
  33. {
  34.     //implement init_linkedlist
  35.     HEAD = NULL;
  36.     TAIL = NULL;
  37.     CURR = NULL;
  38.     SIZE = 0;
  39.     // initialize head, tail with null
  40. }
  41.  
  42.  
  43. // DONE
  44. void clear(LinkedList *list)
  45. {
  46.     //Implement clear
  47.     Node* temp1 = HEAD;
  48.     while(temp1){
  49.         Node* temp2 = temp1->next;
  50.         free(temp1);
  51.         temp1 = temp2;
  52.     }
  53.     HEAD = NULL;
  54.     TAIL = NULL;
  55.     CURR = NULL;
  56.     SIZE = 0;
  57.     // traverse the list and free each node
  58.     // set head and tail to null
  59. }
  60.  
  61.  
  62. // DONE
  63. int get_size(LinkedList *list)
  64. {  
  65.     //Implement get_size
  66.     return SIZE;
  67. }
  68.  
  69.  
  70. // DONE
  71. void append(LinkedList *list, int value)
  72. {
  73.     //Implement append
  74.     Node* temp = (Node*) malloc(sizeof(Node));
  75.     temp->data = value;
  76.     temp->next = NULL;
  77.     SIZE++;
  78.     if(HEAD == NULL){
  79.         temp->prev = NULL;
  80.         CURR = temp;
  81.         HEAD = temp;
  82.         TAIL = temp;
  83.         return;
  84.     }
  85.     temp->prev = TAIL;
  86.     TAIL->next = temp;
  87.     TAIL = temp;
  88.     // create a new node and set its value
  89.     // consider the case when the list is empty and when it isnt
  90. }
  91.  
  92.  
  93. // DONE
  94. void insert(LinkedList *list, int value)
  95. {
  96.     //Implement insert
  97.     Node* temp = (Node*) malloc(sizeof(Node));
  98.     temp->data = value;
  99.     SIZE++;
  100.     if(HEAD == NULL){
  101.         HEAD = temp;
  102.         TAIL = temp;
  103.         CURR = temp;
  104.         temp->next = NULL;
  105.         temp->prev = NULL;
  106.         return;
  107.     }
  108.     temp->next = CURR;
  109.     if(CURR == HEAD){
  110.         temp->prev = NULL;
  111.         HEAD = temp;
  112.     }
  113.     else temp->prev = CURR->prev;
  114.     CURR->prev = temp;
  115.     CURR = temp;
  116.     // create a new node and set its value
  117.     // place it at the current position (check order of operations)
  118.     // consider the case when the list is empty and when it isnt
  119. }
  120.  
  121.  
  122. //DONE
  123. int remove_at_current(LinkedList *list)
  124. {
  125.     //Implement remove_at_current
  126.     Node* temp = CURR;
  127.     int value = temp->data;
  128.     if(HEAD == TAIL) HEAD = NULL, TAIL = NULL, CURR = NULL;
  129.     else if(CURR == HEAD){
  130.         HEAD = CURR->next;
  131.         HEAD->prev = NULL;
  132.         CURR = HEAD;
  133.     }
  134.     else if(CURR == TAIL){
  135.         TAIL = CURR->prev;
  136.         TAIL->next = NULL;
  137.         CURR = TAIL;
  138.     }
  139.     else{
  140.         CURR->prev->next = CURR->next;
  141.         CURR->next->prev = CURR->prev;
  142.         CURR = CURR->next;
  143.     }
  144.     free(temp);
  145.     SIZE--;
  146.     // consider the case when current node is at the begining or at the end
  147.     return value;
  148. }
  149.  
  150.  
  151. //DONE
  152. int find(LinkedList *list, int value)
  153. {
  154.     //Implement find
  155.     Node* temp = HEAD;
  156.     int position = 0;
  157.     while(temp && temp->data != value){
  158.         temp = temp->next;
  159.         position++;
  160.     }
  161.     // traverse the list and return the position of the value
  162.     if(temp) return position;
  163.     else return -1;
  164. }
  165.  
  166.  
  167. //DONE
  168. void move_to_start(LinkedList *list)
  169. {
  170.     //Implement move_to_start
  171.     CURR = HEAD;
  172. }
  173.  
  174.  
  175. //DONE
  176. void move_to_end(LinkedList *list)
  177. {
  178.     //Implement move_to_end
  179.     CURR = TAIL;
  180. }
  181.  
  182.  
  183. //DONE
  184. void prev(LinkedList *list)
  185. {
  186.     //Implement prev
  187.     if(CURR != HEAD) CURR = CURR->prev;
  188. }
  189.  
  190.  
  191. //DONE
  192. void next(LinkedList *list)
  193. {
  194.     //Implement next
  195.     if(CURR != TAIL) CURR = CURR->next;
  196. }
  197.  
  198.  
  199. void move_to_position(LinkedList *list, int position)
  200. {
  201.     //Implement move_to_position
  202.     Node* temp = HEAD;
  203.     int i = 0;
  204.     while(i != position){
  205.         temp = temp->next;
  206.         i++;
  207.     }
  208.     CURR = temp;
  209.     // traverse the list and stop at the given position
  210. }
  211.  
  212.  
  213. //DONE
  214. int get_current_position(LinkedList *list)
  215. {
  216.     //Implement get_current_position
  217.     if(!CURR) return -1;
  218.     Node* temp = HEAD;
  219.     int position = 0;
  220.     while(temp != CURR) temp = temp->next, position++;
  221.     // traverse the list and stop when you are at the current position
  222.     // return the position (integer)
  223.     return position;
  224. }
  225.  
  226.  
  227. //DONE
  228. int get_current_element(LinkedList *list)
  229. {
  230.     //Implement get_current_element
  231.     if(!CURR) return -1;
  232.     int value = CURR->data;
  233.     // return the value at the current position
  234.     return value;
  235. }
  236.  
  237.  
  238. //DONE
  239. void print_list(LinkedList *list)
  240. {
  241.     //Print list elements
  242.     printf("< ");
  243.     Node* temp = HEAD;
  244.     for(int i = 0; temp; i++){
  245.         if(temp == CURR) printf("|");
  246.         if(temp != TAIL) printf("%d  ",temp->data);
  247.         else printf("%d",temp->data);
  248.         temp = temp->next;
  249.     }
  250.     printf(" >\n");
  251. }
  252.  
  253.  
  254. //DONE
  255. void free_list(LinkedList *list)
  256. {
  257.     //Implement free_list
  258.     clear(list);
  259.     // free each node in the list
  260. }
  261.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement