current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top
up vote 3 down vote favorite

Let me know if it seems right to you and if anything can be optimized.

/* 
 * Doubly Linked List
 *
 * Each node of the list contain two references (or links) – one to the previous node and other to the next node.
 * The previous link of the first node and the next link of the last node points to NULL.
 * In comparison to singly-linked list, doubly-linked list requires handling of more pointers 
 * but less information is required as one can use the previous links to observe the preceding element.
 */

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

typedef struct Node {
    int data;
    struct Node *next;
    struct Node *prev;
} Node;

void insert(Node *current, int data);
void delete(Node *current, int data);
void print(Node *current);
int find(Node *current, int data);

void insert(Node *current, int data) {

    // current is pointing to first element
    // we iterate until we find the end
    while(current->next != NULL) {
        current = current->next;
    }
    // create a new Node and insert the item
    current->next = (Node *)malloc(sizeof(Node));
    (current->next)->prev = current;
    current = current->next;
    current->data = data;
    current->next = NULL;
}

void delete(Node *current, int data){

    // Iterate until we find a pointer next to the one we need to delete
    while (current->next != NULL && (current->next)->data != data) {
        current = current->next;
    }

    // Item is not found
    if(current->next == NULL) {
        printf("\nElement %d is not present in the list\n", data);
        return;
    }

    // The element is found in the node next to the one that current points to
    // We removed the node which is next to the pointer (which is also temp)
    Node *tmp = current->next;
    // In special case that we are deleting last node
    if(tmp->next == NULL) {
        current->next = NULL;
    } else {
        current->next = tmp->next;
        (current->next)->prev = tmp->prev;
    }
    tmp->prev = current;

    // We got rid of the node, now time to dellocate the memory
    free(tmp);

    return;
}
void print(Node *current) {
    while(current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }   
}

int find(Node *current, int data) {
    // First pointer is head aka dummy node with no data
    // so we go to next one
    current = current->next;

    // Iterate through the linked list
    while(current != NULL) {
        if(current->data == data) {
            return 1;
        }
        current = current->next;
    }
    return 0;
}

int main() {

    Node *head = (Node *)malloc(sizeof(Node));
    head->next = NULL;
    head->prev = NULL;

    int data = 0;
    int usr_input = 0;

    while(1){
        printf("0. Exit\n");
        printf("1. Insert\n");
        printf("2. Delete\n");
        printf("3. Print\n");
        printf("4. Find\n");


        scanf("%d", &usr_input);

        // can also use a switch instead
        if( usr_input == 0) {
            exit(0);

        } else if(usr_input == 1) {
            printf("\nEnter an element you want to insert: ");
            scanf("%d", &data);
            insert(head, data);

        } else if(usr_input == 2) {
            printf("\nEnter an element you want to delete: ");
            scanf("%d", &data);
            delete(head, data);

        } else if(usr_input == 3) {
            printf("The list is ");
            print(head->next);
            printf("\n\n");

        } else if(usr_input == 4) {
            printf("\nEnter an element you want to find: ");
            scanf("%d", &data);
            int is_found = find(head, data);
            if (is_found) {
                printf("\nElement is found\n\n");
            } else {
                printf("\nElement is NOT found\n\n");
            }
        }
    }
    return 0;
}
share|improve this question
up vote 5 down vote accepted

Some mostly stylistic improvements you could apply:

  • There is no need to cast the return value of malloc(), unless you plan on compiling this code as C++. In C, void* converts implicitly to any other pointer type. So the cast is just boilerplate in this case.

  • Prefer using sizeof(variable) instead of sizeof(Type). Example: 

    Node *head = malloc(sizeof(*head));

    This makes maintenance easier, since now if you introduce a new Node type, you only have to change one place, with no chance of updating one side of the expression and forgetting the other. Note that in this example, the dereference of head is valid because sizeof is a compile-time operation, so there is no actual pointer access taking place here, just type inference.

  • Consider giving more robust names to your functions. find(), insert(), etc, are very common names, which can apply to many things, not just lists. In C, you cannot overload function names, so in any major project, these names would be very likely to cause collisions with other global identifiers. Name prefixes are a common approach in C to solve this problem. Consider prefixing the function names with list_ or any other prefix you might prefer. I.e.:

    void list_insert(Node *current, int data);
