Data Structures: Linked List with C

If you’re learning to program, linked list is one of the most basic data structures that you can learn! This week, I’ll be showing you how to work with doubly linked lists using C programming.

What is a linked list?

Simply put, a linked list is a sequence of nodes that contain data and a reference point to the next node in memory. There are many different variations of linked lists with different capabilities that may better fit different use cases, but in this blog post I’ve created a doubly linked list. This code is mostly based on the python equivalent that I made a few weeks ago. You can read it here!

Code

	#include <stdio.h>
	#include <stdlib.h>
	struct Node {
	int data;
	struct Node* next, *prev;
	};
	struct LinkedList {
	struct Node* head;
	int size;
	};
	struct Node* createNode(int data) {
	/*
	Creates a new node with the provided data.
	*/
	struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
	newNode->data = data;
	newNode->next = NULL;
	newNode->prev = NULL;
	return newNode;
	}
	void push (struct LinkedList** ll, int data) {
	/*
	Pushes a new node behind the linked list's head node.
	*/
	struct Node* newNode = createNode(data);
	if ((*ll)->head == NULL) {
	(*ll)->head = newNode;
	} else {
	newNode->next = (*ll)->head;
	(*ll)->head->prev = newNode;
	(*ll)->head = newNode;
	}
	(*ll)->size += 1;
	}
	void append (struct LinkedList** ll, int data) {
	/*
	Append a new node to the end of the linked list
	*/
	struct Node* newNode = createNode(data);
	if ((*ll)->head == NULL) {
	(*ll)->head = newNode;
	} else {
	struct Node* currentNode = (*ll)->head;
	while (currentNode->next != NULL) {
	currentNode = currentNode->next;
	}
	currentNode->next = newNode;
	newNode->prev = currentNode;
	}
	(*ll)->size += 1;
	}
	int getValueAt(struct LinkedList** ll, int index) {
	/*
	Returns the value of a node at the given index.
	If node does not exist, program will exit.
	*/
	if (index >= (*ll)->size || index < 0) {
	printf("Index %d does not exist in size %d linked list! Exiting…\n", index, (*ll)->size);
	exit(-1);
	}
	struct Node* currentNode = (*ll)->head;
	while (index != 0) {
	currentNode = currentNode->next;
	index -= 1;
	}
	return currentNode->data;
	}
	int removeNodeAt(struct LinkedList** ll, int index) {
	/*
	Removes a node at the provided index.
	If node does not exist, program will exit.
	*/
	if (index >= (*ll)->size || index < 0) {
	printf("Index %d does not exist in size %d linked list! Exiting…\n", index, (*ll)->size);
	exit(-1);
	}
	struct Node* currentNode = (*ll)->head;
	int removedData = 0;
	while (index != 0) {
	currentNode = currentNode->next;
	index -= 1;
	}
	removedData = currentNode->data;
	if (currentNode->prev == NULL && currentNode->next == NULL) {
	(*ll)->head = NULL;
	free(currentNode);
	} else if (currentNode->prev == NULL && currentNode->next != NULL) {
	struct Node* temp = currentNode;
	(*ll)->head = currentNode->next;
	(*ll)->head->prev = NULL;
	free(temp);
	} else if (currentNode->prev != NULL && currentNode->next == NULL) {
	struct Node* temp = currentNode;
	currentNode->prev->next = NULL;
	free(currentNode);
	} else if (currentNode->prev != NULL && currentNode->next != NULL) {
	struct Node* temp = currentNode;
	currentNode->prev->next = currentNode->next;
	currentNode->next->prev = currentNode->prev;
	free(currentNode);
	}
	(*ll)->size -= 1;
	return removedData;
	}
	void clear(struct LinkedList** ll) {
	/*
	Removes all nodes from the linked list
	*/
	struct Node* currentNode = (*ll)->head;
	while (currentNode != NULL) {
	(*ll)->head = (*ll)->head->next;
	free(currentNode);
	(*ll)->size -= 1;
	currentNode = (*ll)->head;
	}
	}
	void printList(struct LinkedList** ll) {
	struct Node* currentNode = (*ll)->head;
	printf("Size %d: ", (*ll)->size);
	while (currentNode != NULL) {
	printf("%d ", currentNode->data);
	currentNode = currentNode->next;
	}
	printf("\n\n");
	}
	int main() {
	// Initialize an empty linked list
	struct LinkedList* linkedList = (struct LinkedList*)malloc(sizeof(struct LinkedList));;
	linkedList->head = NULL;
	linkedList->size = 0;
	printf("Appending 1, 2, 3 to the linked list\n");
	append(&linkedList, 1);
	append(&linkedList, 2);
	append(&linkedList, 3);
	printList(&linkedList);
	printf("Pushing 4, 5, 6 to the linked list\n");
	push(&linkedList, 4);
	push(&linkedList, 5);
	push(&linkedList, 6);
	printList(&linkedList);
	printf("Getting some values from linked list\n");
	printf("Index 0: %d\n", getValueAt(&linkedList, 0));
	printf("Index 3: %d\n", getValueAt(&linkedList, 3));
	printf("Index %d: %d\n", linkedList->size–1, getValueAt(&linkedList, linkedList->size–1));
	printf("\nRemoving some values from linked list\n");
	printf("Removing Index 0: %d\n", removeNodeAt(&linkedList, 0));
	printList(&linkedList);
	printf("Removing Index %d: %d\n", linkedList->size – 1, removeNodeAt(&linkedList, linkedList->size – 1));
	printList(&linkedList);
	printf("Removed Index 1: %d\n", removeNodeAt(&linkedList, 1));
	printList(&linkedList);
	printf("Clearing linked list\n");
	clear(&linkedList);
	printList(&linkedList);
	}

view raw LinkedList.c hosted with ❤ by GitHub

Running Code

gcc ./LinkedList.c -o LinkedList; ./LinkedList

Conclusion

As I previously mentioned, there are many different ways to create a linked list. My provided example is just one of many that you can find on the internet. I just hope that somebody out there can find my example useful in some way.

If you found this post interesting, please consider following my blog here on WordPress where I have many other posts like:

• Data Structures: Linked List with Python
• VulnHub: Jangow 1.0.1 Writeup
• Hosting a Website with Github Pages
• Creating a Python Bot with Selenium
• Asynchronous Server/Client with Python
• Hack The Box: Impossible Password

Feel free to also follow me via my other social media accounts: Instagram, Twitter, Facebook, and Medium!

As always, if you liked what you read and you’d like to support me, please consider buying me some coffee! Every cup of coffee sent my way helps me stay awake after my full-time job so that I can produce more high quality blog posts! Any and all support would be greatly appreciated!