In a pervious section we looked at arrays. That was our first data structure in C.
Arrays are great for many things. They provide us with instant access to any element, all you need to know is the location within the array and then boom! You access it with the [] operator. You can instantly insert a new item into this element, or you can print the value. Regardless of the action, the big advantage is instant access.
However, consider the popular procrastination site, Facebook.
Facebook needs to store user profiles.
Users actively activate new profiles and old accounts may be deleted.
Naturally, to create our own Facebook, we would need some method of storing all these profiles. Naturally, you would consider storing them in an array. Each element of the array could be a pointer to a struct. Within the struct you can store a user’s name and other personal information users decide to enter; social security number, date of birth, etc.
The problem with using an array is how do you control how many profiles can be entered? When you build the array you will have a fixed size, to make it larger, you would have to build a new array with the new size, and copy across each element. This is an inefficient method.
A better solution would be to use a new data structure called the Linked List.

The linked list is essentially a chain of structs, connected by pointers, existing entirely on the heap. Elements of a linked list are called nodes. The pointer to the beginning of the linked list is called the head;. You mark the end of the linked list by having the very last pointer, point to NULL.
Let’s take a look at our node struct.

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

Here is what a typical linked list would look like. You have the first pointer to the start of the linked list called head. Each element of the list, called a node, contains some “key” which can be anything. I’m just using an integer in my example, however when you design your own linked list, this can be a pointer to some other structure, it can be an array, it can be multiple integers and a string. It’s entirely up to you what data the node holds internally.
Finally, each node holds a pointer to the next node. The reason I call this struct node pointer “next” is to make the code for linked list functions more intuitive to read. This will be more clear when we write out linked list traversal, insertion, deletion and other useful functions.
Finally, the very last node in the list points at NULL. In the diagram below the “ground” symbol from electronics is used to denote NULL.

Side note: It’s worth mentioning that this is more specifically called a signally-linked-list. Due to the fact that each node only has a single pointer to the next element. There also exists a doubly-linked-list where each node has one pointer to the next node, and one pointer to the previous node.

Building a List
Let’s write a function that will create a new linked list for us.

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

Here is the struct we will use. Each node will store an integer value, and a pointer to the next node.
Let’s write out our first function to create a node.
The steps are very straightforward for this.
As previously mentioned each node has an integer value and node pointer to the next node.
Inside our function we declare a node pointer, we use malloc to reserve space on the heap for one node and assign that to our new pointer.
We need to pass this function an integer. This is what we will assign to value.
For the next node pointer, we assign it to NULL, and simply return our new node pointer.
Let’s see the code.

Node* Create_Node (int data)
{
	Node* new_node;
	new_node = (Node*)malloc(sizeof(Node))
	new_node -> value = data;
	new_node -> next = NULL;

	return new_node;
}

Note: One issue that can come up with dynamic allocation is running out of memory. If we use up the entire heap (not realistically likely to happen) malloc will return NULL. To protect against this edge case, we can slightly modify our code by writing our malloc statement as the following:

	if(!(new_node = (Node*)malloc(sizeof(Node))))
		return NULL;

This will check to see if malloc returned NULL, if so, it returns NULL automatically, otherwise, just continues like normal.
Thus, the new version of this function can be written like so:

Node* Create_Node (int data)
{
	Node* new_node;
	if(!(new_node = (Node*)malloc(sizeof(Node))))
		return NULL;
	new_node -> value = data;
	new_node -> next = NULL;

	return new_node;
}

Okay, moving on, let’s write a function that will use this create_node function we just wrote to insert nodes into a linked list.
We need to pass this function a pointer to the beginning of the linked list, called head, and an integer.
Inside the function, we declare a new node pointer, and we call our create_node function to build a new node with the integer argument. The “next” pointer of this node gets assigned to head, and finally return the pointer to it.
Let’s see the code.

Node* Insert_At_Start(Node* head, int data)
{
	Node* pNode;
	pNode = Create_Node(data);
	pNode->next = head;

	return pNode;
}

