Saturday 17 August 2019

Data Structures - Lecture 2

Irawen August 17, 2019 Data Strucures No comments

Data structure Lecture -2

Arrays We are going to look at two implementation of list. Two important implementation of list. One is array and another is using linked list. So first let us look at implementation of list using arrays. Before we are going to that we have to know what an arrays? Array is usually associated with pair of values an index and a value. An array is a sequence of indexed items. For example when I say the first element it is the index is one. And then the element is also fix as five are something other. If I say 10, A[10] it means that the 10th index is 10 and the element value of the whatever the element there will come out. So associated with each index there is a value, and normally an important constraint of arrays is that the length of the array has to be fixed. Before the array is created and it is implemented using consecutive memory. Now one important thing that we have do known is that when we represent list using arrays, the list is logically continuous as well as physically continuous in other words the elements of the array are stored in consecutive memory location. When an array is created consecutive memory blocks is allocated dynamically to store the values of the element of the array. So if we take an example.

Let us assume that the array consist of 0,1,2,3,4. You will see that, here we assume that 2 address location are used represent one element of the array. So 1 to 2 it’s contains 0. 1,2,3,0 contains 1. The index will be 1,2,3,4,5. This is contiguous memory location that allocated. Normally, we talk about an array. The indices an array range from the lower index bound normally 0 most programming languages. Through the higher index bound n-1. It means that you can represent N element using the particular array. Any items of the array can be access directly by just giving its index. So when you say A[1] you can access the first element. When you say A[5], you can access the fifth element and time complexity of accessing an element is 0 of the order of 1, which means error if its 1000th the element array. If you say A[1000] you can access directly to the 1000th element. So operation you do create and initialize the length is a find the number of elements in the array and insertion & deletion. So given an array like a left to right. You can insert of a value and a particular location. If necessary we have to shift the elements. Insertion and deletion is most time consuming and inefficient operations. When you represent list using an array. Now search on the other hand is the most efficient operation that we do.

When you represent the list using an array. List in finding an any particular element from the array from the list represented using an array. So array is a basic data structure and it can store any type of an element. It can be integer array. It can be character array, an array consisting of nodes which is the structure. An important application of array is the representation of polynomial. Polynomial is consist of an exponent, degree of the polynomial is largest exponent. So this is particular polynomial you can represent the array. For example 3 has one data element and 20 as other data element and +2 is other, +5 is other ad so on. Linked List 1 Another representation of list, please remember talking about list. And how do an implement the list? The first type saw as an array. The second type is a linked list. Now if you look here. This is typical representation of list. Which is represented to a linked list. Now you see that bat, cat, sat, vat is a list and logically they are next to each other or sequential. But, when you use a linked list to represent a list the memory are physically they or not adjacent to each other, they are only logically adjacent to each other. For example, bat can be stored a 1000 location cat can be stored that 200 location. For example, sat at 600 location and vat at 2000. In spite of that because of this link points that address of the next element and because of this they become logically adjacent to each other. Though they or not physically adjacent to each other. To linked list is a chain of elements. And now every node in a linked list has two parts. At least 2 parts. One is the data and other is the link. So linked list can be represented using a PHead, which is the pointer to the head of the list. Of the first element of the list and if you have an empty linked list then the PHead link pointed to a null value and then node element of the linked list can have just one data field. Which is the example given here can have 3 data fields which is the example given here. Where you have name, id gridPts and whatever it has always in the linked list where see up to now it has a single link field or address field and here we see that node is represented to a structure, name, address, and phone and again have a link field. There are many ways in which linked list can be represented in one the look at we look at defining a linked list using 2 structure. One is head structure, one is data node structure. The head structure need not to be represented there are other implementation do not use a separate structure for representing the head node. We are assuming that they are using a separate structure. So you have head structure and data node structure. The head structure will consist of a count of the no. of element in the node and pointed to the first node in the list. The node consists of data and point to the next element of the list. So if you represent this the head structure consist of count is which is an integer and head which is a pointer. In other words in address and

