How to reduce runtime from linear to constant?-CodePudding

lengthOfLinkedList() below counts the number of nodes in a linked list, but the runtime is linear which I do not want. How can I reduce it to a constant runtime function? Are there any library functions I can use?

typedef struct node {
    int val;
    struct node *next;
} NODE;

struct list_struct {
    NODE *front;
    NODE *back;
};

int lengthOfLinkedList(LIST *l) {
    NODE *n = l->front;
    int count = 0;
    while (n != NULL) {
        count  ;
        n = n->next;
    }
    return count;
}

CodePudding user response：

You cannot achieve constant time size calculation with your current struct definition. Now, if you add a size_t member to the struct and use it to store the length, modifying it on any additions or deletions, you can access the length in constant time.

typedef struct node {
    int val;
    struct node *next;
    size_t length;
} NODE;

CodePudding user response：

Define the head-node struct accordingly.

For int value type the list-node remains same:

typedef struct _node {
    int val;
    struct _node* next;
} listNode_t;

We alter the head-node to suit our needs:

typedef struct {
    // add members as scenario demands
    int size; // updated after every insert/delete
    int min;  // updated/checked after every insert/delete/update
    int max;  // updated/checked after every insert/delete/update
    long sum; // updated after every insert/delete/update
    listNode_t* first; // to insert/delete from beginning (LIFO-Stack)
    listNode_t* last;  // to insert at the end (can't delete though)
} listHead_t;

Then you can get those values in O(1), provided they're updated consistently.

listHead_t* head;
...
int listLength = list_getSize (head);
int listMin = list_getMin (head);
int listMax = list_getMax (head);
long listSum = list_getSum (head);
float listAvg = list_getAverage (head);  // (float)sum/size

/* List Methods */
list_prefix (head, value);  // add value as the first node
list_suffix (head, value);  // add value as the last node

That makes list_prefix() like:

...
#include <limits.h>
...
listHead_t* head = list_init_head ();
...
...
listHead_t* list_init_head () {
    listHead_t* head = malloc (sizeof(listHead_t));
    if (!head) {
        perror("list_init_head-malloc");
        exit (1);
    }
    head->size = head->sum = 0;
    head->first = head->last = NULL;
    head->min = INT_MAX;
    head->max = INT_MIN;
    return head;
}

int list_prefix (listHead_t* head, int val) {
    if (!head) return -1; // invalid call
    listNode_t* node = malloc (sizeof(listNode_t));
    if (!node) {
        perror("list_prefix-malloc");
        exit (1);
    }
    node->val = val;
    // update list-head stats
      head->size;
    head->sum  = val;
    if (val < head->min) head->min = val;
    if (val > head->max) head->max = val;
    if (!head->first) {
        node->next = NULL;
        head->first = head->last = node;
    } else {
        node->next = head->first;
        head->first = node;
    }
    return 0;
}