void list_delete(Node *current, int data);

  • Instead of returning an integer 0|1 to represent a boolean value, you can use the bool type, declared in the <stdbool.h> header, which is more idiomatic.

  • delete() function is a void function, so it doesn't need an explicit return statement at the end.

  • Looks like you are using printf() to log errors:

    if(current->next == NULL) {
    printf("\nElement %d is not present in the list\n", data);
    return;
}

    For error output, the correct is to use the stderr standard stream.

  • The list printing function print() could be made more flexible by receiving the output stream as a parameter. So you don't limit the caller to always printing to stdout, it can also be used to dump the list to a file (notice the use of fprintf()).

    void print(Node *current, FILE *stream) {
    while(current != NULL) {
        fprintf(stream, "%d ", current->data);
        current = current->next;
    }   
}

  • When you want to allocate and immediately zero-initialize data, such as in here:

    Node *head = (Node *)malloc(sizeof(Node));
head->next = NULL;
head->prev = NULL;

    The standard function calloc() can be used to make code more concise:

    Node *head = calloc(1, sizeof(*head));
share|improve this answer
up vote 3 down vote 
void insert(Node *current, int data);
void delete(Node *current, int data);
void print(Node *current);
int find(Node *current, int data);

As written, you don't need these. The definition can serve as a declaration as well. 

// current is pointing to first element
// we iterate until we find the end

You can avoid this with 

typedef struct DoublyLinkedList {
    struct Node *head;
    struct Node *tail;
} DoublyLinkedList;

Then insert can be 

void insert(DoublyLinkedList list, int data) {
    // create a new Node and insert the item
    list.tail->next = (Node *)malloc(sizeof(Node));
    (list.tail->next)->prev = list.tail;
    list.tail = list.tail->next;
    list.tail->data = data;
    list.tail->next = NULL;
}

You also might want to consider calling that append rather than insert. To me, insert implies that it could be at the beginning or in the middle. In fact, my first thought was that you'd insert at the beginning of the list.

Alternately, you could also just make head into a root node. 

Node *root = (Node *)malloc(sizeof(Node));
root->next = root;
root->prev = root;

This is hackier but allows for 

void insert(Node *root, int data) {
    // create a new Node and insert the item
    (root->prev)->next = (Node *)malloc(sizeof(Node));
    ((root->prev)->next)->prev = root->prev;
    root->prev = (root->prev)->next;
    (root->prev)->data = data;
    (root->prev)->next = root;
}

But you have to change the other functions to match. E.g. 

void delete(Node *root, int data) {
    Node *current = root;

    // Iterate until we find a pointer next to the one we need to delete
    while ( current->next != root && (current->next)->data != data ) {
        current = current->next;
    }

    // Item is not found
    if ( current->next == root ) {
        printf("\nElement %d is not present in the list\n", data);
        return;
    }

    // The element is found in the node next to the one that current points to
    // We removed the node which is next to the pointer (which is also temp)
    Node *tmp = current->next;

    current->next = tmp->next;
    (current->next)->prev = tmp->prev;

    // We got rid of the node, now time to deallocate the memory
    free(tmp);
}

I found 

    tmp->prev = current;

Which is unnecessary as the next step is to free tmp. 

    return;

This is also unnecessary. The function will return naturally at the end. You only need to use return if you want to leave early. 

int find(Node *current, int data) {

Why not 

Node * find(Node *current, int data) {

Then you can get the true or false result by something like 

if ( NULL != find(root, value) ) {

Then you can implement delete as 

Node *location = find(root, value);
if ( NULL != location ) {
    delete(location);
}

With definition:

void delete(Node *current) {
    (current->prev)->next = current->next;
    (current->next)->prev = current->prev;

    // We got rid of the node, now time to deallocate the memory
    free(current);
}

Or stick with the original method signature:

void delete(Node *root, int data) {
    Node *current = find(root, value);

    // Item is not found
    if ( NULL == current ) {
        printf("\nElement %d is not present in the list\n", data);
        return;
    }

    (current->prev)->next = current->next;
    (current->next)->prev = current->prev;

    // We got rid of the node, now time to deallocate the memory
    free(current);
}

Note that if you removed the separate declarations, you would want to move find above delete in the code. 

return 0;

This would never be reached and is unnecessary in main. The compiler will add it for you.

share|improve this answer
up vote -3 down vote

You are changing the head pointer in all the function. You should copy that to a temp pointer and traverse it.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.