Comprehensive Guide to Data Structures: Arrays to Graphs Explained

In this lesson and in this series of lessons, we will introduce you to the concept of data structures. Data structure is the most fundamental and building block concept in computer science and good knowledge of data

structures is a must to design and develop efficient software systems. Okay, so let's get started. We deal with data all the time and how we store, organize and group our data together matters. Let's pick up some examples from our day-to-day life

where organizing data in a particular structure helps us. We are able to search a word quickly and efficiently in a language dictionary because the words in the dictionary are sorted. What if the words in the dictionary were not sorted?

It would be impractical and impossible to search for a word among millions of words. So dictionary is organized as a sorted list of words. Let's pick up another example. If we have something like a city map, the data like position of a

landmark and road network connection. So all this data is organized in the form of geometries. We show the map data in the form of these geometries on a two dimensional plane. So map data needs to be structured like this so that we have

scales and directions and we are effectively able to search for a landmark and get route from one place to another. And I'll pick one more example for something like daily cash in and cash out statement of a business, what we

also call a cash book in accounts. It makes most sense to organize and store the data in the form of a tabular schema. It is very easy to aggregate data and extract information if the data is organized in these columns in these

tables. So different kind of structures are needed to organize different kind of data. Now computers work with all kind of data. Computers work with text, images, videos, relational data, geospatial data and pretty much any kind of data that we

have on this planet. How we store, organize and group data in computers matters because computers deal with really really large data and even with the computational power of machines, if we do not use the right kind of

structures, the right kind of logical structures, then our software systems will not be efficient. Formal definition of a data structure would be that a data structure is a way to store and organize data in a computer so that the

data can be used efficiently. When we study data structures as ways to store and organize data, we study them in two ways. So I'll say that we talk about data structures as one, we talk about them as mathematical and logical models. When we

talk about them as mathematical and logical models, we just look at an abstract view of them. We just look at from a high level what all features and what all operations define that particular data structure. Example of abstract view

from real world can be something like the abstract view of a device named television can be that it is an electrical device that can be turned on and off. It can receive signals for satellite programs and play the audio video of the

program and as long as I have a device like this, I do not bother how circuits are embedded to create this device or which company makes this device. So this is an abstract view. So when we study data structures as mathematical or

logical models, we just define their abstract view or in other words, we have a term for this, we define them as abstract data types. An example of abstract data type can be, I want to define something called a list that should be

able to store a group of elements of a particular data type and we should be able to read the elements by their position in the list and we should be also able to modify element at a particular position in the list. I would

say store a given number of elements of any data type. So we are just defining a model. Now we can implement this in a programming language in a number of ways. So this is a definition of an abstract data type. We also call abstract data

type as ADT and if you see, all the high-level language is already have a concrete implementation of such an ADT in the form of arrays. So arrays give us all these functionalities. So arrays are data types which are concrete

implementation. So the second way of talking about data structures is talking about their implementation. So implementations would be some concrete types and not an abstract data type. We can implement the same ADT in multiple ways

in the same language. For example in C or C++ we can implement this list ADT as a data structure named linked list and if you have not heard about it, we will be talking about them a lot. We will be talking about linked list a lot in the

coming lessons. Okay so let's define an abstract data type formally because this is one term that we will encounter quite often. Abstract data types are entities that are definitions of data and operation but do not have implementations.

So they do not have any implementation details. We will be talking about a lot of data structures in this course. We will be talking about them as abstract data types and we will also be looking at how to implement them. Some of the

data structures that we will talk about are arrays linked list, stack, queue, tree, graph and the list goes on. There are many more to study. So when we will study these data structures we will study their logical view. We will study what

operations are available to us with these data structures. We will study the cost of these operations mostly in terms of time and then definitely we will study the implementation in a programming language. So we will be studying all these

data structures in the coming lessons and this is all for this introductory lesson. Thanks for watching. In our previous lesson we introduced you to the concept of data structures and we saw how we can talk about data structures in

two ways. One as a mathematical and logical model that we also call that we also term as an abstract data type or ADT and then we also study data structures as concrete implementations. In this lesson we will study one simple data

structure. We will first define an abstract view of it. We will first define it as an abstract data type and then we will see the possible implementations and this data structure is list. List is a common real world entity. List is nothing

but a collection of objects of the same type. We can have a list of words, we can have a list of names or we can have a list of numbers. So let us first define list as an abstract data type. So when we define abstract data type we just

define the data that will store and we define the operations available with the type and we do not go into the implementation details. Let us first define a very basic list. I want a list that can store a given number of elements of a

given data type. This would be a static list. The number of elements in the list will not change and we will know the number of elements before creating the list. We should be able to write or modify element at any position in the

list and of course we should be able to read element at a particular position in the list. So if I ask you for an implementation of such a list and you have taken a basic course in programming, a basic introductory course then you'll

be like hey I know this and array gives us all these features. All these operations are available with an array. We can create an array of any data type so let us say if we want to create a list of integers then we declare the array

type as integer and then we can give the size as a parameter in declaration. I can write or modify element at a particular position. The elements are A0, A1 and are accessed something like this. We all know about arrays and then we can also

read elements at a particular position. The element at ith position is accessed as AI. So array is a data structure that gives us implementation for this list. Now I want a list that should have many more features. I want it to handle more

scenarios for me. So I'll redefine this list here. I do not want a static list a static collection with a fixed size. I want a dynamic list that should grow as per my need. So the features of my list are that I'll call my list empty if there

are no elements in the list. I'll say the size of the list is 0 when it is empty and then I can insert an element into the list and I can insert an element at any position in the list and in an existing list. I can remove element from the list.

I can count the number of elements in the list and I should be able to read or write or rather read or modify element at a particular position in the list and I should also be able to specify the data type for the list. So I should be able to

while creating the list I should be able to say whether this is a list of integers or whether this is a list of string or float or whatever. Now I want a data structure which is implementation of this dynamic list. So how do I get it?

Well actually we can implement such a dynamic list using arrays. It's just that we will have to write some more operations on top of arrays to provide for all these functionalities. So let us see how we can implement this

particular list using arrays. Let's for the sake of simplicity of design assume that the data type for the list is integer. So we are creating a list of dynamic list of integers. What we can do is to implement such a list we can

declare a really large array. We will define some max size and declare an array of this max size. Now as we know the elements in the array are indexed as a0, a1, a2 and we go on like this. So what I'll do is I'll define a variable that

will mark the end of the list in this array. So if the list is empty we can initialize this variable or we can set this variable as minus 1 because the lowest index possible is 0. So if end is minus 1 the list is empty. At any time

a part of the array will store the list. Okay so let's say initially when the list is empty this pointer end is pointing to index minus 1 which is not valid which does not exist. And now I insert an integer into this array and let's

say if we do not give the position at which the number is to be inserted the number is always inserted towards the tail of the list towards the end of the list. So the list will be like we will have an element at position 0 and now

end is index 0. So at any time end marks the this variable end marks the end of the list in this array. Now if I want to insert something in the list at a particular position let's say I want to insert number 5 at index 2 then to

accommodate 5 here at this particular position we will have to shift all the elements one unit towards the right. All the elements starting index 2 we need to shift all the elements starting index 2 towards the right. Okay I just inserted

some elements into the list let me also write the function call for these. Let's say we went in this order we inserted 2 then we inserted 4 and then we inserted in the end we are inserting 5 and we will also give the position at which we

want to insert. So this insert with two arguments would be the call to insert element at a particular position. So after all these operations after all these insertions this is what the list will look like. This arrow here marks the end

of the list in the array. Now if I want to remove an element from a particular position let's say I make a call to something to the remove function I want to remove the element 2. So I'll pass the index 0 here I want to remove the element

at index 0. So to do so all these elements after index 0 will be shifted one unit towards the left or towards the lower indices and 2 will go away. Now this end variable here is being adjusted after each insertion that we are making. So after

this insertion end will be 0 after this 1, 2, 3 and so on after this remove end will be 4 again. Okay looks like we pretty much have an implementation of this list in the left that is described as an abstract data type. We have a logic

of calling the list empty when we have this variable n is equal to minus 1. We can insert element at a particular position in the list we can remove element. It's just that we have to perform some shifts in the array. We can

count the number of elements in the list. It will be equal to n plus 1 the value in the variable n plus 1. We can read or modify element at a position well this is an array so we can definitely read or modify element at a particular

position. If we wanted to choose the data type it was just choosing the array of that particular data type. Now this looks like a cool implementation except that we have one problem. We said that the array will be of some large size some

max size. But what is a good max size? We can always exhaust array the list can always grow to exhaust the array. There is no good max size. So we need to have a strategy for the scenario when the list will fill up the whole array. So what do

we do in that case? We need to keep that into our design. We cannot extend the same array. It is not possible to do so. So we will have to create a new array a larger array. So when the array is full we will create a new larger array and

copy all the elements from the previous array into the new array. And then we can free the memory for the previous array. Now the question is by how much should we increase the size of the new array? This whole operation of creating a new array

and copying all the elements from the previous array into the new array is costly in terms of time and definitely a good design would be to avoid such big cost. So the strategy that we choose is that each time the array is full we create

a new larger array of double the size of the previous array. And why this is the best strategy is something that we will not discuss in this lesson. So we will create a larger array of double size and copy elements from previous array into

this new array. This looks like a cool implementation. The study of data structures is not just about studying the operations and the implementation of these operations. It's also about analyzing the cost of these operations. So let us see what are

the costs in terms of time for all these operations that we have in the dynamic list. The access to any element in this dynamic list if we want to access access it using index for read or write then this will take constant time because we

have an array here. And in array elements are arranged in one contiguous block of memory using the starting address or the base address of the block of the memory of the block of memory and the index or the position of the element we

can calculate the address of that particular element and access it in constant time. Big O notation that is used to describe the time complexity of operations for constant time it is written as in terms of Big O the time

complexity is written as Big O of 1. If we wanted to insert element if we wanted to insert element at the end of the array end of the list then that again will be constant time but if we would insert element at a particular position in the

list then we will have to shift elements towards higher indices. In the worst case we will have to shift all the elements to the right when we will be inserting at the first position. So the time taken for insertion will be proportional to the

length of the list let's say the length of the list is n or in other words we will say that insertion will be Big O of n in terms of time complexity. If you do not know about Big O notation do not bother just understand that inserting an

element at a particular position will be a linear function in terms of the size of the list. Removing an element will again be Big O of n. Time taken will be proportional to the current size of the list n is the size of the list here okay

now inserting an element at the end we just said that it will happen in constant time it is not so if the array is full then we will create a new array let's call inserting element at the end as adding an element. Adding an element will take

constant time if the list is not full but it will take time proportional to the size of the list size of the array if the array is full. So adding in the worst case will be Big O of n again as we said when the list is full we create a new

copy double the size of the previous array and then we copy the previous array the elements from previous array into the new array. So prime of a see what looks like the good thing with this kind of implementation. Well the good thing is

that we can access elements at any index in constant time which is the property of the array but if we have to insert some element in between and if we have to remove element from the list then it is costly. If the list grows and

strings a lot then we will also have to create a new array and have all this thing of copying elements from previous array into new array again and again. And one more problem is that a lot of time a lot of the array would be unused the

memory there is of no use but definitely the use of array as dynamic list is not efficient in terms of memory this kind of implementation is not efficient in terms of memory. This leads us to think can we have a data structure that will

give us a dynamic list and use the memory more efficiently. We have one data structure that gives us good utilization of the memory and this data structure is linked list and we will study about the linked lists in the

next lesson. So that's it for this lesson thanks for watching. In this lesson we will introduce you to link the list data structure. In our previous lesson we tried to implement a dynamic list using arrays and we had some issues there. It

was not most efficient in terms of memory usage in terms of memory consumption. When we use arrays we have some limitations. To be able to understand linked list well we need to understand these limitations. So I am going to tell

you a simple story to help you understand this. Now let us say this is computer's memory and each partition here is one byte of memory. Now as we know each byte of memory has an address we are showing only a section of the memory that's why it is

extending towards the bottom and the top. Let's say the address increases from bottom to top. So if this byte is address 200 the next byte would be address 201 and next byte would be address 202 and so on. What I want to do is I want to draw

this memory from left to right horizontally instead of trying it from bottom to top like this. This looks better. Let's say this byte here is address 200 and as we go towards the right the address increases. So this is

