Data Structures in Computer Science
Simple Python Tutorials
Data structures from computer science might seem a bit complicated if you want a simple view read this blog we mentioned linked lists so linked list we have nodes which we link together the notes have two parts the first part we can store a value the second part holds a reference to the next node so you can see here these nodes are all linked together like a linked list the first node we can call the head and at the end we point to none so we know that’s the end of the linked list now where do we see linked lists implemented well they’re implemented in queues and stacks and graphs and other uses here’s a list of uses of when you might use a linked list hash tables we want to be able to access elements by the index easy and quickly but how do you know the correct index what about if you could relate the index to the actual value one way of doing this would be to use a function on the value to create the index and then use that function to identify the index and this is called a hash function what does this mean well here’s an example we’ve got a value we’ve got this integer now we’ve got a list of size 10 elements so if we use modular we can change the integer to the value 2 and then we can put that value inside the list at the place index 2. What about strings well here we use a hash function using the ascii code so we have a name tim we get the values add them up list is size 10 we use modular and after modular the remainder is 8 so we can put the word the name tim in the list using index eight so we can carry on doing this with different names and we can fill out our list at the index using the modular and the ascii codes that’s what’s used in this hash function in this example now what happens when we’ve got collision so we want to put leo in and leo’s also at index eight one way is to just move to the next slot if that’s full then we move to the next slot and we keep going if there’s no more available stops at the end we begin at the start so in this case leo will go into the first location in the list at index 0. this is called linear probing and it’s a type of open addressing you could make the hash table bigger if you have very few elements and a huge hash table that’s not very efficient if you have many elements and a smaller hash table you’re going to get a lot of collisions so you need to understand or how many elements you’re likely to need to understand what size hash table you need another method to deal with collisions is called chaining which is a form of close addressing here we use a linked list so where a place index a we have a link to the node with the value tim and that node with the value tim then links to the second node with the value leo so we have cost in linear programming we still got to find the element if it’s not at the index that we expect and we’ve got to find it afterwards so this is like a linear search also if we use chaining we have to traverse the linked list so there’s different cost values which one better depends on the load factor which is the size of the hash table the amount of values now there are other approaches for collision resolution such as double hashing where you use the first hash function and if there’s a collision use the second hash function also we can use a hash table not just for values instead of storing the value we can store keys and those keys can have values such as in a dictionary or even we could use objects now what do we use well as i said in python a lot of these data structures are already implemented we don’t need to understand or write all of the code because python’s already given it to us so a dictionary is already a good way to store values using the key as long as the key is unique that’s fine make your data so you can have a key that’s unique we already do that in databases so for example say we’ve got many students at university some students could have the same name so we make sure every student is unique by registering every student so they have a student id and now we can identify any student because each student id is unique unique to that student and we know as soon as each student is registered that they have an id number this is called a primary key in databases and it makes everything a lot more simple and easy to use so when you’re thinking of data structures you have to think about the costs of what you’re going to do do you need to sort the items do you need to access them quickly for example so in a database if you want to access something quickly you use a number and you make it unique that’s the best primary key so dictionaries what can we use as a key well it has to be unique hashable means like apply hash function on it immutable meaning that it has to not change if you’re going to apply a key at any time it has to have the same value so if we apply a hash function on a key then that key can’t change value otherwise the hash function will give a different return value and then we won’t be able to access our item so in a dictionary we have a key and a value and the key can’t be something like a list or another dictionary because they can change over time the value can can be mutable it can change so we can use other data structures as values in a dictionary other dictionaries lists etc one thing that we need to know is if we try to access a dictionary element like a value and we use key that doesn’t exist we get an error message so rather than have your code crash we can use a function called get so just quickly look at this we have a list called words we create a dictionary called tally and then we’re just going to add up all the amounts of words that are in the list and you can see here we’ve got the four words on in at and is and they all occur once except for in that occurs twice so this is a good way of telling up how many words are in a text file for example.