Linked List in C Tutorial

linked list c
The linked list is one of simplest data structure after the array.
Characteristics:

  • It’s made up of elements and links;
  • Elements can be of only one type;
  • It can have any number of elements;
  • It can be dynamically increased or decreased;
  • Elements can be inserted anywhere: at the beginning, in the middle or at the end.

C Linked List Implementation

For the example we are going to create a linked list of Person elements.
We want each Person element to hold information regarding name and age.

To create elements we use a struct data type. This will hold our required data and also some extra info:

  • a variable that holds the list size;
  • a pointer to the next list element.

Obviously the pointer is of type Person* because we have a list of persons.

#include <stdio.h>
#include <malloc.h>
#include <string.h>

struct Person {
    int listSize;
    char* name;
    int age;
    struct Person* next;
};

int main() {

    return 0;
}

As you can see above we included some C header files. First is for showing input/output to the console, second is for memory allocation and third contains some functions necessary for string manipulation.

Next, let’s see the function that builds the list. Here is how it works:
 
linked list c image

  1. It creates a new Person using name and age passed as parameters;
    • We use calloc to allocate memory and initialize it to zero;
    • Size of allocated memory is size of string got as parameter (+ 1 for the string terminator char);
    • we then copy the newly allocated string into our Person.
  2. Then, if list is NULL (aka this is the first element)
    • we set the size of the list to one;
    • we return this newly created Person as the list.
  3. Otherwise
    • we create a temp variable that holds the same address as the list. Say the address is: 0x05H
    • we then check if temp->next != NULL;
    • while this condition is true then we say temp = the next Person element;
    • obviously when we reach the last element the condition is no longer true;
    • we then set the newly created node as the next element of the currently last node.
struct Person* addNode(struct Person* list, char* name, int age) {
    struct Person* newPersonNode = (struct Person*)calloc(1, sizeof(struct Person));
    newPersonNode->name = (char*)calloc(strlen(name) + 1, sizeof(char));
    strcpy(newPersonNode->name, name);
    newPersonNode->age = age;

    if (list == NULL) {
        newPersonNode->listSize = 1;
        return newPersonNode;
    } else {
        struct Person* temp = list;
        while (temp->next) {
            temp = temp->next;
        }
        temp->next = newPersonNode;
        list->listSize++;
        return list;
    }
}

Please see my video further explaining how a linked list is built.

Lastly, a function that displays the linked list. The iteration mechanism is same as above.

void printList(struct Person* list) {
    struct Person* temp = NULL;
	for (temp = list; temp != NULL; temp = temp->next) {
		printf("%s, age: %d\n", temp->name, temp->age);
	}
}

And the main() method:

int main() {
    struct Person* list = NULL;
    list = addNode(list, "mike", 23);
    list = addNode(list, "joe", 54);
    list = addNode(list, "sam", 30);
    list = addNode(list, "john", 28);

    printf("List size is: %d\n", list->listSize);
    printList(list);

    return 0;
}

If we run this we get:

List size is: 4
mike, age: 23
joe, age: 54
sam, age: 30
john, age: 28

Process returned 0 (0x0)   execution time : 0.273 s
Press any key to continue.
FacebookTwitterLinkedin