like 201 and we go on like 202, 203 and so on. It doesn't really matter whether we show memory from bottom to top or left to right. These are just logical ways to look at the memory. So coming back to our story memory is a crucial resource and

all the applications keep asking for it. So Mr. Computer has given this job of managing the memory to one of his components to one of his guys who he calls the memory manager. Now this guy keeps track of what part of the memory

is free and what part of the memory is allocated and anyone who needs memory to store something needs to talk to this guy. Albert is our programmer and he is building an application. He needs to store some data in the memory so he

needs to talk to the memory manager. He can talk to the memory manager in a high level language like C. Let us say that he is using C to talk to the memory manager. First he wants to store an integer in the memory. So he communicates

this to memory manager by declaring an integer variable something like this. The memory manager sees this declaration and he says that okay you need to store an integer variable. So I need to give you four bytes of memory because integer

variable is stored in four bytes in a typical architecture and let us say in this architecture it is stored in four bytes. So the memory manager looks for four bytes of free space in the memory and assigns it or allocates it for

variable X. Address of a block of memory is the address of the first byte in the memory. So let us say this first byte of memory here is at address 217. So variable X is at address 217. So memory manager kind of communicates it back to Albert

that hey I have assigned address 217 for your variable X you can store whatever you want there and Albert can fill in any data into this variable. Now Albert needs to store a list of integers a list of numbers and he thinks that the

maximum number of integers in this list will be four. So he asks the memory manager for an integer array of size four named A. Now array is always stored in memory as one contiguous block of memory. So memory manager is like okay I need to

look for a block of memory of 16 bytes for this variable this array A. So the memory manager allocates this block starting address 201 and ending address 216 for this variable A which is an array of four integers. Because array is

stored as one contiguous block of memory and memory manager conveys the starting address of this block whenever Albert tries to access any of the elements in the array let's say he tries to access let's say he tries to write some value at

the fourth element in the array which he accesses as A3. Albert's application knows where to write this particular value because it knows the base address the starting address of the block A the array A and from base address using the

index which is three here it calculates the address of A3. So it knows that A3 is at address 213. So to access any of the elements in the array the application takes constant time and this is one awesome thing about arrays that

irrespective of the size of the arrays the application and application can access any of the elements in the array in constant time. Now let's say Albert uses this array of four integers to store his list. So I'll fill in some

values here at these positions let's say this is 8, this is 2, this is 6, this is 5, this is 4. Now Albert at some point feels that okay I need to have one more element in this list. Now he has declared an array of size 4 and he wants to add

a fifth element in the array. So he asks the memory manager that hey I want to extend my array A is it possible to do so I want to extend the same block and the memory manager is like when I allocate memory for an array I do not expect that

you will ask for an extension. So I use whatever memory is available adjacent to that block for other variables. In some cases I may extend the same block but in this case I have an element and a variable X next to your block so I cannot

give you an extension. So Albert is like what all options do I have? Memory manager is like you can tell me the new size and I can recreate a new block at some new address and we will have to copy all the elements from the previous block

to the new block. So Albert says that okay let's do it but the memory manager is like you still need to give me the size of the new block. Albert thinks that this time he'll give a really large size for the new array or the new block so

that it does not fill up. This new block starting address 2 to 4 is allocated. Albert asks memory manager to free the previous block and this is some cost he has to copy all the elements all the numbers from the previous block into the

new block and now he can add one more element to this list and he has kept his array large this time just in case he needs more numbers in the list. So the only option that Albert had was to create a as an entirely new block as an

entirely new array and Albert is still feeling bad because if the list is too small he is not using some part of the array and so memory is getting wasted and if the list again grows too much he will again have to create a new array a

new block and he will again have to copy all the elements from the previous block into the new block. Albert is desperately seeking a solution to this problem and the solution to this problem is a data structure named linked list. So let us

now try to understand linked list data structure and see how it solves Albert's problem. What Albert can do is that instead of asking the memory manager for an array which will be one large contiguous block of memory he can ask memory for

one unit of data at a time for one element at a time in a separate request. I am cleaning up the memory here once again let's say Albert wants to store this list of four integers in the memory. What if he requests memory for one

integer at a time. So first he pings memory manager for some memory to store number six memory manager will be like okay you need space to store an integer so you get this block of four bytes at address 204. So Albert can store number

six here now Albert makes another request a separate request for number five. Let say he gets this block starting address 217 for number five because he makes a separate request he may or may not get memory adjacent to number six higher

probabilities that he will not get an adjacent memory location. So similarly Albert makes separate requests for number four and two. So let's say he gets these two blocks at address 232 and 242 respectively for numbers four and two. So

as you can see when all but makes separate requests for each integer instead of getting one contiguous block of memory he gets these disjoint non-contiguous blocks of memory. So we need to store some more information here we need to

store the information that this is the first element in the list and this is the second element in this list. So we need to link these blocks together somehow with an array it was very simple. We had one contiguous block of memory so so we knew

where a particular element is by calculating its address using the starting address of the block and the position of the element in the array but here we need to store the information that this is the first block which stores

the first element and this is the second block which stores the second element and so on. To link these blocks together and to store the information that this is the first block in the list and this is the second block in the list what we

can do is that we can store some extra information with each block. So what if we can have two parts in each block something like this and in one part of the block we store the data or the value and in the other part of the block we

store the address of the next block. In this example in the first block the address part would be 2 1 7 the address of the next block that stores 5 and in this next block or the second block the address part would be 2 3 2. In the block

at address 2 3 2 we will store the address 2 4 2 the address of the next block that stores number 2 and the block at 2 4 2 is the last block there is no next block after this. So in the address part we can have address as 0 0 is in

valid address 0 can be used to mark that this is the end of the list there is no link to the next node or next block after this particular block. So all but now actually has to request memory manager for a block of memory that will store

two variables one and integer variable that will store the value of our element and one a pointer variable that will store the address of the next block or the next node in the list. In C he can define a type named node like this he

will have two fields in the node one to store the data this field will be an integer and one more field to store the address of the next node in the list. So Albert will ask a node Albert will ask memory for a node from the memory manager

and the memory manager will be like okay you need a node that needs four bytes for an integer variable and four more bytes for the pointer variable that will store the address pointer variable also in a typical architecture is stored in

four bytes. So now memory manager gives us a block of eight bytes and we call this block a node. Now notice that the second field in the node structure is node star which means pointer to node so this field will only store an address

of the next node in the list. So if we store the list like this in the memory as these non-contiguous nodes connected to each other then this is a linked list data structure. Logical view of the linked list data structure will be

something like this. Data is stored in these nodes and each node store the data as well as the link to the next node. So each node kind of points to the next node. The first node is also called the head node and the only information about

the list that we keep all the time is address of the head node or address of the first node. So address of the head node kind of gives us access to the complete list. The address in the last node is null or 0 which means that the

last node does not point to any other node. Now if we want to traverse the linked list the only way to do it is we start at the head and we go to the first guy and then we ask the first guy the address of the next guy address of the

next node and then we go to the next node and ask the address of the next node and this is the only way to access the elements in the linked list. If we want to insert a node in the linked list let's say we want to add number 3 at the end

of the linked list then all we need to do is first create a node in the linked list. Sorry first create a node independently and separately it will get some memory location. So we created this node with value 3. Now all we need to do

is fill the address properly adjust these links properly. So the address of this particular node will be filled in this node with value 2 and this node the address part can be null. So it is the last node it does not point to any other

node. Let's also show these nodes in the memory here. So I've written the address of each node in brown at top of these nodes and I've also filled in this address field of each node. Let's say the node for value 3 gets address 2 5 2. So this is

how things will be in the memory and this is how the logical view will be. The linked list is always identified by the address of the first node and unlike arrays we cannot access any of the elements in constant time. In the case of

arrays using the starting address of the block of memory and using the position of the element in the list. We could calculate the address of the element but in this case we have to start at the head and we have to ask this element for next

element and then ask the next element who is your next. It's like playing treasure hunt. You go to the first guy and then you get the address for the second guy and then you go to the second guy and you get the address for the

third guy. So the time taken to access elements will be proportional to the size of the list. Let's say the size of the list is n. There are n elements in the list. In the worst case to traverse the last element you will go through all

the elements. So time taken to access elements is proportional to n or in other words we say that this operation will cost us or rather the time complexity of this operation is big O of n. Insertion into the list. We can insert anywhere in

the list. We first need to create a node and just adjust these links properly. Like say I want n at third position in the list. So all we need to do is create a node, store the value 10 in the data part, something like this. Let's say we get the

node 10 at address 310. So we will adjust the address field in the second node to point to and this node with address 310 and this node will point to the node with value 4. Now to insert also we will have to traverse the list and go to that

particular position and so this will be big O of n again in terms of time complexity. The only thing is that the insertion will be a simple operation. We will not have to do all the shifts as we had to do in an array to insert

something in between. We had to shift all the elements by one position towards higher indices. Similarly to delete something from this list will also be O n. So we can see some good things about linked list. There is no extra use of

memory in the sense that some memory is unused. We are using some extra memory. We are using some extra memory to store the addresses but we have the benefit that we create nodes as and when we want and we can also free the nodes as and when we want.

We do not have to guess the size of the list beforehand like in the case of arrays. Now we will discuss all the operations on linked list and the cost of these operations as well as comparison with arrays in our next lessons. We will also be implementing

linked list in C or C++. So this is all for a basic introduction to linked list. Thanks for watching. In our previous lesson we introduced you to linked list data structure and we saw how linked lists solve some of the problems that we have with arrays. So now the obvious question would be

which one is better and array or a linked list. Well there is no such thing as one data structure is better than another data structure. One data structure may be really good for one kind of requirement while another data structure can be really good for another kind of requirement.

So it all depends upon factors like what is the most frequent operation that you want to perform with the data structure or what is the size of the data and there can be other factors as well. So in this lesson we will compare these two data structures based on some parameters based on

the cost of operations that we have with these data structures. So all in all we will comparatively study the advantages and disadvantages and try to understand in which scenario we should use an array and in which scenario we should use a linked list. So I will draw two columns here one for array

and another for linked list and the first parameter that we want to talk about is the cost of accessing an element irrespective of the size of an array it takes constant time to access an element in the array. Now this is because an array is stored as one contiguous block of memory. So if we know the

starting address or the base address of this block of memory let us say what we have here is an integer array and the base address is 200 the first byte in this block is at address 200 then let's say if we want to calculate the address of element at index i then it will be equal to 200 plus i into

size of an integer in bytes. So size of an integer in bytes is typically 4 bytes so it will be 200 plus 4 into i. So if 0th element is at address 200 if we want to calculate the address for element at index 6 it will be 200 plus 6 into 4 which will be equal to 224. So knowing address of any

element in an array is just this calculation for our application in terms of big o notation constant time is also called big o of 1. So accessing an element in an array is big o of 1 in terms of time complexity. If you are not aware of big o notation check the description of this video for

a tutorial on time complexity analysis. Now in a linked list data is not stored in a contiguous block of memory. So if we have a linked list something like this let's say we have a linked list of integers here then we have multiple blocks of memory at different addresses. Each block in

the linked list is called a node and each node has two fields one to store the data and one to store the address of the next node. So we call the second field the link field. The only information that we keep with us about a linked list is the address of the first node which we also call

the head node and this is what we keep passing to all the functions also the address of the head node. To access an element in the linked list at a particular position we first need to start at the head node or the first node and at the first node we need to see the address of the second node

and then we go to the second node and see the address of the third node. In the worst case to access the last element in the list we will be traversing all the nodes in the list. In the average case we will be accessing the middle element maybe. So if n is the size of the linked list

and is the number of elements in the linked list then we will traverse n by two elements. So the time taken in the average case also is proportional to number of elements in the linked list. So we can say that the time complexity in average case is big O of n. So on this parameter

cost of accessing an element arrays course heavily over linked list. So if you have a requirement where you want to access elements in the list all the time then definitely array is a better choice. Now the second parameter that we want to talk about is memory requirement or

memory usage. With an array we need to know the size of the array before creating it because array is created as one contiguous block of memory. So array is a fixed size. What we typically do is create a large enough array and some part of the array stores our list

and some part of the array is vacant or empty so that we can add more elements in the list. For example we have an array of seven integers here and we have only three integers in the list. Rest four positions are unused. There would be some garbage value there.

