current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 4 down vote favorite

Let me know if it seems right to you and if anything can be optimized. My concern is that I'm unsure if circular linked lists are supposed to have a tail. I've implemented it just using a head. Is that wrong? If so, how would you change it to make it proper?

/* 
 * Circular Linked List
 *
 */

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

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

void insert_beg_of_list(Node *current, int data);
void delete(Node *current, int data);
void print_list(Node *current);
int find_in_a_list(Node *current, int data);

void insert_beg_of_list(Node *current, int data) {
    //keep track of first node
    Node *head = current;

    while(current->next != head) {
        current = current->next;
    }
    current->next = (Node*)malloc(sizeof(Node));
    current = current->next;
    current->data = data;
    current->next = head;

}

void delete_from_list(Node *current, int data) {

    Node *head = current;
    while(current->next != head && (current->next)->data != data) {
        current = current->next;
    }
    if(current->next == head) {
        printf("%d element is not found\n\n", data);
        return;
    }
    Node *tmp;
    tmp = current->next;
    current->next = tmp->next;
    free(tmp);  
    return;
}

void print_list(Node *current) {

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

}

int find_in_a_list(Node *current, int data) {

    Node *head = current;
    current = current->next;
    while(current != head) {
        if(current->data == data) {
            // Key found
            return 1;
        }
        current = current->next;
    }
    // Key is not found
    return 0;
}

int main() {

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

    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_beg_of_list(head, data);

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

        } else if( usr_input == 3) {
            printf("The list is ");
            print_list(head);
            printf("\n\n");

        } else if( usr_input == 4) {
            printf("\nEnter an element you want to find: ");
            scanf("%d", &data);
            int is_found = find_in_a_list(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
    
a circular linked list should always have both a head and a tail. The head is where to add/write next, the tail is where to delete/read next. This means there should be a separate head pointer and a separate tail pointer. those pointers keep track of the end of the circular linked list –  user3629249 Jan 8 at 20:14

1 Answer 1

up vote 4 down vote

  1. When making a collection of routines to handle a type, strongly advise to create a create and destroy function. Rather then the below, consider some initialization function.

    // Replace this code
Node *head = (Node *)malloc(sizeof(Node));
head->next = head;  

// with this
Node *new_list(void ) {
  Node *head = malloc(sizeof *head);
  if (head) {
    head->next = head;
  }   
  return head;
}  
...
Node *head = new_list();

  2. The names on the functions benefit by having the leading text indicate the grouping. Avoid function delete() - too generic.

    void clist_insert_beg(Node *current, int data);
void clist_delete(Node *current, int data);
void clist_print(Node *current);
int clist_find(Node *current, int data);

  3. Consider 4 operations: Add_Before_First(), Remove_First(), Append(), Remove_End(). A circular list means it is relatively easy (O(1)) to do something at both ends of the list. This code's delete_from_list() is nothing more that a typical linked list would do and take O(n) time. Sadly even the insert_beg_of_list() also takes O(n) time. Recommend to re-work this code so at least 1 of 2 "head" functions and at least 1 of the "tail" functions can operate in O(1) time (no while loops).

  4. Having a circular list with only a single pointer is do-able and perform 3 of the above 4 in O(1) time. Consider a list that points to the tail. No need for a head pointer as tail->next is the head.

  5. Recommend a simpler to code and maintain allocation style. The cast is not needed and the sizeof works even is the type of *(current->next) changes.

    // current->next = (Node*)malloc(sizeof(Node));
current->next = malloc(sizeof *(current->next));

  6. Though posted as 1 file, better to post as a circular_list.c, circular_list.h, main_sample_usage.c files to clearly identify that which is public and private.

  7. I have doubts delete_from_list() works when the last element is deleted. I think that is because of the overall design. IMO, when a list contains no data, it should consume minimal space. IOW, a NULL pointer is an empty list. When a list type is used heavily, there are often many empty lists. So an empty list of a pointer to a node pointing to itself seems wasteful.

  8. Functions that do not modify the list should use const.

    // int find_in_a_list(Node *current, int data) {
int find_in_a_list(const Node *current, int data) {

// void print_list(Node *current) {
void print_list(const Node *current) {

  9. Hoping to find functions like

    unsigned count_list(const Node *current);
bool empty_list(const Node *current);

  10. Minor Use int main(void) {

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.