Linked List in C++

What is Linked List in C++?

Namaste, My name is Nitin Kumar and I am here to write a blog on the topic of C++ Linked list. We will discuss all the important factors of the Linked list in c++. We will discuss the Linked List in C++,  why it is used where it is used when it is used etc.

So, first of all, what is Linked List.

Linked List

Linked List is a linear data structure that contain finite sequence of n data elemnts but that can be related with each other in a linear function using pointer. Each data elemnt along with its link is known as node. Each node contains relevant data elemnt with some pointers.

A linked list is a dynamic memory allocation collection types.  First of all Linked list is a collection nothing but the collection of elements like arrays, stacks, queues. But this is not static right! but it is impossible to create the static linked list there is no fixed size of the linked list.

A Linked list is always a dynamic collection. So, what is the advantage of the linked list.S, when compared with arrays and as well as stacks and queue best comparison is Array VS, Linked List? So, why when we are using.

For example, If you take one array. Whenever we want to insert one element into an array.

For example, Here are some of the elements

Linked List in C++

Linked List in C++

Offcourse if it is a linear data structure. Suppose if we have to insert a new element in between 20 and 30. Rember I don’t want to delete or to replace any element. I only want to insert a new element in between 20 and 30. So, what will happen First it has to shift all the elements because directly if we insert, the 20 will get replaced. Of course, we will lose the value “20”. So, first of all, we need to shift all the elements by one location and then we have to insert.

linked list in C++

linked list in C++

So this process is known as the insertion process of an element into an array.

But here we have to shift the elements to insert an element into a particular position of an array. It will take a lot of time. Accessing is very easy in an array. It’s the reason it is an index based and using some internal pointer concepts. That easily we can access the information in an array. But whenever we are trying to insert an element or trying to delete an element it will take a lot of time because shifting of elements.

Linked List in C++

For Example, If you want to delete an element example 100 if we want to delete after deletion again we have to shift all the elements. Here it is only 3 to 4 elements but the collection is nothing but in real time lakhs of lakhs elements is storing.

Instead of using arrays it is better to go for Stacks. Instead of Stacks and Queue, it is very easy to use the Linked list in C++ concepts. Insertion and Deletion are much better and faster as compare to Stacks, Array and Queue.

See here, For Example How to insert an element into the Linked list in C++. How it will become faster. See, So generally if you want to store elements in the Linked list the data will be stored in the form of the node. Node is nothing but memory block.

For Example, If you want to store an element like

linked list in C++

linked list in C++

 

All there are individual blocks so there is no sequential order, there is no data structure concept. Offcourse processing is nothing but in the form of Linear Data Structure only but storing is not a site by site location.

For Example, the 1st element is a block memory allocation is 2046 next one is 5048, So there is a connection! How are we connecting? 5048 we are connecting into another field that I will show you. So, Continue reading Linked List in C++.

 

Here it is

linked list in C++

linked list in C++

Linked List in C++

 

So For Example, if you want to insert a node in between 20 and 30 no need to disturb anywhere, these locations are not sequential location random location. Using any expression any formula you can not access the elements of the Linked list directly. You have to travel from 1 to 2 or another node and till you get the intended node.

For Example here between 20 and 30 we want to insert 50 we have to connect

50

with 20 and 30 both.

So, the new element will get inserted between 20 and 30. For that no shifting of any element we can directly insert the element. So easily we can insert or delete the elements from the linked list so this is the only advantage when compare with Array. When we go for Linked List in C++ instead of Array this is only the reason. So now, How the nodes are storing how the memory we are allocating to nodes. So what is the structure of the node will be.

Generally, we have these Type of Linked List in C++

!) Single Linked List

2) Double Liked List

3)Circular Linked List

 

In Single Linked List how the node type will be

 

linked list in C++

 linked list in C++

A minimum it is having two fields this is what we called Node. Now, you will ask what is this! How will you create a node in a program by using logic?

The answer is Very simple A user-defined data type in C++ language that is non-other the structure. See,

struct node

{

 

}

How many field? Two fields. First one is What? First one is Data Field. If you take only one integer Here will be only one field. Suppose if I want to enter Employee information. Employee number, Employee salary, Employee name then there field will be an employee number, salary, name.

