Linked List, the ole list that refers to a list that refers to list that refers to... you get my point. A linked list is a data structure with two parts. A node, that contains a value of some sort, and a pointer, or a reference to another linked list. Along with trees, they are also considered abstract data types.
In class we talked about the two ways to think about a linked list. One as thinking a linked list contains a value, then the remaining list, or the rest of it. The other way is as nodes with reference to nodes, the more traditional way. We went over created a linked list using multiple classes like a node class and a wrapper class. It took me an incredible amount of time to understand what a wrapper class was. Even now, I'm not certain, but I believe it is used to hold the entire linked list and hold information that would be useful for methods like inserting or deleting nodes.
We also discussed how we can essentially create trees that are linked lists. Then we went to talk about binary search trees. Binary search trees are binary trees that for each root, it will have maximum two subtrees. All values to the left of the root will be less than the root and all values to the right of the root will be larger than the root. This assists in locating specific nodes as it assists traversing the tree when we can eliminate half the tree on each iteration through it.
To sum things up, this week we discussed linked lists and binary search trees, which both are abstract data types that revolve around nodes and references to other abstract data types of similar objects. My personal experience with this topic is that I still have a fair amount of trouble visualizing how to recursively go through and perform whatever method I want. But this goes back to my trouble with recursion itself which over the next view weeks I will try and improve.
No comments:
Post a Comment