here you have a data which is a data type. Please note this data can have a more than one element it have a structure it can anything and link which is a pointed to the next element. So these are two structures that are used to define type of the element in the linked list as we have represent the linked list. So this is the method in which you represent this. And this is just representation of what seen previously. If you look here, this is typical linked list, which has been created using the structure given here. So here you have the head which pointed to the first node in the list and the count use the no. of element in the list which is 2 and this is a head node. These are data nodes and this consist of the data and the pointed to the next node and this is the data pointed to the next node. This will be null. If the last node in the linked list. This is the representation of the head and count and this is representation, if it is a name. Here the previous one. Put it as the data. If it is the name list. You have the same structure except that. The data will be represented by a character and here you have a person. You can also represented using a person which is the data. Pointed to the data and node which is a represented pointed to the link. Now will have to look at some operations that we have as for as linked list is concern. One is that you have to find out that linked list is empty and another things is because we talking about the linked list. We have to find allocate memory for the node and that is done by this malloc structure. This malloc structure will take the node and will allocate memory location for the data node, when it is created. So the operation we do on linked list implementation of list is same as we do on any list. So you have to create a list. You have add a node, you can delete a node, you can find a node, and can a traverse a list. Please note that in the linked list representation the addition of the node at the beginning, middle or end. It slightly different and similarly deletion beginning, middle or end in the slightly different because we have represented something called a head node. This is a representation of how to create a node. So you will have a pointer and you can create a data here. Have a pointer to the null. It can be represented by a null, which doesn’t have pointed to the next node or you have pointed to the next node. Now please note here that here is creating a two node list. The structure for this. Creating a linked list with two nodes. So first you have defining two nodes. 1st and 2nd in the first node allocating space for the first node you allocating space for the second node and then what you doing is, you are assuming that this is a first node and this is a second node. So you are the second node. The link of the second node is set equal to null. The data of the second node is set equal to 20 and the data of the first node is set equal to 10 and data of the next is made to point to this. How do you get the address of this, this is available here, when you are doing the malloc. So this is a not generalized implementation.