With linked list let's say we have let's say we have this linked list of integers. There is no unused memory. We ask memory for one node at a time so we do not keep any reserved space but we use extra memory for pointer variables. And this extra memory requirement for pointer

variables in a linked list cannot be ignored in a typical architecture let's say integer is stored in four bytes and pointer variable also takes four bytes. So if you see the memory requirement for this array of seven integers is 28 bytes and the memory requirement for this linked list would be

eight into three where eight is the size of each node four for integer and four bytes for the pointer variable. So this is also 24 bytes. If we add one more element to the list in the array we will just use one more position. While in linked list we will create one more node

and we'll take another eight bytes. So this will be 32 bytes linked list would fetch us a lot of advantage of the data. The data part is large in size. So in this case we had a linked list of integers. So integer is only four bytes. What if we had a linked list in which a data part was

some complex type that took 16 bytes. So four bytes for the link and 16 bytes for the data each node would have been 20 bytes and array of seven elements for 16 bytes of data would be 16 byte for each element would be 112 bytes and linked list of four would be only 80 bytes.

So it all depends. If the data part for the list takes a lot of memory linked list will definitely consume lot less memory. Otherwise it depends what strategy we are choosing to decide the size of the array. At any time how much array we keep unused. Now one more point with memory allocation

because arrays are created as one contiguous block of memory. Sometimes when we may want to create a really really large array then maybe memory may not be available as one large block but if we are using linked list memory may be available as multiple small blocks. So we will have this problem

of fragmentation in the memory. Sometimes we may get many small units of memory but may not get one large block of memory. This may be a rare phenomenon but this is a possibility. So this is also where linked list scores. Because arrays have fixed size once array gets filled and we

need more memory then there is no other option than to create a new array of larger size and copy the content from the previous array into the new array. So this is also one cost which is not there with linked list. So we need to keep these constraints and these requirements

in mind when we want to decide for one of these data structures for our requirement. Now the third parameter that we want to talk about is cost of inserting an element in the list. Remember when we are talking about arrays here we are also talking talking about the possible use

of array as dynamic list. So there can be three scenarios in insertion. First scenario will be when we want to insert an element at the beginning of the list. Let's say we want to insert number three at the beginning of the list. In the case of arrays we will have to shift each element

by one position towards the higher index. So the time taken will be proportional to the size of the list. So this will be big O of n. Let's say n is the size of the list. This will be big O of n in terms of time complexity. In the case of linked list inserting an element

in the beginning will mean only creating a new node and adjusting the head pointer and the link of this new node. So the time taken will not depend upon the size of the list. It will be constant. So for linked list inserting an element at the beginning is big O of one in terms of

time complexity. Inserting an element at n for an array. Let's say we are talking about dynamic array a dynamic list in which we create a new array if it gets field filled. If there is space in the array we just write to the next higher index of the list. So it will be constant time.

So time complexity is over if array is not full. If array is full we will have to create a new array and copy all the previous content into new array which will take O in time where n is the size of the list. In the case of linked list adding an element inserting an element at the end will

mean traversing the whole list and then creating a new node and adjusting the links. So time taken will be proportional to n. I'll use this color coding for linked list. Here n is the number of elements in the list. Now the third case would be when we want to insert in the middle of the list

at some nth position or maybe some ith position. Again in the case of arrays we will have to shift elements. Now for the average case we may want to insert at the mid position in the array. So we will have to shift n by two elements where n is the number of elements in the list. So the time

taken will is definitely proportional to n in average case. So complexity will be big O of n. For linked list also we will have to traverse till that position and then only we can adjust the links even though we will not have any shifting we will have to traverse till that point and in

the average case time taken will be proportional to n and the time complexity will be big O of n. If you can see deleting an element will also have these three scenarios and the time complexity for deleting for these three scenarios will also be the same. And the final point the final parameter

that I want to talk about is which one is easy to use and implement and array definitely is a lot easier to use linked list implementation especially in C or C++ is more prone to errors like segmentation fault and memory leak it takes good care to work with linked list. So this was arrays versus linked

list in our next lesson we will implement linked list in C or C++ we will get our hands dirty with some real code. So this is it for this lesson thanks for watching. In our previous lessons we described linked list we saw the cost of various operations in linked list and we also compared

linked list with arrays. So now let us implement linked list the implementation will be pretty similar in C and C++ there will be slight differences that we will discuss. The prerequisite for this lesson is that you should have a working knowledge of pointers in C C++ and you should also know the

concept of dynamic memory allocation. If you want to refresh any of these concepts check the description of this video for additional resources. Okay so let's get started. As we know in a linked list data is stored in multiple non-contiguous blocks of memory and we call each block of memory a

node in the linked list. So let me first draw a linked list here. So we have a linked list of integers here with three nodes as we know each node has two fields or two parts one to store the data and another to store the address of the next node what we can also call link to the next node.

So let's say the address of the first node is 200 and address of the second node is 100 and the address of the third node is 300 for this linked list. This is only a logical view of the linked list. So the address part of the first node will be 100 the address of the second node and we will

have 300 here. The address part of the last node will be null which is only a synonym or macro for address 0. 0 is an invalid address a pointer variable equal to 0 or null with address 0 or null means that the pointer variable does not point to a valid memory location. The memory block

the address of the memory block allocated to each of the nodes is totally random there is no relation it's not a guarantee that the addresses will be in increasing order or decreasing order or adjacent to each other. So that's why we need to keep these links.

Now the identity of the linked list that we always keep with us is the address of the first node what we also call the head node. So we keep another variable that will be of type pointer to node and this guy will store the address of the first node and we can name this pointer variable

whatever let's say this pointer variable is named a. The name of this particular pointer variable that points to the head node or the first node can also be interpreted as the name for the linked list also because this is the only identity of the linked list that we keep with us all the time.

So let us now see how this logical view can be mapped to a real program in C or C++. In our program node will be a data type that will have two fields want to store the data and another to store the address. In C we can define such a data type as structure.

So let's say we define a structure named node with two fields first field to store the data the type of the data here is integer. So this will be node for a linked list of integers. If we wanted a linked list of say double this data type would be double. The second field will be

pointer to node struct node star we can name this link or we can name this next or whatever. This is C style of declaring node star or pointer to node. If this was C++ we could simply write node star I would write it this way the C++ way it looks better to me. In our logical view here

this variable A is of type node star or pointer to node. Each of these three rectangles with two fields are of type node and this field in the node the first field is of type integer and the second field is of type pointer to node or node star. It is important to know which one is what

in the logical view we should have this visualization before we go on to implement linked list. Okay so let us now create this particular linked list of integers that we are showing here through our code. To be able to do so we will have to implement two operations one to insert

a node into the linked list one operation to insert a node in the linked list and another operation to traverse the linked list. But before that the first thing that we want to do is that we want to declare a pointer to the head node a variable that will store the address of the

head node for the sake of clarity I'll write head node here. So I have declared a pointer to node named A. Initially when the list is empty when there is no element in the list this pointer should point nowhere so we write a statement something like A is equal to null to say the same. Now with

these two statements what we have done is we have created a pointer to node named A and this and this pointer points nowhere so the list is empty. Now let's say we want to insert a node in this list so what we do is we first create a node creating a node is nothing but creating a memory block

to store a node in C we use the function malloc to create a memory block as argument we pass the number of bytes that we want in the block so we say that give me a memory block that will be equal to the size of a node so this call to malloc will create a memory block. This is a dynamically

allocated memory memory allocated during runtime and the only way to work with this kind of memory is through reference to this memory location through pointers. Let us assume that this memory block assigned here is at address 200. Now malloc returns a void pointer that gives us the address of

assigned memory block so we need to collect it in some variable so let's say we create a variable named temp which is pointer to node so we can collect the return of malloc the address in this particular variable we will need a type casting here because malloc returns void pointer and we are

having temp as pointer to node so now we have created one node in the memory. Now what we need to do is fill in the data in this particular node and adjust the links which will mean writing the correct address in the variable a and the link field of this newly created node to do so we will

have to dereference this particular pointer variable and that we just created. As we know if we put an asterisk sign in front of the pointer variable we mean dereferencing it to modify the value at that particular address. Now in this case we have a node which has two fields so once we dereference

if we want to access each of the fields we need to put something like a dot data here to access the data and a dot link to write to the link field so we will write a statement like this to fill in value 2 here and we have this temp variable pointing to this right now

and the link part of this newly created node should be null because because this is the first and the last node and the final thing that we need to do is write the address of this newly created node in a so we will write something like a is equal to temp okay temp was to temporarily

store the address of the node till the time we had not fixed all the links properly we can now use temp for some other purpose our linked list is intact now it has one node these two lines that we have written here for dereferencing and writing the values into the new node there is alternate

syntax for this instead of writing something like start temp bracketed dot data we could also write temp followed by this arrow and data we will have two characters to make this arrow one hyphen and one this right angular bracket right angular brace so we can write something like this

and the same thing below we can write something like this to create a memory block in c++ we can use malloc as well as we can use the new operator so in c++ it gets very simple we could simply write node start temp is equal to new node like this and we would mean the same thing

this is a lot cleaner and new operator is always preferred over malloc so if you're using c++ new is recommended so so far through our program we created an empty list by creating this pointer to the head node and assigning the value null to it initially then we created a node and we added

this first node in this linked list when the list is empty and we want to insert a node the logic is pretty straightforward when the list is not empty we may want to insert a node at the beginning of the list or we may want to insert a node at the end of the list or we may even want to insert a

node somewhere in the middle of the list at a particular position we will write separate functions and routines for these different kind of insertions and we will see running code in a compiler in our coming lessons let's just talk about the logic here in this whatever unstructured code I

have right now so I want to write a code to insert two more nodes each time at the end of the list we actually want to create the linked list with three nodes having values two four and six that was our initial example in the beginning okay so let us add two more nodes with values

four and six into this linked list at this stage in our code we already have a variable temp which is pointing to this particular node we will create a new node and use the same variable name to collect the address of this new node so we will write a statement like this so a new node is created

and temp now stores the address of this new node which is located at address 100 here once again we can set the data and then because this is going to be the last node we need to set the link as null now all we need to do is build the link of this particular node right the address of this

newly created node into the address field of this last node to do so we will have to traverse the list and we will have to go to the end of the list to do so we will write something like this we can create a new variable temp one which will be pointed to node and initially we can

point to the head node point this variable to the head node by a statement like this we can write a loop like this now this is generic logic to reach the end of the list it will not be so clear if we see this logic with only one node as we have in this example let's draw a list with multiple

nodes so we are pointing temp one to the first node here and if the link part of this node is null we are at the last node else we can move to the next node so temp one equal temp one dot link will get us to the next node and we will go on till we reach the last node

for the last node this particular condition temp one dot link not equal null will be false because the link part will be null and we will exit this while loop so this is our code logic for traversal of the list all the way till end if we want to print the elements in the list we

will write something like this and we will write print temp dot data inside this while loop but right now we want to insert in the at the end of the list and we are only traversing the list to reach the last node there is one more thing that I want to point out we are using this variable

temp one and initially storing the address in a we are not doing something like a equal a dot link and using the variable a itself to traverse the list because if we modify a we will lose on the address of the head node so a is never modified the address of the head node whatever

variable stores the address of the head node is never modified only these temporary variables are modified to traverse the list so finally after all this we will write a statement like temp one dot link is equal to temp temp one is pointing here so now this address part is updated and this link

is built so we have two nodes now in the list once again when we want to insert node with number six in this list we will have to create a new node by this logic then we will have to traverse the list by this logic so we will point temp one here first and then the loop will

move the temp one to the end let's say this new block is at address 300 so this last line finally will adjust the link of the node at address 100 to insert a node at the end there is one logic in these four lines if the list is empty and there is another logic in these remaining lines if the

list is not empty ideally we will be writing all these logics all this logic in a function we will do that in our coming lessons we will implement separate methods to print all the nodes in a linked list and to insert a node at the end we will implement a separate method to insert a

node at the beginning of the list and at a particular position in the list so this is all for this lesson thanks for watching in our previous lesson we saw how we can map the logical view of a linked list into a c or c++ program we saw how we can implement two basic operations one traversal of