But the second part of the node is Link Field, Added Field it is compulsory. So whatever the data is no matter but the address is matter.

In Double Linked List how the node type will be

 

Here node, The node is having three fields.

linked list in C++

linked list in C++

 

In a single Linked list the node is having two fields one is data field and the second one is linked field.

And in Double Linked List the node is having three fields.

 

The First Part L link denotes Left side link. The middle part of the node is known as data item and the last part of the node represents right side Link.

The two R link and L link are pointer types which are holding the address, not data.

Thus concept which Linked List follows is known as DLL(Double Linked List).

In Circular Linked List how the node type will be

Circular Linked list is same as Double Linked List. The node is having three fields.

linked list in C++

linked list in C++

 

So, we discussed the parts of Linked list Single Linked List, Double Linked List, and Circular Linked List.

In Double Linked List and Circular Linked List the node is having the three field. One data field and two Link field. But in Single Linked List the node is having only two parts one is the data field and a second one of course next one the second one is a mandatory field that is Address Field. So, this we discussed just node types, node structure.

How will we create the nodes in a single Linked List in C++

Here is a single Linked List how the structure will be, see

The node structure

linked list in C++

linked list in C++

Some of the nodes we are writing like that the different memory location. Someone is 9058, 7002, 5048 and 2072 as shown in the figure. So first we have to create the structure. the name we are giving node. How many fields? Two fields are there.

Data suppose 10, I am storing integer data. First Field is of type integer type. But see the second part it is holding the link. What is that link 5048 we are storing here so, that it is pointing? Here the question is what is the type of link. We know that in pointer we have the type of pointer and untype of pointers. Type of pointers means an always should point the specific type of data. Integer pointer pointing to integer data floating pointer pointing to float data, Array p[ointer pointing to an Array structure. Pointer pointing to a structure. So here the pointer is pointing to structure.

linked list in C++

linked list in C++

The type is user-defined data type it is struct node type. So its pointer pointing to the user-defined data type that is the struct type node. So, pointer link is of type what? Pointer Link is struct node type.

struct node

{

int data;

struct node*link;

}

 

So, this is the structure

Continue Reading our article Linked List in C++

So, for Example

The last node and the part of the last node are showing NULL.

20 and 7002 are stored in the second node so that it is pointing. In third node here it is 30 and 9058 and it is pointing and at the last one 40 and no other thing is here we are storing so it is NULL.

No connection from the last node. Now you can ask that who is connecting the first node. that you have to declare one pointer variable struct” node*root”.

struct node

{

int data;

struct node*line;

}

struct node*root;

So how many memory allocation bytes will be allocated. Generally, two bytes or four bytes memory will be allocated depends on the size of the compiler we are using. If we are using sixteen bit then the pointer size is 2 bytes, if we are using 32 bits than the pointer size is of 4 bit. So here it will occupy either two bytes or four-byte memory. So here it will occupy either two bytes or four bytes memory. So, here it is in the root what value will be stored. How many memory will be allocated? Node creation is okay. Node structure is okay but dynamically How the memory will be allocated to the structure. That is important. Already we have discussed How to allocate the memory allocation concept.

So, what is the method we are using malloc method or a malloc method we are using?

A malloc method we are using.

See here it is malloc ( ).

so here it is what we have to pass. How many bytes we have to pass to occupy the memory we don’t know because integer size we don’t know and pointer size is also don’t know that depends on the compiler directly you can’t give the 2-byte memory or 4-byte memory. The reason, that is from compiler to compiler the size varies.

           malloc(sizeof(struct node));

So, here we are directly node data type we are pointing. So malloc function allocates the memory, How many bytes? It will allocate the only first one.

Can we store directly?  This is only just the creation of a node.

So as of now directly I am Assigning. This is the correct rules exactly

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

Here it is we are passing and converting into struct node type because malloc function return type is void pointer we know that. It is the generic pointer.

Here it is a malloc function is returning a void pointer into a variable root. root is a type of struct node type. S, we are converting typecasting.

 

 

Speak Your Mind

*