Why do i suck at C?

Development Code
1

Hey guys, im working on a C project at school that needs me to make a linked list of the names of my friends, there is always an error after i enter one name into this code

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


    typedef struct Node{
      char name[20];
      struct node *next;

    }Node, *NodePtr;

    typedef struct{
         NodePtr first, np, last;
    }LinkedList;


    void printList(NodePtr np){
    while(np!=NULL) {
        printf("%s, /n", np->name);
        np=np->next;
          }
 }

    NodePtr makeNode(char inputName[20]){
    NodePtr np= (NodePtr) malloc(sizeof(Node));

    strcpy(np, inputName);
    np->next=NULL;
    return np;
    }

    int main() {
    char names[20];
    LinkedList ll;

    ll.first = NULL;

    printf("enter teh namez of yo friends dawg\n");
    scanf("%s", &names[20]);
    while (names != "end") {

        ll.np = makeNode(names); // create a new node containing n
        if (ll.first == NULL) {
            ll.first = ll.np;
        } else {

            ll.last->next = ll.np;

            ll.last = ll.np;


            scanf("%s", &names[20]);

        }




    }
    printList(ll.first);
    }

Any help with debugging this would be great :)

Thanks!

2

I'm on my phone and can't test the code,
But right at the top you have,

struct node *next;

Shouldn't it be "Node"?

4 Likes
3

Awww, I was expecting this to be a word post. I was going to give a philosophical answer. Sorry that I can't help :/

4

That's where the error comes from. To be exact, it's called a segmentation fault. This means that your program is trying to access memory, that it wasn't allowed to access.

In your case, this is because you try to dereference (the ->), and therefore access, ll.last which hasn't been initialized before, which means that it's default initialized with NULL and NULL by definition can't be accessed by any program.

You can do a first step yourself and try a debugger like gdb: https://www.cs.umd.edu/~srhuang/teaching/cmsc212/gdb-tutorial-handout.pdf

3 Likes
5

The other reason this is bad is that it's a linked list. A linked list is inferior in every way to an array. Just use an array and resize it. Write your own vector implementation if you want to encapsulate that.

"But a linked list has O(1) insertion complexity!"

Yea, but where are you going to insert exactly? To insert into a Linked List you have to walk it to find the insertion point. At some point, you always have to walk the list. There is no use in an un-walked list because it could only ever store one member.

Walking a linked list is O(n) complexity (worst case) so that might not seem so bad, however, complexity is not performance. A linked list will always perform worse than an array because of contiguous memory read-write performance and CPU level caching. Just use an array.

"But resizing an array means copying all its memory. That's got to be worse!"

Probably not. Copying a contiguous chunk of memory is normally better than walking memory in a random order.

"But... but... but my computer science degree!"

The CPU doesn't care. It's a very complicated bit of metal, and it doesn't hand out favours to those who want to implement poor memory management models.

Rant over. Sorry about that I get triggered by linked lists. I know it's your schools fault, not yours.


Addendum:

  • An array may consume enough memory to perform worse than a very small linked list if you store types that differ wildly in size. E.G. A few gigantic and a few small nested arrays that aren't stored as pointers.
  • A linked list can get similar performance to an array by using memory pooling. Memory pools are arrays. This is the computer science equivalence of lying to yourself. That said memory pooling is the best way to implement a linked list with any relevant number of elements within it.
6

That's beside the point. His task was to implement a linked list.

7

Yes, I said I knew it was his school's idea in my post.

Sure, this isn't a direct response to his question. His school is probably trying to teach algorithms and data structures 101. I think my response is still warranted, it's nice to pretend for a while but I've got my doubts that the school would come back to reality and point out just what a terrible idea it is to use linked lists. There really is such a minimal application for this data structure that I worry the wrong lessons are being learned.

8

I can't speak for his school, but my college gave an overview over all popular data structures and evaluated what drawbacks each of them has.
But I do remember having to implement a linked list in Java too. ;-)

9

My teacher said don't use strings as the keys to Dictionary<TKey, TValue> (C#) because 'it would be too slow'. Just to give an indication of my experience with what my teachers knew about performance. I was also once told that concurrent solutions are always faster than serialised solutions for everything.

10

Thank you for the advice Ill check out the debugging pdf

:)

2 Likes
11

Wouldnt Copying an array into a larger array create a different data structure called an array list?

Also this entire coursed is based on linked lists and linked stacks, linked queues etc. When discussing this idea professor was talking about how using a Linked List and that it "avoids segfaults" which i find a dubious claim in my testing...

12

@Eden thank you for formatting my code <3

13

Yes, you could call an expanding array an 'array list'. The C++ standard library calls it vector (as I eluded to in my post).

No data structure "avoids segfaults" so I don't know what he intended with that comment or what the context was. Linked data structures I would argue are good practice for writing code that does avoid segfaults since you will get practice messing around with pointers. A better structure for that, however, would be a graph.

Graphs are utterly terrible for performance and memory consumption, so why would you ever use a graph? You'll find that the only places graphs are used are in algorithms that utilise their structure. The most simplisitc example are tree-based data structures such as maps. Trees are much easier to make a case for, however, so my preferred example of this would be a neural network. Of course, neural networks are rarely written against graphs implemented via linked nodes. It is expected that memory pooling is used and usually some structural patterns are baked right into the algorithm.

You could implement a graph via linked nodes and in your position, this would be an excellent way to gain brownie points from your prof if you're into that. Particularly if you implement traversal patterns, cycle detection (I.E. a graph that can figure out if it's a tree or not), a basic XOR solving neural network, or a finite state machine with it.

The primary problem you'll run into is that graphs have an arbitrary number of links for each node. This is a rather entertaining challenge to solve in C if you've never run into it before.