2
\$\begingroup\$

Previous versions of this question

First Version

Second Version

Changes

I added these operations:

  • Pop_back

  • Pop_front

You are not allowed to insert_sll at the front or back, but only in position i such that 0 < i < n=size-1.

I also tested the functions, so everything is working!

Thanks in advance for any improvement ideas!

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

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

Node* head = NULL;
Node* tail = NULL;

Node* create_node(int elm) {
    Node* node = malloc(sizeof * node), *exits = NULL;
    if (!node) return exits;
    node->data = elm;
    node->next = NULL;
    return node;
}

int is_empty_sll() { //O(1)
    return head == NULL;
}

int size_sll() { //O(n) 
    int count = 0;
    Node* last = head;
    while (last) {
        count += 1;
        last = last->next;
    }
    return count;
}

Node* node_k_sll(int k) { // 0-based index
    int n = size_sll() - 1;
    if (!is_empty_sll() && (k >= 0 && k <= n)) {
        int i = 0;
        Node* node = head;
        while (i != k) {
            i += 1;
            node = node->next;
        }
        return node;
    }
    else {
        printf("Out of Index");
        Node* node = NULL;
        return node;
    }
}

void append_sll(int elm) { //O(1)
    Node* cur = create_node(elm);
    if (!head) {
        head = cur;
    }
    else {
        tail->next = cur;
    }
    tail = cur;
}

void prepend_sll(int elm) {
    Node* updated_head = create_node(elm);
    if (!head) {
        head = updated_head;
        tail = head;
    }
    else {
        updated_head->next = head;
        head = updated_head;
    }
}

void insert_sll(int elm, int i) {
    if (!is_empty_sll()) {
        int k = 1, size = size_sll(); // we don't prepend, so K > 0
        Node* cur = create_node(elm);
        if (!head) {
            head = cur;
        }
        else {
            Node* last = head;
            if (i > 1 && i < size) { //  1 < i < size | 1:prepend, n:append
                while (k != i) {
                    k += 1;
                    last = last->next;
                }
                cur->next = last->next;
                last->next = cur;
            }
            else {
                printf("Out of Index");
            }
        }
    }
}

void delete_sll(int elm) {
    int n = size_sll();
    Node* node = head;
    if (head->data == elm) {
        head = head->next;
        free(node);
    }
    else {
        Node* prev = head;
        for (int i = 0; i < n; i++) {
            if (node->data != elm) {
                prev = node;
                node = node->next;
            }
            else {
                break;
            }
        }
        prev->next = node->next;
        free(node);
    }
}

int search_sll(int elm) { //O(n)
    if (!is_empty_sll()) {
        int i, n = size_sll();
        Node* last = head;
        for (i = 0; i < n; i++) {
            if (last->data != elm) {
                last = last->next;
            }
            else {
                break;
            }
        }
        return i;
    }
}

void swap_sll(int i, int j) {//O(n) --swap value of position i with j
    Node* node_i = node_k_sll(i);
    Node* node_j = node_k_sll(j);
    int temp = node_i->data;
    node_i->data = node_j->data;
    node_j->data = temp;
}

void print_sll() {
    Node* trav = head;
    while (trav) {
        printf("%d ", trav->data);
        trav = trav->next;
    }
    printf("\n");
}

void reverse_sll() {
    if (!is_empty_sll()) {
        Node* prev = head;
        Node* cur = head->next, * next_node = cur;
        while (next_node) {
            next_node = cur->next;
            cur->next = prev;
            prev = cur;
            cur = next_node;
        }
        head->next = next_node;
        Node* temp = head;
        head = tail;
        tail = temp;
    }
}

//void reverse_sll() {
//    Node* prev = NULL, *cur = head, *next;
//    while (cur) {
//        next = cur->next;
//        cur->next = prev;
//        prev = cur;
//        cur = next;
//    }
//    head = prev;
//    Node* temp = head;
//    head = prev;
//    prev = temp;
//}