The 2 functions above can be combined into 1 function, if you wish, you can do both operations together like so:

Node* InsertNode(Node* head, int n)
{
	Node* pNode;
	if(!(pNode = (Node*)malloc(sizeof(Node))))
		return NULL; 
	pNode->value = n;
	pNode->next = head;

	return pNode;
}

However, it is preferable to keep them separate due to the fact that the function Create_Node is very useful. Any time we want to do build a new node to use in a different function, we just make a call to this function and pass it an integer. For example, if we want to write a function that only inserts a new node at the end of a linked list. We don’t need to worry about doing malloc and checking for a NULL return anymore, it’s already done for us in the Create_Node function, just use it.

Now, let’s write the function that will prompt a user to enter integers. Each of these integers will be passed into the Insert_At_start function we wrote above to construct our list. If the user enters the digit 0, we terminate.

Node* Read_Values (void)
{
	Node* new_node = NULL;
	int n;
	printf("Enter a number to insert into Linked List: ");
	while(1)
	{
		scanf("%d", &n);
		if(n == 0)
			return new_node;
		new_node = Insert_At_Start(new_node, n);
	}
}

Linked List Traversal
Traversing a linked list consists of 2 operations. Check if our traversal pointer is pointing at NULL (the end of the list) and advancing our pointer.
We advance the pointer by writing ptr->next. Where ptr is our pointer and next is the pointer to the next element.
Let’s look at this example of a function to print all nodes.
Print All
Write a function to iterate through each element in the linked list and print out the values.
Very straightforward. Just loop through, while head!=NULL and print out head->value, after printing advance the pointer with head=head->next
Note that, we don’t need to assign a new pointer to head, we can just move head. This is just a print function, and since we don’t need to return anything, we don’t need to save the beginning of the list, just go through and print everything.

void Print_All(Node* head)
{
	while(head!=NULL)
	{
		printf("%dn",head->value);
		head = head->next;
	}
}

Let’s say we call this function on the linked list in the diagram below.

Say we pass the head pointer to this linked list into our Print_All function above.
First thing that happens is, we check is our head pointing to NULL?

No, head is not pointing to NULL.
Hence we print out head->value, which is 2.
Next, we execute the line head=head->next
head->next is this pointer.

Thus, upon saying head=head->next, this is what will happen.

Now, we check again, is head pointing to NULL?

No, head is not NULL.
Print out head->value. For this node it’s 7.
Now we advance head again.
This is head->next

Thus, executing the line head=head->next gives us this:

Upon checking the while-loop condition again, we observe that head is not NULL.
We can now print head->value which is 5.
Advance head once again.
Our linked list now looks like this:

Check again, is head NULL?
Nope.
We print off head->value which is 9.
Okay, what is head->next now?

Executing the line head=head->next gives us:

So, is head pointing to NULL?
Yes!
Thus, we know that we are finished and have gone through every element of the linked list.
Note that, since head is pointing to the end of the linked list, this function has lost the list. It has no way of going back. This is however not a problem since the head pointer is local to this function. When we return from this function, we get back to our original state where we still have a pointer to the beginning of the list.

Search
Write a function to search for a value inside a list and return true if it’s found.
Basic idea is to advance “head” pointer while it’s not NULL and keep checking head->value, if you find it’s equal to search value return true. If you exit the loop, it means you didn’t find it, thus return false.

bool Search_Linked_List(Node* head, int n)
{
	while(head != NULL)
	{
		if(head->value == n)
			return true;
		head = head-> next;
	}
	return false;
}

Insert At Tail
To insert at the tail (end) of a linked list, we just need to check if head is pointing to NULL already. If so, than make head point to our new node and return head. If head is not NULL, than assign a temp pointer to head, and advance temp until it’s pointing to NULL. When you hit NULL, you know you are at the end of the list. Insert a new node there and return head.
Note, it’s important to assign a temp pointer to head, if we disregard that and just advance head while head is not NULL, we lost the beginning of the list since we have no way of going back.
Let’s see the code.

