implementing doubly linked list ADT

typedef struct Node {
    struct Node* front;
    struct Node* rear;
    int data;
} Node;

typedef struct {
    Node* head;
    Node* tail;
    int size;
} List;```

void initList(List* list) {
    list->head = NULL;
    list->tail = NULL;
    list->size = 0;
}```

insertFront

void insertFront(List* list, int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = value;
    newNode->front = NULL;
    newNode->rear = list->head;
    if(list->head == NULL)  {
        list->tail = newNode;
    }
    else{
        list->head->front = newNode;
    }
    list->head = newNode;
    ++list->size;
}

• Allocates memory for a new node
• New node’s front pointer is set NULL since it will be inserted at the front and there will be no previous node
• new node’s rear pointer points to the previous head (or NULL if the list is empty)
• If the list is empty, tail pointer is set to the new node since it is the only node in the list
• If the list is not empty, previous head’s front pointer will point to new node
• In both cases, head pointer will point to the new nod
• Increases the size of the list by 1 because new node was made

insertBack

void insertBack(List* list, int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = value;
    newNode->front = list->tail;
    newNode->rear = NULL;
    if (list->tail == NULL) {
        list->head = newNode;
    } else {
        list->tail->rear = newNode;
    }
    list->tail = newNode;
    ++list->size;
}

• Allocates memory for a new node which will be inserted at the end of the list
• This function works in the opposite way to the insertFront()
• New node’s front pointer will point to the previous tail and its rear pointer is set NULL since there will be no more nodes behind it
• If the list is empty, head pointer will point to the new node
• If the list is not empty, previous tail’s rear pointer will point to the new node
• In both cases, tail pointer will point to the new node (this statement comes after the ‘else’ statement because we don’t want previous tail information to disappear before changing its rear pointer)

insert

void insert(List* list, int index, int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = value;
    Node* temp;
    if(index <= list->size/2) {
        temp = list->head;
        for(int i=1; i<index; i++) {
            temp = temp->rear;
        }
    }
    else{
        temp = list->tail;
        for(int i=1; i<list->size-index+1; i++){
            temp = temp->front;
        }
    }
    temp->rear->front = newNode;
    newNode->rear = temp->rear;
    temp->rear = newNode;
    newNode->front = temp;
    ++list->size;
}

• The temp pointer will point to the position where new node should be inserted
• For greater efficiency (to reach the wanted node with fewer jumps), I broke down the case into two that determines whether the index is closer to the head or the tail
• ‘temp’ pointer will jump ‘index’-1 times from the head of the list if ‘index’ is smaller than half size of the list or ‘size’-‘index’ times from the tail of the list if ‘index’ is bigger than half size if the list
• Once the temp node is set, its rear pointer and its next node’s front pointer will be set to point the new (inserted) node
• Because we don’t want temp node’s rear pointer to lose its address value until it is unneeded, statement that changes it to point the new node is placed at the back
• At the end, the function increases the size of the list by 1 since the new node is inserted

erase

int erase(List* list, int value) {
    Node* node = list->head;
    Node* temp;
    while(node->rear != NULL) {
        if(node->data == value) {
            temp = node->rear;
            node->rear->front = node->front;
            node->front->rear = node->rear;
            free(node);
            node = temp;
        }
        else {
            node = node->rear;
        }
    }
    return 0;
}

• The erase() function initialize two pointers, ‘node’ and ‘temp’
• ‘node’ pointer will be used to show the location of final node that has been checked if its data matches the given value
• ‘temp’ pointer will be used to temporarily hold a reference to the next node because if current node’s data matches the given value, memory will be deallocated
• The while loop continues until ‘node’ pointer reaches the tail so that every node that has the data of the given value can be removed from the list
• If current node’s data matches the given value, it is removed from the list by setting its front node’s rear pointer to point its rear pointer and its rear node’s front pointer to point its front pointer instead
• Also, after deallocating memory of current node, ‘node’ pointer will point its next node by bringing back reference stored in ‘temp’ pointer
• Else (if current node’s data doesn’t match the given value), ‘node’ pointer continues to travel the list by updating itself to the next node

find

int find(List* list, int value) {
    Node* node = list->head;
    while(node != NULL) {
        if(node->data == value){
            printf("%d is in the list\n",value);
            return 0;
        }
       node = node->rear; 
    }
    printf("%d is not in the list\n",value);
    return 0;
}

• The find() function initializes pointer ‘node’ to point the head that will be used to travel through the list
• The while loop continues until ‘node’ pointer reaches the tail
• If the current node matches the given value, the function will print a statement that indicates that the given value is in the list and will return 0 to indicate successful completion
• If the given value is not found in the current node, ‘node’ pointer will point to the next node
• If the while loop ends without finding the value, the function will print a statement that indicates that the given value is not in the list

printList

void printList(List* list) {
    Node* node = list->head;
    while(node != NULL) {
        printf("%d ",node->data);
        node = node->rear;
    }
    printf("\n");
}

• The printList() function prints data for every node in the list
• The ‘node’ pointer will be used to travel through the list
• While loop continues until ‘node’ pointer reaches the tail
• After printing the data of current node, ‘node’ pointer will point to the next node