void clear_sll() { //O(n)
    while (head) {
        Node* temp = head;
        head = head->next;
        free(temp);
    }
    printf("List Cleared!\n");
}

Node* get_tail() {
    // Node* tail = head;
    // while (tail->next != NULL) {
    //     tail = tail->next;
    // }
    return tail;
}

void rotate_sll(int k) {
    int size = size_sll();
    Node* tail = get_tail();
    Node* k_node = node_k_sll(k);
    tail->next = head;

    for (int i = 0; i < size; i++) {
        printf("%d ", k_node->data);
        k_node = k_node->next;
    }
    tail->next = NULL;
    printf("\n");
}

void pop_front_sll() {
    Node* node = head;
    head = head->next;
    free(node);
}

void pop_back_sll() {
    int size = size_sll();
    int elm = node_k_sll(size - 1)->data;
    delete_sll(elm);
}

// void sort_sll() {// //different algorithms

// }

int main() {
    prepend_sll(-13);
    append_sll(1);
    append_sll(2);
    append_sll(4);
    print_sll();
    insert_sll(3, 2);
    print_sll();
    prepend_sll(0);
    print_sll();
    printf("size: %d\n", size_sll());
    printf("index of 3 is: %d\n", search_sll(3));
    delete_sll(2);
    print_sll();
    swap_sll(0, 1);
    print_sll();
    reverse_sll();
    print_sll();
    append_sll(0);
    append_sll(-1);
    print_sll();
    rotate_sll(2);
    pop_front_sll();
    print_sll();
    pop_back_sll();
    print_sll();
    clear_sll();
    print_sll();
    return 0;
}

\$\endgroup\$
4
  • 3
    \$\begingroup\$ Comments have been moved to chat; please do not continue the discussion here. Before posting a comment below this one, please review the purposes of comments. Comments that do not request clarification or suggest improvements usually belong as an answer, on Code Review Meta, or in Code Review Chat. Comments continuing discussion may be removed. \$\endgroup\$
    – Mast
    Feb 12, 2023 at 17:19
  • 1
    \$\begingroup\$ Please do not edit the question, especially the code, after an answer has been posted. Changing the question may cause answer invalidation. Everyone needs to be able to see what the reviewer was referring to. What to do after the question has been answered. \$\endgroup\$
    – pacmaninbw
    Feb 12, 2023 at 18:50
  • \$\begingroup\$ @pacmaninbw yes, I got to know that yesterday. I will post the updated one in a separate question referring to this one. \$\endgroup\$
    – V_head
    Feb 12, 2023 at 18:54
  • \$\begingroup\$ We have a tool that spots edits that may invalidate answers, this question showed up just now. \$\endgroup\$
    – pacmaninbw
    Feb 12, 2023 at 18:55

2 Answers 2

3
\$\begingroup\$

What to mention first? I'll start with interface taking name decoration (xyz_sll) as an indication of trying to create something usable in separate "compilation units".

Interface design is not an easy undertaking.
You can sidestep the issue and implement an existing interface.
With C, the options are somewhat limited:
"Collection" interfaces lend themselves very well to OO modelling.

Interfaces need documentation!
In the code: look how the description for rotate_sll() ended up not included in above question. In C, the definition of an interface belongs in a header file.

Tests are valuable. Include them in your questions - where I present a part of the code (for convenience&reference) that I don't want reviewed, I'd state that above and put the code block in a block quote.

If it is nice to have a list, it got to be nicer to have more than one:
The global variable head doesn't do.
Define a type List and pass a value to each and every function but create_sll();

I'm with your choice to not have nodes visible on the client side of the interface. It would necessitate more functions and limit implementation choices.
(Keep "global non-client names" to a minimum: declare e.g. create_node() & get_tail() static. Maybe move main() to a separate compilation unit - this would raise the question just where to put "debug support". (Java&Python put some in the main Object contract: toString()/str().))

size_sll() is "the other function" that would benefit from being kept instead of re-established. The other one is get_tail().

Keeping tailup-to-date looks quite a chase without a decent set of (automated!) tests in place:
Currently, pop_back_sll() fails to update it.

