Programming - C Linked Lists

in #programming5 years ago (edited)

   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 do
nn->Data = value;
// we set the next pointer to NULL
nn->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!

Sort:  

@drifter1
Nice Job!
Keep the good work up!
Thanks for sharing

Thank you qagiri!
I will, for sure :)

Coin Marketplace

STEEM 0.22
TRX 0.06
JST 0.025
BTC 19602.84
ETH 1329.30
USDT 1.00
SBD 2.45