baseline features - a little buggy
Dependencies: mbed wave_player 4DGL-uLCD-SE MMA8452
Diff: doubly_linked_list.cpp
- Revision:
- 1:4421c1e849e9
- Parent:
- 0:95264f964374
diff -r 95264f964374 -r 4421c1e849e9 doubly_linked_list.cpp --- a/doubly_linked_list.cpp Mon Mar 29 21:17:26 2021 -0400 +++ b/doubly_linked_list.cpp Fri Apr 09 20:44:48 2021 +0000 @@ -12,11 +12,13 @@ #include "doubly_linked_list.h" LLNode* create_llnode(void* data) { + LLNode* node = (LLNode*)malloc(sizeof(LLNode)); + node -> prev = NULL; + node -> next = NULL; + node -> data = data; + return node; + } - // Your code here - - return NULL; // replace this -} DLinkedList* create_dlinkedlist(void) { DLinkedList* newList = (DLinkedList*)malloc(sizeof(DLinkedList)); @@ -27,45 +29,27 @@ } int getSize(DLinkedList* dLinkedList){ - - // Your code here - - return 0; + return dLinkedList -> size; } LLNode* getHead(DLinkedList* dLinkedList){ - - // Your code here - - return NULL; // replace this + return dLinkedList -> head; } LLNode* getTail(DLinkedList* dLinkedList){ - - // Your code here - - return NULL; // replace this + return dLinkedList -> tail; } LLNode* getNext(LLNode* node){ - - // Your code here - - return NULL; // replace this + return node -> next; } LLNode* getPrev(LLNode* node){ - - // Your code here - - return NULL; // replace this + return node -> prev; } void* getData(LLNode* node){ - - // Your code here - - return NULL; // replace this + return node -> data; } void insertAfter(DLinkedList* dLinkedList, LLNode* prev_node, void* data){ @@ -73,9 +57,18 @@ printf("the given previous node cannot be NULL"); return; } - - // Your code here - + LLNode* newNode = create_llnode(data); //creates new node + LLNode* nextNode = prev_node -> next; //creates next for new node + //previous node is passed as argument + if (nextNode != NULL) { //if prev_node is not the tail... + newNode -> next = nextNode; //update next of new node + nextNode -> prev = newNode; //update prev of next_node + } else { //if prev_node is the tail + dLinkedList -> tail = newNode; //update tail of linked list + } // execute no matter what + newNode -> prev = prev_node; //update prev of new node + prev_node -> next = newNode; //update next of prev_node + (dLinkedList -> size)++; //update size of linked list return; } @@ -84,44 +77,103 @@ printf("the given next node cannot be NULL"); return; } - - // Your code here - + LLNode* newNode = create_llnode(data); //creates new node + LLNode* prevNode = next_node -> prev; //creates prev for new node + //next node is passed as argument + if (prevNode != NULL) { //if next_node is not the head... + newNode -> prev = prevNode; //update prev of new node + prevNode -> next = newNode; //update next of prev node + } else { //if next_node is the head + dLinkedList -> head = newNode; //update head of linked list + } // execute no matter what + newNode -> next = next_node; //update next of new node + next_node -> prev = newNode; //update prev of next_node + (dLinkedList -> size)++; //update size of linked list return; } -void insertHead(DLinkedList* dLinkedList, void* data){ - if(dLinkedList->head == NULL){ +void insertHead(DLinkedList* dLinkedList, void* data) { + if (dLinkedList -> head == NULL) { LLNode* newNode = create_llnode(data); - dLinkedList->head = newNode; - dLinkedList->tail = newNode; - dLinkedList->size++; - }else{ - insertBefore(dLinkedList, dLinkedList->head, data); + dLinkedList -> head = newNode; + dLinkedList -> tail = newNode; + (dLinkedList -> size)++; + } else { + insertBefore(dLinkedList, dLinkedList -> head, data); + } +} + +void insertTail(DLinkedList* dLinkedList, void* data) { + if (dLinkedList -> head == NULL ){ + LLNode* newNode = create_llnode(data); + dLinkedList -> head = newNode; + dLinkedList -> tail = newNode; + (dLinkedList -> size)++; + } else { + insertAfter(dLinkedList, dLinkedList->tail, data); } } -void insertTail(DLinkedList* dLinkedList, void* data){ - - // Your code here - -} - void deleteNode(DLinkedList* dLinkedList, LLNode* Node){ - - // Your code here - + //LLNode* prevNode = Node -> prev; + //LLNode* nextNode = Node -> next; + if (dLinkedList -> size == 1){ + free(Node->data); + free(Node); + (dLinkedList->size)--; + return; + } + if (dLinkedList -> head == Node) { + Node -> next -> prev = NULL; + dLinkedList -> head = Node -> next; + } else if (dLinkedList -> tail == Node) { + Node -> prev -> next = NULL; + dLinkedList -> tail = Node -> prev; + } else { + Node -> prev -> next = Node -> next; + Node -> next -> prev = Node -> prev; + } + (dLinkedList -> size)--; + free(Node -> data); + free(Node); + return; } void destroyList(DLinkedList* dLinkedList){ - - // Your code here - + if ((dLinkedList -> size) == 1) { + deleteNode(dLinkedList, dLinkedList -> head); + free(dLinkedList); + return; + } + LLNode* curr = dLinkedList -> head; + if (curr == NULL) { + free(dLinkedList); + return; + } + LLNode* next = curr -> next; + while (next != NULL) { + deleteNode(dLinkedList, curr); + curr = next; + next = curr -> next; + } + free(dLinkedList); + return; } -void reverse(DLinkedList* dLinkedList) -{ - - // Your code here - -} +void reverse(DLinkedList* dLinkedList){ + if (dLinkedList -> size <= 1){ + return; + } + LLNode* curr = dLinkedList -> head; + LLNode* start = dLinkedList -> head; + LLNode* dummy; + while (curr != NULL){ + dummy = curr -> prev; + curr -> prev = curr -> next; + curr -> next = dummy; + curr = curr -> prev; + } + dLinkedList -> head = dLinkedList -> tail; + dLinkedList -> tail = start; + return; +}