Keeping size instead looks a bit simpler - and helps get_tail() a bit: you can use a "counting loop" instead of checking next. You still need to "chase" all those pointers.

There is a memory leak in insert_sll() when size < i.

delete_sll() does not check if the node deleted equals tail.

(I prefer find over search.)


I see one big problem with the interface so far:
How will a client use a list?

Establish size and use a (missing) get_sll(int position)?
Define a function apply_while_sll(int *(handler(int item_value)) to call handler() with every item's value in turn until it returns false?

\$\endgroup\$
6
  • \$\begingroup\$ thanks, I will take up your remarks and update the code in another post \$\endgroup\$
    – V_head
    Feb 12, 2023 at 18:23
  • \$\begingroup\$ I didn't get that insert_sll has a memory leak when size < i, I have this if there if (i > 1 && i < size) unless you mean when I want to insert at the place of tail, is that what you mean? \$\endgroup\$
    – V_head
    Feb 12, 2023 at 18:48
  • \$\begingroup\$ When you print "Out of Index", you have allocated a node. You don't attach it. You don't return it. You don't free() it: It is no longer accessible, its memory is leaked. \$\endgroup\$
    – greybeard
    Feb 12, 2023 at 18:55
  • \$\begingroup\$ you mean it should be like this else { free(last); printf("Invalid i");} \$\endgroup\$
    – V_head
    Feb 12, 2023 at 19:17
  • \$\begingroup\$ I'd "instantiate" when i checks okay, rather. \$\endgroup\$
    – greybeard
    Feb 12, 2023 at 20:59
3
\$\begingroup\$

General Observations

It isn't clear that you understand the usage of singly linked lists, in some cases this looks more like an array implementation than a linked list implementation. Indexing into linked lists is slow and generally not done. The search_sll() function returns an index into the linked list rather than a pointer to a node. This really doesn't make sense. Most of the functions that call Node* node_k_sll(int k) are not O(n) because they may loop through the list more than one time. The error message Out of Index makes no sense in terms of a linked list, and in most cases this should be Index out of Range. Generally one doesn't care about the size of a linked list, so the function int size_sll() might be considered an anti-pattern.

Since this code is using Global Variables the code is not reusable than that breaks a lot of programming principles.

The link provided by @DavidC.Rankin is a good reference.

Unit Testing

The unit testing is insufficient, it doesn't test for behavior on failure. One example is the function int search_sll(int elm), currently if the linked list is empty this function has unknown behavior since there is no else clause and no default return value. To test for failure on this function place this line at the beginning of main():

printf("index of 3 is: %d\n", search_sll(3));

on my computer that function returns 1, I believe that value is incorrect.

Functions That Don't Make Sense

Since there are no PUSH functions the functions void pop_front_sll() and void pop_back_sll() don't make sense. There would need to be corresponding functions void push_front_ssl(ARG) and void push_back_ssl(ARG). I would only expect to see this functions if the linked list was being used to implement a stack or a queue.

DRY Code

There is a programming principle called the Don't Repeat Yourself Principle sometimes referred to as DRY code. If you find yourself repeating the same code multiple times it is better to encapsulate it in a function. If it is possible to loop through the code that can reduce repetition as well.

The functions void delete_sll(int elm) and void insert_sll(int elm, int i) can be implemented using search_sll() function. this would remove the repeated code. There is possibly a bug in delete_sll() since it doesn't check to see if the node as found.

Missing Error Reporting

The function Node* create_node(int elm) may terminate the program without informing the user, this is a big problem.

As a side note, while Node* create_node(int elm) uses EXIT_FAILURE when the program terminates with error, the main() program returns 0 rather than EXIT_SUCCESS. this code was replaced before I posted my answer

\$\endgroup\$
1
  • \$\begingroup\$ Thanks, valuable remarks, indeed, I am preparing this list and its doubly version to be used as generically as possible to be used for stacks and queues \$\endgroup\$
    – V_head
    Feb 12, 2023 at 19:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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