In week 8, we learned about a new data type called linked lists. Python has a built in data type called list, where data can be stored in a specific order. There are many methods for the class list which allow one to add, remove, sort, and analyze data within the list. Data at any position in the list can be mutated or manipulated with the correct usage of list methods.
In contrast, linked lists can also store different types of data, but their use is very different. For linked lists, two classes are used, the node class, and the linked list class. The node class refers to a single point of data within the list, and the linked list organizes a collection of nodes into the linked list by assigning one node as the front, and another as the back. The way the data is connected is that each node has a property "next" (or .nxt) which points to a new node. Each node is referred to by another node, and refers to a new node unless it is the beginning or end of the linked list. Because of the structure of linked lists, a lot more work must be done to use the data in a linked list as compares to a list. To add data in the middle of a linked list, one must change the .nxt of the node before, and use the .nxt of the node to be added to add to the list properly. Additionally, to access data in the middle of a linked list, one must walk through each node in the list until the desired node is available. Recursion must be used for some methods with linked lists.
So far, I don't see the use of linked lists. It seems like everything they can be used for, the built-in list class can also do, and often times can do more efficiently. I can't think of a specific type of problem or data where a linked list would be the ideal class to use. Since recursion must be used for some methods, and others have to access many unneeded nodes before finding the desired node, the runtime for linked list methods would be significantly longer than for lists if one is using a large set of data. I'm curious to see if we revisit linked lists before the end of the course, and to find out if there is a type of problem which this data type is optimal for.
Sunday, 15 March 2015
Sunday, 8 March 2015
Impressions of Week 7
In week 7 we learned about the data class Binary Trees. To explain what a Binary Tree is I'll first have to explain what a Tree is. A Tree is a data class which we had learned about in previous weeks. Trees start at a single node which is at the "top" of the tree. This node contains some type of information, and also has "children", which are other nodes. These children also contain data, and can also have children of their own. Each node within the Tree functions as a starting node for its own "sub-tree", which can be accessed the same way as the original node. Trees are a class which can be used to give data a structural organization, and link certain pieces of data together (parent-children relationship). Additionally, all the data in a tree can be accessed via recursive functions, which go through the tree until there are no children.
A Binary Tree is a specific type of Tree, which has the unique property that each node has a maximum of two children. This gives the data a more organized structure than a normal tree which facilitates some specific functions. Two examples we were shown in class are Binary Expression Trees and Binary Search Trees. With Binary Expression Trees, each interior node (a node with children) is an arithmetic operator, and any leaves (nodes without children) contain numbers. A recursive function can then be used to evaluate the numbers using the arithmetic expression until one reaches the top of the tree. For Binary Search Trees, each node contains a number, and the left child is always less than the value at that node, and the right child is always greater. This allows for numbers to be searched for very quickly.
Binary Trees seem to be a very useful and efficient way to store data. By limiting the number of children to two, Binary Trees have a much more rigid structure than normal trees. This allows for efficient storage and retrieval of data. However, though they are efficient, Binary Trees are only useful for very specific sets of data. For example, Binary Search Trees are incredibly efficient for searching a group of numbers, because with each step down the tree one can eliminate a significant amount of the remaining data. However, this class only works for a set of data containing only numbers, and is only really useful for searching data sets and related functions. Though Binary Trees are very good data storage systems, the fact that they are limited to specific types of data reduces their usefulness to a computer scientist.
A Binary Tree is a specific type of Tree, which has the unique property that each node has a maximum of two children. This gives the data a more organized structure than a normal tree which facilitates some specific functions. Two examples we were shown in class are Binary Expression Trees and Binary Search Trees. With Binary Expression Trees, each interior node (a node with children) is an arithmetic operator, and any leaves (nodes without children) contain numbers. A recursive function can then be used to evaluate the numbers using the arithmetic expression until one reaches the top of the tree. For Binary Search Trees, each node contains a number, and the left child is always less than the value at that node, and the right child is always greater. This allows for numbers to be searched for very quickly.
Binary Trees seem to be a very useful and efficient way to store data. By limiting the number of children to two, Binary Trees have a much more rigid structure than normal trees. This allows for efficient storage and retrieval of data. However, though they are efficient, Binary Trees are only useful for very specific sets of data. For example, Binary Search Trees are incredibly efficient for searching a group of numbers, because with each step down the tree one can eliminate a significant amount of the remaining data. However, this class only works for a set of data containing only numbers, and is only really useful for searching data sets and related functions. Though Binary Trees are very good data storage systems, the fact that they are limited to specific types of data reduces their usefulness to a computer scientist.
Sunday, 1 March 2015
Subscribe to:
Posts (Atom)