the linked list and another inserting a node at the end of the linked list in this lesson we will see a running code that will insert a node at the beginning of the linked list so let's get started I will write a c program here the first thing that we want to do in our program is that we want

to define a node a node will be a structure in c it will have two fields want to store the data let's say we want to create a linked list of integers so our data type will be integer if we wanted to create a linked list of characters then our type would be character here so we will have another

field that will be pointed to node that will store the address of the next node we can name this variable link or some people some people also like to name this variable next because it sounds more intuitive this variable will store the address of the next node in the linked list

in c whenever we have to declare node or pointer to node we will have to write struct node or struct node star in c++ we will have to write only node star and that's one difference okay so this is the definition of our node now to create a linked list we will have to create

a variable that will be pointer to node and that will store the address of the first node in the linked list what we also call the head node so I will create a pointer to node here struct node star we can name this variable whatever often for the sake of understanding

we name this variable head now I have declared this variable as a global variable I have not declared this variable inside any function and I'll come back to why I'm doing so now I'll write the main method this is the entry point to my program the first thing that I want to do is I want to

say head is equal to null which will mean that this pointer variable points nowhere so right now the list is empty so far what we have done here in our code is that we have created a global variable named head which is of type pointer to node and the value in this pointer variable is null

so so far the list is empty now what I want to do in my program is that I want to ask the user to input some numbers and I want to insert all these numbers into the linked list so I'll print something like how many numbers let's say the user wants to input n numbers so I'll collect this

number in this variable n and then I'll define another variable I to run the loop and so I'm running a loop here if it was c++ I could declare this integer variable right here inside the loop now I'll write a print statement like this and I'll define another variable x and each time

I'll take this variable x as input from the user and now I will insert this particular number x this particular integer x into the linked list by making a call to the method insert and then each time we insert we will print all the nodes in the linked list the value of all the nodes in

the linked list by calling a function named print there will be no argument to this function print of course we need to implement these two functions insert and print let me first write down the definition of these two functions so let us implement these two functions insert and print

let us first implement the function insert that will insert a node at the beginning of the linked list now in the insert function what we need to do is we first need to create a node in c we can create a node using malloc function we have talked about this earlier malloc returns a pointer to

the starting address of the memory block we are having to type custer because malloc returns a void pointer and we need a pointer to node a variable that is pointer to node and then only if we day reference we day reference using an asterisk sign then we will be able to access the fields of

the node so the data part will be x and we have an alternate syntax for this particular syntax we could simply write something like temp and this arrow and it will mean the same thing and this is more common with these two lines in the insert function all we are doing is we are

creating a node let's say we get this node and let's assume that the address that we get for this node is hundred now there is a variable temp where we are storing the address we can do one thing whenever we create a node we can set data to whatever we want to set and we can set the link field

initially to null and if needed we can modify the link field so I'll write one more statement temp.next is equal to null remember temp is a pointer variable here and we are de-referencing the pointer variable to modify the value at this particular node temp will also take some space in

the memory that's why I have shown this rectangular block for both the pointer variables head and temp and node has two parts one for the pointer variables and one for the data so this part the link part is null we can either write null here or we can write it like this it's the same thing logically it

means the same now if we want to insert this node in the beginning of the list there can be two scenarios one when the list is empty like in this case so the only thing that we need to do is we need to point head to this particular node instead of pointing to null so I will write a

statement like head is equal to temp and the value in head now will be address hundred and that's what we mean when we say a pointer variable points to a particular node we store the address of that node so this is our linked list after we insert the first node let us now see what we can do to

insert a node at the beginning if the list is not empty like what we have right now once again we can create a node fill in the value x here that is passed as argument initially we may set the link field as null and let's say this node gets address 115 the memory and we have this variable temp

through which we are referencing this particular memory block now unlike the previous case if we just set head is equal to temp now this is not good enough because we also need to build this link we need to set the next or the link of the newly created node to whatever the previous head was

so what we can do is we can write something like if head is not equal to null or if the list is not empty first set m dot next equal head so we first build this link the address here will be hundred and then we say head equal temp so we cut this link and point head to this newly created

node and this is our modified linked list after insertion of this second node at the beginning of the list now one final thing here this particular line the third line temp dot next equal null this is getting used only when the list is empty if you see when the list is empty head is already

null so we can avoid writing two statements we can simply write this one statement m dot next equal head and this will also cover the scenario when the list is empty now the only thing remaining in this program to get this running is the implementation of this print function so let us

implement this print function now what i will do here is i'll create a local variable which is pointed to node named temp and i need to write struct node here i keep missing this in c you need to write it like this and i want to set this as address of the head node so this global

variable has the address of the head node now i want to traverse the linked list so i will write a loop like this while temp is not equal to null i'll keep going to the next node using this statement temp is equal to temp dot next and at each stage i'll print the value in that node as temp dot data

now i'll write two more print one outside this while loop and one outside after this while loop to print an end of line now why did we use a temporary variable because we do not want to modify head because we will lose the reference of the first node so first we collect the address

in head in another temporary variable and we are modifying the addresses in this temporary variable using temp is equal to temp dot next to traverse the list now let us now run this program and see what happens so this is asking how many numbers you want to insert in the list

let's say we want to insert five numbers initially the list is empty let's say the first number that we want to insert is two at each stage we are printing the list so the list is now two the first element and the last element is two we will insert another number the list is now five two five is

inserted at the beginning of the list again we inserted eight and eight is also inserted at the beginning of the list okay let's insert number one the list is now one eight five two and finally I inserted number 10 so the final list is 10 1 8 5 2 this seems to be working

now if we were writing this code in c++ we could have done a couple of things we could have written a class and organized the code in an object oriented manner we could also have used new operator in place of the malloc function and now coming back to the fact that we have declared this head

as global variable what if this was not a global variable this was declared inside this main function as a local variable so I'll remove this global declaration now this head will not be accessible in other functions so we need to pass address of the first node as argument to other functions

to both these functions print and insert so to this print method we will pass let's say we name this argument as head now we can name this argument argument as head or a or temp or whatever if we name this argument as head this head in print will be a local variable of print and will not be

this head in main these two heads will be different these two variables will be different when the main function calls print passing its head then the value in this particular head in the main function is copied to this another head in the print function so now in the print function we

may not use this m variable what we can do is we can use this variable head itself to traverse the list and this should be good we are not modifying this head here in the main similarly to the insert function we will have to pass the address of the first node and this head again is just a copy

this is again a local variable so after we modify the linked list the head in main method should also be modified there are two ways to do it one we can pass the pointer to node as return from this method so in the main method insert function will take another argument head and we will have

to collect the return into head again so that it is modified now this code will work fine whoops i forgot to write a return here return head and we can run this program like before we can give all the values and see that the list is building up correctly there was another way

of doing this instead of asking this insert function to return the address of head we could have passed this particular variable head by reference so we could have passed insert ampersand head head is already a pointer to node so in the insert function we will have to receive

pointer to pointer node star star and to avoid confusion let's name this variable something else this time let's name this pointer to head so to get head we will have to write something like we will have to dereference this particular variable and write astric pointer to head

everywhere and the return type will be void sometimes we want to name this variable as head this local variable as head doesn't matter but we will have to take care of using it properly now this code will also work as you can see here we can insert nodes and this seems to be going well

if you do not understand this concept of scope you can refer to the description of this video for additional resources so this was inserting a node at the beginning of the linked list thanks for watching in our previous lesson we had written code to insert a node at the beginning of the linked list

now in this lesson we will write program to insert a node at any given position in the linked list so let me first explain the problem in a logical view let's say we have a linked list of integers here there are three nodes in this linked list let us say they are at addresses 200 and 250

respectively in the memory and we have a variable head and that is pointer to node that stores the address of the first node in the list now let us say we number these nodes we number these positions on a one based index so this is the first node in the list and this is the second node and this

is the third node and we want to write a function insert that will take the data to be inserted in the list and the position at which we want to insert this particular data so we will be inserting a node at that particular position with this data there will be a couple of scenarios the list could

be empty so this variable head will be null or this argument being passed to the insert function the position n could be an invalid position for example 5 is an invalid position here for this linked list the maximum possible position at which we can insert a node in this list will

be 4 if we want to insert at position 1 we want to insert at the beginning and if we want to insert at position 4 we want to insert at end so our insert function should gracefully handle all these scenarios let us assume for the sake of simplicity for the sake of simplifying our

implementation that we always give a valid position we will always give a valid position so that we do not have to handle the error condition in case of invalid position the implementation logic for this function will be pretty straightforward

we will first create a node let's say in this example we want to insert a node with value 8 at third position in the list so i'll set the data here in the node the data part is 8 now to insert a node at the nth position we will first have to go to the n minus 1th node

in this case n is equal to 3 so we will go to the second node now the first thing that we will have to do is we will have to set the link field of this newly created node equal to the link field of this n minus 1th node so we will have to build this link

let's say the address that we get for this newly created node is 150 once we build this link we can break this link and set the link of this newly created node as address of this set the link of this n minus 1th node as address of this newly created node we may have special cases in our

implementation like the list may be empty or maybe we may want to insert a node at the beginning let's say we will take care of special cases if any in our actual implementation so now let's move on to implement this particular function in our program

in my c program the first thing that i need to do is i want to define a node so node will be a structure and we have seen this earlier so node has these two fields one data of type integer and another next of type pointer to node now to create a linked list the first thing that i need to create

is a pointer to node that will always store the address of the first node or the head node in the linked list so i will create struct node star let's name this variable head and once again i have created this variable as a global variable to understand linked list implementation we need

to understand what goes where what variable sits in what section of the memory and what is the scope of these variables what goes in the stack section of the memory and what goes in the heap section of the memory so this time as we write this code we will see what goes where in the main method

first i'll set this head as null to say that initially the list is empty so let us now see what has gone where so far in our program in what section of the memory and the memory that is allocated to our program or application is typically divided into these four parts or these four sections

we have talked about this in our lesson on dynamic memory allocation there is a link to our lesson on dynamic memory allocation in the description of this video i'll quickly talk about what these sections are one section of the applications memory is used to store all the instructions that need

to be executed another section is allocated to store the global variables that live for the entire lifetime of the program of the application now one section of the memory which is called stack is used to store all the information about function call executions to store all the local

variables and these three sections that we talked about are fixed in size their size is decided at compile time the last section that we call heap or free store is not fixed and we can request memory from the heap during runtime and that's what we do when we use malloc or new operator

now i have drawn these three sections of the memory stack heap and the section to store the global variables in our program we have declared a global variable named head which is pointed to node so it will go and sit here and this variable is like anyone can access it initially value here

is null now in my program what i want to do is i first want to define two functions uh insert and this function should take two arguments data and the position at which i want to insert a node and insert that particular node at that position insert data at that position in the list

and another function print that will simply print all the numbers in the linked list now in the main method i want to make a sequence of function calls first i want to insert number two the list is empty right now so i can only insert that position one so after this insert list

will be having this one number this particular number two and let's say again i want to insert number three at position two so this will be our list after this insertion and i will make two more insertions and finally i'll print the list so this is my main method i could have also

asked a user to input a number and position but let's say we go this way this time now let us first implement insert i'll move this print above so the first thing that i want to do in this method is i want to create a node so i will make a call to malloc in c++ we can simply

write a new node for this call to malloc and this looks a lot cleaner let's go c++ way this time now what i can do is i can first set the data field and set the link initially as null i have named this variable temp one because i want to use another temp variable

in this function i'll come to that in a while now we first need to handle one special case when we want to insert at the head when we want to insert at the first position so if n is equal to one we simply want to set the link field of the newly created node as whatever

the existing head is and then adjust this variable to point to the new head which will be this newly created node and we will be done at this stage so we will not execute any further and return from this function if you can see this will work even when the list is empty because the head will be

null in that case i'll show a simulation in the memory in a while so hold on till then things will be pretty clear to you after that now for all other cases we will first need to go to the n-1th node as we had discussed in our logic initially so what i'll do is i'll create another

pointer to node name this variable temp two and we will start at the head and then we will run a loop and go to the n-1th node something like this we will run the loop n-2 times because right now we are pointing to head which is the first node so if we do this temp two equal temp two dot next

n-2 times we will be pointing temp two to n-1th node and now the first thing that we need to do is set the next or the link field of newly created node as the link field of this n-1th node and then we can adjust the link of this n-1th node to point to our newly created node and now i'm writing this

