Brushing up C part 5-data structure

In my previous blog brushing up C part 4 , we discussed common uses of pointers. We’ll be taking up a few data structures  in this blog.

1. What is data structure?

In simplest words, any structure holding data is data structure . Or data arranged in a format such that it can be used conveniently. It can be a file, array, data base table, accounts in your balance sheet ☺️ . In terms of C, we can add linked lists and  trees to the definition of data structures.

2. Common data structures functions

Almost all data structures have some functionality in common.The common uses are

  1. Insertion: when we add an element to a new or existing DS, it is called insertion. This is mainly used at the time of creation of storage, or when some new item enters the system. 
  2. Deletion: when an item is removed from a DS, its called deletion. For eg, when a user exits a system, his information can be deleted from the record.
  3. Search: This is the most extensively used function. Generally, an entry is added or deleted selectively. Whereas, search is done very rigorously.

In our implementation, we’ll be using dynamic memory allocation for creating space for data.

    3. Linked list

    In simple English, list means a collection of items. A linked list is a collection of items, where items have some way of remaining connected with each other. In linked list, the connection is made using pointers.

    For Eg, a line of kids crossing the road. Each kid holds the front kid with his hand to remain connected. A pointer in a linked list is akin to that connection ☺️ .

    struct node{

    int data;

    struct node *next;

    };

    Here, next is that connection, which points to the next element of the list.

    Memory is allocated as

    struct node *head=(struct node *)malloc(sizeof(struct node));

    head->data = value;

    head->next=NULL;

    More elements are added by allocating memory for them, and assigning the next element of existing node to them.

    struct node *newnode=(struct node *)malloc(sizeof(struct node));



    head->next = newnode;

    newnode->next = NULL;


    4. Diagramatic Representation

    Data

    ⬇️

    ⬇️

    ⬜️⬜️➡️➡️➡️➡️➡️➡️➡️⬜️⬜️➡️➡️➡️NULL

    ⬆️.                  ⬆️                    ⬆️

    ⬆️.                ⬆️.                   ⬆️

    head           next                    newnode

    • Insertion: create a new node, assign the next pointer of the existing node to the new node. Make the next pointer of the new node NULL. 
    • Deletion: assign the next pointer of the node before to the node after the node to be deleted. Free the memory that was assigned to the node deleted.
    • Search: start from the head of the list, traverse all nodes using their next pointers. Look for a match of the data value at those nodes. Stop traversal once match is found.

        4. Stack

        If you have ever piled newspapers, you keep adding one by one on top. And you take out the topmost when you need an old one. This is a stack structure.

        In terms of data structures and linked list, a stack has these operations:

        • Push : adding elements on top.
        • Pop: removing the topmost element.
        • Count: counting the total number of elements in the stack.

        The implementation is derived from the linkedlist logic described above. We need a few more pointers to keep a record of the top of the stack.
        5. Queue

        As the name suggests, like in any normal queue, the first element to enter is the first to come out. Like while standing in a queue for collecting tickets ☺️ .

        Operations are

        • Insertion/push: Adding elements to the top
        • Deletion/pop: Removing the oldest element, the element that was added in the beginning.

        Summary

        Friends, here I end this blog on linked lists and its derivatives. In my next blog, I will be taking up Binary Trees ☺️ . 

        Happy learning .

        My Python tutorial

        2 thoughts on “Brushing up C part 5-data structure

        Leave a Reply

        Fill in your details below or click an icon to log in:

        WordPress.com Logo

        You are commenting using your WordPress.com account. Log Out / Change )

        Twitter picture

        You are commenting using your Twitter account. Log Out / Change )

        Facebook photo

        You are commenting using your Facebook account. Log Out / Change )

        Google+ photo

        You are commenting using your Google+ account. Log Out / Change )

        Connecting to %s