In today's post we will talk about Linked Lists in C Language. I will show you how to create a List, insert and remove an Item. Also, how to search for a specific Item in the List and we will also do some more advanced stuff that includes printing in normal and reverse order using recursive algorithms that are pretty simple if you get the hang of it. So, without further do, let's start out with the representation in Code of an List.
List Representation:
An List is an Data Structure that can be of infinite length were an Item called head points to another item in the list, that points to another item and so on... Every item contains a pointer to the next Item and Data that can be everything. So, an List in C is an struct that is defined like that:
typedef struct Node{ //DATA struct Node *next; //pointer to next Item}Node;Every Item is a Node of the List. We store the Pointer to the first Item in memory in our function so that we can afterwards use it in another variable called current_pointer, without losing it to get the information of all of our Nodes. So, the main function will use an Node of this kind initialized to NULL:
Node *head = NULL;Let's now talk about functions that will do stuff on our List like: insert, remove, search, sort, print.
Insert:
For inserting we will use an Item called new_node or nn that will temporary store our new Node and that we will afterwards insert to our List to the front or rear. This Item will be created using the memory allocation function malloc() for dynamic memory allocation that we already know and because it is a struct we will then access each member of the struct using the '->' modifier. We use an arrow instead of the dot, because we are now going to member's of an struct pointer! So, our new_node Code will look like this:
Node* nn;nn = (Node*) malloc (sizeof(Node));// for every Data Variable we donn->Data = value;// we set the next pointer to NULLnn->next = NULL;When inserting we always make sure if it is the first Item inserted, checking if our List is NULL that means it is empty.
Insert at Front:
Inserting to the front is pretty simple cause we simply set our next pointer to head and afterwards set the nn to by our new head like this:
Node *insertFirst(Node *head, int val){ Node *nn; // create our new node nn = (Node*)malloc(sizeof(Node)); nn->val = val; nn->next = NULL; // check if list is empty if(head == NULL){ // return pointer to nn return nn; } // set head to by our next pointer nn->next = head; // return pointer to nn return nn; }Insert at Rear:
To insert in the rear we have to go to our last Item using a current_node checking if the next pointer is NULL and setting the next to our new_node like this:
Node *insertLast(Node *head, int val){ Node *nn, *cur; // create our new node nn = (Node*)malloc(sizeof(Node)); nn->val = val; nn->next = NULL; // check if list is empty if(head == NULL){ // return pointer to nn return nn; } // set cur to point to our list cur = head; //use a while loop to find the last Item while(cur->next != NULL){ // set cur to next Item cur = cur->next; } // next of last Item will be our new node cur->next = nn; // return head return head; }To insert in a Specific location in between you have to first search the Item after it should be inserted. You can find it out by yourself after I show you searching.
Delete:
To delete an Item we have to check if the List is Empty cause else we will cause an Error.
Delete at Front:
To delete the item in front we simply set the head to it's next pointer like this:
Node* deleteFirst(Node *head){ // check if list is empty if(head == NULL){ // simply return it back after printing printf("Empty List!"); return head; } // return the next pointer return head->next;}Delete at Rear:
To delete in rear we have to find the Item that points to the last Item and set the next pointer to NULL like this:
Node* deleteLast(Node *head){ Node *cur; // check if list is empty if(head == NULL){ // simply return it back after printing printf("Empty List!"); return head; } // check if first Item is the only Item if(head->next == NULL){ // make the list NULL return NULL; } // set cur to point to our list cur = head; // use a while loop to find the Item that points to our last Item while(cur->next->next != NULL){ // set cur to next Item cur = cur->next; } // set the next pointer of it to NULL cur->next = NULL; // return head return head;}To delete a Specific Item in between you have to first search the Item that points to it and afterwards set it's next pointer to be the next pointer of the Item that should be deleted. (that was a mouthful xD). I guess you can do it by yourself after I show you searching that comes next.
Search:
Searching is pretty simple you just loop through all Nodes and check the specific Data value and print if it was found or not, but I will return the Node to make it more interesting. If it returns NULL we know that it was not found. So, the Code will look like this:
Node* searchList(Node *head, int val){ Node *cur; // check if list is empty if(head == NULL){ // simply return it back after printing printf("Empty List!"); return head; } // set cur to point to our list cur = head; // use a while loop to find the Item while(cur != NULL){ // check equality if(cur->val == val){ // return the cur Node return cur; } // set cur to next Item cur = cur->next; } // if not found return NULL return NULL; } Print:
Printing is Last and I will show you how you implement it using recursive algorithms.
Normal Printing:
Normal Printing can be done simple using the concept that I showed you before like this:
void printList(Node *head){ Node *cur; // check if list is empty if(head == NULL){ printf("Empty List!"); } // set cur to point to our list cur = head; //use a while loop to loop through each Item while(cur != NULL){ //print with -> to make it look like a List printf("%d->",cur->val); // set cur to next Item cur = cur->next; } printf("NULL\n"); }But, to make it more interesting let's show it with an recursive function too. The Code will check emptyness as an stop condition and afterwards print the value and recall with next pointer like this:
void printList(Node *head){ // check if list is empty if (head == NULL){ // stop condition printf("NULL\n"); return; } //print with -> to make it look like a List printf("%d->", head->val); // call again using next pointer printList(head->next);}As you can see the Code is much smaller and when you know to use recursion you can create more advanced functions that do more complicated stuff that will be a pain using non-recursive functions.
Reverse Printing:
For reverse printing we use the same Code but we switch places of printing and recalling! So simple:
void reversePrintList(Node *head){ // check if list is empty if (head == NULL){ // stop condition printf("NULL"); return; } // call again using next pointer reversePrintList(head->next); //print with <- to make it look like a List printf("<-%d", head->val);}
Off course, you can do more stuff like sorting, but what I told you here is I think more than enough to start out using Lists in C. A simple programm that uses all off those functions is tha following:
Code:
int main(){ // the head is initialized as NULL first Node *head = NULL; // insert 5 first and print list head = insertFirst(head, 5); printList(head); // insert 6 last and print list head = insertLast(head, 6); printList(head); // insert 3 last and print list head = insertLast(head, 3); printList(head); // search for 5 Node *search; search = searchList(head, 5); // if not found if(search == NULL){ printf("Not Found!\n"); } else{ printf("%d was Found!\n", search->val); } // print in reverse order reversePrintList(head); }I don't included the structs and stuff cause I told you how you set the up before. Also, this is the end of today's post. Hope you enjoyed it and next time prepare for Trees in C!