Implementation of hard coding implementation of how to create the two node list. Now please note that when you have a linked list like this, only you can enter the linked list or access the linked list is throw this the pointer or the pointer has to have an address of the first node. Then only you can access the linked list implementation of the list. So now let us look at how to create a list. Please note that we have said that we had separate structure call head, head node, which is consist of the count the no. of element in the node and pointer to the first node of the element. So before you start the count is undefined and head there is no address pointer. Now I want to create a list. So what I do is I put list head equal to null. That is I set this equal null and I set the count to be equal zero. Because this is an empty list. So after the creation operation. This is the output because count is a becoming equal zero and the head set to be null. Please note that, the no. of element in the list at this pointer still zero and you just create the head node. In the other words, the creation operation you just setting of the head node. So this is an implementation of the head node. So you have the data this pnode, is the pointer to the next element. So you put the pointer equal to null and you can also defined something call empty. You what do check whether the list is empty also can be done. Now you want to add an element to an empty list, so before the add operation you already create the empty list. So this is what you will have so this is what you saw in the last slide also. And now you want to add this particular node, data node, into this list. This is the data. This is pNew is nothing but the address of this node. This is an undefined as f node. How do you add this node to this list? So, this what you have seen. So the first step is that you set the link of this to be equal to link of this. It so happen because it is an empty list into which you adding this actually will be set to null. Than you have to change the count of the head node one. Because you will adding one element and the next step you are doing this actually change the link to the pointer to this. So that is the next step, this link, which is the point of the head node of the new node. Which is given by list head equal to this address, which is we know pNew. So what is happen is the link field of the has been set equal to link field of this which is null and the head has been made to point to pNew and this is the state of the list and the count to be one. Because now it contains one node and this what happens of the add operation. So this link, this link been set here. So this is how you added the pNew. Please don’t think of this link. Just pNew give the address of this node. So this is how add 1 to an empty list. Ok. Now we look at adding at the beginning of the list. This is also similar to adding a node at the one node to empty list. That is this is the list before you do adding at the beginning. This is the node data node. That you want to add to the list. When you want to add here. So this is what the status is. Before you do the add operation. Now, what you have do first is the link field of this has to be set equal to the address of this. What you done is. You have set the address of this node to be equal to you have set the link of this node. To be equal to this and the set the ink of this node to be equal to be this. If you reverse the operations here. You want to get the answer. You will what happen trouble because I do not know the address of this well. The address of the available. The address of the available only in this. Initially changed this and put the equal to zero. I have loss the address of this. You cannot do insertion. If you have to initially necessary in this order. First you have what you do set the link of this point to this and then change the head. To point to the first node. So now the list is like this head node 39,75. So this is have add an element to be front of the list. So this is just show you that. When you doing an insertion you are just inserting like this and you not changing to link, while when you are doing insertion of list. Using arrays, we were actually are changing the index of the no. of elements. So suppose you had add an element in an array in the 5th position. And an array consist of 1500 element. Then from the 6th position upto 1500 change the index of all the elements. Linked List 2 Now we are going to see addition of the node in the middle of the list. So, before the add operation. You are assuming that the linked list is like this which consists of a 2 nodes. 39 and 75. PHead is pointing to the first node. Now what we want to do. Yes, we want to add and element 52. Here, that is we want to list look like this now. In order to do that you need to know the address of this node. So that is what is put as previous? So now the node as change after the addition. Now you have 3 nodes. This doesn’t’ change. Now what you are doing is this pNew’s link. Has to be changed are a link has to be fixed at this 75 or the address of 75. How do we that address of 75 nothing but the link of previous. So now you are setting. pNew’s link nothing but P previous link. The address that you set here. The address that you add here. So that is the first step and then this P previous link has to be set equal to this address of pNew. So that the next step. What happen here is first, the pPre link this link is set. Link is equivalent to these step. This step equivalent to this step. That is pNew link is set equal to pPre link. pPre link was actually that address of this node so that is the link and then what you doing? This link now you are changing. You use already the changing this is point to pNew. That is this step. So this link correspond to this step and this link correspond to this step. Please note again. You cannot interchange. If you interchange this you loss this address. That is very important next is add an end of the list. We are not again go to do. But here what happen is. This is node where you want to add. And this is the address of the previous node. But here that the disadvantage of the just not been told here. We assuming that pPre is available.

pPre will not available please note already told you. That can you access the list only from the head nodes. So if you want to find p previous is that you keep on searching the list, till you find a node who is address link field has null. Then you know come to the end of the list and you note that address as P free and then what you do? You set the change the link this point to pNew. And then make p new link is equal to null. But this is one disadvantage of representing list using linked list. Because what happen that if you want to find the end of the list. Assume that this is only 3 nodes found easily. Suppose if you want to insert at end of the node in 1000. Element list representing using a linked list. You have to search from right here and go upto 1000th element. Before and find the address of the 1000 the element. Before you can do this addition. Addition is end of the list is not very convenient or efficient. If you represent the list in this way and other way is you can insert after a particular position. Insert a node with data into the list pointed to after that node. So you are assuming that you know the address of what is trying do is. You want to insert after these you given the address just insert after it is. That is another way of doing is that is what is told here. And this is where you insert. This is what you already seen in the previous test may be insert you first set point this. This is what is initially there. You remove this link. You don’t remove the link, actually. What do you do this? You address know. So set the link do this and make this link into this after inset it. This is already treated. Just the program for that. So up to known you seen creation of empty list, you seen addition to empty list you seen addition to front of the list, you seen addition of the middle of the list and then seen addition after that particular node whose address is given. This is fairly strait forward suppose you had to insert an element in sorted order. Let us 5,10,15,25. And now I want to insert 18 is sorted order. Then again the have to traversal from the beginning. Find out whether the 15 is store the value and then do insertion in middle. So that is also little bit of DTS of as for as insertion to list using a linked list. Now let us look at deletion again deletion you can delete at the first node. Please note this a head node. And this is the list that I have. Now I want to delete the first node that is want to delete 39. Now what I do. I have to make this point to this that all. So what happen is. The head, the link this head now point to this node. And count has to be change to 2. And this location that is the node contain 39, can be recycled or put back into a store of node available for insertion. So this is the deletion. So actually what happen is when you delete to node change a link there is no link to this node. So this in other words are also called as dangling reference. This was deletion of the first node. Now the advantage here was you know the address of the first node. Which is given by this head. But in suppose