Node* Insert_At_Tail(Node* head, int n)
{
	Node* new_node = Create_Node(n);

	if(head==NULL)
 		head=new_node;

 	else
 	{
		Node* temp = head;
 		while(temp->next!=NULL)
			temp = temp->next;
	temp->next = new_node;
	}
	return head;
}

As you can see, we first build our new node using the insert value given to us (int n). We than check if head is NULL, if it is we know that’s where we are inserting.
Otherwise, assign a temp pointer to head and move forward until you hit NULL, insert it once you get to NULL, and return the head.

Delete List

Clearing a linked list is a bit more tricky. At first you may think to just call free() on head.
That will just result in the following:

It will free the first node that head is pointing to, however you instantly lose everything that head->next points to, i.e. rest of linked list. To avoid such a memory leak, you want to move along the linked list with 2 pointers. Some temp pointer and head.
Hence, our first line in this function has to be:

Node* temp = head;

Let’s look at the diagram.

Okay, we now have temp and head pointing to the start of the list. Our objective is to delete each node one by one without losing a pointer to the rest of the list.
The way to do this to assign head->next to temp, and free head.
We then assign head to temp.
If that was too confusing, let’s take a look at the diagram.
Here is our head->next pointer. It’s pointing to the node with the value 7.

We need to delete whatever head is pointing to. HOWEVER, we need to keep track of whatever head->next is pointing to, so that we avoid memory leak.
Let’s assign head->next to our temp so that if we delete head, we end up with temp being the new head to our shorter list.
So here is what we have after the line:

temp = head -> next;

Now, temp is like a second “head” to the rest of our linked list. We are thus free to delete whatever head is currently pointing to.
Let’s execute the line:

free(head);

Here’s how it’s going to look:

And done. The first element disappears and we have this new list.

We now assign head back to temp, so that head becomes the head of our new, shorter linked list.
so after the line:

head = temp;

Observe that we are back at the same scenario that we started it after our very first line:

Node* temp = head;

We have a head pointer and a temp pointer, both pointing to the beginning of a linked list.
What this means is that this process of executing the 3 lines:

temp = head->next;
free(head);
head = temp;

Must be an iteration.
We repeat these 3 lines over and over again until our head is NULL. Because when head is NULL, we have reached the end of or linked list and have thus deleted every single node successfully without a leak!
Let’s look at the final code.

void Clear_Linked_List(Node* head)
{
	Node* temp = head;
	while(head != NULL)
	{
		temp = head->next;
		free(head);
		head = temp;
	}
}

Delete Node
To delete a single node from a list we need to pass 2 arguments into our function.
The head of the list, and the “value” we wish to delete.
For our example, each node contains a single integer, thus our function should expect and integer value which we need to search for, find and delete. We then return the head of the new list.
The fact that we need to return the head means that we can’t move it. We need to declare new pointers.
To delete a single node, we will need 2 pointers one pointing to the start (call this prev), the second pointing to the one after it(call this curr), they advance together. Run this loop, checking if the curr pointer is either NULL or curr->value is equal to what we are searching for.
Once we exit this loop, check if what the reason we exited the loop is. If curr is NULL, that means we didn’t find what we wished to delete, it therefor doesn’t exist in the list and we just return head.
If curr->value is equal to what we were searching for, that means we need to delete the node that curr is pointing at.
To delete curr we need to rearrange the pointers such that the node before curr, prev, is pointing to the node after prev (prev->next).

prev->next = curr->next;
free(curr);

After that’s done just return head.
The following diagrams should help make it clear.
Here is the linked list that we start off with. We pass head to our function, and the integer value we wish to remove is 5.

Let’s assign our pointers now.
One called prev points to head.
One called curr points to head->next.

Node* prev = head;
Node* curr = head->next; 

Let’s see what we have.

