Linked List is a very important data structure in terms of the concepts required to understand it’s inner working and the operation that can be performed on it.
In this post we will be exploring structure of Linked List and operations that can be performed on Linked list.
So without further ado lets dive into the details.
For the sake of simplicity our linked list will be holding only a integer and an next link filed. We will be using a structure to accomplish this.
1 2 3 4
So it’s a simple structure which only has a int member and a next pointer of the same struct type to hold the address of the next item in the linked list.
As we have the template ready now, how can we create an instance of the structure? It’s simple we can either use C style
malloc() or CPP style
new operator. We will use malloc for this post. So creating an instance of structure is like
In this line what we are doing is declaring and defining an pointer of type struct Node and dynamically allocating memory for it using malloc.
Malloc takes the size of the data type, allocate that amount of memory dynamically at runtime in the heap( Head is the free memory from where every application can request memory from Operating system using function calls).
after this we can use this instance instance with pointer dereferencing or using the pointer operator like follows:
1 2 3
Inserting data into Linked list
Data can be inserted at different points of the linked list like at the
- at the start of the List
- at the end of the List
- at nth position
Insertion at the front of the list
Lets write a function which takes the head of the list and an integer and inserts that number at the front of the list. An example implementation is follows
1 2 3 4 5 6 7
The function is pretty straight forward. We create a new node, add the data, point it the current head, change head to point to the new node and return the new head.
Inserting at the end of the list
Insert at the end function will look like
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
In this function we first create a new node with the data and next pointer as NULL; Then we check if the list is currently empty we just make this new node the head of the list.
If the list is not empty we have first traverse the list to go to the last element of the list and then just add the newly created node in the next link of the last element;
Inserting at the Nth Position in the list
for the sake of simplicity we will assume that the position argument will always be within the list and wont do out of bounds handling in this version.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
Thats all for today. We will be talking about other operations on linked list like printing, deleting etc in future posts. Enjoy!