you have a general case of deletion. Where you want to delete. Let us say this node, then I need the address of this node if I want to delete the node. Because what happen is have to set this I need address of this to find out and set this link point do this. So, again as we did in the case of Insertion what we doing is we are assuming that we know the address may be conveniently but actually find out the address you have to traversal so, what happen this is Ppre the address of the previous node. So this link may to point to link of this node. Because these link was point it to zero. Then only step for deletion and this is the recycled node. Which is no longer in the picture. So this is for searching. So you can search for a target node. So you can 5,10, 15,20, 95, 100 and if you can search for the less than first node. You can search for greater than last node and you can search for particular node. So if you search less than 5 you won’t find it. If you search greater than 15 you can find it. If you target 15 to 25 own to find it. So you can search like that. So this is again deletion just make it clear. So you have the node and you want to delete. So you want to delete 10. Delete it and put there. So if you want to delete the node other than the node. Deleting the first node. This is a special case. As you told before you can insert or you can access a list we representing linked list using only a node and since this node have now the node has been remove you have to set this node to be 50 are the address of this node. Otherwise you cannot access it. The node that’s only that is has been set to 50 and if you want delete here 50. Set the delete here and this been removed. This is removed of this. So here what you have node is equal to next. Node not next equal. So suppose you want to delete the node after the next so you put node of next is equal to node of next. Which is set to address of next. So that is this step and then free this 50. That is free 10. traverseList. Just you go the through the list pointing to one of the other and till you reach the null. So after this function call pointer value will be null. Because only you after reach a null this end of the list. Some time you want to get the first then the pass position will be point to the first element and otherwise it will point to the next element because of link. So you can other operation like swapping elements. Insert first, last, delete before, last and so on. There are lot of variation you do for insertion, deletion also.

Data Structures - Lecture 1

Irawen July 30, 2019 Data Strucures No comments

Data Structure

Lecture 1