Let’s check curr.
Is curr pointing to NULL? NO
Is curr->value equal to 5? NO
Advance both and check again.

curr = curr->next;
prev = prev->next; 

Is curr pointing to NULL? NO
Is curr->value equal to 5? YES

We have to delete the node that curr is pointing to.
We first have to perform a small operation called bypass where the prev node of what we wish to delete is assigned to the next node.

prev->next = curr->next;

Let’s see the diagram.
Here is prev->next

Here is curr->next

And thus, executing the line:

prev->next = curr->next;

Gives us the following.

This effectively “bypasses” the node we want to delete.
Now, we have isolated the node we want to delete.
We can free it.

free(curr);

We get the following:

Here is our new list.

We can now return the head to this new list.

return head;

Here is the complete code for the function.

Node* Delete_Node(Node* head, int n)
{
	Node* prev = head;
	Node* curr = head->next; 

	while(curr != NULL && curr->value != n)
	{
		curr = curr-> next;
		prev = prev->next;
	}
	if (curr = NULL)
		return head;
	if(curr->value == n)
	{
		prev->next = curr->next;
		free(curr);
	}
	return head;
}

Reverse A Linked List
This is the trickiest of the linked list functions we’ve looked at and requires some thinking.
We want to take the following linked list:

And reverse it, turning it into this:

To accomplish this task, we need 2 additional pointers besides our head.
We will have one pointer that will start off assigned to NULL called temp. This will be our new head when we are finished.
We will have another pointer called “nxt” that will point to head->next.
Here’s the steps we must follow.

Node* temp = 0;
while(head != NULL)
{
	Node* nxt = head->next;
	head->next = temp;
	temp = head; 
	head = nxt;
}

Let’s see the diagram.
After the first line:
This is only run once at the start of the function and initially sets temp to NULL.

Node* temp = 0;

Okay, let’s get into the loop.
head is not NULL.

Node* nxt = head->next;

We assign a pointer to head->next.
Now, we take head->next

And we assign that to temp:

head->next = temp;

Next step: set head to point to whatever nxt is pointing to.

This completes the first iteration of our loop.
Let’s check if head is NULL, it’s not.
Continue to execute the loop body a second time.

We need to have nxt to point to head->next

Here is head->next, and thus we set nxt to point there.

We now have to set head->next

Point to whatever temp is pointing to.

As you can see, the list is starting to look like what we want. Moving on, we set temp to point to whatever head is pointing to.

temp = head; 

Set head to point to whatever nxt is pointing to.

head = nxt; 

Loop back to the top and check is head NULL? NO.
Go for a third iteration.

Node* nxt = head->next; 

Set nxt to point to whatever head->next is pointing to:

There’s our head->next, now let’s set nxt to point there.

We now run our next line which says take head->next and point that to whatever temp is pointing to.

head->next = temp;

We see head->next from the above diagram, let’s redirect that pointer at whatever temp is pointing to.
Observe:

Now, set temp to point to where head is pointing to.

temp = head; 

Set head to point to where nxt is pointing to.

head = nxt;

Now we check our loop condition. Is head pointing to NULL? No.
Hence, run loop body for a 4th time.

Node* nxt = head->next;

As before, set nxt to point to where head->next is pointing to.

That’s our head->next, let’s assign nxt to point there.

We now want to take head->next and redirect it to where temp is pointing.

head->next = temp;

There is our head->next
Let’s move it to point where temp is pointing.

Next, we set temp to point where head is pointing.

temp = head; 

Now take head, and have it point where nxt is pointing.

head = nxt;

Now, let’s check our loop condition.
Is head pointing at NULL?
Observe:

Yes! Head is NULL
That means we are finished and can return temp.
We have successfully reversed a linked list.
Here is the final code.

Node* reverseLL (Node* head)
{
	Node* temp = 0;
	while(head != NULL)
	{
		Node* nxt = head->next;
		head->next = temp;
		temp = head; 
		head = nxt;
	}
	return temp;
}