Data Structures

Linked List

Singly Linked List (see video)

What is a linked list? It is a list where each section of the list knows the name of the next section of the list. Something like a->b->c-X where X is null. If we look at a we know we can get the next value, so a.next would be b. This is interesting because without knowing what is third we can find it by going a.next.next = c because b knows about c. Then we can pull the information from that location a.next.next.info = 3000. You might be saying so what?

Here are some reasons for a linked list.

• you need constant-time complexity for insertions and deletions from the list i.e. to increase time predictability
• you don’t know how many items will be in the list. With arrays you might need to re-declare and copy memory if the array grows too large
• you don’t need random access to any elements
• you want to be able to insert items in the middle of the list such as a priority queue.

Though there is debate on almost every reason to use it vs another data structure. Hopefully I will learn more and make up my own mind on when I would like to use them and not. For now… just store it and move on.

Tree

Tree Data Structure

A tree is a hierarchical structure with parents and descendants at the very minimum. Not super useful yet, but add in siblings and it gets a bit more exciting. There is a bunch. So I am going to put them in a list… hrmm.

• Root – The top node in a tree.
• Parent – The converse notion of a child.
• Siblings – Nodes with the same parent.
• Descendant – A node reachable by repeated proceeding from parent to child.
• Ancestor – A node reachable by repeated proceeding from child to parent.
• Leaf – A node with no children.
• See the wikipedia entry for even more good stuff.

Once all of these things go together we can see that now it has some value. Thinking of the DOM right away, but also a great way to store data that has this type of relationship. Grape growers could track down to the grape if they wanted to in a production line. Builders working on a complex structure could be arranged this way with responsibilities being assigned to nodes.

Graph

Undirected Graph

We only looked at one type of graph, the undirected  graph.  This is a set of nodes that have a set of unordered pairs called edges linking them.  Think of a community. House A, House B and House C. House B is on the corner of two streets. House A is on one street and House C is on the other. House A and House B share an route, and House B and House C share another route.

So… House A has an edge to House B. House B has an edge to House A and House C. House C has an edge to House B. Clear? okay good. Also that network at the top is a graph.

Some common things to be done with graphs you say? Glad you asked. Add a node. Add/Remove edges. Get Neighbors? Sure list every node that has an edge to me.

Most of this day was spent on finishing up the sprint and going into the extra credit section a bit.