print here i've written this print here we have used a temporary variable a temporary pointer to node initially pointed to pointed it to head and we have traversed the whole list okay so let us now run this program and see what happens we are getting this output which seems to be correct

the list should be four five two three in this order now i have this code i'll run through this code and show you what's happening in the memory when the program starts execution initially the main method is invoked some part of the memory from the stack is allocated for execution of a

function all the local variables and the state of execution of this function is saved in this particular section we also call this stack frame of a function here in this main method we have not declared any local variable we just set head to null which we have already done here now the

next line is a call to function insert so the machine will set the execution of this particular method main on hold and go on to execute this call to insert so insert comes into this stack and insert has couple of local local variables it has two arguments data and this variable n

this stack frame will be a little larger because we will have a couple of local variables and now we create this another local variable which is a pointer to node m1 and we use the new operator to create a memory block in the heap and this guy temp1 initially stores the address of this

memory block let's say this memory block is at address 150 so this guy stores the address 150 when we request some memory to store something on the heap using new or malloc we do not get a variable name and the only way to access it is through a pointer variable so this pointer variable

is the remote control here kind of so here when we say temp1 dot data is equal to this much through this pointer which is our remote we are going and writing this value to here and then we are saying temp dot next equal null so null is nothing but address 0 so we are writing

address 0 here so we have created a node and in our first call n is equal to 1 so we will come to this condition now we want to set temp1 dot next equal head temp1 dot next is this section this second field and this is already equal to head head is null here and this is

already null null is nothing but 0 the only reason we set temp dot next equal head will work for empty cases because head would be null and now we are saying head is equal to temp1 so head guy now points to this because it stores address 150 like temp1

and in this first call to insert after this we will return so the execution of insert will finish and now the control returns to the main method we come to this line where we make another call to insert with different arguments this time we pass number 3 to be inserted at position 2

now once again memory in the stack frame will be allocated for this particular call to insert the stack frame allocation is corresponding to a particular call so each time the function execution finishes all the local variables are gone from the memory

now once again in this call we create a new node we keep the address initially in this temporary variable temp1 now let's say we get this node at address 100 this time now n is not equal to 1 we will move on to create another temporary variable temp2 now we are not creating a new node and

storing the address in temp2 here we are saying temp2 is initially equal to head so we store the address 150 so initially we make this guy point to the head node and now we want to run this loop and want to keep going to the next node until we reach n minus 1th node in this case n is equal to

2 so this loop will not execute this statement even once n minus 1th node is the first node itself now we execute these two lines the next of the newly created node will be set first so we will build this link oops no temp2 dot the next is 0 only so even after reset this will be 0

and now we are setting temp2 dot next as temp1 so we are building this link and now this call to insert will finish so we go back to the main method so this is how things will happen for other calls also so after everything we have inserted when we will reach this print statement

in the main function our list will be something like this in the memory this is a little messy i've chosen this addresses as per my convenience for the sake of example and now print will execute and once again i'm using a temp variable in print by now it should have been clear to you

why we use temp variable again and again and why this variable head that stores the address of the first node is so important now what if this head was not global what if we would have declared this head inside the main method we have talked about this in our previous lesson head will not

be accessible everywhere so in each call to these functions in each call to insert we will have to return some value from the function to update this head or we will have to pass this head by reference we have talked about this in our previous lesson so this is it for this this lesson

in our next lesson we will see program to delete a node at a particular position in the list so thanks for watching in our previous lesson we wrote program to insert a node at nth position or a given position in a list in a linked list now in this lesson we will write a program to delete

a node at any given position in a linked list so once again i have drawn a linked list here we have four nodes in this list at addresses 100, 200, 150 and 250 respectively so this is my example of a linked list of integers and let's say we number the positions on a one based index

so this is the first node in the list and this is the second node this is the third node and this is the fourth node when we talk about deleting a node from the linked list we will have to do two things first we will have to fix the links so that the node is no more a part of the list

let's say in this case we want to delete the node at third position so we will go to the second node for nth node we will have to go to the n minus 1th node and we will have to set the link part of the n minus 1th node as the link of the nth node which will be the n plus 1th node so we will cut

this link and now this node at address 150 is not part of the linked list because when we will traverse the linked list we will go from address 100 to 200 and from 200 we will go to 250 this is one scenario for deletion in which we have a node before and a node after

there will be special cases like we may want to delete the node at the first position or the head itself in that case we will have to point head to the second node we will have to build this link now we will talk about all these special cases in our implementation let's first understand

the logic now fixing the links is not good enough because all that we do when we fix the links is that we detach the node from the linked list so that it is no more accessible but it is still occupying space in the memory as we know a node is allocated space from what we call the dynamic

memory or the heap section of the memory we have talked about this earlier in C or C plus plus we have to explicitly free this memory when we are done using it because it is not automatically deallocated and memory being a crucial resource we do not want to consume it unnecessarily when

we do not need it so the second thing that we will have to do is we will have to free the space that's being taken by the node and that's when the node will actually be deleted from the memory so let us now write code for this I'm writing my C program here the first thing that I have

done is I have defined a node which is a structure with two fields one to store data and another to store address of the next node so the second field is appointed to node now to create a linked list we will have to first create a pointer to node a variable which is pointer to node and

that will store the address of the head node or the first node in the list and now I want to define three functions first insert function that will take some value some data to be inserted into the list and always insert this value at the end of the list then I want to define a print function

that will print all the elements in the list now we have defined this variable head as a global variable so it will be accessible to all these functions and the third function that I want to write is delete that will take the position end of the node to be deleted and delete the node at

that particular position we will go back to implementing these methods first I'll write the main method so in the main method first what I'll do is I'll set head as null so at this stage the list is empty and then I'll make a couple of calls to insert function to insert some integers

in the list so after this fourth insert the list will be two four six five because we are always inserting at the end of the list this insert function will insert the node at the end of the list now what I want to do in my main method is I want to ask a user for a position and I'll input this

position from the console and then I'll delete the node at this particular position and then I'll print the whole linked list now let's also make a call to print after all the inserts okay so this is what we want to do in our main method we want to insert four integers

in a linked list to create a list two four six five in this order and then I want to print the list then I want to input a number from the console and delete the node at that particular position now let us assume that we will always give a valid position and in my implementation also

I will not handle the error condition when position will not be valid we have seen implementation of insert and print earlier so I will not go into their implementation details what I'll do now is I'll implement delete function now in my delete function let's first

handle the case when there is a node before the node that we want to delete so we have an n minus one-th node what I'll do is I'll first create a temporary variable that is pointed to node and point this to head and using this temporary variable we will go to n minus one-th node to go

to the n minus one-th node we will have to run a loop n minus two times and we will have to do something like this temp1 is equal to temp1.next now what I'll do is I'll create a variable to point to the nth node name this temp2 and this will be equal to temp1.next and now I can fix the link

I can say that adjust the link section the link part of n minus one-th node to point to n plus one-th node which will be temp2.next now our linked link is fixed and this variable temp2 stores the nth node reference to the nth node so we can make a call to free

function now free function deallocate whatever memory is allocated through malloc if we were using c++ and used and if we would have used new operator we should have said delete temp2 okay now we should be good this much code will work for scenarios when we have an n minus one-th

node and even if there is no n plus one-th node if n plus one-th position is null this will work for this that scenario I'll leave that as an exercise for you to validate now we have not handled one special case when we want to delete the head node so if n is equal to one then what we want

to do is we just want to set head as temp1.next temp1 is right now equal to head and now head has moved on to point to the second node and temp1 still points to the first node so links are fixed and we can free the first node which is now detached from the linked list because head is now

pointing to the second node okay so this is our delete function I have missed one thing here for n not equal to one we should not execute this section of the code so either we put an else statement after this or what we can do is we can say return after we execute these statements

for this condition now this code should work if I've got everything right so let us now run this and see what happens I have already written the insert and print functions I'll come back to this main function this is my list 2465 and I can enter any of the positions one two three or four

so let's first say we want to delete the head node and we are printing the list after deleting a particular node so the list now is 465 this seems to be correct let us run this again and this time I delete number five from position four the list is now 246 which is correct again

similarly if I enter position two the list is 265 which is correct so we seem to be good I'll quickly walk you through this code in the logical view to make things further clear let's say we first make a call to delete node from the first position that is we want to delete

the head node so in this code what we are doing is we are first creating a variable temp1 which is pointed to node initially temp1 is equal to head so it stores the address 100 so it points to the head node now n is equal to 1 so we come to this instruction head is equal to temp1 dot next

actually this is temp arrow dot next but while reading we read this as temp1 dot next this is nothing but a syntactical sugar for this statement asterisk temp1 dot next so we are de-referencing this pointer variable to go to this node and then accessing the next

field of this node now we are saying head is equal to temp1 dot next so head is now 200 so we are building this link and breaking this link and now in the next line we say free temp1 so we want to free the memory which is being pointed to by this variable temp1

temp1 still points to this node at address 100 so this node now will be cleared from the memory and now we return so this function does not execute any further it finishes its execution once the function execution finishes temp1 which was a local variable also gets cleared from the

memory head is a global variable so it does not gets cleared this is how we know the linked list this is the identity of the linked list this particular variable head let's read on this code again and this time i want to delete the node at third position in the list i have drawn this

initial list so once again we create this variable temp1 we say that the address here is equal to 100 so it points to the head node or the first node and now n is not equal to 1 it is equal to 3 so we come to this particular loop n is equal to 3 so this loop will execute exactly once

this statement will execute exactly once so temp1 will now move to address 200 so temp1 is now pointing to the second node this is what we wanted to do we wanted temp1 to point to n minus 1th node n is 3 here now we create another variable another pointer to node temp2 and we set this guy as temp1

dot next temp1 dot next is 150 so we set this guy as 150 so this guy points to the nth node or the third node now in the next line we are saying that temp1 dot next this value which is 150 right now is now temp2 dot next address of the n plus 1th node or fourth node so this guy will

now be 250 so we are building this link and we are breaking this link so we have fixed the links and now finally we are saying that free the memory which is being pointed to by temp2 so now this third node the memory block will be deleted from the memory and once this function

execution finishes all the local variables temp1 and temp2 will be cleared and this is what the list will be this node at address 250 will now be the third node so this was deleting a node at a particular position in the linked list now we can also have a problem where we may want to delete

a node with a particular value now you can try implementing it in the coming lessons we will see more problems on linked list so thanks for watching in our lessons on linked list so far we have implemented some of the basic scenarios like inserting a node in linked list and deleting a node

from linked list in this lesson we will write code to reverse a linked list this is one of the most favorite interview questions and this is a really interesting problem so let me first define the problem let's say we have been given a linked list of integers like this so this is our input

we have four nodes in this linked list at addresses 100, 200, 150 and 250 respectively I always write these addresses in the logical view because it's really important that we visualize how things are in the memory and what is what like this first node that we also call the head node

is being pointed by this particular variable named head so this variable is basically storing the address of the head node now this variable is only a pointer this is not the head node itself and we do not have any other identity of the linked list except the address of the head node

so given a linked list like this if we have to reverse it and by reversing we do not mean moving around data like we cannot move five at address 100 two at address 250 and do something like this we actually have to adjust the links so our output should be something like this the head

pointer should point to this node at address 250 and we should go like 250 250 150 to 200 and this node at address 100 should have address 0 or null in each of these nodes this first field in red is the data part and the second field is the address part so this is what we will get when

we will reverse the list there are two approaches to solve this problem one is an iterative approach where we will be using a loop we will traverse through the list and at each step we will revert one of the links another solution is using recursion in this lesson we will try to understand

the iterative solution so coming back to our input list the iterative solution is relatively easier to understand what we can do is we can traverse the whole list and as we go to each node we can adjust the link part of that node to make it point to the previous node instead of the next

node so we will start at the first node at each step we want to reverse the link so we want to make the node point to the previous node instead of the next node for the first node there is no previous node so let's say the previous node is null and now we want to cut this particular link

and we want to build this particular link so we will simply change the address field to 0 and we have reversed the link part of this particular node and now we will go to the next node in the list we will come to this node of course the question would be how would we

go to the next node if we have broken this link here we will come back to that in our implementation details let's say we are able to traverse the list and go to each of the nodes at each step let's say we store all the relevant information to do that in some temporary variables now at this

