Algorithm to create a single linked list

Creating a singly linked list means reading values repeatedly, making a node for each one and attaching it at the end. We keep start (first node) and last (current last node).

Algorithm CREATE

1. Set start = NULL, last = NULL.
2. Repeat until the user stops (e.g. enters -1):
   1. Read item x.
   2. Allocate a new node p; if allocation fails print "no memory" and stop.
   3. Set p->info = x and p->next = NULL.
   4. If start == NULL: start = p (first node); else last->next = p.
   5. Set last = p.
3. Return start.

Input 10, 20, 30
Step1: start -> [10|NULL]                 last = 10
Step2: start -> [10|*]->[20|NULL]         last = 20
Step3: start -> [10|*]->[20|*]->[30|NULL] last = 30

C implementation

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

struct node { int info; struct node *next; };

struct node *create(void) {
    struct node *start = NULL, *last = NULL, *p;
    int x;
    printf("Enter numbers (-1 to stop): ");
    while (scanf("%d", &x) == 1 && x != -1) {
        p = (struct node *)malloc(sizeof(struct node));
        if (p == NULL) { printf("No memory\n"); break; }
        p->info = x;
        p->next = NULL;
        if (start == NULL) start = p;     /* first node */
        else last->next = p;              /* attach at end */
        last = p;
    }
    return start;
}

void display(struct node *start) {
    for (struct node *p = start; p != NULL; p = p->next)
        printf("%d -> ", p->info);
    printf("NULL\n");
}

int main(void) {
    struct node *head = create();
    display(head);
    return 0;
}

Keeping the last pointer makes each insertion O(1), so creating n nodes costs O(n).