Data structure is a systematic way of manipulating data. A data structure structures data. Usually more than one piece of data and we have to provide legal operations on the data and the data can also be joined together. That is it can be collection. Basically data structure talks about two aspects. One aspect is data organization and other is manipulating data. In fact manipulation of data, how we want to manipulate the data and how do we organize the data. Results in different data structure that we going to talk about. All of you are some of you have done computer programming and they you have used programming languages and there are some data types that are called primitive data types. For example and this holds a single piece of data in java are may be in ‘C’ most programming languages built in data types called int means integer, char means character ,long stand for long integer and Boolean means Boolean values. There are some Legal operations which is stress for this built in data types like for example for integer: +,-,*, /. Because of the coming of object oriented programming languages abstract data types are get a lot of importance .We talk about data types we also talk about abstract data types. Abstract data types are like a black box. An abstract data type (ADT) is a data type together with the operations, whose properties are specified user of the abstract data type does not have to know what particular implementation used for implementing that particular data type. When we look from data to data structures actually the machine store only binary data. So that what we can see the figure and then you have primitive data types. For example 23 which is an integer 3.1415 which is a decimal and ‘A’ is a character and then you have some basic data structures like arrays and structures used to store the data types and then have a high level data structure like stack, queue and list. Stack, queue and list are data structures that define so that does particular operations these types of data structures. We talk about data to data structures actually as we all of you know data stored in a machine in the form of binary bits and that’s what machine level data storage and then we have primitive data types that are provided most programming languages like integers, floating point 3.145 and character like A and then have basic data structures that are also provided in programming languages like arrays and structures in addition to this we have high level data structure which are special type of list and structures like stack, queue and list. When you talk about data structures there are two types of data structures one is linear data structure and another one is non-linear data
structures.
Linear structures
Array is common linear data structure. Most important concept of array is that the size of array is fixed. Linked list is a variable size. Then you have a stack is very common data structures. It is a restricted form of list where we can add and delete from one point on top of the list. Then we have queue add to back and remove from front. These are ordinary queue. Priority queue add anywhere remove the highest priority. Other important types of data structures which is very necessary for many application of computer science and one such as a hash table .The hash table commonly used for compilers , storing of variables names compilers and so on. Hash tables: unordered list which use a 'hash function' to insert and delete. A tree is a very important data structures. It is unlike most of the data structure since it is a non-linear data structure because it has a branching structure. Graph: Graph is a more linear type of data structure than the Tree. Tree has no loops. Graph has less stringent connection conditions there can be loops in that. When we talk about data structures talk about the data organizations then addition to the data organizations what manipulation you can do with this data types its very important concept. Necessarily to some of the operations you normally do in data structures one is creating an empty data structures. Create an empty list. Give a list we have Determine whether a list is empty. Determine the number of items on a list. Add an item at a given position in a list. Remove the item at a given position in a list. Remove all the items from a list. Now actually what are the actions doing have a half a do depends on the application. Some applications just we do look at only addition and deletion. Certain application you do have to find a list is empty. So operation and combination of operations depends on a particular application that you want to a data structure to have and another important operations are data structures. Another important operation of data structure is to get the item from a given position in a list. Accessing on elements in a list very important operation so in a sorting and searching in any application. For example counseling that you have in Anna University and certain other application. Sorting of the ranks and searching for a particular student then list is a very important operation and mostly all these occupied searching and sorting frequently used operations of data structure. Some time you need the capacity of the list data structure what is the total count of the elements in list. Some time you have needed to modify, update, delete and insert in list. Generally you say that for most applications. This type of modification is not accessed common as action. If we look at the data
structure you can also think of a matrix as a data structures. Linked list as a data structures, a tree and network as a data structures. How this is implemented in how this is represented. LIST: This is the fundamental data structure in computer science and this processing is considered as one of the most important data structures. Infract has been the inspiration for the particular type of programming and language called Lisp. List of integers is the most widely used kind of list and that can also be set or collection of instance. Examples of list are 0,+1,-1,+2,-2,+3,-3 is an example of integer list. We can also have the Days of week = { s,m,t,w,th,f,sa} and sometimes it is not necessary that all elements need to be same type. Instances may or may not be related. {Apple, chair, 2,5.2, red, green, jack}. There is no connection between elements of the list back but tree still that also a list. In many ways list can be classified. But most important classification is unordered and ordered list. Unordered list means insertion list are not in any particular order. Sorted order it could be an alphabetical, numerically but the way in unordered list. Ordered lists are very similar to alphabetical list of employee names. E.g.: The rank of student exam and so on. Difficult example of ordered list. These ordered lists keep items in a specific order and so most manipulation depends on one this order list. When ever an item added to a list. That has to be placed in correct order and similarly when you remove an element from the list. Still have to remain in sorted order. Linear list: Example of linear list. It is a sequence of elements. There is something called as a first element and last element and if you take an every element it has a previous and next element is obliviously there is no element before first another is no element in after the last element. So for an example you can represent list. Linear (or ordered lists) It could be a linear list or ordered list of the form of each row to e0,e1,e2,..en-1 and assigning that n is finite. And size of the list is obliviously n. e0 is the zero. Here if we look e0 is the front e0 is the zeroth element of the list. En-1 is the last element and ei always precedes ei+1 succeeds en. So there is definite relation between elements of the list. Especially in the case of order list. Example of linear list is Student in some particular course. Jack, Jill, tree, henry, Mary and Judy. Please note that this is not an ordered list. Linear list examples Students in comp 2210 = (jack, Jill, able, Hendry, Mary, Judy). OPERATIONS ON LIST:
First create an empty list. We go and look at each operation in detail as we go long. So create an empty list. Determine whether a list is empty. Get the item at a given position is a list that is normally called as retrieval. Determine the no.of items on a list that is count the item of list. Then given an element finite index of an element. Then traverse the list you want to find the all element in the list. Add as item at a given position in a list. Remove the item at a given position in a list. Remove all the items from a list. You can thing a may such operation depending on an application. But which are discussed some of the very common operation do on any list. So first we look at create an empty list. First look at a create (list). Create (list)
In description is creates a new empty list and the inputs are either it can be no inputs are and i want to create an integer list. Types of elements are list integers are character list or character and output as an only empty list no specific output is given. If we look at this result is a new creating an empty list? You have specified in size. You may have specific the type and you may have want to specify something else also. Is empty () .You have found whether list is empty or not. So input is obliviously in the list. Output is it a Boolean output. True if one list is empty and gives false if the list is not empty and the result is after still list is remain unchanged. Important operation of the list or linear list is getting an index. Get an element the input is getting in element which has specific an index. L=(a,b,c,d,e), this an example list if you give get(0). Remember that list is start from 0 to n-1. When you say get(0) you get a. when you say get(2) you get c and so on. If you give index that are not valid like -1 you get an error and 9 though it is a valid integer. It is not a index of the list. Maximum of the index list is e0 to e4. Here so that gives an error. The index is given an index want to get an item from the list. So the input is an index. The item to be got that an index. Output is return to the items at the specified index and it throws an exception if index is not valid. But here result for list is unchanged. Throws an exception if index is out of range. The result is remaining in unchanged. Retrieval means which we just discuss. Suppose i give this and i want to retrieval the element called dog. I don’t know for examples are given index is one. It retrieval dog for me. List at the top and the bottom do not change. Only for that particular index taking are data element and showing it the use. Size and indexof: Size means determine list size. For example if given L is a,b,c,d,e the size of the list is 5. Important one is index of the element. Here unlike the previous one. When for example given a list a,b,c,d,e given the index of d is 2. Given the index of a is 0. The index of z is -1. Because is not there. The index of d is actually here 3.
Traverse
Traverse is finding all the going to list and get out the elements in particular order. When you say get first you gave an input. Get first (list) - returns first element of it list. Get next (list) returns next element if it exists. Both functions will return null if there is no data at all. Otherwise calling get next in a loop we will get one by one all elements in the list. Linear list operation first one is inserting. You adding given an index add an element and adding an element into the array. So function answer an item to list and the pre condition is list has to be existing. The list should not be full. Give a more explanation of full as we go long. And assuming the no duplicates are allowed. If the item is already in the list does not allowing insertion the element. The post condition is after insertion operation will be in the list. Suppose if we have list L is a,b,c,d,e,f,g and give an add(0,h) 0 is which are index to be add. L is element to be added. Then this will be a result. L=h{a,b,c,d,e,f,g). Please note the index of a,b,c,d,e,f,g has increase by 1. Value to be provided before the insert an add operation the index of a is 0. After the add operation index of a is 1. Similarly, that when we have want to add to the front of the list. Suppose if you want to add in the second position 0,1, & 2. So here add (2,h) now the index of c,d,e,f will not change or increase by 1. Again complete elements after insertion operation shifted or moved by one place. Suppose if you give add (10,h) the 10 does not exist in the element . That the no of element is <10. Then will get an error and given an (-6, h) also will get an error. Insert list, data -> new list Let look at insertion operation. I want to insert an element which is called 25. And i want to insert it. Add the second position. So what happen in the initial list is having 10,20,30 and data want to add 25. And it has been told to the i want to added after 25. After the insertion operation i get 10,20. 25 & 30. Now have be 25 is added to a list and get the new list. Next is removing. Specifications (Remove index)
Remove an element from the list given an index. Remove an element from the list. Input which an item which you want to remove. And index of an item. And then if an item out of range. If an item is valid has to be removed. An all item in the list will have moved position ok decreased by 1. You will see the example so this is about previous saw about removal next is deleting. Remove and return an element with given index. Remove an element delete the element whose key matches the item's key. List there are some pre condition are delete. First if you have to a list and the key member of an item has been initialized and there are assuming again no duplicate if you find an item finally 1. So item's key will be nothing to only one element. Post condition is delete is key element matching is
key element. So suppose if have a,b,c,d,e,f,g and is given remove 2. Please remember index is 0,1,2,3,4,5. so remove 2 means if will return c. And list will change. Now a,b,c,d,e,f,g and now what has happened is d,e,f and g all the index is d,e,f, and g has increased by 1. If you take an example of this particular list blue, green, red and yellow. And you want to delete an element which called red what will happen after the deletion operation. The list is been blue, green and yellow only the output given red because the red has been deleted. Other operation is remove all. Removes all the elements in the list. Input is none and output is none after you finish the operation the output comes out to be empty. Example for this kind is phone book data phone records. The normal operation you want to do on the list add to an empty list, remove an entry, and look up someone’s phone number by name. Name will be given we have to search for that particular name and number. We have to find the list of all the phone number for one entry at a time this like a traversal and get the number of entries is like a count. Add, remove, retrieve, traverse and get the number of items. Here the details are normally in the phone book entries are stored in alphabetical order. Another is shopping list to do list schedule. Normally there are some order and when we talk about items in a list they of the same type. They will be either integer or they will be names of people or they will be name and phone number and so on. And the variation of list include what order you have. For the same list you have alphabetical order and numerical order and what are the types of element in the list and what are the common operations you want to do. Depending upon the application it may vary. What can we can do with the linear list is we can delete element, insert element, find an element and we can traverse a list and so on. You can sort by numerically alphabetically you can do any type of sorting. Classification of list When you look at this a specifically linear list and think of 2 types of following classification. Where you have general and restricted list? General list can be unordered and order. Restricted list can FIFO will talk about the queue. And LIFO talk list in detail. Which is the stack? Up to now where not look at the implementation at all. We generally look at as what is the list and how the list can be how the list looks like and be the list of numbers. It can be names can be list of telephone numbers and so on. And we look at what are the operations you can do. All the operation that any application of which user list you what but then if you what to actually represent in this computer. You have to implement using some particular method of implementation. IMPLEMENTATION OF LIST:
Different ways in which list can be implemented. One is arrays one is linked list and we can also implement list using doubly linked list. Array: how to choose the implementation of whether do you want an array implementation a list implementation depends upon operation you want do to the list. And nothing else and what are the operations you want to do the list depends upon the applications of the list. You have decide you want to do array implementation or linked list implementation depending upon the applications and application will be desired what operation. Operation decided on the application. First we look at the array implementation before look how do to array implementation letters look at what type of operation in list mode easy by the array implementation. Search is easy if you use the array. Traversal is easy use arrays. Insert and delete is not easy. It is fairly operation in an application better to avoid array. One of the major problem in array implementation is before you start the implementation you do not the application is not know how much storage want to an array. For an array, before start an implementation. Ok 100. I want to allocate 100 locations for the particular implementation in the list. But the problem is application can you guess it. To large in a number waste in a memory. So this is the problem of using array. But has array is one advantage it because if the list which is implementation using an array. But has array is one advantage it because if the list which is implemented using an array it mainly using for searching. For traversal then the array implementation of the list is best. So you can also implement list using linked list and slight confusion among the students as what is the list and what is the linked list. Actually list is nothing but list of names, numbers and so on. Nothing to do with the implementation list can be implemented using different data structures like arrays, link list and so on. Linked list data structures is used for implementation is make of the difference in the data structures which we can implement either an array or link list. Linked list not only used for represent the list. Linked list implementation can be used for queue, stack, trees and so on. This is the difference between list and array. Implementation list using arrays. Array is set of pairs the pair is an index and a value is a data structures. Array is a sequence of indexed items for each index there is a value associated with that particular index suppose you say array one. Array one will a value A, array 5 will have a particular value c. This is a pair that is index along with the value. One of important concepts in array is the length array is fixed when the array is created and the array is consecutive memory location is allocated to the array that is physically as well as logically contiguous memory. Actually what happen when a array is created is sequence of blocks are allocated dynamically to store the value of the array. Example: we are assuming that two address spaces are used to store content 1228 as 0 and 1230 as 1 so this 01234 if you take it as list it is stored in contiguous
memory location. That is the basic aspect of arrays. Normally when you talk about the array you have in this is ranging from the lower bound. Normally 0 in most programming languages through a higher bound n-1 and n represents total no of elements stored in the array. Any item in the array can be accessed using the index if you say a1 it will be access the first element a5 it will access the fifth element. If you say 1 you will get the element you can access it directly. That why you say the time clock complexity is of the order of one because if you cay one you get immediately go and get the element in the first place and a1000 suppose the array of size thousand. The operation that you do obviously the same the you going represent the list in the array means operations are create initialize then the length property to find the length of the array then insertion deletion and then searching. Searching for the element from the array. There are many application that uses list and which use arrays for list implementation. One of it is polynomial. Polynomial is defined by list of coefficient and exponents and the degree of polynomial is the largest exponent. This particular polynomial can be represented using list. If you look at link list implementation this is how the link list will be I will talk about this in detail later. One important different between list implementation using array and list implementation using link list is while in array the elements of the list are logically contiguous and physically contiguous and when you use link list for implementation of the list the elements of the list are logically still contiguous but physically need not to be contiguous for example bag, cat, sat and vat. Bag can stored at thousandth location and cat can be stored at three hundredth location sat can be stored at four fifty location and vat can be stored at some 600 location no continuity but still bag, cat, sat and vat are logically connected because of the links between the nodes if you look at the link list implementation. Link list is the chain of elements. If you look at each node of elements or each element it consist of two parts data part and the link part and the link part job is to point to the next element or logically next element in the list. Here a link list will normally have a head pointer which is called a p head that pointed to the first node in the list and each node in the list will have date and link data will store element and link will be the address of the next element and if you have an empty link list it will just represented by the p head. You can have a node of different types for example a node with one date field. The element and the data stored is number the link is the address if you look at the next one the node with three data field name id and some grdpts are whatever you can any number of data fields. But normally only one link if it is this type of link list and that is structure like name, address and phone and the link can also be represented as structures there are many ways in which link list are implemented we are looking at one we are defining two structure one is list head
some implementations of link list do no separate out this list head bt in this particular implementation we are talking about list head. List head will also have the count of the number of elements as well as a link field so if you look at the left hand side you have list count integer and head is a pointer. Pointer means address. That is the structure heads structures you have a node structure where you have data which is the data type and link which is again a hundreds this is data here we have assumed that data is one field it can have more than one.

Concepts of electrical and electronics engineering

Irawen July 22, 2019 No comments

The book is written per the syllabus of first year engineering degree course for various universities. It covers basic topics of electrical, electronics and communication engineering. It also includes worked out examples, University examination questions and answers, exercise, etc in every chapter. This book is suitable for course in basic electrical engineering under various Universities.

Authors have tried to elucidate the topics in such a way that even a mediocre student can assimilate them. Many solved problems, sample question papers and exercise given in every section will provide a thorough understanding of the topics. Other features include attractive writing style, well structured equations and numerical examples, pictures of high clarity, etc.