node again we will reverse the link so the address part will be set as 100 here now we will go to the next node at address 150 once again to reverse the link we will set the address as 200 here so we will break this link and basically we are building this link and now we will go to address

250 the next node we will set the address 150 here so we will cut this link and build this link and finally when we have reached the last node we will adjust the address in this head variable to 250 so this particular variable this particular pointer

will point to this node at address 250 and our linked list is reversed now so let us implement this particular logic in a real c program I will redraw the original input list in my ccode I will define node as a structure like this this is how we have defined a node

in all our previous lessons so there will be two fields one to store the data which will be of type integer and another to store the address of the next node we will name this feed it next and it will be of type pointer to node and let's say head is a global variable so head is a pointer to node

head is a variable which is a pointer to node and it is a global variable so it is accessible to all the functions it we do not need to pass it around to functions now all I want to do in my code is I want to write a reverse function that will reverse the linked list which is pointed to

by this particular pointer head as we said we will traverse the whole list and at each step we will modify the link field of the node to make it point to the previous node instead of the next node so how do we traverse the list we would traverse the list in our ccode something like this

we will first take a variable which will be pointer to node let's say we will name it temp then first we will set temp to head by saying this we will make temp point to the first node and then we will run a loop like this we will say that what temp while temp is not

equal to null take temp to the next address with a statement like temp is equal to temp dot next in our problem here we don't just have to traverse the list as we traverse the list we have to reverse the link so we have to set the address field of a particular node as the address of the

previous node instead of the next node now in a linked list we would always know the address of the next node but we would never know the address of the previous node so as we traverse the list we will have to keep track of the previous node in another variable so what I will do here is

something like this I will also declare a variable named previous and initially set it to null because for the first node or the head node the previous node is null and now in my loop we will have to update both these variables and the variable temp that will store the current node

and the variable pref that will store the address of the previous node and now in my loop I can do something like this at each step if temp is our current node as we are traversing the list then we will say that temp dot next is equal to previous so we will set the link part of the

current node as the address of the previous node in our example here at the first step we will say that temp dot next will be 0 null is nothing but address 0 so we will cut this link and we will build this link now we should be able to move temp to 200 now and we should be able to move

previous to 100 now in the next step but there is a problem as soon as we adjusted the link of this particular node at address 100 to make it point to null we lost the address of the next node so how do we move temp to this particular node at address 200 we cannot set temp equal temp

dot next now if we set temp equal temp dot next now we will go to null so this is a problem so at each step in our iteration before we set the link field of the current node to make it point to the previous node we should store the address of the next node in our temporary variable in

another temporary variable so what I'll do here is something like this first of all I want to name this particular variable temp as current to mean that this is the current node at any stage in my iteration so we initially set current to head and then we are running the loop as while current is

not equal to null and then I've also declared one more temporary pointer variable named next what I'll do at each step each step in my iteration inside the while loop is that first I'll say something like next is equal to current dot next so first I'll store the address of the next node

in this particular variable next so in our example here for the first node initially things will look some something like this now we can set the link part of the current node as address of the previous node with a statement like this so when we will write the address 0 here initially we will break

this link and create this link we will not lose the information about the next node now we can redefine our previous and current so we will first move previous to current and then we will move current to next please note that this particular variable next is a local variable in the reverse

function and when we say something like current dot next we mean the link field in the node while when we say when we simply say next we mean this particular local pointer variable so they're different this is not current dot next actually this is current arrow next which is an alternate

syntax for asterisk current dot next so we use the asterisk operator to dereference that address and then we access the next field for the sake of saying we say current dot next dot temp dot next so with these two lines in our loop we are resetting our previous and current pointers

this is how we are traversing the list if you see in the next iteration current is 200 it is not equal to null null is 0 so we will go to this particular statement next is equal to current dot next so next we'll now store the address 150 and now we will say current dot next is equal to previous

so we will cut this link previous is 100 right now so we will set 100 here so basically we will build this particular link and then we will move we will first move previous to current and then move current to next and we will go on like this

so finally we will reach a stage like this when current will be equal to null we will come out of the loop and when we will come out of the loop this particular variable previous this particular pointer previous will store the address of the last node and there is one more thing remaining

here we need to adjust this particular variable head this link at this stage does not exist and in my code I'll say head should now be equal to the address invariable previous so head is now 250 this is our new head and now our list is reversed there are a couple of things that I

want to point out here one thing is that we must see whether our implementation is working for all test cases so we must also verify it for special or corner test cases in this case corner test case will be when the list is empty in that case head will be null or when the list is having

only one node if you see this particular implementation will work for these two scenarios give it give it some time and you should be able to figure it out let's now run this code with complete implementation of all the functions to insert and print nodes in my code here i have

written reverse function to accept the address of the head node as argument and then return the address of the head node after modification of the list after reversal of the list and then i have written the main method in which i'm declaring head as a local variable

and then i'm using couple of insert functions i'm making couple of calls to insert function insert function also takes two arguments the address of the head node and the data to be inserted and it returns back the address of the head node it could either be modified or not modified

let's say we are inserting at the end of the list so initially our list will be two four six eight and then we are making a call to the print function which i have written to print the elements in the list and then i'm making a call to reverse and finally printing again

my logic of the reverse function remains the same except that i've changed the method signature and in the end i'm returning head which will return the address of the head node let's say we have written all the other functions insert and print correctly

these are the two functions insert and print so let's now run this code and see what happens before the list is reversed the output is two four six eight and after the list is reversed the output is eight six four two let us try this for the case when we have only one element in the list

so i'll remove i'll comment out these three insert statements and this also seems to be working so this was reversal of linked list through iteration in the next lesson we will write code to reverse linked list using recursion so thanks for watching in our series on linked list so far we have implemented

some of the basic operations like insertion deletion and traversal now in this lesson we will write code to traverse and print the elements of a linked list using recursion prerequisite for this lesson is that you should understand a recursion as a programming concept

recursive traversal of linked list actually helps us solve a couple of interesting problems but in this lesson we will keep it simple we will just traverse and print all the elements in linked list using recursion and we will write one simple variation to print all the elements in reversed

order using recursion we will actually not reverse the list we will just print the elements in reversed order so once again i have taken example of a linked list of integers here we have four nodes each rectangle here is a node it has two fields one to store the data and another to store the

address of the next node let's say we have four nodes that addresses 100 200 150 and 250 respectively and of course we will also have a variable that will store the address of the head node let's name this variable head programmatically in our c or c++ program a node will be defined something

like this we will have a structure with two fields one to store the data and another to store the address of the next node what we want to do in this particular lesson is that we want to write two functions first we want to write a function named print that will take address of a node as

argument we will pass this function the address of the head node so let's name this argument head and in this function we will use recursion to print the elements in the list so for this particular example here if we want to print a space separated list of all the elements our output will be

something like this and we also want to write another function named reverse print here also we will take the address of a node so we will pass this guy the address of the head node and in this function we will use recursion to print the elements in the list in reversed order so if we have to

print a space separated list for this example and our output will be something like this so let's first implement the print function in my c code here i'll declare print function like this it will take us argument the address of a node so the argument is of type pointer to node

initially we will pass the address of the head node we can name this argument head or we can name this argument p we can name it whatever but we must understand that this will be a local variable and let's not bother about other infrastructure in the code like how we would create a linked

list and how we would insert a node in the linked list let's assume that they are in place so let's keep the name of this particular argument p now recursion is a function calling itself so we have been passed the address of a node initially the head node so what we can do in our code is first

we can print the value at that particular node with a print f statement like this and then we can make another call to the print function and this time we will pass the address of the next node with a statement like this this next field is also a pointer to node so this will pass the address

of the this will be the address of the next node there is one more important thing in recursion and that we should never forget and it's the exit condition from recursion we should not go on making recursive calls infinitely so in this case if we go from the first node to the second node

and from the second node to the third node using recursion then finally at one stage p will be equal to null in one of the calls at this stage we can avoid making a recursive call we will exit we will show you a simulation of how things will happen in memory hold on for a while

so once we will reach the end of the list p will be equal to null and we will exit the recursion at that stage now i'll write the main method i've already written the insert function here so i'll declare a variable head as null in the main method so head will be a local variable

once again we could name this particular variable a or b or whatever just because this variable points to the head node or the first node in the list we named this variable as head and then we will insert some nodes in the linked list using by making call to the insert function

that takes the address of the head node as argument initially head is set as null to say that the list is empty and there should be two arguments to head to the function insert the address of the head node and the value that needs to be inserted and why is it that this particular function insert

is returning a pointer it's because this head in the main method is a local variable and if we pass it to the function we just pass a copy of the address of the head node in this head which will be a local variable of insert function so this guy returns back the address of the modified head

so we can update it in the main function this function inserts a node at the end of the list so initially when head is null head will be modified in the insert function for other cases it will not be modified if we are inserting at the end so we will make four such calls to the insert

function to create a linked list of four integers two four six five and now we will make a call to print function and pass it the address of the head node let us now run this code and see what happens as you can see we have got this output two four six five the print function here in our

code which is a recursive implementation to print the lists is working now i'll make one slight change in the print function instead of printing the value in the node and then making a recursive call i'll first make a recursive call and then when the recursive call finishes

i'll print the value in the node and i'll not modify anything else in the code the main method will remain the same and if we run this code we can say that we can see that the elements in the list are printed in reversed order so we just implemented the reverse print function that we

had talked about let us now analyze these two recursive implementations in a logical view in our example here if we want to print this particular list we will do something like from the main method we will make a call to the print function passing a third address of the head node

so initially this print function is being called with p equal hundred now in the execution of this function we will come here if p is equal to null null is address 0 and our argument is hundred so control will not go inside this if condition we will come here we will print p arrow data p arrow

data means that we will first dereference the address so we will go to the address hundred and then we will look at the data field there so on the console we will print the data field of data field at address hundred and now we will make a recursive call we will make a call to

print function passing it address p arrow next which is 200 and the execution of this particular call will not finish it will finish only after print 200 finishes we will come back to it now print 200 once again prints the data at address 200 and then makes a recursive call to print function

passing address 150 and we will go on like this in this call to print with address 250 we will first print the data and the address field the the value of p dot next p arrow next is 0 what we can also say null so we will make a call like this now for this call

with argument null we have reached and the exit condition recursion will not go grow any further so we will just print an end of line and return this particular structure that we have drawn here is called recursion tree so print null function call will finish and control will return back

to print 250 there is no statement after this particular recursive call finishes so we will simply exit this function call also and control will return back to print 150 and we will go on like this finally we will come back to the main method

if you want to see how the recursion will execute in the memory then i'll have to draw a diagram like this applications memory the memory that is allocated for the execution of a program has these two sections all the details of function call execution and the local variables

they are stored in the stack section of the memory and any memory that is allocated using the malloc function or the new operator in c++ they go into the heap section the memory for the nodes in a linked list is allocated from the heap so that's why these four nodes

in our example are sitting in the heap if you want to know in detail about stack and heap check the description of this video for a lesson on dynamic memory allocation when the program will start executing first the main function will be invoked

anytime a function is invoked some amount of memory from the stack is allocated for the execution of that particular function now it's called the stack frame of that function so let's say main is executing we have already inserted some nodes in the linked list we have this variable head in

the main function so all the local variables in sit in the stack frame of the function so head will sit here now at this stage let's say main makes a call to print function so main was executing and now it makes a call to print function execution of main will be paused

and we will go on to execute the print function the argument passed to the print function is hundred which is stored in a local variable this argument p is a local variable in the print function now print function again makes a recursive call now a stack frame is always allocated

corresponding to each recursive each call of a function so a function calling itself is not different from a function calling another function at any time whatever function call is at the top of the stack is executing finally even we will reach the exit condition of the recursion stack

will be something like this and then first this call where p is zero will finish we will come back to this particular call and then this will finish and we will go on like this so this is how recursion works this is how things will happen in the memory okay so now i'll clear this diagram

of stack and heap in the right and i'll make some change in my print function what i've done is i have renamed my function print as reverse print and in my function i'm first making a recursive call and after coming back from that recursive call i'm writing

a print statement and from the main function i'll make a call to reverse print let's write rp as shortcut for reverse print and initially i'll pass the address of the head node so i'll make a call like this reverse print hundred the control will come inside this function

