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
- 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.
- 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.
- 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 *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;
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
⬆️. ⬆️ ⬆️
⬆️. ⬆️. ⬆️
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.
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.
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 ☺️ .
- Insertion/push: Adding elements to the top
- Deletion/pop: Removing the oldest element, the element that was added in the beginning.
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 .