Doubly Linked List example Code Answer

Hello Developer, Hope you guys are doing great. Today at Tutorial Guruji Official website, we are sharing the answer of Doubly Linked List example without wasting too much if your time.

The question is published on by Tutorial Guruji team.

The header file I customised is below.

#ifndef DLinkedList_h
#define DLinkedList_h

#include <stdio.h>
#include <stdlib.h>

typedef int ElementType;
typedef struct tagNode{
ElementType data, key;
struct tagNode* prevNode;
struct tagNode* nextNode;
char myName [30];
char telNum [30];
} Node;



Node* CreateNode(ElementType newData);
void DestroyNode(Node* node);
void AppendNode(Node** head, Node* newData);
void InsertAfter(Node* current, Node* newNode);
void InsertNewHead(Node** head, Node* newHead);
void RemoveNode(Node** head, Node* remove);
Node* GetNodeAt(Node* head, int location);
int GetNodeCount(Node* head);

#endif

So far, the end of the DLinkedList.h file

#include "DLinkedList.h"
#include <time.h>
#include "Chaining.h"


int numbersInCache [] = {23, 22, 33, 44, 55, 77, 99, 20, 24, 67, 89, 90, 24, 43, 98, 63, 43, 96, 45, 43};

Node* CreateNode(ElementType newData){
Node* newNode = (Node*)malloc(sizeof(Node));

newNode->data = newData;
newNode->prevNode = NULL;
newNode->nextNode = NULL;



return newNode;

} 

//Node destroyed
void DestroyNode(Node* node){
free(node);
}

//To add a node
void AppendNode(Node** head, Node* newNode){
if(*head == NULL)
    *head = newNode;
else {
    Node* tail = *head;
    while(tail->nextNode != NULL)
        tail = tail->nextNode;

    tail->nextNode = newNode;
    //The current tail node is pointed by the preNode of the new node.
    newNode->prevNode = tail;
    }
}

void insertIntheFront(Node* newNode, Node** head){
if(*head == NULL)
    *head = newNode;
else{
    Node* tail = *head;
    while(tail->nextNode != NULL)
        tail = tail->nextNode;

    tail->prevNode = newNode;
    newNode->nextNode = tail;
 }
}


//Insert a new node
void InsertAfter(Node* current, Node* newNode){
newNode->prevNode = current;
newNode->nextNode = current->nextNode;

if(current->nextNode != NULL){
    current->nextNode->prevNode= newNode;
}

current->nextNode = newNode;
}




//Removal of a node
void RemoveNode(Node** head, Node* remove){
//if the head is identical to the one to remove
if(*head == remove){

    //head points to the address of the next node
    *head = remove->nextNode;

    //if the head still exists,
    if(*head != NULL)//Null is assigned because the previous node does not exist.
        (*head)->prevNode = NULL;


    remove->prevNode = NULL;
    remove->nextNode = NULL;
} else {
    Node* temp = remove;
    //If the node to remove still has the previous node address
    if(remove->prevNode != NULL)//The previous node is connected with the next node
        remove->prevNode->nextNode = temp->nextNode;
    //if the node to remove still has the next node address
    if(remove->nextNode != NULL)//the next node address and the previous node address     are connected together.
        remove->nextNode->prevNode = remove->prevNode;
    remove->prevNode = NULL;
    remove->nextNode = NULL;
    }
}


//Node searching
Node* GetNodeAt(Node* head, int location){
Node* current = head;

while(current != NULL && (--location) >= 0){
    current = current->nextNode;
}
return current;
}

//Count nodes
int GetNodeCount(Node* head){
int count = 0;
Node* current = head;

while(current != NULL){
    current = current->nextNode;
    count++;
}
return count;
}

int lookUpFunction(Node* head, int numInput){
int foundOrNot = 0;
int indexNum = -1;
for(int i=0; i<GetNodeCount(head); i++){
    int numData = GetNodeAt(head, i)->data;
    if(numInput == numData){
        indexNum = i;
        foundOrNot = 1;
    }
}

return indexNum;

}


void inputToCacheOperation(Node* list){


int numToSubmit = rand()%50;

printf("a generated number moving into the cache is %dn ", numToSubmit);
Node * newNode = NULL;

int cacheElementCount = sizeof(numbersInCache)/sizeof(int);

int indexNumForOperation = lookUpFunction(list, numToSubmit);//returns an index    number, -1 is returned when it cannot find any.
if(indexNumForOperation == -1 ){
    AppendNode(&list, CreateNode(numToSubmit));

This part below is a big trouble.

        if(cacheElementCount>19){
        Node* firstNode = GetNodeAt(list, 0);
        RemoveNode(&list, firstNode);
        DestroyNode(firstNode);
        //When the number of nodes exceeds the cache size, it deletes the very first   node to maintain its maximum capacity.

I am annoyed….

} else {

    RemoveNode(&list, GetNodeAt(list, indexNumForOperation));
    newNode = CreateNode(numToSubmit);
    AppendNode(&list, newNode);
    }
}


}




int main(int argc, const char * argv[]) {
int i = 0;
int count = 0;
Node* list = NULL;
Node* newNode = NULL;
Node* current = NULL;
Node* tempNodeStorage = NULL;
Node* firstNode = NULL;

srand(time(NULL));

int numInput;
numInput=0;
//Created 20 nodes
for(int i=0; i< sizeof(numbersInCache)/sizeof(int); i++){
    //scanf("%d", &numInput);

    printf("%dn", numbersInCache[i]);
    newNode=CreateNode(numbersInCache[i]);
    AppendNode(&list, newNode);

}

//Printing out the list.
count = GetNodeCount(list);
for(i = 0; i < count; i++){
    current = GetNodeAt(list, i);
    printf("List[%d] : %dn", i, current->data);
}




for(int i= 0; i< 10; i++){ //Cache operation to perform
    inputToCacheOperation(list);
}


//Printing the list
count = GetNodeCount(list);
for(i = 0; i<count; i++){
    current = GetNodeAt(list,i);
    printf("List[%d] ; %dn", i, current->data);
}

// All nodes are removed in the memory
printf("nDestroying List....n");

for(i=0; i<count; i++){
    current = GetNodeAt(list, 0);

    if(current != NULL){
        RemoveNode(&list, current);
        DestroyNode(current);

    }
}

}

I am coding a simple doubly linked list example simulating a disk operation. When I modify “Node* firstNode = GetNodeAt(list, 0);” to “Node* firstNode = GetNodeAt(list, 1);” it works fine. However, when i put the parameter value with “0”, it crashes with a memory error. Can you give me any improvement on it? I used Xcode to build and run the code.

Answer

In function RemoveNode(), you didn’t check the parameter Node* remove is NULL before you access it. So RemoveNode(&list, GetNodeAt(list, indexNumForOperation)) possible pass a NULL to RemoveNode() when your indexNumForOperation more current list count.

We are here to answer your question about Doubly Linked List example - If you find the proper solution, please don't forgot to share this with your team members.

Related Posts

Tutorial Guruji