p is hundred it is not equal to null and i've also drawn the console like before now this particular function call does not print first it first makes a recursive call so this guy will go ahead and make a recursive call to the reverse print function passing

it address 200 nothing will be written on the console and once again this particular function will make a recursive call like this and once again this particular function will go ahead and make a recursive call like this and finally we will have a recursive call where the function

is passed address null at this stage we will come to in the exit condition in the recursion the recursion will not grow any further we will simply return the control will return to this particular call reverse print 250 so we will come here now to this print of statement

the data field at address 250 is 4 so 4 will be printed on the console and now this particular function call will finish and we will go to reverse print 150 and now this call will print 5 and exit and we will go on like this finally we will return back to the main function with this output

on the console the elements of the list printed in reversed order so this was recursive traversal of linked list to print its elements i must point out here that for normal traversal of the linked list not for the reverse print for the normal print an iterative approach will be a lot more

efficient than the recursive approach because in a iterative approach we will just use one temporary variable while in recursion we will use space in the stack section of the memory for so many function calls so there is implicit use of memory there for reverse print operation

we will anyway have to store elements in some structure so if we use recursion it's still okay in the coming lessons we will solve more problems more interesting problems on linked list so thanks for watching in our previous lesson we saw how we can traverse a linked list using recursion

we wrote code to print the elements of linked list in forward as well as reverse order using recursion we did not actually reverse the list we just printed the elements in reverse order now in this lesson we will reverse a linked list using recursion this is yet another famous programming

interview question so if we have an input list like this we have a linked list of integers here we have four nodes in the linked list each rectangular block here with two partitions is a node first field is to store the data and another to store the address of the next node the second field stores

the address of the next node and of course we will have one variable to store the address of the first node or head node we named that variable head we may name it anything i have named it head so this is our input list and after reversal our output should be like this

this variable head should store the address of the last node in the original list the last node in the original list was that address 250 and we will go like from 250 to 150 to 250 to 200 200 to 100 and 100 to null null is nothing but address 0 we have already seen how we can reverse

a linked list using iterative method in one of our previous lessons let us now see how we can solve this problem using recursion in our solution we must reverse the list by adjusting the links by reversing the links not by moving around data or something so let us first understand the logic

that we can use in our recursive approach if you remember from our previous lesson where we had used recursion to print the list backward print the elements in reverse order then recursion gives us a way to traverse the list backward in our c or c++ program programmatically

node will be a structure like this so let's first look at the function from the previous lesson the recursive function that was used to print the list backward to this function we pass the address of a node initially we pass the address of the head node and we have this exit

condition if the address passed is null then we simply return else we make a recursive call and pass the address of the next node so main method will typically call reverse print passing it the address of the head node and this guy will first make a recursive call and then

when this recursive call finishes then only it will print so i'm writing rps shortcut for reverse print so the recursion will go on like this and when it reaches this particular call when argument is null it will return so this call will finish and again the control will come

to this call with an address 250 as argument and now we are printing the value of the node at address 250 which will be 4 and then this guy finishes and then we go ahead and print 5 and similarly we then go on to print 6 and 2 so recursion kind of gives us a way to first

traverse the list in the forward direction and then traverse the list in the backward direction so let us now see how we can implement reverse function using recursion let's say for the sake of simplicity and implementation that head is a global variable so it is accessible to all the

functions now we will implement a function named reverse that will take the address of a node as argument initially we will pass address of the head node to this function now i want to do something like this in my recursion i want to go on till the end i want to go on making a recursive

call till i reach the last node for the last node the link part will be null so this is my exit condition from recursion this exit condition is what will stop us from going on infinitely in a recursion and what i'm doing here is something very simple as soon as i'm reaching the last

node i'm modifying the head pointer to make it point to this guy so the recursion will work like this from the main method we will call the reverse function passing it the address of the head node address 100 we will come and check this condition if p.next is equal to null no it is equal to 200

for the node at address 100 so this recursion will go on till we reach this call call to reverse passing it address 250 and now we will come down and now we have come to this exit condition and now head will be set as p and the list will look like this and now reverse 250 the call to reverse 250

will finish and we will come back to reverse 150 there is no statement here after this recursive call to reverse function if there were some statements here then they would have executed now for reverse 150 after we would have come from reverse 250 and that's how we actually traverse

the list in reverse order if you see when reverse 250 has finished the node till 250 is already reversed because head is pointing to this node and the link part of this node node is set as null so till 250 we are already reversed now when we come to 150 we can make sure the list is reversed

till 150 when we finish the execution of reverse 150 to do to do that we can write statement like this we will have to do two things we will have to cut this node and make this type point to this guy so we will build this link and we would have to cut this link and make this guy point to null

and that's how node till address 150 will be reversed after we finish this call so i've written these three lines in my function that will execute after the recursive call so they will execute when the recursion is folding up and we are traversing the list in the backward

direction so when we are executing reverse 150 and we have come back to it after recursion we are at this particular line so p would be 150 and q would be p dot next so q would be 250 so this guy is p and this guy is q and we are saying that set q dot next is equal to p so we will set this

particular field as 100 so we are building this link and cutting this link and now we are saying that set p dot next equal null so we are building this link making p dot next null and now this call to reverse 150 finishes and when this call has finished the list till 150 is reversed as you can

see head is 250 so from 250 we will go to 150 and 150 from 150 we are going to null so till 150 we have a reversed list so this is how things will look like when the call to reverse 200 finishes till 200 we have a reversed list and once again we come to execution of reverse 100

and this is how things will look like finally when reverse 100 will finish and we will return back to the main function we had seen in the previous lesson that how things will happen in the memory when recursion executes in recursion we save the state of execution of all the function calls

in stack section of the memory in this function all we are doing is basically we are storing the addresses of node in a structure as we go forward in recursion and then we first work on the last node to make it part of the reversed list and then we once again come back to the previous node and

we and we keep doing this watch the previous lesson for detailed explanation and simulation of how things will happen in the memory for recursion there are a couple of more things here one thing is that instead of writing these two lines i could write one line for these two lines

i could say something like p arrow next arrow next equal p and that would have meant the same except that this statement is more obfuscated and there is one more thing we have assumed that head is a global variable whatever head is not a global variable this reverse function

will have to return the address of the modified head i'll leave that as an exercise for you to do so this was reversing a linked list using recursion thanks for watching hello everyone in our lessons in this series so far we have discussed linked list quite a bit

we have seen how we can create a linked list and how we can perform various operations with linked list linked lists as we know our collections of entities that we call nodes so far in all our implementations we have created linked lists in which each node would contain two fields one to

store data and another to store address of the next node let's say we have a linked list of integers here so i'll fill in some values in data field of each node let's assume that these nodes are at addresses 200, 250 and 350 respectively i'll also fill in the address field in each node the address

field in first node will be the address of second node which is 250 the address field in second node will be address of third node which is 350 and address part in third node will be zero or null the identity of a linked list that we always keep with us is the address of head node or

reference to head node let's say we have a variable named head only to store the address of the head node remember this variable named head is only a pointer to the head node ideally we should have named there's something like head pointer it's only pointing to the head node it's not

the head node itself head node is this guy the first node in the linked list okay so right now in the linked list that we are showing here each node has only one link a link to the next node in a real program node for the linked list that i'm showing here will be defined like this

this is how we have defined nodes so far in all our lessons we have two fields here one of type integer to store data and another of type pointer to node struct node asterisk i'm calling this field next when we say linked list by default we mean such a list that we can also

call singly linked list what we have here is a singly linked list what we want to talk about in this lesson is idea of a doubly linked list the idea of a doubly linked list is really simple in a doubly linked list each node would have two links one to the next node and another to

the previous node programmatically this is how we will define node for a doubly linked list in c or c plus plus i have one more field here which once again is a pointer to node so i can store the address of a node i can point to a node using this field and this field will be used to store

the address of the previous node in a logical representation i will draw my node like this now i have one field to store data one to store address of previous node and one to store address of next node let's say i want to create a doubly linked list of integers i have created three nodes here

let's say these address these nodes are at addresses 400 600 and 800 respectively i'll fill in some data let's say the cell in the middle in each node is to store data the right most cell is let's say to store the address of the next node so for first node this field will be 600

which means we have a link like this for second node this field will be 800 for third node this field will be zero for first node there is no previous node so this leftmost cell which is supposed to contain the address of the previous node will be zero or null

the previous node for second node will be 400 and the previous node for the third node is the node at address 600 and of course we will have a variable to store the address of the head node okay so what we have here is a doubly linked list of integers with three nodes okay so with this much

you already know doubly linked list if you have ever implemented a singly linked list then it should not be very difficult implementing a doubly linked list one obvious question would be why would we ever want to create a doubly linked list what are the advantages or huge cases of a

doubly linked list first advantage is that now if we have a pointer to any node then we can do a forward as well as reverse lookup with just one pointer we can look at the current node the next node as well as the previous node i am showing a pointer named temp here if temp is a pointer

pointing to a node then temp dot next is a pointer pointing to the next node it's the address of the next node and temp dot previous or rather temp arrow previous this is actually a syntactical sugar for asterisk temp dot prev so this guy temp arrow prev is previous node or in pure words pointer to

previous node the value stored in temp for this example right now is 600 temp dot next is 800 and temp dot prev is 400 in a singly linked list there is no way you can look at the previous node with just one pointer you will have to use an extra pointer to keep track of the previous node

in a lot of scenarios the ability to look at the previous node makes our life easier even implementation of some of the operations like deletion becomes a lot easier in a singly linked list to delete a node you would need two pointers one to the node to be deleted and one to the previous

node but in our doubly linked list we can do so using only one pointer the pointer to the node to be deleted all in all this ability that we can do a reverse lookup in the linked list is really useful we can flow through the linked list in both directions disadvantage of doubly linked list

is that we are having to use extra memory for pointer to previous node for a linked list of integers let's say integer takes four bytes in a typical architecture and pointer also takes four bytes pointer variable also takes four bytes then in a singly linked list each node

will be eight bytes four for data and four for a link to the next node in a doubly linked list each node will be 12 bytes we will take four bytes for data and eight bytes for links for a linked list of integers we will take twice for links than data with a doubly linked list we also need to be more

careful while resetting links while inserting or deleting we need to reset a couple of more links than a singly linked list and so we are more prone to errors we will implement doubly linked list in a c program in next lesson we will write basic operations like traversal insertion and deletion

this is it for this lesson thanks for watching in our previous lesson we saw what doubly linked lists are now in this lesson we are going to implement doubly linked list in c we are going to write simple operations like insertion traversal and deletion in a doubly linked list as we saw in

our previous lesson each node contains three fields i have drawn logical representation of a doubly linked list here one to store data one to store address of next node and one to store address of previous node for a linked list of integers node will be defined like this in a c

or c plus plus program in the logical representation i'll fill in some data in each node let's say these nodes are at addresses 400 600 and 800 respectively i'll also fill in next and previous fields and we must also have a pointer variable pointing to the head node quite often we

name this pointer variable head in my implementation i'm going to write these functions i'm going to write a function to insert a node at beginning or head of linked list this function will take an integer as argument i'll write another function to insert a node at tail of linked list i'll write

one function to print elements in linked list while traversing it from head to tail i'll write another one to print the elements in reverse order while traversing the list from tail to head reverse print function will validate whether reverse link for each node is created properly

or not let's now write these functions in a real c program in my c program here i have defined node as a structure with three fields first field is of type integer to store data second field is of type pointer to node to store reference of next node and the third field is a pointer to

node to store the reference of previous node i have defined a variable named head which once again is a pointer to node and i have defined this variable in global scope head is a global variable when we define a variable inside a function it's called a local variable the lifetime of a

local variable is lifetime of a function call it's created during a function call execution and it's cleared from the memory when function call execution finishes but global variables live in the memory for whole lifetime of an application they live till the time program is

executing global variables can be accessed everywhere in all functions local variables are not accessible everywhere unless you access them through pointers in all our previous implementations we have mostly declared head as global variable okay so let's now write the functions the first function that i want

to write is insert at head this function will take an integer as argument the first thing that we want to do here is we want to create a node we can always declare a node like this just like declaration of any other variable we can say struct node and then we can give an identifier

or name and now in this my node that i have created i can fill in all the fields but the problem here is that when i'm creating a node like this i'm creating it as a local variable and it will be cleared from memory when function call will finish a local variable lives in what we

