A linked list is a collection of struct variables that have attributes that are pointers to other struct variables in the linked list. It differs from a regular array because items in a linked list are not stored right next to each other in memory, so there isn't really an easy way to "index" the items like there is with arrays. However, it is much easier to insert or delete items in linked lists without having to affect the rest of the items.

Linked List Structure

Linked lists use nodes, which are just a struct that contains data and a pointer to another struct. Thus, they follow this structure:

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

Linked List Head

At the beginning of every linked list, you have a node that is defined as the head. This node does not have any data stored in it (or, it could, but it would be useless); instead, the only useful part of it is its pointer to the first node in the list, or NULL (if there are no nodes yet).

Dynamic Linked Lists

We generally do not want to create nodes in a linked list manually or locally in a function, since:

1. It's impractical to create new variable names each time
2. Declaring a node locally in a function means that the node is destroyed once the function finishes being called
3. Deleting a node from a linked list would result in the node still being in memory

Thus, we can dynamically create nodes in a linked list using malloc.

Example:

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

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

int main(void) {
	Node *head;
	Node *newNode = (Node *)malloc(sizeof(Node));
	// initializing a node by allocating some memory in the heap
	newNode->next = NULL;
	head = newNode; // head node is now set to the newNode's address
	
	newNode = (Node *)malloc(sizeof(Node));
	// an entirely new node is initialized at a different address
	newNode->data = 2;
	newNode->next = NULL;

	head->next = newNode; // linking the head ot the new node
	
	free(head->next); // freeing memory because we are responsible
	free(head);
	return 0;
}