call stack section of applications memory and we cannot control its lifetime it's cleared from memory when function call finishes we do not want this our requirement is that a node should be in memory unless we explicitly remove it so that's why we create a node in in dynamic memory or what

we call heap section of memory anything in heap is not cleared unless we explicitly free it to create a node in heap we use malloc function in c or new operator in c++ all malloc function does is it reserves some memory in heap and this memory can be used for writing anything

any variable any object access to this memory always happens through a pointer variable we have talked about this concept quite a bit in our previous lessons but i keep on repeating because this is really important concept so here with this statement i have created a node in dynamic

memory or heap that can be referenced through a variable which is pointer to node i have named this variable temp now i can use this pointer variable to fill in values in various fields of the node i'll have to dereference this pointer variable using asterisk operator and then i can

access various fields like data prep or next there is an alternate syntax for this asterisk temp dot data we can simply write temp arrow data and similarly i can access other fields also so to access prep field i can say temp arrow prep let's set this as null and let's also set the

next field as null if you want to understand or refresh the concept of stack and heap in memory then you can check the description of this video for a link to our lesson on dynamic memory allocation okay so in my function insert at head i have created a node in heap section of memory

and i'm referencing that node using this pointer variable named temp temp is not a very meaningful name let's use a name like new node or new node pointer i would like to separate out this logic of node creation these lines for node creation in a separate function i've written a function

here named ket new node that will take an integer's argument create a node filling in data field as x and setting both previous and next pointers as null this function will return a pointer to nodes so i will return new node from here i'm writing a separate function because i can avoid duplicate

code by using a separate function for creation of node because i'm going to create a node for function in function insert at head as well as in function insert at tail that i'll be writing after some time now in insert at head function i can simply call this function get new node passing

it x this function is returning a pointer to newly created node that i'm going to receive in this variable which once again is appointed to node named temp we can name this variable also as new node this new node in insert at head is different from this new node in get new node these are local

variables this new node is local to insert at head and this new node is local to get new node now there will be two cases in insertion at head list could be empty so head will be equal to null in this case we can simply set head as the address of new node and return or exit

things will be clear if i'll show everything in logical view also right now my linked list is empty here in this logical view that i'm showing let's say i have made a call to insert at head passing it number two get new node function will give me a new node let's say a new node is created

at address 400 with this statement head equal new node we are setting the address stored in new node variable in head null is nothing but address 0 as soon as this function insert at head will finish this variable new node will be cleared from memory but the node itself will not be cleared

if we would have created node like this struct node new node and in this declaration new node is not pointed to node it's node and we are not saying struct node as stress so if we would have created node like this the node also would have been cleared okay coming back

to the function here let's write rest of the logic to insert a node when list is not empty this is what i'll do now i'm making a call to insert at head passing it number four once new node is created i'll first set the previous field of existing existing head node

as the address of this new node so i'm building this link then i'll set the next field of new node as the address of current head and now i can break this link and build this link so i'll set head as address of new node this is how things will look like finally

let's also quickly see how things will actually move in various sections of applications memory the memory that is allocated to a program is typically divided into these four segments we have seen this diagram quite a bit in our earlier lessons code or text segment stores

all the instructions to be executed there is a segment to store global variables there is a section that we call stack that is used just like scratch pad or white board for function call execution stack is where all the local variables go and not just local variables all

the information about function call execution heap is what we also call dynamic memory i'm showing stack heap and global section separately here in our program we had declared head as a global variable initially for an empty list we'll set head as null or zero now let's say we will do

that in main function now when a call to insert at head is made at this stage let's say i'm making a call passing number two as argument let's say we are making a call to insert head from main function when program starts execution first main function is invoked whenever a function is invoked some

amount of memory from the stack is allocated for execution of that function that section is called stack frame of that function and all the local variables of that function live inside its stack frame when function call execution finishes the stack frame is reclaimed when main will make a

call to insert at head the execution of main will pause at at at the line where it's making a call a stack frame will be allocated for execution of insert at head i'm writing shortcut i a h for insert at head because i'm short of space here all the arguments of insert at head all the local

variables will live inside this stack frame we are creating a variable named new named new node which is a pointer to node as local variable and we are making a call to get new node function execution of insert at head will pause and we will go on to execute get new node we could

write get new node like this here i'm creating a node on stack x is a local variable and get new node also then i'm creating a node filling in data as the value of x which is two i'm setting previous and next fields as null or zero and then because i need to return a pointer to node i have

used ampersand operator here using ampersand operator gives us pointer to a variable let's say this new node that we have in the stack frame of get new node has addressed 50 with this return when get new node will finish the value in this new node of insert at head will be 50

please note that with this code this new node in get new node function is of type struct node while this new node in insert at head is of type pointer to struct node so they are different types we can return this address 50 that's fine but the stack frame for get new node will

be reclaimed once the function finishes so now even though you have the address 50 there is no node there we cannot control allocation and deallocation of memory on stack it happens automatically that's why we use the memory on heap if i'm using this code for creation

of new node then what i'm doing is i'm declaring this variable new node not as struct node but as struct node asdrisk that is pointer to node i'm using malloc to create the actual node in heap section let's say i'm getting a dress 400 for this node now for a section of memory in heap

for something in heap we cannot have a direct name the only way to access something in heap is through a pointer if we will lose this pointer we will lose this node okay so now what we are doing is using this point a new node which is local to get new node function we are accessing this node

filling in data filling in address fields and now we are returning this address 400 now when get new node is finishing i'm collecting the return this address 400 in this variable in this local variable new node we are returning back to insert at head function and at this line

head at this stage is null so now we are saying that set head is equal equal new node head is a global variable it's not going to be cleared for whole lifetime of application and now we are returning stack frame of insert at head will be cleared and this is what we finally have

when we will make another call to insert at head once again fresh stack frames will be allocated in the execution of functions appropriate links will be created so our linked list will be modified accordingly i hope all of this is making some sense with another call to insert at head when

everything will finish and control will return back to main we can have a picture like this let's say i got a node at 600 right cell is for next node right cell is storing the address of next node and left cell is storing the address of previous node so this will this is what

we will have let's now go and write rest of the functions print function will be same as print for singly linked list we will take a temporary pointer to node initially set it to head and then we will use this statement temp equal temp dot next to go to the next node and we will keep on

printing in reverse print we will first go to the end node of the list using next pointer and then we will traverse backward using this statement temp equal temp arrow pref so we will use the previous pointer and while traversing backward we will print the data okay let's now test all

these functions that we have written so far in the main function i'm setting head as null to say that the list is empty initially and now i'm writing couple of insert statements i'm making a couple of calls to insert at head function and after each call i'm printing the list both in

forward as well as reverse direction let's run this code and see the output this is what i'm getting and i think this is as expected there is one more function insert at tail that i had said i'll write if you have understood things so far it should not be very difficult for you to write this function

insert at tail i'll leave this as an exercise for you i'll stop here now if you want to get this source code check the description of this video for a link in coming lessons we are going to talk about circular linked list and we will see some more interesting problems on linked list thanks

for watching in this lesson we are going to introduce you to stack data structure data structures as we know are ways to store and organize data in computers so far in the series we have discussed some of the data structures we have talked about arrays and linked lists now in

this lesson we are going to talk about stacks and we are going to talk about stack as abstract data type or ADT when we talk about a data structure as abstract data type we talk only about the features or operations available with the data structure we do not go into implementation details

so basically we define the data structure only as a mathematical or logical model we will go into implementation of stack in later lessons in this lesson we are going to talk only about stack ADT so we are only going to have a look at the logical view of stack stack as

a data structure in computer science is not very different from stack as a way of organizing objects in real world here are some examples of stack from real world first figure is of a stack of dinner plates second figure is of a mathematical puzzle called tower of hanoi where we have three

rods or three pegs and multiple disks and the game is about moving a stack of disks from one peg to another with this constraint that a disk cannot go on top of a smaller disk third figure is of a pack of tennis balls stack basically is a collection with this property that

an item in the stack must be inserted or removed from the same end that we call the top of stack in fact this is not just a property this is a constraint or restriction only the top of a stack is accessible and any item has to be inserted or removed from the top a stack is also called last

in first out collection most recently added item in a stack has to go out first in the first example you will always pick up a dinner plate from top of the stack and if you will have to put a plate back into the stack you will always put it back on top of the stack you can argue that

I can slip out a plate from in between without actually removing the plates on the top so the constraint that I should take out a plate always from the top is not strictly enforced for the sake of argument this is fine you can say this in other two examples when we have disks in a peg

and tennis balls in this box that can open only from one side there is no way you can take out an item from in between any insertion or removal has to happen from top you cannot slip out an item from in between you can take out an item but for that you will have to remove all the items

on top of that item let's now formally define stack as an abstract data type a stack is a list or collection with the restriction that insertion and deletion can be performed only from one end that we call the top of stack let's now define the interface or operations available with

stack adt there are two fundamental operations available with a stack and insertion is called a push operation push operation can insert or push some item x onto the stack another operation second operation is called pop pop is removing the most recent item from the stack most recent

element from the stack push and pop are the fundamental operations and there can be few more typically there is one operation called top that simply returns the element at top of the stack and there can be an operation to check whether a stack is empty or not so this operation will

return true if the stack is empty false otherwise so push is inserting an element on top of stack and pop is removing an element from top of stack we can push or pop only one element at a time all these operations that have written here can be performed in constant time

or in other words the time complexity is big o of one remember an element that is pushed or inserted last onto a stack is popped or removed first so stack is called last in first out structure what goes in last comes out first last in first out in short is called leafo logically a stack is

represented something like this as a three-sided figure as a container open from one side this is representation of an empty stack let's name this stack s let's say this figure is representing a stack of integers right now the stack is empty i will perform push and pop operations

to insert and remove integers from the stack i will first write down the operation here and then show you what will happen in the logical representation let's first perform a push i want to push number two onto the stack the stack is empty right now so we cannot pop anything after the push

stack will look something like this there is only one integer in the stack so of course it's on top let's push another integer this time i want to push number 10 and now let's say we want to perform a pop the integer at top right now is 10 with a pop

it will be removed from the stack let's do few more push i just pushed 7 and 5 onto the stack at this stage if i will call top operation it will return me number five is empty will return me false at this stage a pop will remove five from the stack

as you can see the element the integer which is coming last is going out first that's why we call stack last in first out data structure we can pop till the stack gets empty one more pop and stack will be empty so this pretty much is stack data structure

now one obvious question can be what are the real scenarios where stack helps us let's list down some of the applications of stack stack data structure is used for execution of function calls in a program we have talked about this quite a bit in our lessons on dynamic memory

allocation and linked lists we can also say that stack is used for recursion because recursion is also a chain of function calls it's just that all the calls are to the same function to know more about this application you can check the description of this video for a link to my course schools

lesson on dynamic memory allocation another application of stack is we can use it to implement undo operation in an editor and we can perform undo operation in any text editor or image editor right now i'm pressing ctrl z and as you can see some of the text that i have written

is getting cleared you can implement this using a stack stack is used in a number of important algorithms like for example a compiler verifies whether parenthesis in a source code are balanced or not using stack data structure corresponding to each opening curly brace or opening parenthesis

in a source code there must be a closing parenthesis at appropriate position and if parenthesis in a source code are not put properly if they are not balanced compiler should throw error and this check can be performed using a stack we will discuss some of these problems in detail

incoming lessons this much is good for an introduction in our next lesson we will discuss implementation of stack this is it for this lesson thanks for watching in our previous lesson we introduced you to stack data structure we talked about stack as abstract data type or ADT as we

know when we define a data structure as abstract data type we define it as a mathematical or logical model we define only the features or operations available with the data structure and do not bother about implementation now in this lesson we will see how we can implement

stack data structure we will first discuss possible implementations of stack and then we'll go ahead and write some code okay so let's get started as we had seen a stack is a list or collection with this restriction with this constraint that insertion and deletion that we call push and pop operations

in a stack must be performed one element at a time and only from one end that we call the top of stack so if you see if we can add only this one extra property only this one extra constraint to any implementation of a list that insertion and deletion must be performed only from one end

then we can get a stack there are two popular ways of creating lists we have talked about them a lot in our previous lessons we can use any of them to create a stack we can implement stacks using a arrays and p linked lists both these implementations are pretty intuitive let's first